DGP fundamentals

This notebook will introduce you to the fundamentals of disciplined geometric programming (DGP), which lets you formulate and solve log-log convex programs (LLCPs) in CVXPY.

LLCPs are problems that become convex after the variables, objective functions, and constraint functions are replaced with their logs, an operation that we refer to as a log-log transformation. LLCPs generalize geometric programming.

import cvxpy as cp

1. Log-log curvature

Just as every Expression in CVXPY has a curvature (constant, affine, convex, concave, or unknown), every Expression also has a log-log curvature.

A function \(f : D \subseteq \mathbf{R}^{n}_{++} \to \mathbf{R}\) is said to be log-log convex if the function \(F(u)=\log f(e^u)\), with domain \(\{u \in \mathbf{R}^n : e^u \in D\}\), is convex (where \(\mathbf{R}^{n}_{++}\) denotes the set of positive reals and the logarithm and exponential are meant elementwise); the function \(F\) is called the log-log transformation of \(f\). The function \(f\) is log-log concave if \(F\) is concave, and it is log-log affine if \(F\) is affine.

Notice that if a function has log-log curvature, then its domain and range can only include positive numbers.

The log-log curvature of an Expression can be accessed via its .log_log_curvature attribute. For an Expression to have known log-log curvature, all of the Constants, Variables, and Parameters it refers to must be elementwise positive.

# Only elementwise positive constants are allowed in DGP.
c = cp.Constant(1.0)
print(c, c.log_log_curvature)

c = cp.Constant([1.0, 2.0])
print(c, c.log_log_curvature)

c = cp.Constant([1.0, 0.0])
print(c, c.log_log_curvature)

c = cp.Constant(-2.0)
print(c, c.log_log_curvature)

1.0 LOG-LOG CONSTANT
[1. 2.] LOG-LOG CONSTANT
[1. 0.] UNKNOWN
-2.0 UNKNOWN

# Variables and parameters must be positive, ie, they must be constructed with the option `pos=True`
v = cp.Variable(pos=True)
print(v, v.log_log_curvature)

v = cp.Variable()
print(v, v.log_log_curvature)

p = cp.Parameter(pos=True)
print(p, p.log_log_curvature)

p = cp.Parameter()
print(p, p.log_log_curvature)

var0 LOG-LOG AFFINE
var1 UNKNOWN
param2 LOG-LOG CONSTANT
param3 UNKNOWN

Functions from geometric programming

A function \(f(x)\) is log-log affine if and only if it is given by

\[f(x) = cx_1^{a_1}x_2^{a_2} \ldots x_n^{a_n},\]

where \(c > 0\) and the \(a_i\) are real numbers. In the context of geometric programming, such a function is called a monomial.

x = cp.Variable(shape=(3,), pos=True, name="x")
c = 2.0
a = [0.5, 2.0, 1.8]

monomial = c * x[0] ** a[0] * x[1] ** a[1] * x[2] ** a[2]
# Monomials are not convex.
assert not monomial.is_convex()

# They are, however, log-log affine.
print(monomial, ":", monomial.log_log_curvature)
assert monomial.is_log_log_affine()

2.0 * power(x[0], 1/2) * power(x[1], 2) * power(x[2], 9/5) : LOG-LOG AFFINE

A sum of monomial functions is log-log convex; in the context of geometric programming, such a function is called a posynomial. There are functions that are not posynomials that are still log-log convex.

x = cp.Variable(pos=True, name="x")
y = cp.Variable(pos=True, name="y")

constant = cp.Constant(2.0)
monomial = constant * x * y
posynomial = monomial + (x ** 1.5) * (y ** -1)
reciprocal = posynomial ** -1
unknown = reciprocal + posynomial

print(constant, ":", constant.log_log_curvature)
print(monomial, ":", monomial.log_log_curvature)
print(posynomial, ":", posynomial.log_log_curvature)
print(reciprocal, ":", reciprocal.log_log_curvature)
print(unknown, ":", unknown.log_log_curvature)

2.0 : LOG-LOG CONSTANT
2.0 * x * y : LOG-LOG AFFINE
2.0 * x * y + power(x, 3/2) * power(y, -1) : LOG-LOG CONVEX
power(2.0 * x * y + power(x, 3/2) * power(y, -1), -1) : LOG-LOG CONCAVE
power(2.0 * x * y + power(x, 3/2) * power(y, -1), -1) + 2.0 * x * y + power(x, 3/2) * power(y, -1) : UNKNOWN

2. Log-log curvature ruleset

