What is the correct change of variables to yield convexity in this nonlinear optimization problem?

Question

$$ \text{min. } x/y \\ \text{s.t. } 2\leq x \leq 3 \\ x^2+y/z\leq \sqrt{y} \\ x/y=z^2 \\ x,y,z\geq 0 $$

To transform this problem into a nonlinear convex optimization problem, both the objective function and constraints must be convex.

If we simply let $x/y=z^2$ in the objective function as given by the constraint, the objective function becomes convex.

Letting new variable $q=1/y$ gives $z^2-xq=0$ for the third constraint, which is convex (provable by definition & the inequality of arithmetic & geometric means).

However this gives the ugly $x^2+1/zq \leq 1/\sqrt{q}$ for the second constraint.

A different approach of substituting the third constraint, $x=yz^2$, into the second constraint, gives $zx^2+x/z^2\leq \sqrt{x}$, no closer to convexity.

Is there a different substitution involving $y$ that gives convex constraints 2 and 3?

Answer 1

You're in luck: this is a geometric program. Therefore, the change of variables $$x\rightarrow e^{u}, ~~ y\rightarrow e^{v}, ~~ z\rightarrow e^{w}$$ will get us close, and a few logarithms will get us the rest of the way there. Substitution yields \begin{array}{ll} \text{minimize} & e^{u-v} \\ \text{subject to} & 2 \leq e^u \leq 3 \\ & e^{2u} + e^{v-w} \leq e^{v/2} \\ & e^{u-v}=e^{2w} \end{array} Now let's take some logarithms: \begin{array}{ll} \text{minimize} & u-v \\ \text{subject to} & \log 2 \leq u \leq \log 3 \\ & \log \left( e^{2u} + e^{v-w} \right) \leq v/2 \\ & u-v=2w \end{array} And there you have it: a convex optimization problem. The "log-sum-exp" expression is indeed a smooth convex function; you'll have to take that on faith or prove it to yourself. Recovering $x,y,z$ once you have solved for $u,v,w$ just requires three exponentials.

Some notes:

1. We could skip a few of the logarithms and still have a convex problem: the objective, the $e^u\leq 3$ constraint, the nonlinear inequality. But in practice we keep those logarithms in there; the problems are better behaved numerically that way. (I have no theoretical support for this; someone else might, though). The other logarithms must be taken, however.

2. Strictly speaking, the convex version of this model is equivalent only if we assume strict positivity on $x,y,z$. Yes, you can handle the case of zero variables with more technical machinery; but fortunately we don't need that here. After all, $x\geq 2$ is guaranteed from the constraints; and $y$ cannot be zero unless the entire problem is infeasible, because of the $x/y$ objective. And therefore, from the $x/y=z^2$ constraint, we know that $z$ is nonzero as well.

3. If we wish we can eliminate $z$ and $w$ altogether, by taking advantage of the equality constraint, to yield

\begin{array}{lllll} \text{minimize} & x/y & & \text{minimize} & u-v \\ \text{subject to} & 2 \leq x \leq 3 & & \text{subject to} & \log 2 \leq u \leq \log 3 \\ & x^2 + y^{3/2} x^{-1/2} \leq y^{1/2} && & \log \left( e^{2u} + e^{(3v-u)/2} \right) \leq v/2 \\ \end{array}

4. I cannot emphasize the following enough, but I am going to try:

   Under no circumstances should one assume that a nonconvex problem can be made convex if only you can find the right change of variables.

   The title of this question suggests the author is making this assumption. Perhaps that's because this problem was assigned as a homework or test question, in which case it was known in advance by the question designer to be a geometric program. But geometric programs are the exception, not the rule. I'm unaware of any other general, non-manufactured class of nonconvex problems that can be made convex with just a change of variables.