# Quadratic Programming in Mechanics: Dynamics of One-Sided Constraints

Jean Jacques Moreau

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jean Jacques Moreau. Quadratic Programming in Mechanics: Dynamics of One-Sided Constraints. SIAM Journal on Control and Optimization, 1966, 4 (1), pp.153 - 158. 10.1137/0304014. hal-01379713

HAL Id: hal-01379713

https://hal.science/hal-01379713

Submitted on 12 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# QUADRATIC PROGRAMMING IN MECHANICS: DYNAMICS OF ONE-SIDED CONSTRAINTS

## J. J. MOREAU†

1. Let $S$ be a frictionless mechanical system with $n$ degrees of freedom; we denote by $q_1, q_2, \dots, q_n$ the generalized coordinates, representing the point $q$ of a configuration space. A finite family of one-sided constraints is imposed on the system; the kinematic effect of these constraints is expressed by the conditions (assumed compatible)

$$ (1) \qquad f_{\alpha}(q, t) \ge 0, \quad \alpha \in I, \text{ finite set of indexes.} $$

For instance, some solid parts of the system may be in contact or become detached but they can never overlap. These constraints are frictionless, i.e., as long as the equalities hold in (1), the motion of the system is governed by Lagrange's equations with multipliers $\lambda_{\alpha}$, $\alpha \in I$. The mechanical meaning of these multipliers is to describe the reaction forces associated with possible contacts and, conventionally, we have

$$ (2) \qquad \lambda_{\alpha} \ge 0, $$

i.e., the force of reaction is directed towards the region defined by (1) and

$$ (3) \qquad \lambda_{\alpha} f_{\alpha}(q, t) = 0, \qquad \text{for all } \alpha \in I, $$

i.e., as soon as a contact ceases, the corresponding reaction becomes zero.

The set of the active forces experienced by the system is described by its covariant components $Q^i$ (continuous functions of $q, t$) relative to the coordinates $(q_i)$.

The kinetic energy is expressed as

$$ (4) \qquad T(q, \dot{q}, t) = \frac{1}{2} \sum_{i,k} a^{ik}(q, t) \dot{q}_i \dot{q}_k + \sum_i b^i(q, t) \dot{q}_i + c(q, t). $$

We shall always assume that the considered configuration is regular with respect to the coordinates $(q_i)$ so that the quadratic part of this expression is positive definite.

It is usual to study such a mechanical system by starting with the tentative hypothesis that all the contacts $f_{\alpha} = 0$ are present at any instant. Then, by putting $\partial f_{\alpha}/\partial q_i = u_{\alpha}^i$, the $n$ differential equations of Lagrange

<footnote>† Mathématiques, Faculté des Sciences, Université de Montpellier, Montpellier, France.</footnote>
$$ (5) \qquad \frac{d}{dt} \left( \frac{\partial T}{\partial \dot{q}_i} \right) - \frac{\partial T}{\partial q_i} = Q^i + \sum_{\alpha \in I} \lambda_{\alpha} u_{\alpha}^i, $$

together with the vanishing of $f_\alpha$ (for every $\alpha \in I$), determine the functions $q_i(t)$ and $\lambda_\alpha(t)$.

As long as the values $\lambda_\alpha$ so calculated are all nonnegative, the initial hypothesis of permanent contacts is accepted. When, on the contrary, some of the $\lambda_\alpha$ become negative, the hypothesis is rejected: some of the contacts must cease. But, as Delassus [1] pointed out, the contacts $f_\alpha$ which cease are not necessarily those for which the above computation gives a negative $\lambda_\alpha$ (simple counterexamples may be formulated). Delassus' arguments towards a correct solution were rather intricate; actually the author has proved [4] that the determination of the acceleration (i.e., the second derivatives $\dot{q}_i$) is governed by a generalization of Gauss' variational principle; this leads to a typical quadratic programming procedure. An extremal principle also holds which characterizes the values of the one-sided reactions (i.e., the $\lambda_\alpha$), independently of the accelerations: this leads to a quadratic programming problem dual to the preceding one.

