Quadratic minimization with norm constraint

Minimizes convex or non-convex quadratics subject to (in)equality constraint on norm(x)

This routine minimizes an arbitrary quadratic function subject to a constraint on the l2-norm of the variables. The problem is of a form commonly encountered as a sub-problem in trust region algorithms, but undoubtedly has other applications as well.

USAGE:

[xmin,Jmin] = trustregprob(Q,b,w)
[xmin,Jmin] = trustregprob(Q,b,w,doEquality)

When doEquality=true (the default), the routine solves,

minimize J(x) = x.'*Q*x/2-dot(b,x) such that ||x|| = w

where ||x|| is the l2-norm of x. The variables returned xmin, Jmin are the minimizing x and its objective function value J(x).

When doEquality=false, the routine solves instead subject to ||x|| <= w .

Q is assumed symmetric, but not necessarily positive semi-definite. In other words, the objective function J(x) is potentially non-convex. Since the solution is based on eigen-decomposition, it is appropriate mainly for Q not too large. If multiple solutions exist, only one solution is returned.