# Maximize $2^{(-x)} + 2^{(-y)}$ subjected to certain conditions

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

• @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? Dec 30, 2015 at 3:50
• Not necessarily: en.wikipedia.org/wiki/… Dec 30, 2015 at 3:53
• @A.G. The objective function's Hessian is positive semi-definite... so, the obj. function has to be convex..?? Dec 30, 2015 at 4:45
• 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.
– A.G.
Dec 30, 2015 at 6:23
• 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 (?).
– A.G.
Dec 30, 2015 at 6:33

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$.
• 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$.