The Lagrangian - An analytical tool translating geometrical properties

Abstract: This note starts with a quick introduction to non-linear program (NLP) problem - mainly to set the notations. Then, the problem is temporary simplified to get some “useful results” to then show how they can be transferred to the un-simplified problem. Basically, we consider cases where only equality constrains are present, to then go back to the general case. Those “useful results” are finally used to get a “more practical” formulation of NLPs.

Through this note, key concepts of optimization are re-discovered and explained : Lagrangian function and multipliers as well as the KKT optimality conditions.

This note key points are :

 1✦ NLP general
 2✦ NLP with only equality constraint
 3	• Geometrical def. of optimality
 4	• Fondational analytical def. of optimality
 5	• Improved analytical def. of optimality: The Lagrangian 
 6		◦ Interpretation of lagrangian multipliers  
 7	• NLP with inequality constraints
 8✦ Generalised formulation of the Lagrangian 
 9	• KKT conditions  
10	• New expression for NLP Problems 
11✦ Outlook

Notations used:

NLPs

A non-linear program (NLP) without inequality constraints is usually written as :

NLPs with only equality constraints

Basic NLP problem

replanification:

• Définir le problème NLP avec inégalités
• Faire un route break et dire que pour l’instant on se concentre sur le problème avec seulement égalité. Dire que les problème avec inégalité seront vu plus tard.

A non-linear program (NLP) without inequality constraints is usually written as :

where …

Geometrical definition of optimality

If $\bm{x}^{\star}$ is the solution of (1), then:

Lagrangian function

Separating optimal points from other points - Lagrange multipliers $(\eta, \lambda)$

The geometrical definition of optimality can be translated by the fact that the two following convex sets do not intersect :

If $\bm{x}^\star$ satisfies the optimality conditions, then there exists an hyperplan $\bm{p}^T\bm{z} = c$ separating those two sets, where $\bm{p}$ and $c$ are the hyper plan parameters and they must be finite values, i.e., not $\pm \infty$. So, on one of its side there is $\mathcal{C}_1$ and on the other side there is $\mathcal{C}_2$, which mathematically translates in:

where the signs of the inequalities is arbitrary selected. To align with the usual notations used in the literature, we define $\eta = p_{(1)}$ and $\bm{\lambda} = \bm{p}_{(2:\text{end})}$, meaning that $\bm{p} = (\eta, \ \bm{\lambda}^T)^T$. Those variables $\eta$ and $\bm{\lambda}$ are called Lagrange multipliers (we will come back to it later). Then, those inequalities can be reformulated as:

[!success] Translation : Geometrical properties –> Analytical equations Equation (2) is a prototype of the simpler equation we need (the Lagrangian), but most components are here. To go further, we are now investigating particular cases of this equation.

When $z_1\rightarrow - \infty$

Since there is no lower bound on $z_1$, we can push it to $-\infty$. Then, for both $\eta$ and $c$ to remain finite and satisfy (2), we need that the lower bound on $c\geq \max_{z_1\leq 0} \big(\eta z_1\big) \geq \lim_{z_1\rightarrow -\infty} \big(\eta z_1\big)$ to not be $+\infty$. To this end, we can’t have $\lim_{z_1\rightarrow -\infty} \big(\eta z_1\big)\rightarrow +\infty$, meaning that we need $\eta$ to be positive to not change the sign of $\eta z_1$ :

When $z_1 = 0$

Since (2) is true for all $z_1\leq 0$, it is true for $z_1 = 0$. Also, it is true for any vector $\bm{d}$, so it is true for $\bm{d} = - \big(\eta \nabla_xf(\bm{x}^{\star}) + \nabla_x\bm{h}(\bm{x}^{\star})\bm{\lambda}\big)$. Using those values for $z_1$ and $\bm{d}$, we get :

• (Ideal case) If there is no constraints, then …
  • Si $\eta=0$ alors on a des problèmes
• (worst case) If there are constraints but some are colinear, then:
  • it is possible to have : $\nabla_xh_i(\bm{x}^{\star})\lambda_i + \nabla_xh_j(\bm{x}^{\star})\lambda_j = \bm{0}$ with an infinite number of couples $\{\lambda_i,\lambda_j\}$ solution.
  • $\eta \nabla_xf(\bm{x}^{\star})$ has to cancel the contraints that dont cancel each other plus those who can cancel each other but don’t do it completely.
