Disciplined Quasiconvex Programming

Disciplined quasiconvex programming (DQCP) is a generalization of DCP for quasiconvex functions. Quasiconvexity generalizes convexity: a function \(f\) is quasiconvex if and only if its domain is a convex set and its sublevel sets \(\{x : f(x) \leq t\}\) are convex, for all \(t\). For a thorough overview of quasiconvexity, see the paper Disciplined quasiconvex programming.

While DCP is a ruleset for constructing convex programs, DQCP is a ruleset for quasiconvex programs (QCPs), which are optimization problems in which the objective is to minimize a quasiconvex function over a convex set. The convex set can be specified using equalities of affine functions and inequalities of convex and concave functions, just as in DCP; additionally, DQCP permits inequalities of the form \(f(x) \leq t\), where f(x) is a quasiconvex expression and \(t\) is constant, and \(f(x) \geq t\), where f(x) is quasiconcave and \(t\) is constant. Every disciplined convex program is a disciplined quasiconvex program, but the converse is not true.

CVXPY lets you form and solve DQCP problems, just as it does for DCP problems. For example, the following code solves a simple QCP,

import cvxpy as cp

x = cp.Variable()
y = cp.Variable(pos=True)
objective_fn = -cp.sqrt(x) / y
problem = cp.Problem(cp.Minimize(objective_fn), [cp.exp(x) <= y])
problem.solve(qcp=True)
assert problem.is_dqcp()
print("Optimal value: ", problem.value)
print("x: ", x.value)
print("y: ", y.value)

and it prints the below output.

Optimal value:  -0.4288821220397949
x:  0.49999737143004713
y:  1.648717724845007

To solve DQCP problems, you must pass the option qcp=True to the solve() method.

This section explains what DQCP is, and it shows how to construct and solve DQCP problems using CVXPY. At the end of the section are tables listing all the atoms that can be used in DQCP problems, similar to the tables presented in the section on DCP atoms.

For an in-depth reference on DQCP, see our accompanying paper. For interactive code examples, check out our notebooks.

Note: DQCP is a recent addition to CVXPY. If you have feedback, please file an issue or make a pull request on Github.

Curvature

DQCP adds two new types of curvature to CVXPY: quasiconvex and quasiconcave. A function \(f\) is quasiconvex if and only if its domain is a convex set and its sublevel sets \(\{x : f(x) \leq t\}\) are convex, for all \(t\); \(f\) is quasiconcave if \(-f\) is quasiconvex. Every convex function is also quasiconvex, and every concave function is also quasiconcave; the converses of these statements are not true. An expression that is both quasiconvex and quasiconcave is called quasilinear.

CVXPY’s curvature analysis can flag Expressions as unknown even when they are quasiconvex or quasiconcave, but it will never mistakenly flag an expression as quasiconvex or quasiconcave.

The curvature of an Expression is stored in its .curvature attribute. For example, running the following script

import cvxpy as cp

x = cp.Variable(3)
y = cp.length(x)
z = -y
print(y.curvature)
print(z.curvature)

w = cp.ceil(x)
print(w.curvature)

prints the following output.

QUASICONVEX
QUASICONCAVE
QUASILINEAR

You can also check the curvature of an Expression by calling the methods is_quasiconvex() and is_quasiconcave(). For example, y.is_quasiconvex() and z.is_quasiconcave() would evaluate to True. You can check if an expression is quasilinear by calling the is_quasilinear() method.

Composition rules

DQCP analysis is based on applying a general composition theorem from convex analysis to each expression. An expression is verifiably quasiconvex under DQCP if it is one of the following:

  • convex (under DCP);

  • a quasiconvex atom, applied to a variable or constant:

  • the max (cvxpy.maximum) of quasiconvex expressions;

  • an increasing function of a quasiconvex expression, or a decreasing function of a quasiconcave expression;

  • an expression of the form \(f(e_1, e_2, \ldots, e_n)\) such that (1) \(f\) is a quasiconvex atom, and (2) for each \(i\), \(f\) is increasing in argument \(i\) and \(e_i\) is convex, \(f\) is decreasing in argument \(i\) and \(e_i\) is concave, or \(e_i\) is affine.

An expression is quasiconcave under DQCP if it is one of the following:

  • concave (under DCP);

  • a quasiconcave atom, applied to a variable or constant:

  • the min (cvxpy.minimum) of quasiconcave expressions;

  • an increasing function of a quasiconcave expression, or a decreasing function of a quasiconvex expression;

  • an expression of the form \(f(e_1, e_2, \ldots, e_n)\) such that (1) \(f\) is a quasiconcave atom, and (2) for each \(i\), \(f\) is increasing in argument \(i\) and \(e_i\) is concave, \(f\) is decreasing in argument \(i\) and \(e_i\) is convex, or \(e_i\) is affine.

Whether an atom is quasiconvex or quasiconcave may depend on the signs of its arguments. For example, the scalar product \(xy\) is quasiconcave when x and y are either both nonnegative or both nonpositive, and quasiconvex when one the arguments is nonnegative and the other is nonpositive.

