Suggestions to solve an optimization problem that involves quadratic forms.

80 Views Asked by At

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.

1

There are 1 best solutions below

0
On

The square roots do not pose a significant problem. The bigger issue is your constraint $x^\intercal S x \geq 0$.

If $S$ is positive semidefinite then the constraint is trivial, and if $S$ is negative semidefinite then the constraint would be better expressed as $Sx = 0$. If is is neither NSD nor PSD then you have yourself a non-convex quadratic program.

With the exception of single-constraint quadratic programming, there are no particularly easy ways to solve non-convex quadratic programs.