CVXPY has a library of atomic functions with known log-log curvature and monotonicty. It uses this information to tag every Expression, i.e., every composition of atomic functions, with a log-log curvature. In particular,

A function \(f(expr_1,expr_2,...,expr_n)\) is log-log convex if \(f\) is a log-log convex function and for each expri one of the following conditions holds:

\(f\) is increasing in argument i and \(expr_i\) is log-log convex. \(f\) is decreasing in argument \(i\) and \(expr_i\) is log-log concave. \(expr_i\) is log-log affine. A function \(f(expr_1,expr_2,...,expr_n)\) is log-log concave if \(f\) is a log-log concave function and for each \(expr_i\) one of the following conditions holds:

\(f\) is increasing in argument \(i\) and \(expr_i\) is log-log concave. \(f\) is decreasing in argument \(i\) and \(expr_i\) is log-log convex. \(expr_i\) is log-log affine. A function \(f(expr_1,expr_2,...,expr_n)\) is log-log affine if \(f\) is an log-log affine function and each \(expr_i\) is log-log affine.

If none of the three rules apply, the expression \(f(expr_1,expr_2,...,expr_n)\) is marked as having unknown curvature.

If an Expression satisfies the composition rule, we colloquially say that the Expression “is DGP.” You can check whether an Expression is DGP by calling the method is_dgp().

x = cp.Variable(pos=True, name="x")
y = cp.Variable(pos=True, name="y")

monomial = 2.0 * x * y
posynomial = monomial + (x ** 1.5) * (y ** -1)

print(monomial, "is dgp?", monomial.is_dgp())
print(posynomial, "is dgp?", posynomial.is_dgp())

2.0 * x * y is dgp? True
2.0 * x * y + power(x, 3/2) * power(y, -1) is dgp? True

3. DGP problems

An LLCP is an optimization problem of the form

\[\begin{split}\begin{equation} \begin{array}{ll} \mbox{minimize} & f_0(x) \\ \mbox{subject to} & f_i(x) \leq \tilde{f_i}, \quad i=1, \ldots, m\\ & g_i(x) = \tilde{g_i}, \quad i=1, \ldots, p, \end{array} \end{equation}\end{split}\]

where the functions \(f_i\) are log-log convex, \(\tilde{f_i}\) are log-log concave, and the functions \(g_i\) and \(\tilde{g_i}\) are log-log affine. An optimization problem with constraints of the above form in which the goal is to maximize a log-log concave function is also an LLCP.

A problem is DGP if additionally all the functions are DGP. You can check whether a CVXPY Problem is DGP by calling its .is_dgp() method.

x = cp.Variable(pos=True, name="x")
y = cp.Variable(pos=True, name="y")
z = cp.Variable(pos=True, name="z")

objective_fn = x * y * z
constraints = [
  4 * x * y * z + 2 * x * z <= 10, x <= 2*y, y <= 2*x, z >= 1]
assert objective_fn.is_log_log_concave()
assert all(constraint.is_dgp() for constraint in constraints)
problem = cp.Problem(cp.Maximize(objective_fn), constraints)

print(problem)
print("Is this problem DGP?", problem.is_dgp())

maximize x * y * z
subject to 4.0 * x * y * z + 2.0 * x * z <= 10.0
           x <= 2.0 * y
           y <= 2.0 * x
           1.0 <= z
Is this problem DGP? True

Solving DGP problems

You can solve a DGP Problem by calling its solve method with gp=True.

problem.solve(gp=True)
print("Optimal value:", problem.value)
print(x, ":", x.value)
print(y, ":", y.value)
print(z, ":", z.value)
print("Dual values: ", list(c.dual_value for c in constraints))

Optimal value: 1.9999999926890524
x : 0.9999999989968756
y : 1.9999999529045318
z : 1.000000020895385
Dual values:  [1.1111111199586956, 1.94877846244994e-09, 0.1111111217156332, 0.11111112214962586]

If you forget to supply gp=True, an error will be raised.

try:
    problem.solve()
except cp.DCPError as e:
    print(e)

Problem does not follow DCP rules. However, the problem does follow DGP rules. Consider calling this function with gp=True.

4. Next steps

Atoms

CVXPY has a large library of log-log convex functions, including common functions like \(\exp\), \(\log\), and the difference between two numbers. Check out the tutorial on our website for the full list of atoms: https://www.cvxpy.org/tutorial/dgp/index.html

References

For a reference on DGP, consult the following paper: https://web.stanford.edu/~boyd/papers/dgp.html