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 os

os.environ["JAX_PLATFORMS"] = "cpu"
os.environ["JAX_ENABLE_X64"] = "1"

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}")

******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit https://github.com/coin-or/Ipopt
******************************************************************************

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.

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}")
print(f"Skipped:  convex_fast_path={result_skipped.convex_fast_path}")
same = abs(result_default.objective - result_skipped.objective) < 1e-6
print(f"Both find the same optimum: {same}")

Default:  convex_fast_path=True
Skipped:  convex_fast_path=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).