44.05.03 · optimization-control / 05-conic-semidefinite

Geometric Programming

shipped3 tiersLean: none

Anchor (Master): Boyd, Kim, Vandenberghe & Hassibi 2007 A Tutorial on Geometric Programming (Optimization and Engineering 8(1)) §4-§9; Duffin, Peterson & Zener 1967 Geometric Programming (Wiley) Ch. 1-3; Chiang 2005 Geometric Programming for Communication Systems (now Publishers) §1-§3

Intuition Beginner

Many engineering quantities multiply rather than add. The power a chip burns scales with the product of its width, its voltage squared, and its switching rate; the volume of a box is length times width times height; signal strength falls off as a product of gains and distances raised to powers. When the things you can tune enter as products of powers, ordinary linear thinking does not fit. Geometric programming is the optimization method built exactly for this multiply-and-power world.

The two building blocks have plain meanings. A monomial here is a single product term: a positive number times each variable raised to some power, like $3 x^{2} y^{- 1}$ . A posynomial is a sum of such terms, all with positive coefficients, like $3 x^{2} y^{- 1} + 5 x y$ . Posynomials are the natural language for costs, areas, powers, and delays that pile up from several multiplicative effects. A geometric program asks you to make one posynomial as small as possible while keeping other posynomials below their budgets.

Why is this special? Because of one magic trick. If you stop working with the variables themselves and instead work with their logarithms, every one of these multiply-and-power expressions straightens out. Products turn into sums, powers turn into multipliers, and the whole tangled problem becomes a bowl-shaped one — the kind with a single global lowest point and no hidden traps. So a problem that looked hopelessly nonlinear is secretly one of the friendly problems we can always solve.

That is the appeal of geometric programming: a large, practical family of design problems that look forbidding in their raw form but become reliably solvable the moment you take logarithms.

Visual Beginner

