2.1 Constrained optimization

A typical problem arising in signal processing is to minimize $x^TAx$ subject to the linear constraint $c^Tx=1$ . $A$ is a positive definite, symmetric matrix (a correlation matrix) in mostproblems. Clearly, the minimum of the objective function occurs at $x=0$ , but his solution cannot satisfy the constraint. The constraint $g(x)=c^Tx-1$ is a scalar-valued one; hence the theorem of Lagrange applies as there are no multiple components in theconstraint forcing a check of linear independence. The Lagrangian is $$L(x, )=x^TAx+(c^Tx-1)$$ Its gradient is $2Ax+c$ with a solution $x_{}=-\left(\frac{{}_{}A^{(-1)}c}{2}\right)$ . To find the value of the Lagrange multiplier, this solution must satisfy the constraint. Imposing theconstraint, ${}_{}c^TA^{(-1)}c=-2$ ; thus, ${}_{}=\frac{-2}{c^TA^{(-1)}c}$ and the total solution is $$x_{}=\frac{A^{(-1)}c}{c^TA^{(-1)}c}$$

Consider slight variations to the previous example: let the vector $z$ be complex so that the objective function is $(z)Az$ where $A$ is a positive definite, Hermitian matrix and let the constraint be linear, but vector-valued ( $Cz=c$ ). The Lagrangian is formed from the objective function and the real part of the usual constraint term. $$L(z, )=(z)Az+()(Cz-c)+^T(\overline{C}\overline{z}-\overline{c})$$ For the Lagrange multiplier theorem to hold, the gradients of each component of the constraint must be linearlyindependent. As these gradients are the columns of $C$ , their mutual linear independence means that each constraint vector mustnot be expressible as a linear combination of the others. We shall assume this portion of the problem statement true.Evaluating the gradient with respect to $\overline{z}$ , keeping $z$ a constant, and setting the result equal to zero yields $$A{z}_{}+(C){}_{}=0$$ The solution is $z_{}$ is $-(A^{(-1)}(C){}_{})$ . Applying the constraint, we find that $CA^{(-1)}(C){}_{}=-c$ . Solving for the Lagrange multiplier and substituting the result into the solution, we find that thesolution to the constrained optimization problem is $$z_{}=A^{(-1)}(C)CA^{(-1)}(C)^{(-1)}c$$ The indicated matrix inverses always exist: $A$ is assumed invertible and $CA^{(-1)}(C)$ is invertible because of the linear independence of the constraints.

Consider the problem of minimizing a quadratic form subject to a linear equality constraint and an inequality constrainton the norm of the linear constraint vector's variation. $$\min\{x , x^TAx\}\text{subject to}(c+)^Tx=1\text{and}()^2\le$$ This kind of problem arises in robust estimation. One seeks a solution where one of the "knowns" of the problem, $c$ in this case, is, in reality, only approximately specified. Theindependent variables are $x$ and $$ . The Lagrangian for this problem is $$L(\{x, \}, , )=x^TAx+((c+)^Tx-1)+(()^2-)$$ Evaluating the gradients with respect to the independent variables yields $$2A{x}^{}+{}^{}(c+{}^{})=0$$ $${}^{}{x}^{}+2{}^{}{}^{}=0$$ The latter equation is key. Recall that either ${}^{}=0$ or the inequality constraint is satisfied with equality. If ${}^{}$ is zero, that implies that $x^{}$ must be zero which will not allow the equality constraint to be satisfied. The inescapable conclusion isthat $({}^{})^2=$ and that ${}^{}$ is parallel to $x^{}$ : ${}^{}=-(\frac{{}^{}}{2{}^{}}{x}^{})$ . Using the first equation, $x^{}$ is found to be $$x^{}=-\left(\frac{{}^{}}{2}\right)A-\frac{{}^{}^2}{4{}^{}}I^{(-1)}c$$ Imposing the constraints on this solution results in a pair of equations for the Lagrange multipliers. $$(1/4\frac{{}^{}^2}{{}^{}})^{2}c^T(A-1/4\frac{{}^{}^2}{{}^{}}I)^{-2}c=$$ $$c^TA-1/4\frac{{}^{}^2}{{}^{}}I^{(-1)}c=-\left(\frac{2}{{}^{}}\right)-2\frac{{}^{}}{{}^{}^2}$$ Multiple solutions are possible and each must be checked. The rather complicated completion of this example is left tothe (numerically oriented) reader.