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.

Improve this question
$\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$
    – Mauricio Fernández
    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$
    – Mauricio Fernández
    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$
    – Daniel Lichtblau
    Aug 1, 2017 at 14:41
  • $\begingroup$ @Daniel, that's the one that uses CLP under the hood, no? $\endgroup$
    – J. M.'s eventual burnout ♦
    Aug 1, 2017 at 14:43

1 Answer 1

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

Improve this answer
$\endgroup$
0

Your Answer

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

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