Optimization problem with an added quadratic inequality constraint

237 Views Asked by At

Consider the following (non-convex) optimization problem on the real variables $\lambda_\ell^\pm$ with $\ell=1,\ldots,n$

\begin{align} \mbox{maximize}&\quad \lambda_{1}^+-\lambda_{1}^--2\sum_{\ell= 2}^n\sqrt{\lambda_\ell^+\lambda_\ell^-}\nonumber\\ \mbox{subject to}&\quad\sum_{\ell=1}^{n}{({\lambda_\ell^+}+{\lambda_\ell^-})}=1\quad\mbox{and}\quad\quad \lambda_\ell^+\geq\lambda_\ell^-\geq 0\quad \forall \ell=1,\ldots,n\,. \end{align}

It is clear that, without loss of generality, we can set $\lambda_{2,\ldots,n}^-=0$ and solve the resulting LP for $\lambda_1^-$ and $\lambda_\ell^+$.

If, however, we further constrain this problem with the quadratic inequality constraint

\begin{equation} \sum_{\ell=1}^{n}{[({\lambda_\ell^+})^2+({\lambda_\ell^-})^2]}\leq P \end{equation} for some fixed $P\in [1/(n+1),1]$, can we still assume that there is an optimal solution with $\lambda_{2,\ldots,n}^-=0$?

1

There are 1 best solutions below

2
On BEST ANSWER

You can definitely set $\lambda^-_l=0$ for $l=2,\ldots,n$.

Indeed, whatever is $P$, you will never need to increase any of that variable to get feasibility. Your problem is actually equivalent to

$$ min \lambda^-_1 - \lambda^+_1\\ s.t.\\ (\lambda^-_1)^2 + (\lambda^+_1)^2\leq P\\ \lambda^-_1 + \lambda^+_1 = 1\\ \lambda^-_1,\lambda^+_1\geq 0$$

which is a simple quadratic convex problem. (actually even the original one is convex).

Then you set $\lambda^-_1= 1-\lambda^+_1$ and after few passages you get

$$ \max \lambda^+_1 \\ s.t.\\ (\lambda^+_1)^2 \leq \lambda^+_1 + \frac{P-1}{2}\\ \lambda^+_1\geq 0$$

Since you maximize $\lambda_1^+$, the last equation is never binding so you can drop it. The solution can be find in closed form from the optimality conditions.