2. Our problem may be expressed in the following manner.

For $t = t_0$, the configuration $q$ (i.e., the values of the $q_i(t_0)$) and the velocity $\dot{q}$ (i.e., the values of the derivatives $\dot{q}_i(t_0)$) are given. These data are assumed compatible with the contacts $f_\alpha = 0$ for $\alpha \in K \subset I$; that means that

$$ (6) \qquad \left( \frac{df_\alpha}{dt} \right)_{t=t_0} = \sum_i u_\alpha^i \dot{q}_i + \frac{\partial f_\alpha}{\partial t} = 0, \quad \text{for all } \alpha \in K, $$

while $f_\alpha > 0$ for $\alpha \notin K$. The question is to find the state of acceleration after $t_0$, i. e., the right-limits $\ddot{q}_i(t_0 + 0)$.

By continuity, for $\alpha \notin K$, we have $f_\alpha > 0$ during an interval $(t_0, t_0 + \epsilon)$ so that the corresponding contact does not intervene. For $\alpha \in K$, on the contrary, the conditions (1), together with (6), yield

$$ (7) \qquad \left( \frac{d^2 f_\alpha}{dt^2} \right)_{t=t_0} = \sum_i u_\alpha^i \ddot{q}_i - s_\alpha \ge 0, $$

where $s_\alpha$ is a known quantity. Using the energy expression (4), Lagrange's equations, analogous to (5), may be written

$$ (8) \qquad \sum_k a^{ik} \ddot{q}_k = z^i + \sum_{\alpha \in K} \lambda_{\alpha} u_{\alpha}^i, $$

where $z^i$ denotes known quantities. The $\lambda_\alpha$ are nonnegative by virtue of (2), and (3) yields

$$ (9) \qquad \lambda_{\alpha} \left[ \sum_{i} u_{\alpha}^{i} \ddot{q}_{i} - s_{\alpha} \right] = 0. $$
We can prove that the conditions (2), (7), (8), (9) define one and only one set of values for the unknowns $\ddot{q}_i$, $i = 1, 2, \dots, n$, and $\lambda_\alpha$, $\alpha \in K$; this solution possesses the following variational characterization: in the $\mathbb{R}^n$-space of $\ddot{q}$, the inequalities (7) define a closed convex polyhedral region $\mathcal{C}$ (non-empty, since the set of inequalities (1) is assumed to permit a motion). One proves that the above solution corresponds to the unique point $\ddot{q}$ of $\mathcal{C}$ where the function

$$ (10) \qquad G = \frac{1}{2} \sum_{i,k} a^{ik} \ddot{q}_i \ddot{q}_k - \sum_i z^i \ddot{q}_i $$

attains its minimum. The proof may be derived from Kuhn and Tucker's theory of multipliers in nonlinear programming. A direct derivation may also be found in [4].

On the other hand, Gauss' principle (of "least deviation") may be formulated, for the classical case of two-sided differentiable constraints, in the following way: given the configuration and the velocity state of such a classical system $\mathcal{E}$ at an instant $t_0$, the resulting acceleration state is, among all the acceleration states compatible with these data and with the constraints, that one which confers its minimum to the "Appell function"

$$ \mathcal{A} = \frac{1}{2} \int_{\mathcal{E}} \Gamma^2 dm - \int_{\mathcal{E}} \Gamma \cdot d\mathbf{F}, $$

where $\Gamma$ denotes the acceleration of the generic element of $\mathcal{E}$, $dm$ is the mass measure defined on $\mathcal{E}$, while the vectorial measure $d\mathbf{F}$ represents the active forces experienced by $\mathcal{E}$. Since it happens that, for an arbitrary motion defined by some $q_i(t)$, the function $\mathcal{A}$ has exactly the expression $G$ written in (10) (disregarding an additive constant), the variational characterization given above for the solution of our problem means that Gauss' principle is still valid for systems with one-sided frictionless constraints.