Figure: two panels showing the same problem before and after taking logarithms. On the left, in the original variables, the feasible region is a curved, lopsided patch bounded by hyperbola-like curves, and the cost contours are warped — it looks nonlinear and forbidding. On the right, after the substitution "new variable = log of old variable," the same region becomes a clean convex shape with straight-ish smooth boundaries and nested bowl-shaped cost contours, with a single distinctly marked lowest point.

   ORIGINAL VARIABLES x, y            LOG VARIABLES  u = log x, v = log y

   y |   curved, warped              v |    convex region,
     |   feasible patch                |    smooth bowl contours
     |    __                           |      .-''''-.
     |   /  \___  cost                 |     /  (min) \
     |  | curves |  (hard to read)     |    |    *     |
     |   \______/                      |     \        /
     +-------------- x                 +------'-....-'------- u
     multiply-and-power:               take logs:
     products and powers               products -> sums,
     everywhere                        powers -> multipliers

         "looks nonlinear"      ==>     "is secretly convex"

Worked example Beginner

We design a rectangular open-top storage box of cheapest material, a classic geometric program small enough to do by hand. Let the base be $x$ by $y$ and the height be $z$ , all positive lengths in meters. The box must hold at least one cubic meter: $x y z \geq 1$ . The material cost counts the base and the four sides: cost $= x y + 2 x z + 2 y z$ (the base area plus the two pairs of opposite walls). We want the cost as small as possible.

Step 1. Read off the pieces. The cost $x y + 2 x z + 2 y z$ is a sum of three positive product terms, so it is a posynomial. The volume rule $x y z \geq 1$ rearranges to $x^{- 1} y^{- 1} z^{- 1} \leq 1$ , also a posynomial budget. This is a geometric program.

Step 2. Use symmetry to guess. The two side-wall terms treat $x$ and $y$ the same way, so try a square base $x = y$ . The volume rule at the boundary gives $x^{2} z = 1$ , so $z = 1/ x^{2}$ .

Step 3. Reduce to one variable. Substituting, the cost becomes $x^{2} + 2 x \cdot (1/ x^{2}) + 2 x \cdot (1/ x^{2}) = x^{2} + 4/ x$ .

Step 4. Find the lowest point. As $x$ grows the $x^{2}$ term climbs; as $x$ shrinks the $4/ x$ term blows up, so a single best $x$ sits in between. Testing values: at $x = 1$ the cost is $1 + 4 = 5$ ; at $x = 1.25$ it is $1.5625 + 3.2 = 4.7625$ ; at $x = 1.26$ it is about $1.588 + 3.175 = 4.763$ . The minimum is near $x = 1.26$ with cost about $4.76$ .

What this tells us. The cheapest box has a square base of side about $1.26$ m and height $z = 1/ x^{2} \approx 0.63$ m. A multiply-and-power design problem that looked nonlinear had one clean best answer, and posynomials were the exact language to write it down.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, the optimization variable is $x = (x_{1}, \dots, x_{n})$ with each $x_{i} > 0$ ; the domain is the positive orthant $R_{++}^{n}$ .

Definition (monomial). A monomial is a function $f : R_{++}^{n} \to R_{++}$ of the form

f (x) = c x_{1}^{a_{1}} x_{2}^{a_{2}} \dots x_{n}^{a_{n}}, c > 0, a_{i} \in R .

The coefficient $c$ is positive but the exponents $a_{i}$ may be any real numbers (negative, fractional). This is the geometric-programming sense of "monomial" and differs from the algebraic sense (no nonnegative-integer-exponent restriction, single term, positive coefficient).

Definition (posynomial). A posynomial is a finite sum of monomials,

p (x) = k = 1 \sum K c_{k} x_{1}^{a_{1 k}} x_{2}^{a_{2 k}} \dots x_{n}^{a_{nk}}, c_{k} > 0, a_{ik} \in R .

Posynomials are closed under addition, multiplication, positive scaling, and raising to a nonnegative power; a monomial is the special case $K = 1$ , and the ratio of a posynomial by a monomial is again a posynomial.

Definition (geometric program in standard form). A geometric program (GP) is the optimization problem

minimize subject to p_{0} (x) p_{i} (x) \leq 1, i = 1, \dots, m, g_{j} (x) = 1, j = 1, \dots, r,

where $p_{0}, p_{1}, \dots, p_{m}$ are posynomials, $g_{1}, \dots, g_{r}$ are monomials, and the variable ranges over $x \in R_{++}^{n}$ ^{[Boyd & Vandenberghe §4.5]}. Inequality constraints use posynomials bounded above by $1$ , equality constraints use monomials equal to $1$ . A constraint $p (x) \leq b$ with $b > 0$ is brought to standard form by dividing through, $p (x) / b \leq 1$ ; a constraint $m_{1} (x) \leq m_{2} (x)$ between monomials becomes $m_{1} (x) / m_{2} (x) \leq 1$ .

Definition (the log-log change of variables). Substitute $y_{i} = lo g x_{i}$ , so $x_{i} = e^{y_{i}}$ , and replace each posynomial by the logarithm of its value. A monomial $c \prod_{i} x_{i}^{a_{i}}$ becomes

lo g (c i \prod e^{a_{i} y_{i}}) = a^{⊤} y + lo g c,

an affine function of $y$ . A posynomial $p (x) = \sum_{k} c_{k} \prod_{i} x_{i}^{a_{ik}}$ becomes

\tilde{p} (y) = lo g k = 1 \sum K e^{a_{k}^{⊤} y + b_{k}}, a_{k} = (a_{1 k}, \dots, a_{nk}), b_{k} = lo g c_{k},

a log-sum-exp of affine functions, which is convex by the convexity of log-sum-exp (44.01.01) composed with affine maps.

Definition (convex form of a GP). Applying the substitution and taking logarithms throughout, the GP becomes

minimize subject to \tilde{p}_{0} (y) = lo g \sum_{k} e^{a_{0 k}^{⊤} y + b_{0 k}} \tilde{p}_{i} (y) = lo g \sum_{k} e^{a_{ik}^{⊤} y + b_{ik}} \leq 0, i = 1, \dots, m, \tilde{g}_{j} (y) = g_{j}^{⊤} y + h_{j} = 0, j = 1, \dots, r .

This is a convex optimization problem: the objective and inequality functions are convex (log-sum-exp of affine), and the equality constraints are affine. Solving the original GP is equivalent to solving this convex program, after which $x_{i} = e^{y_{i}}$ recovers the design.

Counterexamples to common slips

A single negative coefficient breaks the posynomial structure. $x^{2} - 3 x y + y^{2}$ is not a posynomial; the $- 3 x y$ term has a negative coefficient. Such expressions are signomials, and the log-log trick does not convexify them — log-sum-exp requires every coefficient positive.
Equality of two posynomials is not a GP constraint. A constraint $p (x) = 1$ with $p$ a genuine ( $K \geq 2$ ) posynomial is generally nonconvex after the substitution, because $lo g \sum_{k} e^{(\cdot)} = 0$ is not an affine equality. Only monomial equalities ( $K = 1$ ) stay affine in $y$ ; posynomial equalities must be relaxed or restructured.
Maximizing a posynomial is not a GP. GP minimizes a posynomial. Maximizing a posynomial, or minimizing $1/ p$ for a posynomial $p$ , makes the objective concave-after-substitution and is outside the class.

Key theorem with proof Intermediate+

The organizing result is that the log-log substitution converts every geometric program into an equivalent convex program, so the global solvability of GP rests entirely on the convexity of log-sum-exp from 44.01.01.

Theorem (GP convexification). Let a GP be given in standard form with posynomial objective and constraints $p_{0}, \dots, p_{m}$ and monomial equalities $g_{1}, \dots, g_{r}$ , feasible over $x \in R_{++}^{n}$ . Under the bijection $y_{i} = lo g x_{i}$ between $R_{++}^{n}$ and $R^{n}$ , the transformed problem with objective $\tilde{p}_{0} (y) = lo g \sum_{k} e^{a_{0 k}^{⊤} y + b_{0 k}}$ , inequality constraints $\tilde{p}_{i} (y) \leq 0$ , and affine equality constraints $\tilde{g}_{j} (y) = 0$ is a convex optimization problem, and $x^{⋆}$ solves the GP if and only if $y^{⋆} = lo g x^{⋆}$ (componentwise) solves the convex problem, with equal optimal values up to the monotone map $lo g p_{0}^{⋆} = \tilde{p}_{0} (y^{⋆})$ .

Proof. The map $Φ : R_{++}^{n} \to R^{n}$ , $Φ (x)_{i} = lo g x_{i}$ , is a bijection with inverse $Φ^{- 1} (y)_{i} = e^{y_{i}}$ , both continuous and strictly monotone in each coordinate. Feasibility is preserved exactly: a monomial constraint $g_{j} (x) = 1$ holds iff $lo g g_{j} (x) = 0$ iff $g_{j}^{⊤} y + h_{j} = 0$ (an affine equality), and a posynomial constraint $p_{i} (x) \leq 1$ holds iff $lo g p_{i} (x) \leq lo g 1 = 0$ iff $\tilde{p}_{i} (y) \leq 0$ , using that $lo g$ is strictly increasing on $R_{++}$ so the inequality direction is retained.

For convexity, fix any posynomial $p (x) = \sum_{k = 1}^{K} c_{k} \prod_{i} x_{i}^{a_{ik}}$ with $c_{k} > 0$ . After substitution each term is $c_{k} \prod_{i} e^{a_{ik} y_{i}} = e^{a_{k}^{⊤} y + b_{k}}$ with $b_{k} = lo g c_{k}$ , so

\tilde{p} (y) = lo g p (e^{y_{1}}, \dots, e^{y_{n}}) = lo g k = 1 \sum K e^{a_{k}^{⊤} y + b_{k}} .

The log-sum-exp function $ℓ (z) = lo g \sum_{k} e^{z_{k}}$ is convex on $R^{K}$ (44.01.01, where its Hessian $\frac{1}{Z} diag (z) - \frac{1}{Z ^{2}} z z^{⊤}$ with $z_{k} = e^{z_{k}}$ , $Z = \sum_{k} z_{k}$ was shown positive semidefinite by Cauchy-Schwarz). Each argument $z_{k} = a_{k}^{⊤} y + b_{k}$ is affine in $y$ , so $\tilde{p} = ℓ \circ A$ for the affine map $A : y \mapsto (a_{1}^{⊤} y + b_{1}, \dots, a_{K}^{⊤} y + b_{K})$ . Composition of a convex function with an affine map is convex (the operation calculus of 44.01.01), so $\tilde{p}$ is convex. Applying this to $p_{0}$ gives a convex objective and to each $p_{i}$ a convex inequality function with the sublevel constraint $\tilde{p}_{i} (y) \leq 0$ defining a convex feasible set; the $\tilde{g}_{j} (y) = 0$ are affine. The transformed problem therefore minimizes a convex function over a convex set, which is a convex program.

Equivalence of solutions follows because $Φ$ is a feasibility-preserving bijection and $lo g$ is strictly increasing: minimizing $p_{0} (x)$ over the GP-feasible set is the same as minimizing $lo g p_{0} (x) = \tilde{p}_{0} (Φ (x))$ , so $x^{⋆}$ is a minimizer iff $y^{⋆} = Φ (x^{⋆})$ minimizes $\tilde{p}_{0}$ over the transformed feasible set, with $lo g p_{0}^{⋆} = \tilde{p}_{0} (y^{⋆})$ . $□$

Bridge. This theorem builds toward the interior-point solvers of 44.05.04 and appears again in every practical use of GP, from circuit sizing to power control. This is exactly the convexity of log-sum-exp from 44.01.01 doing all the work: the multiply-and-power structure of posynomials is the precise structure that the logarithm linearizes, and the only nonlinearity left, the sum inside the log, is the one function 44.01.01 already certified convex. The foundational reason GP is a tractable modeling class while general signomial programming is not is visible here — the proof needs every coefficient $c_{k}$ positive so that $b_{k} = lo g c_{k}$ is real and the expression is a genuine log-sum-exp; a single negative coefficient destroys this and the convexity with it. Putting these together, GP generalises the linear program in the log domain (a GP whose every posynomial is a single monomial becomes an LP in $y$ , since each $\tilde{p}_{i}$ is then affine), and the convex form is dual to the original posynomial form through the bijection $x \leftrightarrow e^{y}$ ; the convexified GP is precisely the problem class that the self-concordant-barrier machinery of 44.05.04 solves to global optimality in polynomial time.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Show that a GP in which every posynomial (objective and constraints) is in fact a single monomial reduces, after the log substitution, to a linear program.

Hint

A monomial becomes an affine function of $y$ ; what kind of problem has an affine objective and affine constraints?

Answer

A monomial $c \prod_{i} x_{i}^{a_{i}}$ becomes $a^{⊤} y + lo g c$ , affine in $y$ . If the objective and every constraint function is a single monomial, then $\tilde{p}_{0} (y)$ is affine, each inequality $\tilde{p}_{i} (y) \leq 0$ is an affine inequality, and each equality $\tilde{g}_{j} (y) = 0$ is an affine equality. Minimizing an affine objective over affine inequalities and equalities is a linear program (44.05.01). So monomial GPs are exactly LPs in the log domain, which is why GP is sometimes described as "LP with curved (posynomial) terms allowed."

Exercise 5 (medium, symbolic).

A wireless link has signal-to-interference ratio $SIR = \frac{G _{11} P _{1}}{σ + G _{12} P _{2}}$ , where powers $P_{1}, P_{2} > 0$ are the variables and the $G$ 's and $σ$ are positive constants. Show that requiring $SIR \geq γ$ for a target $γ > 0$ is a posynomial constraint in GP standard form.

Hint

Cross-multiply and divide so the constraint reads (posynomial) $\leq 1$ . Note $1/ P_{1}$ is a monomial.

Answer

$SIR \geq γ$ means $G_{11} P_{1} \geq γ (σ + G_{12} P_{2})$ , i.e. $γ σ + γ G_{12} P_{2} \leq G_{11} P_{1}$ . Dividing by $G_{11} P_{1}$ gives

\frac{γ σ}{G _{11}} P_{1}^{- 1} + \frac{γ G _{12}}{G _{11}} P_{2} P_{1}^{- 1} \leq 1.

The left side is a sum of two positive-coefficient power-product terms in $P_{1}, P_{2}$ , hence a posynomial, and the constraint is in standard $\leq 1$ form. This is the basic reason power control in interference-limited networks is a geometric program ^{[Chiang 2005 §2]}.

Exercise 6 (hard, symbolic).

Prove that a generalized posynomial — built from variables and posynomials by addition, multiplication, positive powers, and the $max$ of posynomials — becomes a convex function of $y = lo g x$ . (You may use that a $max$ of convex functions is convex.)

Hint

Induct on the construction. Each operation must be shown to preserve convexity after the substitution.

Answer

A plain posynomial becomes a convex log-sum-exp by the Key theorem. Proceed by structural induction on the generalized-posynomial expression tree, tracking the transformed function $\tilde{f} (y) = lo g f (e^{y})$ . Sum and product: if $f, g$ become convex $\tilde{f}, \tilde{g}$ , then $f g$ gives $f g = \tilde{f} + \tilde{g}$ (convex), and $f + g$ gives $lo g (e^{\tilde{f}} + e^{\tilde{g}})$ , a log-sum-exp of the convex $\tilde{f}, \tilde{g}$ , convex because log-sum-exp is convex and nondecreasing in each argument composed with convex arguments (44.01.01 composition rule). Positive power: $f^{r}$ for $r > 0$ gives $r \tilde{f}$ , convex. Maximum: $max (f, g)$ gives $max (\tilde{f}, \tilde{g})$ after the increasing $lo g$ , and a pointwise maximum of convex functions is convex. Every construction step preserves convexity, so the transformed generalized posynomial is convex; this is what makes generalized geometric programming still convex and solvable.

Exercise 7 (hard, symbolic).

Condensation. Given a posynomial $p (x) = \sum_{k = 1}^{K} u_{k} (x)$ (each $u_{k}$ a monomial) and any weights $θ_{k} > 0$ with $\sum_{k} θ_{k} = 1$ , prove the monomial lower bound

p (x) \geq k = 1 \prod K (\frac{u _{k} ( x )}{θ _{k}})^{θ_{k}},

and explain why the right side is a monomial. This is the arithmetic-geometric-mean step used to approximate a posynomial by a monomial in signomial programming.

Hint

Apply the weighted AM-GM inequality $\sum_{k} θ_{k} t_{k} \geq \prod_{k} t_{k}^{θ_{k}}$ to $t_{k} = u_{k} (x) / θ_{k}$ .

Answer

By the weighted arithmetic-geometric-mean inequality, for positive $t_{k}$ and weights $θ_{k} > 0$ summing to $1$ , $\sum_{k} θ_{k} t_{k} \geq \prod_{k} t_{k}^{θ_{k}}$ . Set $t_{k} = u_{k} (x) / θ_{k}$ ; then $\sum_{k} θ_{k} t_{k} = \sum_{k} u_{k} (x) = p (x)$ , giving $p (x) \geq \prod_{k} (u_{k} (x) / θ_{k})^{θ_{k}}$ . The right side is a product of monomials each raised to a positive power $θ_{k}$ , hence a monomial (closure under products and positive powers, Exercise 1). Choosing $θ_{k} = u_{k} (x_{0}) / p (x_{0})$ at a point $x_{0}$ makes the bound tight at $x_{0}$ , so a posynomial can be locally replaced by a tight monomial under-estimate; iterating this condensation turns a signomial program into a sequence of GPs, the standard heuristic for the nonconvex signomial case ^{[Boyd, Kim, Vandenberghe & Hassibi 2007 §9]}.

Exercise 8 (hard, symbolic).

Explain why a constraint of the form $p (x) / q (x) \leq 1$ , with $p$ a posynomial and $q$ a posynomial (not a monomial), is generally not a GP constraint, but becomes one if $q$ is a monomial. What goes wrong, and how does this motivate signomial programming?

Hint

A posynomial divided by a monomial is a posynomial; a posynomial divided by a posynomial is not.

Answer

If $q$ is a monomial, $p / q$ is a sum of (monomial) $/$ (monomial) terms, each a monomial (Exercise 1), so $p / q$ is a posynomial and $p / q \leq 1$ is a standard GP constraint. If $q$ is a genuine posynomial ( $\geq 2$ terms), $p / q$ is a ratio of posynomials, which is not in general a posynomial: clearing denominators gives $p (x) \leq q (x)$ , i.e. $p (x) - q (x) \leq 0$ , and $p - q$ has terms of both signs — a signomial, not a posynomial. The log substitution then yields $lo g \sum e^{(\cdot)} - lo g \sum e^{(\cdot)}$ , a difference of convex functions, which is generally nonconvex. This is exactly the boundary of the GP class: ratio-of-posynomial constraints push a model into signomial programming, handled by the condensation heuristic of Exercise 7 rather than by a single convex solve.

Advanced results Master

The GP dual and the degree of difficulty

Geometric programming was born with a dual, predating the convex-analytic viewpoint. For the unconstrained primal $min_{x} \sum_{k = 1}^{K} c_{k} \prod_{i} x_{i}^{a_{ik}}$ , the GP dual is the maximization, over dual weights $δ = (δ_{1}, \dots, δ_{K})$ , of the product form

δ max k = 1 \prod K (\frac{c _{k}}{δ _{k}})^{δ_{k}} s.t. δ_{k} \geq 0, k \sum δ_{k} = 1 (normality), k \sum δ_{k} a_{ik} = 0 \forall i (orthogonality),

derived directly from the arithmetic-geometric-mean inequality ^{[Duffin, Peterson & Zener 1967 Ch. 3]}. Weak duality is the AM-GM bound of Exercise 7; strong duality holds under the primal-feasibility (Slater) hypothesis. The constrained case attaches one block of weights per posynomial and an extra normalization per constraint. The degree of difficulty is $K - (n + 1)$ , the number of dual variables minus the number of normalization-plus-orthogonality equations; when it is zero the orthogonality system pins $δ$ uniquely and the GP is solved in closed form by linear algebra, with the optimal primal recovered from the monomial-term ratios $δ_{k} = u_{k} (x^{⋆}) / p_{0} (x^{⋆})$ . This dual is the modern conic dual of 44.05.01 read through the exponential cone, but its closed-form low-degree-of-difficulty cases remain the reason GP duality is taught on its own terms.

Generalized geometric programming and the modeling reach of the class

The convexity-after-logarithm property survives a substantial enlargement of the syntax. Generalized posynomials are formed from ordinary posynomials by addition, multiplication, positive powers, maximum, and composition with posynomials of posynomials; Exercise 6 shows each becomes convex in $y$ . Generalized geometric programming minimizes a generalized posynomial subject to generalized-posynomial $\leq 1$ constraints, and remains a convex problem after the substitution, hence globally solvable ^{[Boyd, Kim, Vandenberghe & Hassibi 2007 §8]}. The practical payoff is that maxima of posynomials (worst-case delays, worst-case power), fractional powers (norms, RMS quantities), and nested posynomial-of-posynomial expressions all stay inside the tractable class. Modeling tools exploit this by certifying a model as a generalized GP through a parse-tree check identical in spirit to the disciplined-convex-programming ruleset of 44.01.01, so a designer writes the multiply-and-power model directly and the convexification is automatic.

Signomial programming, condensation, and the loss of convexity

A signomial is a sum of monomial terms with coefficients of either sign, and a signomial program allows signomial objective and constraints. The class is genuinely larger and genuinely harder: after the log substitution a signomial constraint becomes a difference of log-sum-exp functions, a difference-of-convex constraint, and the problem is in general nonconvex and NP-hard. The dominant heuristic is condensation (Exercise 7): at the current iterate, replace each posynomial appearing in a denominator or on the larger side of a signomial inequality by its tight monomial AM-GM under-estimate, producing a GP whose solution becomes the next iterate. This is a convex-concave / inner-approximation scheme; each GP solve is a global step on a tightened convex surrogate, and the iteration converges to a point satisfying the KKT conditions of the signomial program though not necessarily its global optimum ^{[Boyd, Kim, Vandenberghe & Hassibi 2007 §9]}. The contrast with the GP case is the central structural fact of the subject: positive coefficients buy global solvability, mixed signs cost it.

Applications: where multiply-and-power structure is native

The reach of GP is widest precisely where physical and economic quantities combine multiplicatively. In analog and digital circuit design, transistor delays, areas, and power are monomials in device widths and lengths, so gate and op-amp sizing is a GP solved to global optimality over hundreds of devices ^{[Hershenson, Boyd & Lee 2001]}. In wireless power control, signal-to-interference constraints are posynomial (Exercise 5) and network utility maximization is a GP or, with rate-dependent interference, a signomial program attacked by condensation ^{[Chiang 2005]}. Other native domains include chemical-equilibrium and process design (the original Zener applications), structural and mechanical sizing under stress and deflection limits, information-theoretic and queueing performance bounds, and statistical maximum-likelihood for log-concave models. The common thread is that the design law arrives as products of powers, the form for which GP is not an approximation but the exact convex reformulation.

Synthesis. Geometric programming is exactly the convex optimization hiding behind multiply-and-power design laws: the log-log substitution maps posynomials to log-sum-exp of affine functions, and the central insight is that one convexity fact from 44.01.01 — that log-sum-exp is convex — globalizes the entire class. The foundational reason GP is a distinct and durable modeling category, rather than a footnote to general convex programming, is its closure algebra: monomials and posynomials are closed under the operations designers actually use, so a parse-tree check certifies convexity without a Hessian, and the convexified program feeds the self-concordant-barrier interior-point machinery of 44.05.04 that solves it at scale. Putting these together, the GP dual generalises the AM-GM inequality into a duality theory whose zero-degree-of-difficulty cases close in algebra, and it is dual to the conic exponential-cone formulation of 44.05.01, the two viewpoints meeting at the same optimum. This is exactly where the boundary of tractability sits: positive coefficients keep the transformed problem convex, while a single negative coefficient drops the model into signomial programming, where condensation replaces global solvability with a sequence of GP surrogates; the bridge is the logarithm, the one map through which posynomial algebra, log-sum-exp convexity, the AM-GM dual, and the interior-point solvers of 44.05.04 become a single story, and it appears again in circuit sizing, power control, and every engineering design whose governing law is a product of powers.

Full proof set Master

Proposition 1 (posynomials form a convex cone under the log substitution). For a fixed exponent structure, the set of functions ${\tilde{p} (y) = lo g \sum_{k} e^{a_{k}^{⊤} y + b_{k}}}$ obtained from posynomials is closed under the log-domain image of posynomial addition and positive scaling, and each such $\tilde{p}$ is convex.

Proof. Convexity of each $\tilde{p}$ is the Key theorem: $\tilde{p} = ℓ \circ A$ with $ℓ$ the convex log-sum-exp and $A$ affine. For the algebra, if $p = \sum_{k} u_{k}$ and $q = \sum_{j} w_{j}$ are posynomials then $p + q$ is the posynomial with the concatenated term list, and its log-domain image is $lo g (\sum_{k} e^{a_{k}^{⊤} y + b_{k}} + \sum_{j} e^{c_{j}^{⊤} y + d_{j}})$ , a log-sum-exp over the union of terms; positive scaling $α p$ ( $α > 0$ ) shifts each $b_{k}$ by $lo g α$ . Both stay log-sum-exp of affine functions, hence convex. Multiplication $pq = \sum_{k, j} u_{k} w_{j}$ is again a posynomial (its log-domain image is the log-sum-exp over the product terms with exponents $a_{k} + c_{j}$ ), so the posynomial set is closed under addition, positive scaling, and multiplication, and the log substitution carries each into the convex cone of log-sum-exp functions. $□$

Proposition 2 (GP weak duality via AM-GM). For the unconstrained primal $p_{0} (x) = \sum_{k = 1}^{K} c_{k} \prod_{i} x_{i}^{a_{ik}}$ and any dual-feasible $δ$ (i.e. $δ_{k} \geq 0$ , $\sum_{k} δ_{k} = 1$ , $\sum_{k} δ_{k} a_{ik} = 0$ for all $i$ ), the dual objective lower-bounds the primal optimum: $\prod_{k} (c_{k} / δ_{k})^{δ_{k}} \leq p_{0} (x)$ for every $x \in R_{++}^{n}$ .

Proof. Apply the weighted AM-GM inequality $\sum_{k} δ_{k} t_{k} \geq \prod_{k} t_{k}^{δ_{k}}$ (weights $δ_{k} \geq 0$ summing to $1$ ) to $t_{k} = u_{k} (x) / δ_{k}$ , where $u_{k} (x) = c_{k} \prod_{i} x_{i}^{a_{ik}}$ is the $k$ -th monomial term. The left side is $\sum_{k} δ_{k} \cdot u_{k} (x) / δ_{k} = \sum_{k} u_{k} (x) = p_{0} (x)$ . The right side is

k \prod (\frac{u _{k} ( x )}{δ _{k}})^{δ_{k}} = k \prod (\frac{c _{k}}{δ _{k}})^{δ_{k}} k \prod (\prod_{i} x_{i}^{a_{ik}})^{δ_{k}} = \prod_{k} (\frac{c _{k}}{δ _{k}})^{δ_{k}} \prod_{i} x_{i}^{\sum_{k} δ_{k} a_{ik}} .

The orthogonality conditions $\sum_{k} δ_{k} a_{ik} = 0$ make every $x_{i}$ exponent vanish, so $\prod_{i} x_{i}^{0} = 1$ and the right side equals $\prod_{k} (c_{k} / δ_{k})^{δ_{k}}$ , independent of $x$ . Therefore $\prod_{k} (c_{k} / δ_{k})^{δ_{k}} \leq p_{0} (x)$ for all feasible $x$ , which is GP weak duality. $□$

Proposition 3 (zero degree of difficulty gives a closed-form solution). If the unconstrained GP has $K = n + 1$ terms and the orthogonality-plus-normality system $\sum_{k} δ_{k} a_{ik} = 0 (i = 1, \dots, n), \sum_{k} δ_{k} = 1$ has a unique nonnegative solution $δ^{⋆}$ , then the primal optimum equals $\prod_{k} (c_{k} / δ_{k}^{⋆})^{δ_{k}^{⋆}}$ and is attained.

Proof. The system is $n + 1$ linear equations in the $K = n + 1$ unknowns $δ_{k}$ ; uniqueness of the nonnegative solution $δ^{⋆}$ makes the dual feasible set a single point, so the dual maximization is the evaluation $\prod_{k} (c_{k} / δ_{k}^{⋆})^{δ_{k}^{⋆}}$ . By Proposition 2 this value lower-bounds the primal for every $x$ . AM-GM holds with equality iff all the $t_{k} = u_{k} (x) / δ_{k}^{⋆}$ are equal, i.e. $u_{k} (x) / δ_{k}^{⋆} = u_{j} (x) / δ_{j}^{⋆}$ for all $k, j$ . These ratio conditions are monomial equalities in $x$ ; taking logarithms gives a linear system in $y = lo g x$ that is solvable because the exponent matrix has full row rank (its kernel is the one-dimensional normality direction already fixed). The resulting $x^{⋆}$ attains $p_{0} (x^{⋆}) = \prod_{k} (c_{k} / δ_{k}^{⋆})^{δ_{k}^{⋆}}$ , so the bound is met and is the optimum. $□$

Proposition 4 (condensation produces a monomial under-estimate tight at the chosen point). Let $p (x) = \sum_{k = 1}^{K} u_{k} (x)$ be a posynomial and $x_{0} \in R_{++}^{n}$ . With weights $θ_{k} = u_{k} (x_{0}) / p (x_{0})$ , the monomial $\overset{p}{^} (x) = \prod_{k} (u_{k} (x) / θ_{k})^{θ_{k}}$ satisfies $\overset{p}{^} (x) \leq p (x)$ for all $x$ , with equality at $x = x_{0}$ , and $\nabla \overset{p}{^} (x_{0}) = \nabla p (x_{0})$ .

Proof. The inequality $\overset{p}{^} \leq p$ is Proposition 2 / Exercise 7 with this weight choice. Equality at $x_{0}$ : the AM-GM equality condition requires all $u_{k} (x_{0}) / θ_{k}$ equal, and $u_{k} (x_{0}) / θ_{k} = u_{k} (x_{0}) \cdot p (x_{0}) / u_{k} (x_{0}) = p (x_{0})$ for every $k$ , a common value, so the bound is tight and $\overset{p}{^} (x_{0}) = \prod_{k} p (x_{0})^{θ_{k}} = p (x_{0})^{\sum_{k} θ_{k}} = p (x_{0})$ . For the gradient match, work in the log domain where $lo g p (y) = \sum_{k} θ_{k} lo g u_{k} = \sum_{k} θ_{k} (a_{k}^{⊤} y + b_{k})$ is the affine first-order term of $\tilde{p} (y) = lo g \sum_{k} e^{a_{k}^{⊤} y + b_{k}}$ at $y_{0} = lo g x_{0}$ : indeed $\partial_{i} \tilde{p} (y_{0}) = \sum_{k} \frac{e ^{a_{k}^{⊤} y_{0} + b_{k}}}{\sum _{j} e ^{a_{j}^{⊤} y_{0} + b_{j}}} a_{ik} = \sum_{k} θ_{k} a_{ik}$ , matching the gradient of the condensed affine form. Equal value and equal log-domain gradient at $x_{0}$ give $\nabla \overset{p}{^} (x_{0}) = \nabla p (x_{0})$ , so condensation is a tight, first-order-accurate monomial under-estimate — the property that makes the condensation iteration a convergent inner-approximation method. $□$

Connections Master

The convex-modeling unit 44.01.01 is the direct parent: the entire tractability of geometric programming is the convexity of the log-sum-exp function proved there, applied after the bijection $x_{i} = e^{y_{i}}$ . Posynomial addition becomes log-sum-exp, monomials become affine maps, and the convexity-preserving operation calculus of 44.01.01 is what certifies the convex form of a GP and of every generalized GP without computing a Hessian.
Conic optimization 44.05.01 situates GP in the broader convex-programming landscape: the convexified GP is representable over the exponential cone, so GP joins LP, SOCP, and SDP as a named convex modeling class, and the GP dual is the conic dual of 44.05.01 read through that cone. A monomial GP collapses to an LP in the log domain, exhibiting the LP $\subset$ GP-in-log-form inclusion alongside the conic ladder of that unit.
Interior-point methods 44.05.04 are how GP is actually solved: once convexified, a GP is a smooth convex problem with log-sum-exp objective and constraints, and the self-concordant-barrier primal-dual path-following machinery of 44.05.04 returns the global optimum in polynomial time, which is the reason GP scales to circuit-sizing problems with thousands of devices.
The signomial extension links GP to the difference-of-convex and sequential-convex-programming circle: a signomial program is a difference-of-log-sum-exp problem solved by condensation, an inner-approximation scheme that produces a sequence of GPs and converges to a KKT point, connecting GP to the constraint-qualification and KKT theory consumed throughout the optimization-control section 44.05.01.

Historical & philosophical context Master

Geometric programming originated not in convex analysis but in engineering economics. Clarence Zener, studying the cost minimization of equipment whose terms were products of powers, observed in the early 1960s that the arithmetic-geometric-mean inequality gave a clean lower bound, and with Richard Duffin and Elmor Peterson developed this into a full duality theory in the 1967 monograph Geometric Programming: Theory and Application ^{[Duffin, Peterson & Zener 1967]}. Their formulation was dual-first: the posynomial primal was attacked through the AM-GM dual, with the degree of difficulty measuring how far the orthogonality system fell short of determining the dual weights, and zero-degree-of-difficulty problems solved in closed form. The name "geometric programming" honors the geometric mean at the center of the inequality.

The recognition that the log-log substitution turns a GP into a convex program reframed the subject within the convex-optimization theory codified by Boyd and Vandenberghe ^{[Boyd & Vandenberghe §4.5]}, and the 2007 tutorial of Boyd, Kim, Vandenberghe, and Hassibi ^{[Boyd, Kim, Vandenberghe & Hassibi 2007]} consolidated the modern view: GP as a convex modeling class solved by interior-point methods, with generalized GP and the signomial/condensation heuristics as principled extensions. The applications that revived the field were technological — analog circuit sizing by Hershenson, Boyd, and Lee ^{[Hershenson, Boyd & Lee 2001]}, and wireless power control and network utility maximization synthesized by Chiang ^{[Chiang 2005]} — each exploiting that delays, powers, and rates are native posynomials, so global optimization replaced the local heuristics that had dominated those design disciplines.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@article{boyd2007tutorial,
  author  = {Boyd, Stephen and Kim, Seung-Jean and Vandenberghe, Lieven and Hassibi, Arash},
  title   = {A Tutorial on Geometric Programming},
  journal = {Optimization and Engineering},
  volume  = {8},
  number  = {1},
  pages   = {67--127},
  year    = {2007}
}

@book{duffin1967geometric,
  author    = {Duffin, Richard J. and Peterson, Elmor L. and Zener, Clarence},
  title     = {Geometric Programming: Theory and Application},
  publisher = {Wiley},
  address   = {New York},
  year      = {1967}
}

@article{hershenson2001optimal,
  author  = {Hershenson, Maria del Mar and Boyd, Stephen P. and Lee, Thomas H.},
  title   = {Optimal Design of a {CMOS} Op-Amp via Geometric Programming},
  journal = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
  volume  = {20},
  number  = {1},
  pages   = {1--21},
  year    = {2001}
}

@article{chiang2005geometric,
  author  = {Chiang, Mung},
  title   = {Geometric Programming for Communication Systems},
  journal = {Foundations and Trends in Communications and Information Theory},
  volume  = {2},
  number  = {1--2},
  pages   = {1--154},
  year    = {2005}
}

Prerequisites

44.01.01
44.05.01

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.5 — monomials, posynomials, and the log change of variables
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §4.5; Boyd, Kim, Vandenberghe & Hassibi 2007 A Tutorial on Geometric Programming (Optimization and Engineering 8(1)) §1-§4
master: Boyd, Kim, Vandenberghe & Hassibi 2007 A Tutorial on Geometric Programming (Optimization and Engineering 8(1)) §4-§9; Duffin, Peterson & Zener 1967 Geometric Programming (Wiley) Ch. 1-3; Chiang 2005 Geometric Programming for Communication Systems (now Publishers) §1-§3

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §4.5 geometric programming: monomials and posynomials, GP in standard form, the log-log transformation to a convex problem, extensions
Boyd, S., Kim, S.-J., Vandenberghe, L. & Hassibi, A. — A Tutorial on Geometric Programming · Optimization and Engineering 8(1) (2007), 67-127; §2 monomials/posynomials; §3 GP and convex form; §4 GP duality; §8 generalized GP; §9 signomial programming and condensation
Duffin, R. J., Peterson, E. L. & Zener, C. — Geometric Programming: Theory and Application (Wiley, 1967) · Ch. 1-3 the original posynomial theory and the arithmetic-geometric-mean dual; the degree of difficulty
Chiang, M. — Geometric Programming for Communication Systems (Foundations and Trends in Communications and Information Theory, now Publishers, 2005) · §1-§3 power control and resource allocation in wireless networks as GP/signomial programs
Hershenson, M., Boyd, S. & Lee, T. H. — Optimal Design of a CMOS Op-Amp via Geometric Programming · IEEE Transactions on Computer-Aided Design 20(1) (2001), 1-21; analog-circuit and device sizing as a GP

Estimated time

beginner: 20m
intermediate: 50m
master: 85m