10
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Looks like chapter 8 of your linked review paper tries to address my question. However, after a first cursory look over it, I get the impression that actually any convex program can be approximated by a geometric program (logarithmically transformed, of course...). However, as any linear program is "obviously" also a geometric program, this could also just be a variant of the statement that any convex program can be approximated by a linear program, but that wouldn't be what I mean by "approximated reasonably well". $\endgroup$ – Thomas Klimpel Feb 29 '12 at 8:33
  • $\begingroup$ When the term geometric programming arose, it wasn't easy to solve general convex programs, and the special structure could be exploited. Now, of course, once one recognizes that a program is geometric, one transforms it into a convex program and solves the latter by interior point methods. $\endgroup$ – Arnold Neumaier Jun 22 '12 at 19:55
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Geometric programming isn't a strict subset of convex programming; however, under the log-exponential transformation, transformed geometric programs are convex programs. $\endgroup$ – Geoff Oxberry Feb 28 '12 at 21:39
  • $\begingroup$ Yeah, that's what I meant to say. Edited answer for clarity. $\endgroup$ – Opt Feb 28 '12 at 21:46

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.