3
$\begingroup$

I'm interested in the optimization problem

$$\begin{array}{ll} \text{maximize} & x^T M \, x\\ \text{subject to} & \| x \| \leq 1\\ & x \geq 0\end{array}$$

where $M$ is positive definite. As I understand it, this isn't a convex problem, but the constraints should define a convex set. Is there a well-known way of solving this sort of problem?

For those curious about how I might have gotten here: I have $c$ sensors, each of which has $k$ features. I want to find a convex combination of the $k$ features per sensor that maximizes the distance between some patterns over the sensors.

$\endgroup$
  • 1
    $\begingroup$ This seems relevant: mathoverflow.net/questions/145028/… $\endgroup$ – Michael Grant Nov 1 '17 at 21:34
  • $\begingroup$ it is easy to see that the maximum is obtained where $\|x\|=1$. Then, maybe you can use lagrangian multipliers for $x^Tx=1$ and see what happens? $\endgroup$ – supinf Nov 2 '17 at 13:27
  • $\begingroup$ maybe the wiki article for quadraticly constrained problems could be helpful as well: en.wikipedia.org/wiki/… $\endgroup$ – supinf Nov 2 '17 at 13:29
  • $\begingroup$ @supinf with the lagrange multiplier approach I can't use the positivity constraint, though, right? $\endgroup$ – bibliolytic Nov 2 '17 at 17:25
  • 1
    $\begingroup$ The objective is convex but I'm not minimizing, I'm maximizing and so standard convex solvers (or at least cvxpy) won't allow me to do it $\endgroup$ – bibliolytic Nov 4 '17 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.