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 Answer 1


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.

  • $\begingroup$ Thanks. Two questions for clarification: 1) It seems to me that you're implying the following: "If the optimal solution of a problem has a certain property that is feasible for a more constrained version of the original problem, then the optimal solution of the more constrained problem also has that property". Is this true in general? 2) When you write the equivalent problem, you disappear with the variables $λ_{2,\ldots,n}^+$. Was that just for brevity? I think they should still appear in the constraints like $(\lambda_1^-)^2+\sum_{\ell=1}^n(\lambda_\ell^+)^2\leq P$, etc, or am I losing some? $\endgroup$
    – AquilaXi
    Jan 6, 2015 at 23:55
  • $\begingroup$ (1) I would not generalized so much! (2) I just set all those variables to 0 and then remove them for sake of brevity. I think you can show they are set to zero from the optimality condition of the original problem. $\endgroup$ Jan 7, 2015 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .