<< Chapter < Page | Chapter >> Page > |
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}\phantom{\rule{3.33333pt}{0ex}}\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 $\u27e8\nabla f\left({x}_{0}\right),h\u27e9=0$ , as stated by Theorem [link] .
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,\phantom{\rule{3.33333pt}{0ex}}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)=\u27e8x,{w}_{i}\u27e9$ ; therefore, we can rewrite the space above as its dual equivalent
Now since $\u27e8w,{w}_{i}\u27e9={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=\u27e8w,{w}_{0}\u27e9$ . 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 $2{x}_{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}$ .
Notification Switch
Would you like to follow the 'Signal theory' conversation and receive update notifications?