How is geometric programming different from convex programming?

Question

How is (generalized) geometric programming different from general convex programming?

A geometric program can be transformed into a convex program, and is typically solved by an interior point method. But what is the advantage over directly formulating the problem as a convex program and solving it by an interior point method?

Does the class of geometric programs only constitutes a subset of the class of convex programs that can be solved especially efficient by interior point methods? Or is the advantage simply that a general geometric program can easily be specified in computer readable form.

On the other hand, are there convex programs that cannot be approximated reasonably well by geometric programs?

Answer 1

I'd actually never heard of geometric programming until this question. Here is a review paper by Stephen Boyd, et al (Vandenberghe is a co-author too) that is a tutorial on geometric programming.

Geometric programs as originally expressed are not convex. For instance, $x^{1/2}$ is a posynomial, and it is not convex, so geometric programs aren't a strict subset of convex programming.

The advantage of transforming a geometric program into a convex program is that the original geometric program is not necessarily convex. If you solved the geometric program as a nonlinear program (NLP), you would need to use methods from non-convex optimization in order to guarantee a global optimal solution. These methods are more expensive than convex optimization methods, require more algorithmic tuning, and require initial guesses.

Moreover, if you use an algorithm from non-convex NLP, you would need to specify your feasible set as a compact set in $\mathbb{R}^{n}$; in geometric programs, $x > 0$ is a valid constraint.

It's not clear if the set of geometric programs maps (through the log-exponential transformation) to a set of convex programs that solves particularly efficiently. I don't see any advantages to geometric programming beyond the transformation to convex programs.

As for your last question, I don't think the set of geometric programs is isomorphic to the set of convex programs, so I suspect that there are convex programs that cannot be expressed as geometric programs, and of these programs, I suspect that there are some that can't be approximated reasonably well by geometric programs. However, I don't have a proof or a counterexample.

Answer 2

Geometric programming can be transformed into a class of convex programs which is a strict subset of the set of all convex programs. However arbitrary convex programs cannot be expressed as geometric programs. The constraints in Geometric Programming are restricted to be of the form $f(x) \leq 1$ where $f(x)$ is a posynomial (i.e. a polynomial with positive coefficients). Posynomials are closed under addition, multiplication and positive scaling. Now if you consider the constraint $-x-y \leq 1$, then $-x-y$ is not itself a posynomial. It cannot be represented as the addition/multiplication of posynomials and it cannot be a positive scaling of another posynomial. Thus it cannot be part of a geometric program. But the constraint above is linear and thus the program is convex. There does exist mixed linear geometric programming in which one can add in arbitrary linear constraints though which can be also converted into a convex program and solved efficiently. Again more complicated constraints like $-x^2-y^2\leq 1$ cannot be handled even by mixed linear geometric programming for the same reason as given above.