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 '17 at 13:15
  • $\begingroup$ 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] $\endgroup$ Aug 1 '17 at 13:19
  • $\begingroup$ Or maybe #/Total[#] &@LinearSolve[A + Transpose@A, Table[1, {Length@A}]]. $\endgroup$
    – Michael E2
    Aug 1 '17 at 13:47
  • $\begingroup$ (1) A specific example would be useful here. (2) FindMinimum supports Method -> "QuadraticProgramming". $\endgroup$ Aug 1 '17 at 14:41
  • $\begingroup$ @Daniel, that's the one that uses CLP under the hood, no? $\endgroup$
    – J. M.'s torpor
    Aug 1 '17 at 14:43
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, privacy policy and cookie policy

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