• (classical textbook case) If all constraints are independent, then [..]. To make the solution unique, the scaling is fixed to $\eta=1$ which respect the tow condition on $\eta$ seen so far : $\eta \geq 0$ and $\eta \neq 0$.

[!remarque] For sake of simplicity, we continue assuming we are in the classical textbook case. If you are in the ideal case, then no $\lambda$, and if you are in the worst case just bare in mind that $\bm{\lambda}$ is not unique. This uniqueness is the only difference, and it would only affect solvers (as it will be discussed later in their dedicated section) [!pathsplit] Contents

CONTINUE FROM HERE

The Lagrangian

Linearly independent constraints : Constraints are considered as linearly independent when their derivatives are independent, i.e. : $\nabla_xh_{(i)}$ is not a linear combination of all the other contraintes derivatives $\nabla_xh_{(j\neq i)}$. In that case : $\nabla_x\bm{h}(\bm{x}^{\star})\bm{\lambda} \neq 0$, so for (2) to be possible we need $\eta\nabla_xf(\bm{x}^{\star}$) to compensate $\nabla_x\bm{h}(\bm{x}^{\star})\bm{\lambda}$, meaning $\boxed{\eta \neq 0}$. More precisely, those two vectors are colinear with $\bm{\lambda}$ aggregating and scaling the active constraints dérivatives and $\eta$ juste scaling the objective function derivative. Since there is scaling of both parts, we can fix one of those scaling $\eta = 1$. Then, (2) can be reformulated as:

The function :

is the Lagrangian of the optimization problem which holds all its optimality conditions:

• Interpretation of the Lagrange multipliers existence :
  • Definition : Basically, the existence of Lagrange multipliers satisfying (3) mean that there existe an hyperplan separating the sets $\mathcal{C}_1$ and $\mathcal{C}_2$ defined earlier. Their existence emerges from the geometrical definition of optimality.
