# Quadratic optimisation problem

I'm trying to solve the optimisation problem $\mathbf x^\top\mathbf A\mathbf x$ such that $x_1 + \ldots + x_n = 1$, where $\mathbf x$ is the vector of variables to be optimised and $\mathbf A$ is some arbitrary matrix.

This is of course easy to do when $x$ is of small dimension using

Minimize[{f, cons}, {x1, x2, ...}]


But when $\mathbf x$ is arbitrarily large, this does not scale up in an obvious way. I was looking for some sort of built-in quadratic optimiser similar to quadprog in MATLAB, but there does not seem to be such a thing.

• If your $A$ is allowed to be indefinite, you will find nothing, since $f=x^TAx$ is then unbounded. Is your $A$ positive definite? Aug 1 '17 at 13:15
• If your $A$ is definite, then try first a direct forumlation: n = 5; A = RandomReal[{-1, 1}, {n, n}]; A = Transpose@A.A; Eigenvalues@A x = Array[xc, n]; f = x.A.x; cons = Total@x == 1; NMinimize[{f, cons}, x] Aug 1 '17 at 13:19
• Or maybe #/Total[#] &@LinearSolve[A + Transpose@A, Table[1, {Length@A}]]. Aug 1 '17 at 13:47
• (1) A specific example would be useful here. (2) FindMinimum supports Method -> "QuadraticProgramming". Aug 1 '17 at 14:41
• @Daniel, that's the one that uses CLP under the hood, no? Aug 1 '17 at 14:43

## 1 Answer

As already noted, the matrix $\mathbf A$ should be symmetric positive definite for the minimization of $\mathbf x^\top\mathbf A\mathbf x$ to make sense. With that, here's an example of how to get a minimal vector corresponding to an SPD matrix of arbitrary dimensions:

With[{n = 8},
mat = HilbertMatrix[n];
Minimize[{x.mat.x, x.ConstantArray[1, n] == 1}, x ∈ FullRegion[n]]]
{1/64, {x -> {-1/8, 63/8, -945/8, 5775/8, -17325/8, 27027/8, -21021/8, 6435/8}}}


Check that the constraint is satisfied:

Total[x /. Last[%]]
1


(Note that this still works if Minimize[] is replaced with NMinimize[].)