3. In order to deal with duality, it is useful to introduce additional geometrical terminology. Let $(e_i)$, $i = 1, 2, \dots, n$, represent a base in an $n$-dimensional linear space $E$ and let $(e^i)$ be the dual base in the dual space $E'$; we denote by $\langle \cdot, \cdot \rangle$ the duality bilinear form. The symmetric positive regular matrix $a^{ik}$ represents, relative to these bases, a one-to-one linear mapping $A$ of $E'$ onto $E$. We provide $E$ with an Euclidean metric by defining, for every pair $x \in E, y \in E$, the scalar product

$$ (x | y) = \langle x, A^{-1}(y) \rangle = \langle y, A^{-1}(x) \rangle. $$

Let us put

$$ \ddot{q} = \sum_i \ddot{q}_i e^i \in E', $$

$$ u_{\alpha} = \sum_{i} u_{\alpha}^{i} e_{i} \in E, $$
$$z = \sum_i z^i e_i \in E,$$

so that the system of Lagrange's equations (8) is written as an equation in E,

$$(11) \qquad A(\ddot{q}) = z + \sum_{\alpha \in K} \lambda_{\alpha} u_{\alpha}.$$

Instead of $\ddot{q} \in E'$, we now introduce the new unknown $x = A(\ddot{q}) \in E$, so that (11) becomes

$$(12) \qquad x - \sum_{\alpha \in K} \lambda_{\alpha} u_{\alpha} = z.$$

The inequalities (7) are rewritten as

$$(13) \qquad (u_{\alpha} | x) - s_{\alpha} \geq 0, \quad \text{for all } \alpha \in K,$$

defining thereby a closed convex polyhedral region C in E.

Then the variational characterization stated above is formulated with regard to the Euclidean metric of the space E: the solution x is, in C, the nearest point from the known point z.

**4.** We are now prepared to invoke the author's duality-decomposition theorem on quadratic programming (cf. [3], [8]). This theorem was derived for the more general case of infinite-dimensional Hilbert spaces in connection with problems of unilaterality in the mechanics of continua. In contrast with other duality treatments, the elements of a pair of dual problems belong to the same self-dual (Hilbert) space, so that they may be added together.

Let us first recall Fenchel's [2] concept of conjugate convex functions (slightly modified by the author, in order to accept $+\infty$ as a value for such functions): we denote by $\Gamma_0(E)$ the totality of the functions everywhere defined in E, taking their values in $(-\infty, +\infty]$, which are convex, lower semicontinuous, and other than the constant $+\infty$. For instance, given a nonempty subset P of E, the indicatrix function

$$\psi_P(x) = \begin{cases} 0 & \text{if } x \in P, \\ +\infty & \text{if } x \notin P, \end{cases}$$

belongs to $\Gamma_0(E)$ if and only if P is closed and convex. Now one easily proves that a one-to-one involutory mapping of $\Gamma_0(E)$ onto itself is defined by associating to any $f \in \Gamma_0(E)$ its conjugate or dual function

$$(14) \qquad g(y) = \sup_{x \in B} [(x | y) - f(x)].$$

In other words, g is the smallest element in the set of functions for which

$$(15) \qquad f(x) + g(y) \geq (x | y)$$
for every $x$ and $y$ in $E$. The points $x$ and $y$ are called *conjugate*, relative to the pair of dual functions $(f, g)$, if the equality holds in (15).

For any $z \in E$ and $f \in \Gamma_0(E)$ we denote by $\text{prox}_f z$ (proximal point of $z$ with regard to the function $f$) the point where the function

$$u \to \frac{1}{2} \|z - u\|^2 + f(u)$$

attains its minimum (existence and uniqueness of this point are assured): specifically, if $f$ is the indicatrix function of a closed convex set $C$, $\text{prox}_f z$ is the nearest point from $z$ which lies in $C$, denoted by $\text{proj}_C z$.

