3
$\begingroup$

I am reading through convex optimization and I came across this following problem:

\begin{align*} \max \text{ } & 2^{-x}+2^{-y}\\ \text{s.t. } & \frac{1}{1+x}+\frac{1}{1+y}\leq b\\ & x\geq0\\ & y\geq0 \end{align*}

I have tried a few different approaches but none seem to work. How should I approach this problem?

Also, is there a way to solve the generalized version of this problem with the original constraints modified to include terms for the new variables (lets say $N$ variables.) ? (i.e. $x_i \geq 0$ and $\frac{1}{1 + x_1} + \frac{1}{1 + x_2} ... + \frac{1}{1 + x_N} \leq b $)

$\endgroup$
6
  • $\begingroup$ @par Yes, b has to between 0 and 2 ... But doesn't KKT conditions require (for sufficiency) that the given problem must be convex.? For example, isn't it true that the 1st constraint is not convex? $\endgroup$ Dec 30, 2015 at 3:50
  • $\begingroup$ Not necessarily: en.wikipedia.org/wiki/… $\endgroup$
    – parsiad
    Dec 30, 2015 at 3:53
  • $\begingroup$ @A.G. The objective function's Hessian is positive semi-definite... so, the obj. function has to be convex..?? $\endgroup$ Dec 30, 2015 at 4:45
  • 1
    $\begingroup$ The feasible region is convex, which is nice, but the objective function is not concave (it is convex), which is what you would like for a convex maximization problem (i.e., minimize a convex function). Therefore this is not a "convex optimization problem" per se. Global optimization techniques are in order. $\endgroup$
    – A.G.
    Dec 30, 2015 at 6:23
  • $\begingroup$ Might I suggest a change of variable... either linearize the constraint with $$ u=\frac{1}{1+x}\ v=\frac{1}{1+y}\ \rightarrow u+v\leq b $$ or linearize the objective with $$ u=\frac{1}{2^x}\ v=\frac{1}{2^y}\ \rightarrow Z = u+v $$ Playing with these in Mathematica reveals some interesting nonconvexities (?). $\endgroup$
    – A.G.
    Dec 30, 2015 at 6:33

1 Answer 1

2
$\begingroup$

If $b\leq0$, it is easily verified that the program is infeasible. If $b\geq2$, it is easily verified that an optimal solution is $x=y=0$. Therefore, suppose $0<b<2$.

Edit: I removed my erroneous solution but am not deleting this answer since there are some useful comments below.

$\endgroup$
3
  • $\begingroup$ Thanks, it surely seems that the optimal solution has to be symmetric.. but how do we exactly prove it? Moreover, is there any standard procedure (similar to KKT etc...) through which we can solve this problem? $\endgroup$ Dec 30, 2015 at 5:10
  • 2
    $\begingroup$ I fail to see why an optimal solution would verify x=y. Surely if {x,y} is optimal then so is {y,x}, but that does not mean that x=y. $\endgroup$
    – A.G.
    Dec 30, 2015 at 5:38
  • 2
    $\begingroup$ Let me deal with the case $b\leq1$. Consider a solution with $y\to \infty$; if the constraint is active then $\frac{1}{1+x}+\frac{1}{1+y}=b$, thus $x\approx \frac{1}{b}-1$ and the objective is $$ Z\approx \frac{1}{2^{x}}\approx\frac{1}{2^{\frac{1}{b}-1}}. $$ If for example $b=1/2$, a solution is $x=1$ and $y\to\infty$ with $Z\approx1/2$, which is better that the solution $x=y=(2/b)-1=3$ that yields $Z=1/4$. $\endgroup$
    – A.G.
    Dec 30, 2015 at 5:49

You must log in to answer this question.

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