0
$\begingroup$

I am in a crucial part of my research, I have arrived at an optimization problem that I can not solve, I need to solve it to be able to perform simulations and thus complete my research, due to this difficulty I am satisfied with an approximation of the optimal value of my problem. The optimization problem that I am referring is $(*)$ which I will describe below:

Let $E$ and $S$ be symmetric matrices of $m\times m$ such that $E$ is positive semidefinite. We define $\mathbf{e}\in\mathbb{R}^{m}$ column vector such that $\mathbf{e}_{i}=1$ for $i=1,\ldots,m-1$ and $\mathbf{e}_{m}=0$.

We consider the following optimization problem

$$\left\{\begin{array}{ll} {\displaystyle \inf_{w\in\mathbb{R}^{m}}} & {\displaystyle \left( \sqrt{w^{T}Ew}+\sqrt{w^{T}Sw} \right)^{2} }\\ \mbox{subject to} & w^{T}Sw\geq 0, \\ & \mathbf{e}^{T}w=1, \\ & w(m-1)\geq 0, \\ & w(m)=1. \end{array}\right. \tag{*}$$

The question: I need to solve $(*)$, for this purpose I appeal to the community of this website to help me with any suggestions, this help can be a way to reformulate $(*)$ in such a way that the new problem is in a context in which has more information, another help would be with some suggestion about an algorithm to approximate the optimal value of $(*)$.

Remark: Note that (*) is very similar to a quadratic program, the problem is square roots.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Commented Mar 22, 2018 at 0:35
  • $\begingroup$ 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 ... $\endgroup$
    – Mark L. Stone
    Commented Mar 22, 2018 at 0:51
  • $\begingroup$ 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$. $\endgroup$
    – fedja
    Commented Mar 22, 2018 at 2:05

0

Reset to default

You must log in to answer this question.