• Interpretation of the Lagrange multiplier values :
  • Intuition - Perturbe the optimization problem : Each Lagrange multiplier of $\lambda'_{(i)}$ is associated to the equality constraint $h_{(i)}$ and scale then so that the derivative of the Lagrangian is null at the optimum. A way to understand what those multipliers do, could be to perturbe those constraints and see hox they are affected. The perturbed optimization problem can be formulated as follow : $$V^\star(\bm{\varepsilon}) := \min_x f(\bm{x}) \quad s.t. \quad \bm{h}(\bm{x}) = \bm{\varepsilon}, \qquad \text{where } \bm{\varepsilon} \rightarrow \bm{0} \text{ but } \bm{\varepsilon} \neq \bm{0},$$and $\xi^\star(\bm{\varepsilon})$ is the argument minimizing this function : $$\xi^\star(\bm{\varepsilon}) := \arg \min_x f(\bm{x}) \quad s.t. \quad \bm{h}(\bm{x}) = \bm{\varepsilon}, \qquad \text{where } \bm{\varepsilon} \rightarrow \bm{0} \text{ but } \bm{\varepsilon} \neq \bm{0}.$$Then: $$\frac{d V^\star(\bm{\varepsilon})}{d\bm{\varepsilon}} = \frac{d}{d \bm{\varepsilon}} f\big(\bm{\xi}^\star(\bm{\varepsilon})\big) = \nabla_\varepsilon \bm{\xi}^{\star}(\bm{\varepsilon}) \cdot \nabla_xf\big(\bm{\xi}^\star(\bm{\varepsilon})\big) \quad \Rightarrow \quad \lim_{\varepsilon \rightarrow 0} \left(\frac{d V^\star(\bm{\varepsilon})}{d\bm{\varepsilon}}\right) = \nabla_\varepsilon \bm{\xi}^{\star}(\bm{0}) \cdot \underbrace{\nabla_xf\big(\bm{\xi}^\star(\bm{0})\big)}_{(A)}. \qquad \qquad (4)$$Let’s make two observations to reformulate (A):
    • Observation 1 - Express (A) w.r.t. the Lagrange multiplier: The optimality condition implies: $$\nabla_x f(\bm{\xi}^\star(\bm{\varepsilon})) + \nabla_x \bm{h}(\bm{\xi}^\star(\bm{\varepsilon})) \bm{\lambda}(\bm{\varepsilon}) = \bm{0}, \quad \Rightarrow \quad \lim_{\bm{\varepsilon} \rightarrow 0} \left(\nabla_x f(\bm{\xi}^\star(\bm{\varepsilon})) \right) = - \nabla_x \bm{h}(\bm{\xi}^\star(\bm{0})) \bm{\lambda}(\bm{0}) = - \underbrace{\nabla_x \bm{h}(\bm{x}^\star)}_{(B)} \bm{\lambda}$$
    • Observation 2 - Express (B) to simplify (4) : By definition: $$\bm{h}(\bm{\xi}^\star(\bm{\varepsilon})) = \bm{\varepsilon}, \quad \forall \bm{\varepsilon} \in \mathbb{R}^{n_h}, \qquad \Rightarrow \qquad \nabla_\varepsilon \bm{h}(\bm{\xi}^{\star}(\bm{\varepsilon})) = I$$and by splitting the derivative : $$\nabla_\varepsilon \bm{h}(\bm{\xi}^{\star}(\bm{\varepsilon})) = \nabla_\varepsilon \bm{\xi}^{\star}(\bm{\varepsilon}) \cdot \nabla_x\bm{h}\big(\bm{\xi}^\star(\bm{\varepsilon})\big).$$By combining those two equations we get : $$\nabla_\varepsilon \bm{\xi}^{\star}(\bm{\varepsilon}) \cdot \nabla_x\bm{h}\big(\bm{\xi}^\star(\bm{\varepsilon})\big) = I, \qquad \Rightarrow \qquad \lim_{\bm{\varepsilon}\rightarrow \bm{0}} \nabla_x\bm{h}\big(\bm{\xi}^\star(\bm{\varepsilon})\big) = \underbrace{\nabla_x\bm{h}\big(\bm{x}^\star\big) = \nabla_\varepsilon \bm{\xi}^{\star}(\bm{0})^+}_{(B)}$$
  • An interpretation of the Lagrange multipliers values : From those observations, (4) becomes: $$ \lim_{\varepsilon \rightarrow 0} \left(\frac{d V^\star(\bm{\varepsilon})}{d\bm{\varepsilon}}\right) = - \nabla_\varepsilon \bm{\xi}^{\star}(\bm{0}) \cdot \nabla_\varepsilon \bm{\xi}^{\star}(\bm{0})^+ \cdot \bm{\lambda} = -\bm{\lambda}, \qquad \Rightarrow \qquad \boxed{\lim_{\varepsilon \rightarrow 0} \left(\frac{d V^\star(\bm{\varepsilon})}{d\bm{\varepsilon}}\right) = - \bm{\lambda}} \ .$$Meaning that the Lagrange multipliers vector $\bm{\lambda}$ is the derivative of the optimal cost of the optimization problem w.r.t. to the offset $\bm{\varepsilon}$ on the active constraints around $\bm{\varepsilon}=\bm{0}$. In other words, it tells us how sensitive the objective if to all the active constraints.
    • Exemple: An active constraint associated to a large Lagrange multipliers has a great effect on the optimale cost. Meaning that a little modification of this constraint can greatly affect this optimal cost.
