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 Constant
s, Variable
s, and
Parameter
s 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
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
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