Notions of constrained optimization

Let us define the problem:
Find the minimum of $f(x)$ subject to $m$ constraints $c_j(x) \geq 0 (j=1, ..., m)$.

Figure 13.2: Existence of Lagrange Multiplier $\lambda$

To be at an optimum point $x^*$ we must have the equi-value line (the contour) of $f(x)$ tangent to the constraint border $c(x)=0$. In other words, when we have $r=1$ constraints, we must have (see illustration in Figure 13.2) (the gradient of $f$ and the gradient of $c$ must aligned):

$$\nabla f= \lambda \nabla c$$

In the more general case when $r>1$, we have:

$$\nabla f(x)= g(x) = \sum_{j\in E} \lambda_j \nabla c_j(x) \\ c_j(x)=0, \; j \in E$$ (13.19)

Where E is the set of active constraints, that is, the constraints which have $c_j(x)=0$ We define Lagrangian function $\L$ as:

$$\L (x, \lambda)= f(x)-\sum_i \lambda_i c_i(x).$$ (13.20)

The Equation 13.19 is then equivalent to:

$$\begin{picture}(.27,.3) \put(0,0){\makebox(0,0)[bl]{$\nabla$}} \put(.16,.17){\circle*{.18}} \end{picture} \L (x^*,\lambda^*)=0 \begin{picture}(.27,.3) \put(0,0){\makebox(0,0)[bl]{$\nabla$}} ... ...e} = \left( \begin{array}{c} \nabla_x \\ \nabla_\lambda \end{array} \right)$$ (13.21)

In unconstrained optimization, we found an optimum $x^*$ when $g(x^*)=0$. In constrained optimization, we find an optimum point ( $x^*, \lambda^*$), called a KKT point (Karush-Kuhn-Tucker point) when:

$$(x^*, \lambda^*) \Longleftrightarrow \begin{array}{rcl} \nabla_x \L (x^*,\lambda^*) &= & 0 \\ \lambda_j^* \: c_j(x^*) & = & 0 , \; \; i=1,...,r \end{array}$$ (13.22)

Figure 13.3: complementarity condition

The second equation of 13.22 is called the complementarity condition. It states that both $\lambda^*$ and $c_i^*$ cannot be non-zero, or equivalently that inactive constraints have a zero multiplier. An illustration is given on figure 13.3.
To get an other insight into the meaning of Lagrange Multipliers $\lambda$, consider what happens if the right-hand sides of the constraints are perturbated, so that

$$c_i(x)=\epsilon_i, \;\; i \in E$$ (13.23)

Let $x(\epsilon)$, $\lambda(\epsilon)$ denote how the solution and multipliers change as $\epsilon$ changes. The Lagrangian for this problem is:

$$\L (x,\lambda, \epsilon)=f(x)-\sum_{i \in E} \lambda_i (c_i(x)-\epsilon_i)$$ (13.24)

From 13.23, $f(x(\epsilon))=\L (x(\epsilon),\lambda(\epsilon), \epsilon)$, so using the chain rule, we have

$$\frac{d f}{d \epsilon_i}=\frac{d \L }{d \epsilon_i}= \frac{d x^t... ...frac{d \lambda^t}{d \epsilon_i} \nabla_\lambda \L + \frac{d \L }{d \epsilon_i}$$ (13.25)

Using Equation 13.21, we see that the terms $\nabla_x \L$ and $\nabla_\lambda \L$ are null in the previous equation. It follows that:

$$\frac{d f}{d \epsilon_i}= \frac{d \L }{d \epsilon_i} = \lambda_i$$ (13.26)

Thus the Lagrange multiplier of any constraint measure the rate of change in the objective function, consequent upon changes in that constraint function. This information can be valuable in that it indicates how sensitive the objective function is to changes in the different constraints.