5
$\begingroup$

I have a (non-strictly) convex quadratic form and I am wondering what the best (in terms of speed) method (iterative or not) to find a local minimum is. Since the objective function is convex, every local minimum is also global.

I thought of the conjugate gradient method, but the matrix of the quadratic form is not positive definite (but rather positive semidefinite).

Whatever you have to suggest I am listening (papers to read, books). Thanks you in advance.

$\endgroup$
5
  • 1
    $\begingroup$ Especially since you're concerned about speed, you may want to take this to a Computer Science StackExchange website. $\endgroup$ – Clarinetist Jan 15 '18 at 15:21
  • 1
    $\begingroup$ The set of minima is an affine subspace cut out by certain linear equations, whose coefficients appear in the presentation of your quadratic form. Solve the equations somehow, and you are done. $\endgroup$ – kimchi lover Jan 15 '18 at 15:35
  • 1
    $\begingroup$ How large is your matrix? Is it sparse (most entries are zero) or dense (most entries non-zero)? Of the infinitely many least squares solutions do you have any reason to prefer one of them (for example, you might want the least squares solution of minimum norm.) $\endgroup$ – Brian Borchers Jan 15 '18 at 15:52
  • $\begingroup$ @BrianBorchers It is a 3x3 matrix . I don't have any special solution to find. I have optimization problems in which it appears a positive semidefinite matrix and instead of writing by hand the solution I want a method to solve it so that I can write a programm about it. $\endgroup$ – chaviaras michalis Jan 15 '18 at 17:02
  • $\begingroup$ There should be no difference for 3 x 3 matrices. Solving an unconstrained convex quadratic program is equivalent to solving the corresponding linear system $Ax=b$. $\endgroup$ – mathmath8128 Jan 15 '18 at 20:06
6
$\begingroup$

You have a convex quadratic form to minimize. This can be written in the form:

$\min f(x)=\frac{1}{2} x^{T}Ax - b^{T}x + c$

where $A$ is symmetric and positive semidefinite.

The gradient of $f$ is

$\nabla f(x)=Ax-b$

Any point $x$ where $\nabla f(x)=0$ will be a minimizer. In other words, any solution to $Ax=b$ will be a minimizer. If there is no solution, then the minimization problem is unbounded. Since $A$ is positive semidefinite, $A$ may be a singular matrix.

There are lots of ways of solving such a system of equations. Since $A$ is tiny (3 by 3), using a direct factorization method is most appropriate. Since $A$ is likely singular, a good choice is to use the QR factorization with column pivoting. This gives you a permutation matrix $P$, orthogonal matrix $Q$, and an upper triangular matrix $R$ such that

$AP=QR$

If $A$ is positive semidefinite but not positive definite, then the $R$ matrix will be singular, with one or more effectively 0 entries on the diagonal. You'll have to apply some tolerance in deciding what "effectively 0" is.

To solve $Ax=b$,

$APP^{-1}x=b$

$QR(P^{-1}x)=b$

$R(P^{-1}x)=Q^{-1}b$

Since $Q$ is orthogonal $Q^{-1}=Q^{T}$

$R(P^{-1}x)=Q^{T}b$

Let $y=P^{-1}x$ or $x=Py$. Solve

$Ry=Q^{T}b$

Since $R$ is upper triangular, it's easy to solve this sytem of equations by back substitution. If this system is inconsistent, then the original minimization problem is unbounded. If the system is consistent, then take any $y$ that solves the system of equations, and let $x=Py$. In solving the system of equations you may see some entries in $y$ that are free to take on any value. A simple solution is to set these to 0.

The QR factorization with column pivoting is implemented in MATLAB, Julia, Python/Numpy, etc. At a lower level, this is available in the LAPACK library that you can call from languages like C, Fortran, etc.

$\endgroup$
2
  • $\begingroup$ In this procedure I must compute the Q and R matrix ... So do you suggest the Gram–Schmidt process? $\endgroup$ – chaviaras michalis Jan 15 '18 at 18:29
  • $\begingroup$ No, the QR factorization is typically computed in a more numerically stable way by using Householder transformations. You should use a library routine to do this for you. $\endgroup$ – Brian Borchers Jan 15 '18 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.