Geometric Programming
Products of arbitrary powers look hopeless; substitute x = e^y and the whole problem turns convex.
The idea
A geometric program is an optimization problem built entirely from products of powers of positive variables. It is not convex as written, but a single change of variables converts it into a convex problem exactly, so it can be solved as reliably as if it were.
Definition (Geometric program).
A monomial is a product $c\,x_{1}^{a_{1}} \cdots x_{n}^{a_{n}}$ of positive variables, with a positive coefficient $c$ and arbitrary real exponents $a_{i}$; a posynomial is a sum of monomials. A geometric program minimizes a posynomial subject to posynomial constraints $f_{i}(x) \le 1$ and monomial equalities $h_{i}(x) = 1$.
The word monomial clashes with its meaning in algebra, where the exponents must be nonnegative integers and the coefficient may have any sign; here the exponents are unrestricted and the sign is not.
Expressions like $3x_{1}^{2}x_{2}^{-1/2}x_{3}$ fill engineering design problems, because physical laws produce products of powers: a volume, a resistance, a stress. Yet minimizing a sum of such terms is not a convex problem — even the single constraint $x_{1}x_{2} \le 1$ describes a set that is not convex.
Theorem.
Under the change of variables $x_{i} = e^{y_{i}}$, followed by taking the logarithm of the objective and of each constraint, every geometric program becomes a convex optimization problem in $y$, with the same feasible points and the same optimal value.
The transformation involves no approximation and no loss. Recognizing that a problem is a geometric program is therefore most of the work of solving it.
Ways to work on it
- Walkthrough. Monomials, posynomials, standard form, and the substitution that converts them.
- Proof. Why the log-transformed problem is convex — and why the original one is not.
- Practice. Classify expressions, reach standard form, and read off the convex form's exponents.
- Hardest. Solve a matrix-scaling problem end to end as a geometric program.
Not sure where to start? Take the ten-question placement test.