When It Isn’t a Geometric Program

Author

Balasubramanian Narasimhan

Introduction

The other examples in this section all share a property worth making explicit: they are geometric programs, and psolve(..., gp = TRUE) accepts them. This one is about the boundary. It works through a problem published under the heading “geometric programming” that CVXR correctly refuses, explains why the refusal is right, and shows how to solve it anyway using a sequence of genuine geometric programs.

Disciplined geometric programming (Agrawal et al. 2019) admits an inequality constraint in one direction only: posynomial \(\leq\) monomial. A constraint pointing the other way — a posynomial bounded below — is called a reverse constraint. Under the logarithmic change of variables \(y_i = \log x_i\) that makes a GP convex, a posynomial becomes a convex function, so \(p(x) \geq c\) describes the complement of a convex set. Such a problem is a signomial program, and it is not convex under any change of variables (Boyd et al. 2007).

This distinction matters in practice because the optimization literature applies the label “geometric programming” generously. Problems presented as GPs routinely contain reverse constraints.

The Problem

The following is the illustrative example of Huang and Kao (2009):

\[ \begin{array}{ll} \mbox{minimize} & x_1 x_2^{0.5} x_3^{1.2} + 2 x_1 \\ \mbox{subject to} & 2 x_1 + x_2 + x_3 \geq 8, \\ & x_2 + 2 x_3 \geq 10.5, \\ & x_1 + 2 x_3 \leq 10, \\ & 1 \leq x_1, x_2, x_3 \leq 5. \end{array} \]

Transcribed directly:

mk_vars <- function() {
  lapply(1:3, function(i) Variable(pos = TRUE, bounds = list(1, 5)))
}

v <- mk_vars()
x1 <- v[[1]]; x2 <- v[[2]]; x3 <- v[[3]]

objective <- x1 * power(x2, 0.5) * power(x3, 1.2) + 2 * x1
constraints <- list(
  2 * x1 + x2 + x3 >= 8,
  x2 + 2 * x3 >= 10.5,
  x1 + 2 * x3 <= 10
)

problem <- Problem(Minimize(objective), constraints)

Why It Isn’t a GP

is_dgp() works on individual expressions and constraints, not only on whole problems, which is what lets us find the culprit:

cat("Objective is DGP? ", is_dgp(Minimize(objective)), "\n", sep = "")
for (i in seq_along(constraints))
  cat("Constraint ", i, " is DGP? ", is_dgp(constraints[[i]]), "\n", sep = "")
cat("Problem is DGP?   ", is_dgp(problem), "\n", sep = "")
Objective is DGP? TRUE
Constraint 1 is DGP? FALSE
Constraint 2 is DGP? FALSE
Constraint 3 is DGP? TRUE
Problem is DGP?   FALSE

The objective is fine: a posynomial is log-log convex. The third constraint is fine: posynomial \(\leq\) constant. The first two are the reverse constraints, and they are what makes the problem non-DGP. Asking for a GP solve reports exactly that:

psolve(problem, gp = TRUE)
Error in `construct_solving_chain()`:
! Problem is not DGP compliant.
ℹ Remove `gp = TRUE` or reformulate as a geometric program.

Dropping gp = TRUE does not rescue it either. The constraints are all linear in \(x\), so the feasible set is a polytope, but the objective is not convex on the positive orthant: for \(x_1^{a} x_2^{b}\) the Hessian determinant carries a factor \((1 - a - b)\), and with a leading exponent of \(1\) that matrix is indefinite.

is_dcp(problem)
[1] FALSE

The problem is genuinely non-convex. That is precisely why Huang and Kao (2009) attack it with piecewise linearization and binary variables — it is their mixed-integer benchmark, not a worked GP.

Condensation: A Sequence of Geometric Programs

The classical remedy is condensation. Let \(p(x) = \sum_i u_i(x)\) be a posynomial with monomial terms \(u_i > 0\), and fix a point \(x^{0}\). Setting the weights

\[\alpha_i = \frac{u_i(x^{0})}{p(x^{0})}, \qquad \sum_i \alpha_i = 1,\]

the arithmetic-geometric mean inequality gives

\[p(x) \;=\; \sum_i u_i(x) \;\geq\; \prod_i \left(\frac{u_i(x)}{\alpha_i}\right)^{\alpha_i} \;=:\; m(x),\]

with equality at \(x = x^{0}\). Being a product of powers of monomials, \(m\) is itself a monomial.

So replace each reverse constraint \(c \leq p(x)\) by \(c \leq m(x)\). That is a legal GP constraint, and since \(m \leq p\) everywhere it is a conservative inner approximation: anything feasible for the surrogate is feasible for the original problem. Re-derive the weights at the new iterate and repeat.

f0 <- function(z) z[1] * sqrt(z[2]) * z[3]^1.2 + 2 * z[1]

condense <- function(z0, tol = 1e-10, maxit = 60) {
  z <- z0
  prev <- Inf
  for (it in seq_len(maxit)) {
    ## AGM weights from the term values at the current iterate
    t1 <- c(2 * z[1], z[2], z[3]); a1 <- t1 / sum(t1)
    t2 <- c(z[2], 2 * z[3]);       a2 <- t2 / sum(t2)

    v <- mk_vars()
    y1 <- v[[1]]; y2 <- v[[2]]; y3 <- v[[3]]

    m1 <- power(2 * y1 / a1[1], a1[1]) * power(y2 / a1[2], a1[2]) *
          power(y3 / a1[3], a1[3])
    m2 <- power(y2 / a2[1], a2[1]) * power(2 * y3 / a2[2], a2[2])

    sub <- Problem(
      Minimize(y1 * power(y2, 0.5) * power(y3, 1.2) + 2 * y1),
      list(m1 >= 8, m2 >= 10.5, y1 + 2 * y3 <= 10)
    )
    val <- psolve(sub, gp = TRUE)          # each subproblem IS a GP
    if (!identical(status(sub), "optimal")) break

    z <- c(value(y1), value(y2), value(y3))
    if (abs(prev - val) < tol) break
    prev <- val
  }
  z
}

