Timeline for Suggestions to solve an optimization problem that involves quadratic forms
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2018 at 2:05 | comment | added | fedja | Note that (*) is very similar to a quadratic program, the problem is square roots If it were your only problem, you could use the old trick and define $U_t=(1+t)E+(1+t^{-1})S$. Then for each $w$, your objective function is just $\inf_t w^TU_tw$, so you could swap the infima and find $\inf_w w^TU_tw$ first and then solve a one-dimensional optimization problem in $t$ (still need to think how to do the latter in an intelligent way, of course). However, like Mark, I'm much more concerned about possible sign changes of $S$. | |
| Mar 22, 2018 at 0:51 | comment | added | Mark L. Stone | As for changing due a different, non-equivalent formulation, it is hard to provide guidance without understanding what you need the optimization to accomplish (for instance, there are different ways of combining the 2 terms inside the square in the o0bjective function). How large are the problems? How important is the runtime?Do you need to solve many different instances of this problem within a simulation (once for each scenario or simulation replication)? Also. 1st comment had typo: should be re-write this as Second Order Cone Problem ($w^TSw \ge 0$ is deleted ... | |
| Mar 22, 2018 at 0:35 | comment | added | Mark L. Stone | If $S$ is positive semidefinite,get rid of the square in the objective (which doesn't affect the argmin), and using Cholesky factors of E and S, it's easy to re-write this as Second Order Cone Problem ($w^TSw$ is deleted and objective terms moved to the constraints), which is convex and easy to solve to global optimality with many solvers. If S is indefinite, then due to non-convex terms in objective and constraints, you may need a general non-convex solver (your problem is not (just) the square roots it is the constraint $w^TSw$, which is non-convex if S is indefinite or unnecessary if psd. | |
| Mar 21, 2018 at 23:57 | review | First posts | |||
| Mar 22, 2018 at 1:43 | |||||
| Mar 21, 2018 at 23:55 | history | asked | Diego Fonseca | CC BY-SA 3.0 |