I am trying to solve a simple quadratic minimisation problem of the form:
$$ min_x\;\;\; \underline{x}^TQ\underline{x} $$ $$ s.t.\quad (\underline{\mu}-r\,\underline{1} )^T\;\underline{x} = 1 $$
Where Q is s.p.d.
Using the method of Lagrange multipliers, I should be able to form: $$ \mathcal{L}(x,\lambda) = \underline{x}^TQ\underline{x} - \lambda\,\left(\,(\,\underline{\mu}-r\,\underline{1} )^T\,\underline{x} - 1\right)$$
And finding the stationary point: $$\nabla \mathcal{L} = 2\, Q \,\underline{x} \,- \lambda \,(\underline{\mu}-r\,\underline{1} ) =0$$
If we let $N$ be the length of vector $ \underline{x} $, then this system of equations ($\nabla_{x_1},\, \nabla_{x_2}, \, ..., \nabla_{x_N} , \nabla_\lambda $) can be described in a matrix equation of the form $Ax=b$, which (including the terms for $\nabla_\lambda$) has size N+1, and which can be solved using any typical technique for systems solvers.
However, I find two glaring issues here which suggest I have misunderstood something fundamental.
- I find (using Python http://scipy-cookbook.readthedocs.io/items/RankNullspace.html) that matrix A (and indeed, also the original $ N\times N$ matrix $Q$) has an empty nullspace. This seems to suggest there is only the trivial solution $\underline{x} = \underline{0}$.
- If we were to replace the equality constraint with the even simpler: $$ s.t.\quad \underline{1}^T \, \underline{x} = 1 $$ then we find the constraint would evaluate to zero in the Lagrangian derivative, and so would essentially be ignored. This is particularly strange since this constraint should prevent the trivial solution - c.f. $\underline{x}$ being probabilities or allocations which must sum to 1.
What have I got wrong, and how can I solve this minimisation problem using Lagrangian multipliers to solve for Ax=b?
You don't have a linear term in your objective function, so of course you are getting the multidimensional version of $x^2$. (If you expand $Q$ in eigenvectors, you can find the linear change of coordinates that diagonalizes $Q$, making it explicitly $\sum\hat{x}_i^2$.)
Since you have equality constraints, the method here is what you are doing and is perhaps organized a little more transparently.