2
$\begingroup$

I try to solve a maximization problem using CVX. In its simplest form, I want to maximize $$f(x,y)=y*h_b\left(\frac{x}{y}\right),$$ where $h_b(\cdot)$ is the binary entropy function. In the context of CVX, it can be written as $$f(x,y)=y*\left(entr\left(\frac{x}{y}\right)+entr\left(1-\frac{x}{y}\right)\right).$$ The conditions that I want to impose is as \begin{align*} 1 \geq y \geq x &\geq 0, \end{align*} While the function $f(x,y)$ is a concave function, it's not accepted by CVX. Do you have any suggestions regarding that?

$\endgroup$
5
$\begingroup$

The disciplined convex rules used by CVX don't know how to deal with ratios or products of variables or functions of variables, so this can't be written directly in CVX. However, it can be written using $\mbox{rel_entr}$ in CVX. To see this,

$y \; \mbox{entr}(x/y)= -y (x/y) \log(x/y) = -x \log(x/y) = -\mbox{rel_entr}(x,y)$

where $\mbox{rel_entr}(x,y)=x \log (x/y)$ is known to CVX. Similarly, since

$1-\frac{x}{y}=\frac{y-x}{y}$, we have

$y \; \mbox{entr}(1-x/y)= -y \frac{y-x}{y} \log \left( \frac{y-x}{y} \right) = -\mbox{rel_entr}(y-x,y)$.

Thus your $f(x,y)$ is

$f(x,y)=-\mbox{rel_entr}(x,y)-\mbox{rel_entr}(y-x,y)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. It is very helpful. Just a small point. $f(x,y)$ is indeed concave. I think just a small modification is needed, since $entr(x)=-x\cdot \log(x)$. I think you missed the minus sign. The minus sign is needed for the rest of calculations also. Basically, in above relations, all rel_entr should be multiplied by minus 1. $\endgroup$ – Mini May 18 at 16:09
  • 1
    $\begingroup$ I've fixed the sign error. $\endgroup$ – Brian Borchers May 18 at 18:43

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.