Minimization of a convex quadratic function

L. El Ghaoui

Minimization of a convex quadratic function

Here we consider the problem of minimizing a convex quadratic function without any constraints. Specifically, consider the problem

$p^ast := min_x : q(x) := frac{1}{2}x^TAx + b^Tx$

where $A=A^T in mathbf{R}^{n times n}$ , and $b in mathbf{R}^n$ . We assume that is convex, meaning that its Hessian is positive semi-definite.

The optimality condition for an unconstrained problem is nabla q(x) = 0 , which here reduces to

Case when is positive-definite

When is positive-definite, that is, it has only positive (non-zero) eigenvalues, then there is a unique minimizer. The above optimality condition provides it: $x^ast = -A^{-1}b$ .

Degenerate case: a simple example

Consider the case with

$q(x) = frac{1}{2}x_1^2 + b_1x_1 + b_2 x_2.$

The optimality condition is

$left(begin{array}{cc} 1 & 0 0 & 0 end{array} right) left(begin{array}{c} x_1 x_2 end{array} right) = left(begin{array}{c} b_1 b_2 end{array} right).$

These equations are feasible if and only b_2 = 0 (that is, is in the range of ). In that case, the set of optimal points are of the form x_1 = b_1 , x_2 arbitrary.

Otherwise, when b_2 ne 0 , the optimality conditions are not feasible, and the minimum value is actually p^ast = -infty . It is only attained in the limit, for example with x_1 fixed arbitrarily, x_2 rightarrow infty , with sign of x_2 equal to that of -b_2 .

General case

If is not invertible, but is in the range of , then there exist $x_0 in mathbf{R}^n$ such that b = -Ax_0 . Then any point such that x-x_0 is in the nullspace of is optimal, since

$q(x) = frac{1}{2}x^TAx-x_0^TAx = frac{1}{2}(x-x_0)^TA(x-x_0) - frac{1}{2}x_0^TAx_0.$

In particular, x_0 is optimal, and the corresponding value of the problem is $p^ast = -frac{1}{2}x_0^TAx_0$ .

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 p^ast = -infty , 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 b not in mbox{bf R}(A) , can be written as b = Ar+c , with cne0 and Ac =0 . Set x(t) :=-t c , with t in mathbf{R} ; since Ax(t) = 0 , we obtain q(x(t)) = -b^T(tc) = -tc^Tc . Letting t rightarrow +infty achieves the desired result.

Proof via the eigenvalue decomposition

A constructive proof involves the eigenvalue decomposition of the symmetric matrix . We have A = ULambda U^T , with Lambda 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 $bar{x} = U^Tx$ , as follows:

$min_{bar{x}} : frac{1}{2} bar{x}^TLambda bar{x} + bar{b}^Tbar{x},$

with $bar{b}:= U^Tb$ . Now decompose Lambda as $Lambda = mbox{bf diag}(Lambda_+,0)$ with containing the positive eigenvalues. We decompose the variable bar{x} as $bar{x} = (bar{x}_+,bar{x}_0)$ , with vector $bar{x}_+$ (resp. $bar{x}_0$ ) the variables corresponding to the positive (resp. zero) eigenvalues. Decompose bar{b} similarly, as $bar{b} = (bar{b}_+,bar{b}_0)$ . The problem writes

$min_{bar{x}_+,bar{x}_0} : frac{1}{2} bar{x}_+^TLambda_+ bar{x}_+ + bar{b}_+^Tbar{x}_+ + bar{b}_0^Tbar{x}_0.$

The problem looks exactly like the simple 2D example above.

The optimality conditions then write

$bar{x}_+ = Lambda_+^{-1}bar{b_+}, ;; 0 = bar{b}_0.$

If $bar{b}_0 = 0$ , the solutions are of the form $x = Ubar{x} = U(Lambda_+^{-1}bar{b_+},bar{x}_0)$ , with $bar{x}_0$ free. (We recover a unique solution when there are no zero eigenvalues, that is, is invertible.)

Otherwise, there are no optimal points. Choosing $bar{x} = (0,-tbar{b}_0)$ , with t rightarrow +infty , achieves the optimal value p^ast = -infty .

Minimization of a convex quadratic function

Case when is positive-definite

Degenerate case: a simple example

General case

Proof via the eigenvalue decomposition

License

Share This Book