1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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[].)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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