Each surrogate is a genuine geometric program, so gp = TRUE accepts it. Starting from an interior point:

z <- condense(c(2, 3, 4))
cat("x1:", z[1], "\n")
cat("x2:", z[2], "\n")
cat("x3:", z[3], "\n")
cat("Objective value:", f0(z), "\n")
x1: 1 
x2: 1.5 
x3: 4.5 
Objective value: 9.445616

The iteration converges to \(x = (1,\ 1.5,\ 4.5)\) with objective value \(9.445616\). All three constraints are active there, and solving the resulting linear system \(2x_1 + x_2 + x_3 = 8\), \(x_2 + 2x_3 = 10.5\), \(x_1 + 2x_3 = 10\) returns that vertex exactly. Huang and Kao (2009) report a minimum of \(9.446\), the value produced by their mixed-integer linear approximation.

Condensation Is Local

Condensation converges to a KKT point, not necessarily a global optimum. Different starting points make that concrete:

starts <- list(c(2, 3, 4), c(1, 5, 5), c(5, 5, 2.5),
               c(1.2, 2, 4.9), c(3, 1.5, 4))
multistart <- t(sapply(starts, function(s) {
  zz <- condense(s)
  c(x1 = zz[1], x2 = zz[2], x3 = zz[3], objective = f0(zz))
}))
multistart
     x1  x2   x3 objective
[1,]  1 1.5 4.50  9.445616
[2,]  1 5.0 2.75  9.528080
[3,]  1 5.0 2.75  9.528080
[4,]  1 1.5 4.50  9.445616
[5,]  1 1.5 4.50  9.445616

Two of the five land on \((1,\ 5,\ 2.75)\) with value \(9.528080\) — a genuine local optimum, not a solver failure.

A Global Certificate

For this particular problem a global check is cheap, because the objective is strictly increasing in every coordinate. For fixed \((x_1, x_2)\) the best \(x_3\) is therefore the smallest feasible one, which collapses the search to two dimensions:

grid <- seq(1, 5, length.out = 1201)
best <- c(objective = Inf, x1 = NA, x2 = NA, x3 = NA)
for (u in grid) for (w in grid) {
  lo <- max(1, 8 - 2 * u - w, (10.5 - w) / 2)
  if (lo > 5 || u + 2 * lo > 10) next
  fv <- f0(c(u, w, lo))
  if (fv < best[1])
    best <- c(objective = fv, x1 = u, x2 = w, x3 = lo)
}
best
objective        x1        x2        x3 
 9.445616  1.000000  1.500000  4.500000

The grid search agrees with the condensation result, so \((1,\ 1.5,\ 4.5)\) is the global optimum.

Takeaways

  • DGP requires posynomial \(\leq\) monomial. A posynomial bounded below is a reverse constraint, which makes the problem signomial rather than geometric.
  • Call is_dgp() on individual constraints to find which one is responsible. The problem-level answer alone will not tell you.
  • Condensation replaces each reverse constraint with its arithmetic-geometric mean monomial lower bound, yielding a sequence of true geometric programs, each solvable with gp = TRUE. It is conservative and converges monotonically, but only to a local optimum.
  • A global guarantee needs either problem structure, as exploited above, or a global solver — which is outside what a convex modeling framework such as CVXR provides.

Session Info

R version 4.6.1 (2026-06-24)
Platform: aarch64-apple-darwin23
Running under: macOS Tahoe 26.6.2

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.6/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.6/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] CVXR_1.9.2

loaded via a namespace (and not attached):
 [1] vctrs_0.7.3       slam_0.1-56       cli_3.6.6         knitr_1.51       
 [5] ECOSolveR_0.6.1   rlang_1.3.0       xfun_0.60         clarabel_0.11.3  
 [9] otel_0.2.0        Rglpk_0.6-5.1     highs_1.14.0-2    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.2          jsonlite_2.0.0    glue_1.8.1       
[17] backports_1.5.1   rprojroot_2.1.1   htmltools_0.5.9   gmp_0.7-5.1      
[21] piqp_0.6.2        rmarkdown_2.31    grid_4.6.1        evaluate_1.0.5   
[25] fastmap_1.2.0     lifecycle_1.0.5   yaml_2.3.12       compiler_4.6.1   
[29] codetools_0.2-20  htmlwidgets_1.6.4 Rcpp_1.1.2        here_1.0.2       
[33] osqp_1.0.0        lattice_0.23-1    digest_0.6.39     pillar_1.11.1    
[37] checkmate_2.3.4   Matrix_1.7-6      tools_4.6.1

References

Agrawal, Akshay, Steven Diamond, and Stephen Boyd. 2019. “Disciplined Geometric Programming.” Optimization Letters 13 (5): 961–76. https://doi.org/10.1007/s11590-019-01422-z.
Boyd, Stephen, Seung-Jean Kim, Lieven Vandenberghe, and Arash Hassibi. 2007. “A Tutorial on Geometric Programming.” Optimization and Engineering 8 (1): 67–127. https://doi.org/10.1007/s11081-007-9001-7.
Huang, C.-H., and H.-Y. Kao. 2009. “An Effective Linear Approximation Method for Geometric Programming Problems.” 2009 IEEE International Conference on Industrial Engineering and Engineering Management (Hong Kong, China), 1743–46. https://doi.org/10.1109/IEEM.2009.5373154.