• NLP with inequality constraints - Problem definition : Problem: $$\bm{x}^\star := \arg \min_{\bm{x}} \quad f(\bm{x}) \qquad \text{s.t.} \quad \bm{h}(\bm{x}) = \bm{0} , \quad g_j(\bm{x})\leq \bm{0}, \quad j = 1,\dots, n_g. \qquad \qquad (5)$$
  • Idea - Reformulate the problem in the “Simple NLP” formulation : If $\bm{x}^\star$ is a solution of (5), then it’s also the solution of the same optimization problem where all the inequality constraints are either replaced by an equality constraint if the constraint is active at $\bm{x}^\star$, or simply ignored (if not active at $\bm{x}^\star$). This equivalent problem is: $$\bm{x}^\star := \arg \min_{\bm{x}} \quad f(\bm{x}) \qquad \text{s.t.} \quad \bm{h}(\bm{x}) = \bm{0} , \quad \bm{g}_a(\bm{x}) = \bm{0}, \quad a \in\mathcal{A}(\bm{x}) \qquad \qquad (6)$$where $\mathcal{A}(\bm{x})$ is the subset of inequality constraint indexes $j = 1,\dots, n_g$ associated to the active constraints at $\bm{x}$, and $\bm{g}_a$ is the concatenation vector of all the active inequality constraints.
  • Development - Reusage of “Simple NLP” results : Assuming all active constraints are linearly independent, the Lagrangian of (6) is : $$\mathcal{L}(\bm{x},\bm{\lambda}, \bm{\nu}_a) := f(\bm{x}) + \begin{pmatrix}\bm{h}(\bm{x}) \\ \bm{g}_a(\bm{x})\end{pmatrix} ^T \begin{pmatrix}\bm{\lambda} \\ \bm{\nu}_a\end{pmatrix} = f(\bm{x}) + \bm{h}(\bm{x})^T\bm{\lambda} + \bm{g}_a(\bm{x})^T\bm{\nu}_a,$$where the Lagrange multiplier of the equality constraints $\bm{\lambda}$ are extended with the ones of the active inequality constraints $\bm{\nu}_a$.
    • A practical approach : Okay, but a priori we never know which constraints are active and which ones are inactive.
    • Have we ignored an active constraint ? If when you solve the solve the problem with a set of active constraints and check whether the obtained solution is feasible. If the solution is not feasible, , i.e., that we haven’t ignored a constraint that should be active.
    • Have we activated an inactive constraint ? Activating a constraint that doesn’t need to be active generally means suboptimality. Visually speaking, it’s like finding the best spot in a room while sticking to a wall. To check whether we are “sticking to a wall”, we can verify if the active inequality constraint are such that the projection of the gradient of the constraint on the gradient of the cost is negative, i.e., the cost pushes on the constrained area (on the wall).
      • Mathematically speaking, it means that a part of $\nabla_xf$ is (partially) counteracted by $\nabla_xg_{a}$, and since those two vectors are already opposed in direction, the factor $\nu_a$ that scales the effect of $\nabla_xg_{a}$ must be positive. Inversely, (when we are in the sticking wall case) the angle between $\nabla_xf$ and $\nabla_xg_{a}$ is less than 90°, then to counteract $\nabla_xf$ with $\nabla_xg_{a}$ we would need $\nu_a<0$. That’s the indicator we are looking for ! When the Lagrange multiplier of an inequality constraint is negative, we are in a suboptimal case. Then, we want to force: $$\bm{\nu}_a>0.$$
  • Generalised formulation : Since, we don’t know which constraints are active, we can simply extend the definition of the Lagrangian to incorporate the inactive inequality constraints $\bm{g}_i(\bm{x})$ while associating them to null Lagrange multipliers $\bm{\nu}_i = \bm{0}$: $$\mathcal{L}(\bm{x},\bm{\lambda}, \bm{\nu}) = f(\bm{x}) + \bm{h}(\bm{x})^T\bm{\lambda} + \begin{pmatrix}\bm{g}_a(\bm{x}) \\ \bm{g}_i(\bm{x}) \end{pmatrix}^T\begin{pmatrix}\bm{\nu}_a \\ \bm{\nu}_i \end{pmatrix} = f(\bm{x}) + \bm{h}(\bm{x})^T\bm{\lambda} + \bm{g}^T\begin{pmatrix}\bm{\nu}_a \\ \bm{\nu}_i \end{pmatrix}, \qquad \qquad (7)$$Doing that is not actually problematic since having $\bm{\nu}_i = \bm{0}$ cancels all the affects of $\bm{g}_i$ and the interpretation of those multipliers as the sensitivity of the optimal cost to variations of a constraint is still valide. Indeed, if those inactive constraints are perturbed, it won’t have any effect on the optimal cost. Then, from the “simple” optimality constions of (7) combined with the particular conditions of inequality constraint, we get the following optimality conditions: $$\begin{aligned}& \nu_k \cdot g_k(x) = 0 \quad \forall k, \quad \left\{ \begin{array}{ll} \text{If $g_k(x)$ is active } (g_k(x) = 0), \text{ then } \ \nu_k > 0, \\ \text{If $g_k(x)$ is inactive } (g_k(x) \leq 0), \text{ then } \ \nu_k = 0, \\ \end{array} \right. & & (\text{$\bm{\nu}_a$ extended with $\bm{\nu}_i=\bm{0}$}) \\ & \bm{\nu}\geq \bm{0} & & (\text{"not sticking to walls"}) \\ & \nabla_x\mathcal{L}(\bm{x}^{\star},\bm{\lambda},\bm{\nu}) = \nabla_xf(\bm{x}^{\star}) + \nabla_x\bm{h}(\bm{x}^{\star})\bm{\lambda} + \nabla_x\bm{g}(\bm{x}^\star)\bm{\nu}= 0 & & \text{(no feasible descent direction)} \\ & \nabla_{\lambda}\mathcal{L}(\bm{x}^{\star},\bm{\lambda},\bm{\nu}) = \bm{h}(\bm{x}^{\star}) = \bm{0}, & & \text{(local feasibility)} \\ & \nabla_{\nu}\mathcal{L}(\bm{x}^{\star},\bm{\lambda},\bm{\nu}) = \bm{g}(\bm{x}^{\star}) \leq \bm{0}, & & \text{(local feasibility)} \end{aligned}$$In the literature, those conditions are known as the first-order KKT conditions of optimality. Finding $\{\bm{x}^{\star},\bm{\lambda},\bm{\nu}\}$ satisfying this whole system of equation guarantees that $\bm{x}^\star$ is a stationary point of the optimization problem without
    • ignoring an active inequality constraint constraint (thanks to $\nabla_{\nu}\mathcal{L}(\bm{x}^{\star},\bm{\lambda},\bm{\nu}) = \bm{g}(\bm{x}^{\star}) \leq \bm{0}$),
    • wrongly activating a constraint (thanks to $\bm{\nu}\geq \bm{0}$),
    • mistreating inactive inequality constraints (thanks to $\nu_k \cdot g_k(x) = 0$).
  • Interpretation of those optimality conditions : Those conditions basically describe a stationary point in the space $\{\bm{x},\bm{\lambda},\bm{\nu}\}$ with a little twist on the dimension $\bm{\nu}$ since we can’t go in its negative half plan to reach a potential “actual” stationary point". A nice way to combine all those conditions into a single one is the following : $$\{\bm{x}^\star,\bm{\lambda}^\star,\bm{\nu}^\star\} = \min_{\bm{x},\bm{\lambda},\bm{\nu}} \mathcal{L}(\bm{x},\bm{\lambda}, \bm{\nu}) \quad \text{s.t.} \quad \bm{\nu}\geq\bm{0}, \quad \bm{\nu}^T\bm{g}=\bm{0}.$$And this formulation presents a very high interest since it kind of standardises the formulation of complexe optimization problems by the “simple” minimisation of an objective function in the space $n_x+n_\lambda+n_\nu$ with only constraints w.r.t. the inequality constraint function $\bm{g}$ where the initial problem was to minimise an objective function in a space $n_x$ with all the constraints (equalities and inequalities). In brief, manages smoothly the equality constraints by trading a “small” research space $n_x$ with complex constraints for a “large” research space $n_x+n_\lambda+n_\nu$ with “less” constraints. In other words, this new formulation manages implicitly the equality constraints (that we know are active) but doesn’t provides “better” tools to deal with the inequality ones. It is possible to make one more step deeper in the world of mathematics to improve this last formulation of the optimization problem to actually open doors to very smart optimization protocols that are very efficient and present nice tools to deal with inequality constraints : > link to the introduction of the dual function <

Next tutorials in this series:

• Lagrangian optimization problem => The dual optimization problem
• The dual optimization problem => Block Coordinate Descent (BCD)

END OF THE POLISHED PART

START OF THE DRAFT PART

hereafter :

• Second order optimality condition
• Bases of dynamic optimization

La condition d’optimalité du second ordre pour un problème de minimisation est:

i.e. pour l’ensemble des directions faisables (dans le nul space des contraintes actives) .

Ces conditions sont généralement appelées conditions KKT.

! following section should be another Note !

Hamiltonien - Conditions d’optimalité d’un problème dynamique non-contraint

Soit le problème:

Le lagrangien de ce problème est:

Par intégration par partie, on peut se débarrasser de $\dot{x}_u(t)$: $$

• \int_{t_0}^{t_f} \lambda(t)^T \dot{x}u(t) dt \quad = \quad \lambda(t_0)^Tx_u(t_0) - \lambda(t_f)^Tx_u(t_f) + \int{t_0}^{t_f} \dot{\lambda}(t)^T x_u(t) dt \quad = \quad \int_{t_0}^{t_f} \dot{\lambda}(t)^T x_u(t) dt $$ Comme $x(t_0) = x_0$, il est claire que $x_u(t_0) = 0$. Aussi, on posera $\lambda(t_f)=0$ en partant du principe que les multiplicateurs de Lagrange traduisent la sensibilité du cout a une contrainte, et la clairement, le cout n'est pas sensible à une perturbation sur le dernier état de la trajectoire. En effet, ce serait intégrer l'effet d'une perturbation sur un temps infinitésimal. Si cette perturbation est n'est par infinie, ce qui est le cas quand on parle de sensibilité, alors quelque soit cette perturbation, l'intégrale du cout en résultant n'est pas affectée. Ce qui nous permet d'arriver à: $$ \begin{aligned} \mathcal{L}u(u,\lambda) = \ & \underbrace{\int{t_0}^{t_f} \Big[ \ell_u(t,x(t),u(t)) + \lambda(t)^Tf_u(t,x(t),u(t))\Big]dt}{A} \ \dots \ & + \underbrace{\int{t_0}^{t_f} \Big[ \ell_x(t,x(t),u(t)) + \lambda(t)^Tf_x(t,x(t),u(t)) + \dot{\lambda}(t)\Big]x_u(t)}{B}dt \end{aligned} $$ Pour que la condition d'optimalitee $\mathcal{L}_u = 0$ soit satisfaite il faut que $A + B = 0$ et on pourrait dire que ca revient à avoir: $A = 0$ et $B = 0$, mais il n'est pas justifié que les composantes A et B soient traitées independent. Pour avoir ces deux conditions plus explicitement, il faut passer par des dérivées directionnelles du Lagrangien le long de la trajectoire. Pour se faire, introduisons la trajectoire des directions $d(t)\in\mathbb{R}^{n_u}$ et la trajectoire optimale perturbée par $d(t)$: $$ v(t,\eta) := u(t)^\star + \eta d(t). $$ Le Lagrangien perturbe est alors: $$ \mathcal{L}\big(v(t,\eta),\lambda\big) = \int{t_0}^{t_f} \Big[
  \ell(t,y(t,\eta),v(t, \eta)) + \lambda(t)^T \big( f(t,y(t,\eta),v(t,\eta)) - \dot{y}(t,\eta) \big) \Big]dt $$ where $y(t,\eta)$ est la trajectoire des états issue des entrées perturbées $v(t,\eta)$, i.e. $$ \left{ \begin{array}{cl} \dot{y}(t,\eta) & = f(t,y(t,\eta),v(t,\eta)), \ y(t_0,\eta) & = x_0 \end{array} \right. $$ On remarque que: $$ \int_{t_0}^{t_f}
  -\lambda(t)^T\dot{y}(t,\eta)dt = \lambda(t_0)^Ty(t_0,\eta) - \lambda(t_f)^Ty(t_f,\eta) + \int_{t_0}^{t_f} \dot{\lambda}(t)^Ty(t,\eta)dt $$ Et: $$ \begin{aligned} \lim_{\eta\rightarrow 0}\Big( y_\eta(t_0,\eta) \Big) = \ & 0 & & \text{car } y(t_0,\eta) = 0 \ \forall \eta, \text{ donc } y_\eta(t_0,\eta) = 0 \ \forall \eta, \ \lim_{\eta\rightarrow 0}\Big( y(t,\eta) \Big) = \ & x^{\star}(t), \ \lim_{\eta\rightarrow 0}\Big( v(t,\eta) \Big) = \ & u^{\star}(t), \ v_\eta(t,\eta) = \ & \frac{d}{d\eta} \Big( u^\star + \eta d(t) \Big)= d(t), \ \lambda(t_f) = \ & 0 \end{aligned} $$ Donc: $$ \begin{aligned} \mathcal{L}(v(t,\eta),\lambda) = \ & \int_{t_0}^{t_f} \Big[ \ell(t,y(t,\eta), v(t,\eta)) + \lambda(t)^Tf(t,y(t,\eta), v(t,\eta)) + \dot{\lambda}(t)^Ty(t,\eta) \Big] dt + \lambda(t_0)^Ty(t_0,\eta) - \lambda(t_f)^Ty(t_f,\eta), \ %% \Rightarrow \lim_{\eta\rightarrow 0} \left(\mathcal{L}\eta (v(t,\eta),\lambda) \right) = \ & \lim{\eta\rightarrow 0} \Big( \int_{t_0}^{t_f} \Big[ \ell_u\big(t,y(t,\eta),v(t,\eta)^T v_\eta(t,\eta)\big) + \ell_x\big(t,y(t,\eta),v(t,\eta)\big)^T y_\eta(t,\eta)) + \lambda(t)^T\Big( f_u\big(t,y(t,\eta),v(t,\eta)^T \ %% & v_\eta(t,\eta)\big) + f_x\big(t,y(t,\eta),v(t,\eta)\big)^T y_\eta(t,\eta)) + \Big) \dot{\lambda}(t)^Ty_\eta(t,\eta) \Big] dt + \lambda(t_0)^Ty(t_0,\eta) - \lambda(t_f)^Ty(t_f,\eta) \Big),\ %% = \ & \int_{t_0}^{t_f} \Big[ \ell_u\big(t,x^\star(t),u^\star(t)\big) + \lambda(t)^T f_u\big(t,x^\star(t),u^\star(t)\big) \Big]^Td(t) dt \ \dots \ & + \int_{t_0}^{t_f} \Big[ \ell_x\big(t,x^\star(t),u^\star(t)\big) + \lambda(t)^T f_x\big(t,x^\star(t),u^\star(t)\big) + \dot{\lambda}(t) \Big]^Ty_\eta(t,0) dt \ \dots \ %% = \ & 0 \qquad \text{Condition d’optimalite (reduite aux directions $d(t)$, $\forall d(t)$)} \end{aligned} $$ Comme cette égalité doit être vraie pour tout $d(t)$ il est claire qu'il faut que independent on ait: $$ \left{ \begin{aligned} \ell_u\big(t,x^\star(t),u^\star(t)\big) + \lambda(t)^T f_u\big(t,x^\star(t),u^\star(t)\big) = \ & 0, \ \ell_x\big(t,x^\star(t),u^\star(t)\big) + \lambda(t)^T f_x\big(t,x^\star(t),u^\star(t)\big) = \ & - \dot{\lambda}(t) \end{aligned} \right. $$ Si on définit la fonction $\mathcal{H}\big(x(t), u(t), \lambda(t)\big)$ comme: $$ \mathcal{H}\big(x(t), u(t), \lambda(t)\big) := \ell(t,x(t),u(t)) + \lambda(t)^Tf(t,x(t),u(t)) $$ où $\mathcal{H}$ et appelé Hamiltonien du problème d'optimization dynamique (l'Hamiltonien est propre aux problème dynamiques), alors les conditions d'optimalité peuvent être présentées comme: $$ \left{ \begin{aligned} \mathcal{H}_u\big(x(t), u(t), \lambda(t)\big) = \ & 0 \ \mathcal{H}x\big(x(t), u(t), \lambda(t)\big) = \ & -\dot{\lambda}(t)\ \mathcal{H}\lambda\big(x(t), u(t), \lambda(t)\big) = \ & f\big(t,x(t),u(t)\big)
  \end{aligned} \right. $$ Aussi, dans les problème d’optimisation dynamiques, les multiplicateurs de Lagrange associés à la trajectoire des états sont généralement appelées variables adjointes.

Interprétation des variables adjointes

En suivant la logique de l’étude sur les problèmes NLP, on peut penser que $\lambda(t_i)$ correspond à la sensibilité du cout de la trajectoire restante de $t_i$ à $t_f$ à une variation de l’état $x(t_i)$. Pour le prouver, on définit le problème d’optimization perturbé suivant:

où $x^\star$ est la solution du problème non-perturbé où $\tau=t_0$ et $\xi=0$. Pour confirmer notre intuition, calculons $V_{\xi}(\tau,\xi)$:

Les conditions d’optimalité nous permettent de faire entrer les variables adjointes dans cette équation. En effet:

Aussi:

On peut donc réécrire la limite comme:

Car par définition:

Aussi:

On trouve alors bien que:

Donc, $\lambda(\tau)$ caractérise bien la sensibilité de la fonction coût sujet à une variation de l’état $x$ à l’instant $\tau$ sur l’intervale de temps restant $[\tau, t_f]$.