Convex NLP Fast Path

Convex NLP Fast Path#

When discopt detects that a continuous optimization problem is convex, it automatically skips the Branch and Bound machinery and solves it with a single NLP call. This guarantees global optimality without the overhead of spatial B&B [Belotti et al., 2013].

A problem qualifies for the convex fast path when all three conditions hold:

All variables are continuous (no integer or binary variables).
The objective is convex (for minimization) or concave (for maximization).
All inequality constraints have convex left-hand sides (in \(g(x) \le 0\) form), and all equality constraints are affine.

The detection uses DCP (Disciplined Convex Programming) composition rules [Grant et al., 2006] applied to the expression DAG. It recognizes convex-preserving compositions such as exp(affine), sum_of_convex, nonneg_scale * convex, and others.

import discopt.modeling as dm

Example: Convex NLP Solved via Fast Path#

The following problem has a convex objective (sum of exp and a quadratic, both convex) with a linear constraint. discopt detects convexity and solves it in a single NLP call.

\[\min_{x,y} \; e^x + y^2 \quad \text{s.t.} \quad x + y \ge 1, \quad x,y \in [-5, 5]\]

m = dm.Model("convex_example")
x = m.continuous("x", lb=-5, ub=5)
y = m.continuous("y", lb=-5, ub=5)

m.minimize(dm.exp(x) + y**2)
m.subject_to(x + y >= 1)

result = m.solve()

print(f"Status:          {result.status}")
print(f"Objective:       {result.objective:.6f}")
print(f"Convex fast path: {result.convex_fast_path}")
print(f"Node count:      {result.node_count}")
print(f"Gap:             {result.gap}")
print(f"x = {result.x['x']:.6f}")
print(f"y = {result.x['y']:.6f}")

Status:          optimal
Objective:       1.839484
Convex fast path: True
Node count:      0
Gap:             0.0
x = 0.314923
y = 0.685077

The convex_fast_path flag confirms that B&B was skipped. The node count is 0, and the gap is exactly 0.0 because a single NLP solve of a convex problem yields the global optimum.

Maximizing a Concave Function#

Maximizing a concave function is equivalent to minimizing a convex function, so it also qualifies for the fast path.

\[\max_{x} \; \log(x) \quad \text{s.t.} \quad x \le 5, \quad x \in [0.1, 10]\]

m = dm.Model("concave_max")
x = m.continuous("x", lb=0.1, ub=10)

m.maximize(dm.log(x))
m.subject_to(x <= 5)

result = m.solve()

print(f"Status:          {result.status}")
print(f"Convex fast path: {result.convex_fast_path}")
print(f"Node count:      {result.node_count}")
print(f"x = {result.x['x']:.6f}  (expected: 5.0)")

Status:          optimal
Convex fast path: True
Node count:      0
x = 5.000000  (expected: 5.0)

Nonconvex Problems Fall Back to B&B#

When the problem is nonconvex, the fast path is not used and discopt falls back to spatial Branch and Bound with McCormick relaxations [McCormick, 1976]. The convex_fast_path flag will be False.

\[\min_{x} \; \sin(x) \quad x \in [-5, 5]\]

m = dm.Model("nonconvex_example")
x = m.continuous("x", lb=-5, ub=5)

m.minimize(dm.sin(x))

result = m.solve()

print(f"Status:          {result.status}")
print(f"Convex fast path: {result.convex_fast_path}")
print(f"Objective:       {result.objective:.6f}  (expected: -1.0)")
print(f"x = {result.x['x']:.6f}  (expected: ~ -1.5708)")

Status:          optimal
Convex fast path: False
Objective:       -1.000000  (expected: -1.0)
x = -1.570796  (expected: ~ -1.5708)

Opting Out#

If you want to bypass convexity detection (for example, during benchmarking or debugging), pass skip_convex_check=True to solve(). The solver will then use the standard NLP path for continuous problems.

The two arms find the same point, but they do not certify it the same way, and the cell prints that rather than only the objectives. exp(x) on [-5, 5] has no McCormick envelope, so with the fast path skipped the relaxation layer produces no valid dual bound at all and the solver says so on stderr — the run comes back feasible, not optimal. That message is the point of this section: convexity detection is not an optimization, it is what supplies the certificate here.

m = dm.Model("skip_check_demo")
x = m.continuous("x", lb=-5, ub=5)

m.minimize(dm.exp(x))

result_default = m.solve()
result_skipped = m.solve(skip_convex_check=True)

print(f"Default:  convex_fast_path={result_default.convex_fast_path}, "
      f"status={result_default.status}, gap_certified={result_default.gap_certified}")
print(f"Skipped:  convex_fast_path={result_skipped.convex_fast_path}, "
      f"status={result_skipped.status}, gap_certified={result_skipped.gap_certified}")
same = abs(result_default.objective - result_skipped.objective) < 1e-6
print(f"Both find the same optimum: {same}")

assert result_default.convex_fast_path and not result_skipped.convex_fast_path
assert same, "the opt-out must not change the answer, only how it is certified"
assert result_default.gap_certified, "the fast path is what certifies this model"

No valid dual bound was produced for model 'skip_check_demo': the relaxation layer could not bound this objective (status=feasible). The result cannot be certified globally optimal. A nonlinear term with no envelope is the usual cause; an epigraph reformulation (minimize z subject to f(x) <= z) often gives the relaxation something to bound.

Default:  convex_fast_path=True, status=optimal, gap_certified=True
Skipped:  convex_fast_path=False, status=feasible, gap_certified=False
Both find the same optimum: True

What Makes a Problem Convex?#

The convexity detector recognizes these patterns through DCP composition rules [Grant et al., 2006]:

Expression	Curvature
Variables, constants, parameters	Affine
`ax + by` (linear combinations)	Affine
`x2`, `x4` (even powers of affine)	Convex
`exp(convex)`	Convex
`log(concave)`, `sqrt(concave)`	Concave
`cosh(affine)`	Convex
`sum(convex_terms)`	Convex
`nonneg_const * convex`	Convex
`sin(x)`, `cos(x)`, `x*y` (bilinear)	Unknown (nonconvex)

A minimization problem is convex when the objective is convex and all constraints define a convex feasible set (convex \(\le\) constraints and affine \(=\) constraints).