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$?


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 '15 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$ – AndreaCassioli Jan 7 '15 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.