1
$\begingroup$

I have this optimization problem on the variables $\lambda_\ell^+, \lambda_\ell^-$ such that $ \lambda_\ell^+ \geq \lambda_\ell^-$ with $\ell=1,\ldots,n$ , and fixed $P\in [1/(n+1),1]$

\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 \sum_{\ell=1}^{n}{({\lambda_\ell^+}^2+{\lambda_\ell^-}^2)}\leq P\quad\mbox{and}\quad \lambda_\ell^+\geq\lambda_\ell^-\geq 0\quad \forall \ell=1,\ldots,n\,. \end{align}

If I make $\lambda_\ell⁻=0$ for every $\ell= 2,\ldots,n$, the objective function becomes linear and the resulting problem can be cast as a semidefinite program, which is nice. In fact, as it turns out, $\lambda_\ell⁻=0$ for every $\ell= 2,\ldots,n$ is a necessary condition for the optimal solution of the problem above (I know that because the physical problem that gives rise to this mathematical problem has been solved in some independent way elsewhere). I was hoping that someone could offer a mathematical argument that enables me to restrict my feasible set with $\lambda_{2,\ldots,n}^⁻=0$.

$\endgroup$
7
  • 1
    $\begingroup$ Are you sure the signs are right in the objective? The function $f(x,y) = -\sqrt{xy}$, defined for $x,y \geq 0$, is not concave. This makes me wonder if it should be $+2$ rather than $-2$ in the objective. $\endgroup$
    – littleO
    Oct 7, 2014 at 11:58
  • $\begingroup$ Actually for $\lambda^-_i=0$ you get a second order conic problem, so even easier. What about writing down the KKT condition? I suspect they should be rather simple... $\endgroup$ Oct 7, 2014 at 14:33
  • $\begingroup$ @littleO, yes, I am sure about the negative sign. The geometric mean is concave, so my objetive function is convex (linear + convex). $\endgroup$
    – AquilaXi
    Oct 8, 2014 at 1:14
  • $\begingroup$ @AC_MOSEK, yes, for $\lambda_i^-0$ I have a SOCP. My problem is precisely about how to argue that I can make $\lambda_i^-=0$ for $i=2,\ldots,n$ in order to take advantage of this fact. $\endgroup$
    – AquilaXi
    Oct 8, 2014 at 1:17
  • $\begingroup$ Here's a thought: Consider the relaxation \begin{align} \mbox{maximize}&\quad \lambda_{1}^+-\lambda_{1}^--2\sum_{\ell= 2}^n\sqrt{\lambda_\ell^+\lambda_\ell^-}\nonumber\\ \mbox{subject to}&\quad\lambda_\ell^+\geq\lambda_\ell^-\geq 0\quad \forall \ell=1,\ldots,n\,. \end{align} Here, there is no doubt that the optimal solution satisfies $\lambda_\ell=0$ for $\ell=2,\ldots,n$. Now, since this is still feasible if we further require $\sum_{\ell=1}^{n}{({\lambda_\ell^+}+{\lambda_\ell^-})}=1$ and $\sum_{\ell=1}^{n}{({\lambda_\ell^+}^2+{\lambda_\ell^-}^2)}\leq P$, can conclude that it's necessary? $\endgroup$
    – AquilaXi
    Oct 8, 2014 at 1:33

1 Answer 1

0
$\begingroup$

Let $\lambda_l^+,\lambda_l^-$ for $l=1,\ldots,n$ be a feasible solution such that there exists $l$ such that $\lambda_l^->0$. Setting

$$ \lambda_l^+ \leftarrow \lambda_l^ + + \lambda_l^-,\\ \lambda_l^- \leftarrow 0, $$

we obtain a new feasible solution. It is easy to see that the objective function cannot decrease.

$\endgroup$
5
  • $\begingroup$ That's looking good. I just don't get why the solution after the replacement is still feasible, since the quadratic constraint after the replacement becomes $\sum_{\ell=1}^n(\lambda_\ell^++\lambda_\ell^-)^2\leq P$, which is not implied by the original constraint $\sum_{\ell=1}^n({\lambda_\ell^+}^2+{\lambda_\ell^-}^2)\leq P$. So, why is the new solution still feasible? $\endgroup$
    – AquilaXi
    Oct 8, 2014 at 23:02
  • $\begingroup$ Because $\lambda_l^+ + \lambda_l^-$ does not change after the replacement. $\endgroup$ Oct 9, 2014 at 6:09
  • $\begingroup$ I understand that due to the invariance of $\lambda_l^++\lambda_l^-$ the first constraint remains satisfied. Moreover, the last constraint is also still trivially satisfied. However, I don't see how the invariance of $\lambda_l^++\lambda_l^-$ can be used to justify that the quadratic constraint is satisfied after the replacement (cf. my previous comment). Am I missing something? $\endgroup$
    – AquilaXi
    Oct 9, 2014 at 10:28
  • $\begingroup$ well $(\lambda_l^+)^2 + (\lambda_l^-)^2$ becomes $(\lambda_l^+ + \lambda_l^-)^2= (\lambda_l^+)^2 + (\lambda_l^-)^2 - 2 \lambda_l^+ \lambda_l^-$ that is smaller because the variables are positive. Thus you are still feasible. $\endgroup$ Oct 9, 2014 at 14:50
  • $\begingroup$ So, there's where the problem is: we disagree on the minus sign. $(\lambda_l^+)^2+(\lambda_l^-)^2$ indeed becomes $(\lambda_l^++\lambda_l^-)^2$, but this is $(\lambda_l^+)^2+(\lambda_l^-)^2+2\lambda_l^+\lambda_l^-$, which is NOT smaller than the original. Thus, feasibility is not guaranteed. $\endgroup$
    – AquilaXi
    Oct 9, 2014 at 19:08

You must log in to answer this question.

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