# Speeding up a numerical constrained quadratic optimization

I'm trying to solve a quadratic optimization problem in 35 variables, $\vec{α} = \left< α_1, \ldots, α_{35}\right>$:

\begin{aligned} &\operatorname*{maximize}_\vec{α}&&1.0\cdot α_1 - 2.7\cdot {α_1}^2 + 1.0\cdot α_2 + \cdots + 0.6\cdot α_{34} \cdot α_{35} -1.6 \cdot {α_{35}}^2 \\ &\operatorname*{subject to}&&0 = α_1 + α_2 + \cdots - α_{34} + α_{35} \\ &&& \forall_i(α_i \geq 0) \end{aligned}

where the expression to be maximized has 665 terms, all linear or quadratic.

The obvious command:

nn = 35;
objective = 1.0*Subscript[α,1] - 2.7*Subscript[α,1]^2 + [...];
equalityConstraint = 0 == Subscript[α,1] + Subscript[α,2] + [...];
NMaximize[{objective, equalityConstraint} ~Join~ Table[Subscript[α, n] >= 0, {n, 1, nn}],
Table[Subscript[α, n], {n, 1, nn}]]


runs too slowly. I suspect that Mathematica's full nonlinear-optimization machinery, unneeded for this type of problem, may be slowing it down. What can I do to increase performance?

-
You will probably be better off using FindMinimum with Method -> "QuadraticProgramming" or "LevenbergMarquardt" rather than NMinimize, as the latter uses derivative-free metaheuristic approaches that are not well suited for this problem. – Oleksandr R. May 21 '13 at 1:53
@OleksandrR.: I thought FindMinimum only gives a local minimum. – Mechanical snail May 21 '13 at 2:30
That's correct, but you can still use it, via the "RandomSearch" method of NMinimize, if you want to try to find the global minimum. Of course, that you will actually find it can't be guaranteed unless you use Minimize, but I expect this will be even slower than NMinimize, if it works at all. – Oleksandr R. May 21 '13 at 4:00
@Mechanicalsnail can you give us the objective formulation explicitly in your code. Then one may give the problem a better try. – PlatoManiac May 21 '13 at 6:29
Actually FindMaximum with Method->"QuadraticProgramming" can give the global optimum. If the objective is the negative of a convex function then that should go to a global max. I'm guessing this is the case, since otherwise Levenberg-Marquardt would not be a viable approach (also i believe the quadratic programming method would give a failure message). If the objective is not negative semidefinite then you might still get a reasonable result with Method->"InteriorPoint". – Daniel Lichtblau May 21 '13 at 14:18