# projection theorem for a finite-dimensional problem

Using the projection theorem, solve the finite-dimensional problem:

minimize $x'Qx$ ($x'$ is the transpose of $x$ )

subject to $Ax = b$

where $x$ is an $n$-vector, $Q$ a positive-definite symmetric matrix, A an $m$x$n$ matrix ($m<n$), and $b$ and $m$-vector

Solution: I tried to apply Gauss-markov theorem but the professor told me that my approach was completely unnecessary,

Source: Book Optimization by Vector Space Methods (Luenberger). Ch3, prob 21.

In Luenburger's book, the minimum norm is treated extensively. So if you are following his book carefully, one natural idea is convert the problem into a minimal norm problem.

Let $A = \begin{pmatrix} a_1^T \\ \vdots \\ a_m^T\end{pmatrix}$, where $a_j \in \mathbb{R^n}$ are column vectors. Consider the inner product $\langle \cdot, \cdot \rangle_Q$induced by $Q$, and it is easy to see this is well defined. The problem is equivalent to \begin{align*} \begin{array}{ll} \text{min} & \|x\|_Q \\ \text{s.t.} & \langle Q^{-1} a_1, x \rangle_Q = b_1, \; \dots, \; \langle Q^{-1} a_m, x \rangle_Q = b_m. \end{array} \end{align*} Let $M = \text{span} \left( Q^{-1}a_1, \dots, Q^{-1}a_m \right) \subset \mathbb{R}^n$. The constraint is a translation of $M^{\perp}$ (Think about it). By projection theorem, the minimizer $x_* \in M^{\perp \perp}$. Since $M$ is finite dimensional subspace and consequently closed, $M = M^{\perp \perp}$. So $x_* = \sum_{j=1}^m \beta_j Q^{-1} a_j = Q^{-1}A^T \beta$. The remaining part is to determine the vector $\beta = (\beta_1, \dots, \beta_m)^T$. We note $x_*$ satisfies all the constraints. Thus $\langle x_*, Q^{-1}a_j \rangle_Q = b_j$ for all $j \in \{1, \dots, m\}$. If you write down everything, you should be able to recogonize the Gram matrix is given by $AQ^{-1}A^T$ and it follows $\beta = (AQ^{-1}A^T)^{-1} b$. Hence \begin{align*} x_* = Q^{-1}A^T \beta = Q^{-1}A^T(AQ^{-1}A^T)^{-1} b. \end{align*}

You have to minimize $f(x)=x'Qx$ over the (affine) subspace $\pi:Ax=b$. But, being $Q=L'L$ for Cholesky's theorem, I guess is more simple to minimize $\|y\|$ over $L(\pi)$ easy-to-do by taking the orthogonal (which we have in parametric form, actually, from the equation form of $\pi$). This automatically prove you have a solution and (knowing Cholesky algorithm) gives you a way of calculate the solution.

Since $B$ is definite positive and symmetric, it defines a scalar product over $H=\mathbb{R}^n$, namely $\langle x,y\rangle_B = \langle x, B y\rangle$. Consider the Hilbert space $(H, \langle \cdot,\cdot\rangle_B)$ (it has the same topology as the usual $(H, \langle \cdot,\cdot\rangle)$ since for finite dimensional vector spaces all the norms are equivalent).

It is well known that any convex closed subset of an Hilbert space has an element of minimal norm.

In your case the set $\{Ax=b\}\subset H$ is closed and convex and you want to find the minimal $B$-norm element $$(\min_{\{Ax=b\}} ||x||_B )^2=\min_{\{Ax=b\}} ||x||_B^2$$ where $||x||_B^2 = \langle x, B x\rangle$.

So what you can do is consider the metric projector $P:H\to \{Ax=b\}$ (with the new metric given by $B$) and $P(0)$ is your mimimum.