Then our duality-decomposition theorem may be stated in the following form: If $f$ and $g$ are dual functions, every $z \in E$ equals the sum of $x = \text{prox}_f z$ and $y = \text{prox}_g z$; the points $x$ and $y$ are conjugate relative to $(f, g)$ and they embody the unique decomposition of $z$ into a sum of two such terms.

A particularly interesting case occurs when $f$ and $g$ are the indicatrices of two *mutually polar closed convex cones* $P$ and $Q$, i. e.,

$$Q = \{y \in E : (x | y) \le 0 \text{ for every } x \in P\}$$

(and conversely). Here the theorem gives: Every $z \in E$ equals the sum of $x = \text{proj}_P z$ and $y = \text{proj}_Q z$; the elements $x$ and $y$ are orthogonal and embody the unique decomposition of $z$ into a sum of two orthogonal elements respectively belonging to $P$ and $Q$. This result may be regarded as a generalization of the classical decomposition of $E$ into the direct sum of two orthogonal complementary subspaces.

5. Returning to our mechanical problem, let us take as $f$ the indicatrix of the set $C$ defined by (13). The dual function

$$g(y) = \sup_{x \in E} [(x | y) - f(x)] = \sup_{x \in C} (x | y)$$

is the *support function* of $C$. Our generalization of Gauss' principle means that the unknown $x$ defined in §3 has the value $x = \text{prox}_f z$. Then, by the duality-decomposition theorem, (12) leads to a *variational characterization of the (abstract) reaction exerted by the system against its set of one-sided constraints*, i.e., the term

$$-\sum_{\alpha \in K} \lambda_{\alpha} u_{\alpha} \in E.$$

This term equals the proximal point $\text{prox}_g z$.

Incidentally, we may note that, in the present case, the set $C$ is a (non-homogeneous) cone with vertex at the point $x_0$ which would be found for $x$, in the case where the system underwent the *two-sided* constraints $f_\alpha = 0$, $\alpha \in K$. That leads to an alternate characterization of $\text{prox}_g z$: it is the nearest point from $z - x_0$ in the convex polyhedral homogeneous cone $C'$ gener-
ated by the $-u_\alpha$, $\alpha \in K$. Actually, $z - x_0$ is the value found for the re-
action in this hypothetical case of two-sided constraints; in that sense, it can
be said that the motion in the presence of one-sided constraints takes place
in such a way that the one-sided reactions differ the least from the reactions
corresponding to the two-sided case.

6. In conclusion, we hope that such a theory may prove useful in studying the dynamical response of mechanical transmissions affected by looseness. The author's main concern in mechanics is with the infinite-dimensional cases appearing in the mechanics of continua, e.g., inception of cavitation in a liquid flow (cf. [6], [7]). In this connection, conjugate convex functions in topological linear spaces, more general than Hilbert's, have been intensively studied for three years, together with various related notions such as subdifferentiability, inf-convolution (see, e.g., [5]).

REFERENCES

[1] E. DECLASSUS, *Sur les liaisons unilatérales*, Ann. Sci. École Norm. Sup., 34 (1917), pp. 95-179.

[2] W. FENCHEL, *On conjugate convex functions*, Canad. J. Math., 1 (1949), pp. 73-77.

[3] J. J. MOREAU, *Fonctions convexes duales et points proximaux dans un espace hilbertien*, C. R. Acad. Sci. Paris, 255 (1962), pp. 2857-2899.

[4] ——, *Les liaisons unilatérales et le principe de Gauss*, Ibid., 256 (1963), pp. 871-874.

[5] ——, *Théorèmes "inf-sup"*, Ibid., 258 (1964), pp. 2720-2722.

[6] ——, *Sur la naissance de la cavitation dans une conduite*, Ibid., 259 (1964), pp. 3948-3950.

[7] ——, *One-sided constraints in hydrodynamics*, Nonlinear Programming, a Course, J. Abadie, ed., North-Holland, Amsterdam, to appear.

[8] ——, *Proximité et dualité dans un espace hilbertien*, Bull. Soc. Math., to appear.