Minimization of a convex quadratic functionHere we consider the problem of minimizing a convex quadratic function without any constraints. Specifically, consider the problem where , and . We assume that is convex, meaning that its Hessian is positive semi-definite. The optimality condition for an unconstrained problem is , which here reduces to Case when is positive-definiteWhen is positive-definite, that is, it has only positive (non-zero) eigenvalues, then there is a unique minimizer. The above optimality condition provides it: . Degenerate case: a simple exampleConsider the case with The optimality condition is These equations are feasible if and only (that is, is in the range of ). In that case, the set of optimal points are of the form , arbitrary. Otherwise, when , the optimality conditions are not feasible, and the minimum value is actually . It is only attained in the limit, for example with fixed arbitrarily, , with sign of equal to that of . General caseIf is not invertible, but is in the range of , then there exist such that . Then any point such that is in the nullspace of is optimal, since In particular, is optimal, and the corresponding value of the problem is . If is not in the range space of , then there are no minimizing points. This means that the minimum is not attained. We can in fact show that , and construct a sequence of points that achieves this value in the limit. We simply invoke the fundamental theorem of linear algebra. For symmetric matrices, the theorem specializes to the fact that range and nullspace are orthogonal. Since , can be written as , with and . Set , with ; since , we obtain . Letting achieves the desired result. Proof via the eigenvalue decompositionA constructive proof involves the eigenvalue decomposition of the symmetric matrix . We have , with a diagonal matrix containing the (non-negative) eigenvalues of , and an orthogonal matrix of eigenvectors. The original problem can be expressed in terms of the new variable , as follows: with . Now decompose as with containing the positive eigenvalues. We decompose the variable as , with vector (resp. ) the variables corresponding to the positive (resp. zero) eigenvalues. Decompose similarly, as . The problem writes The problem looks exactly like the simple 2D example above. The optimality conditions then write If , the solutions are of the form , with free. (We recover a unique solution when there are no zero eigenvalues, that is, is invertible.) Otherwise, there are no optimal points. Choosing , with , achieves the optimal value . |