If an Expression satisfies the above rules, we colloquially say that the Expression “is DQCP.” You can check whether an Expression is DQCP by calling the method is_dqcp(). For example, the assertions in the following code block will pass.

import cvxpy as cp

x = cp.Variable(pos=True)
y = cp.Variable(pos=True)

product = cp.multiply(x, y)

assert product.is_quasiconcave()
assert product.is_dqcp()

An Expression is DQCP precisely when it has known curvature, which means at least one of the methods is_constant() is_affine(), is_convex(), is_concave(), is_quasiconvex(), is_quasiconvex() will return True.

DQCP problems

A Problem is constructed from an objective and a list of constraints. If a problem follows the DQCP rules, it is guaranteed to be a DQCP and solvable by CVXPY (if a solution to the problem exists). The DQCP rules require that the problem objective have one of two forms:

  • Minimize(quasiconvex)

  • Maximize(quasiconcave)

The only valid constraints under the DQCP rules are

  • affine == affine

  • convex <= concave

  • concave >= convex

  • quasiconvex <= constant

  • quasiconcave >= constant

You can check that a problem, constraint, or objective satisfies the DQCP rules by calling object.is_dqcp(). Here are some examples of DQCP and non-DQCP problems:

import cvxpy as cp

# The sign of variables affects curvature analysis.
x = cp.Variable(nonneg=True)
concave_fractional_fn = x * cp.sqrt(x)
constraint = [cp.ceil(x) <= 10]
problem = cp.Problem(cp.Maximize(concave_fractional_fn), constraint)
assert concave_fractional_fn.is_quasiconcave()
assert constraint[0].is_dqcp()
assert problem.is_dqcp()

w = cp.Variable()
fn = w * cp.sqrt(w)
problem = cp.Problem(cp.Maximize(fn))
assert not fn.is_dqcp()
assert not problem.is_dqcp()

CVXPY will raise an exception if you call problem.solve(qcp=True) on a non-DQCP problem.

DQCP atoms

Quasiconvex and quasiconcave expressions can be constructed using convex and concave atoms, using the curvature rules given above. This section describes new semantics for some existing atoms under DQCP, and introduces new atoms that are quasiconvex or quasiconcave (but not convex or concave). Many of these new atoms are integer-valued.

Ratio. The infix operator / is an atom, denoting ratio. This atom is both quasiconvex and quasiconcave when the denominator is known to be either nonnegative or nonpositive. The ratio x/y is increasing in x when y is nonnegative, increasing in y when x is nonpositive, decreasing in x when y is nonpositive, and decreasing in y when x is nonnegative.

The ratio atom can be used with the composition rule to construct interesting quasiconvex and quasiconcave expressions. For example, the ratio of a nonnegative concave function and a positive convex function is quasiconcave, and the ratio of a nonnegative convex function and a positive concave function is quasiconvex. Similarly, the ratio of two affine functions is quasilinear when the denominator is positive.

Scalar product. The scalar product * is quasiconvex when one of its arguments is nonnegative and the other is nonpositive, and it is quasiconcave when its arguments are both nonnegative or both nonpositive. Hence, by the composition rule, the product of two nonnegative concave functions is quasiconcave, and the product of a nonnegative concave function and a nonpositive convex function is quasiconvex.

Distance ratio function. The atom cvxpy.dist_ratio(x, a, b) denotes the function \(\|x - a\|_2 / \|x - b\|_2\), implicitly enforcing the constraint that \(\|x - a\|_2 \leq \|x - b\|_2\). The expressions a and b must be constants. This atom is quasiconvex.

Maximum generalized eigenvalue. The atom cvxpy.gen_lambda_max(A, B) computes the maximum generalized eigenvalue of A and B, defined as the maximum \(\lambda \in \mathbf{R}\) such that \(Ax = \lambda Bx\) for some \(x\). This atom is quasiconvex, and it enforces the constraint that A is symmetric and B is positive definite.

Ceiling and floor. The atoms cvxpy.ceil(x) and cvxpy.floor(x) are quasilinear, and increasing in their arguments.

Sign. The atoms cvxpy.sign(x), which returns -1 for x <= 0 and +1 for x > 0, is quasilinear.

Length of a vector. The atoms cvxpy.length(x), which returns the index of the last nonzero element in \(x \in \mathbf{R}^n`\), is quasiconvex.

Solving DQCP problems

A DQCP problem problem can be solved by calling problem.solve(qcp=True). CVXPY uses a bisection method on the optimal value of the problem to solve QCPs, and it will automatically find an upper and lower bound for the bisection. You can optionally provide your own upper and lower bound when solving a QCP, which can sometimes be helpful. You can provide these bounds via the keyword arguments low and high; for example, problem.solve(qcp=True, low=12, high=17) would limit the bisection to objective values that are greater than 12 and less than 17.

Bisection involves solving a sequence of optimization problems. If your problem is ill-conditioned, or if you’re unlucky, a solver might fail to solve one of these subproblems, which will result in an error. If this happens, you can try using a different solver via the solver keyword argument. (For example, problem.solve(qcp=True, solver=cp.SCS).) To obtain verbose output describing the bisection, supply the keyword argument verbose=True to the solve method (problem.solve(qcp=True, verbose=True)).