3.3 Constrained optimization  (Page 2/2)

Example 2 Let $X={\mathbb{R}}^2$ ; solve

In words, we look for the point in a unit circle in ${\mathbb{R}}^2$ that has the largest sum of its coordinates. It is easy to see by inspection that such point is given by $x_0={\left[\sqrt{2}\sqrt{2}\right]}^T$ . The feasible set can be given in terms of the single equality constrain

From previous work, we know that the gradient is given by $\nabla g\left(x\right)=(I+I^{*})x=2Ix=2x$ We can also write the objective function as

which has gradient $\nabla f\left(x\right)=\left[\begin{array}{c}1\\ 1\end{array}\right]$ . Thus, we can write the tangent space in this case as

Therefore, we can write the tangent space as $T_{\Omega }\left(x_0\right)=\{h\in X:h_1=-h_2\}$ . It is easy to see at this point that for any such $h\in T_{\Omega }\left(x_0\right)$ we will have $⟨\nabla f\left(x_0\right),h⟩=0$ , as stated by Theorem  [link] .

Lagrangian multipliers

In this section, we will develop a method to solve optimization problems with linear objective functions and linear equality constraints.

Lemma 1 Let $f_0,f_1,f_2,...,f_n$ be linear functionals on a Hilbert space X and suppose $f_0\left(x\right)=0$ for all $x\in X$ such that $f_i\left(x\right)=0,i=1,2,...,n$ . Then there exists constants ${\lambda }_1,{\lambda }_2,...,{\lambda }_n$ such that $f_0={\lambda }_1{f}_1+{\lambda }_2{f}_2+...+{\lambda }_n{f}_n$ .

Since our functionals are linear we have $f_0,f_1,...,f_n\in X^{*}$ . Define the subspace $M=\mathrm{span}\left(\{f_1,f_2,...,f_n\}\right)$ . Since $M$ is finite-dimensional, then $M$ is closed. We can therefore define its orthogonal complement:

Since Hilbert spaces are self-dual, then for each function $f_i$ there exists $w_i\in X$ such that $f_i\left(x\right)=⟨x,w_i⟩$ ; therefore, we can rewrite the space above as its dual equivalent

Now since $⟨w,w_i⟩=f_i\left(w\right)$ , it follows that for all $w\in M^{\perp }$ we have that $f_i\left(w\right)=0$ , $w=1,...,n$ . Therefore, the Lemma implies that for all $w\in M^{\perp }$ we have that $f_0\left(w\right)=0=⟨w,w_0⟩$ . This implies that $w_0\in {\left(M^{\perp }\right)}^{\perp }=M$ , due to $M$ being closed. Reversing to the dual space $X^{*}$ , this implies that $f_0\in M=\mathrm{span}\left(\{f_1,...,f_n\}\right)$ , and so we can write $f={\lambda }_1{f}_1+{\lambda }_2{f}_2+...+{\lambda }_n{f}_n$ .

Theorem  [link] shows that we can apply Lemma  [link] to the constrained optimization problem. Thus, at the extremum $x_0\in X$ of the constrained program there exist constants ${\lambda }_1,...,{\lambda }_n$ such that for all $h\in X$ ,

which is equivalent to $\nabla f\left(x_0\right)+{\sum }_{i=1}^n{g}_i\left(x_0\right)=0$ . This can be written as the gradient of the Lagrangian function

Thus, we say that the extremum must provide a zero-valued directional derivative of the Lagrangian in all directions or, equivalently, a zero-valued gradient for the Lagrangian. The results obtained in this section can be collected into a proof for the following theorem.

Theorem 2 If $x_0\in X$ is an extremum of a functional $f$ subject to constraints ${\left\{g_i\right\}}_{i=1}^n$ , then there exist scalars ${\lambda }_1,\cdots ,{\lambda }_n$ , such that the Lagrangian $L(x,\lambda )=f\left(x\right)+{\sum }_{i=1}^n{\lambda }_i{g}_i\left(x\right)$ is stationary at $x_0$ , i.e., for all $h\in X$ we have that $\delta L(x,\lambda ;h)=0$ , i.e., $\nabla L(x,\lambda )=0$ .

The constants ${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ are known as Lagrange multipliers.

Example 3 We want to minimize $f\left(x\right)=x_1^2+x_2^2$ subject to $2x_1+x_2=3$ . The constraint function is

From earlier we know that $\nabla f\left(x\right)=2x,$ while we can rewrite the constraint as

so that $\nabla g\left(x\right)=\left[\begin{array}{c}2\\ 1\end{array}\right]$ . Therefore, the extremum's condition on the gradient of the Lagrangian results in the equation

the solution to this equation is $x_1=-\lambda ,x_2=-\frac{1}{2}\lambda$ . To solve for the value of the Lagrangian multiplier $\lambda$ , we plug the solution into the constraint: Plug in the constraint function

which gives $\lambda =-\frac{6}{5}$ . Therefore, we end up with the solution $x_1=\frac{6}{5},x_2=\frac{3}{5}$ .