Ferkans — Interactive Telecom Tutor

From Solvers to Modeling Languages

SciPy's minimize requires you to hand-write objective functions, gradients, and constraint functions. For convex problems, CVXPY provides a higher-level abstraction: you declare variables, write the objective and constraints using natural mathematical syntax, and CVXPY automatically verifies convexity, transforms the problem into standard form, and dispatches to an appropriate solver.

This separation of modeling from solving is the same philosophy behind MATLAB's CVX, Julia's Convex.jl, and AMPL.

Definition:
Convex Optimization Problem

A convex optimization problem has the form:

$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \le 0, \; \mathbf{A}\mathbf{x} = \mathbf{b}$

where $f$ and all $g_i$ are convex functions, and the equality constraints are affine.

Key property: every local minimum is a global minimum. This makes convex problems fundamentally easier than general nonlinear programs.

import cvxpy as cp

x = cp.Variable(n)
objective = cp.Minimize(cp.sum_squares(A @ x - b))
constraints = [x >= 0, cp.sum(x) == 1]
prob = cp.Problem(objective, constraints)
prob.solve()
print(x.value)

Definition:
Disciplined Convex Programming (DCP) Rules

CVXPY uses DCP rules to verify convexity at problem construction time. Every expression is tagged with its curvature (convex, concave, affine, constant) and sign (positive, negative, unknown).

Composition rules (simplified):

$\text{convex} + \text{convex} = \text{convex}$
$\text{convex} \circ \text{affine} = \text{convex}$
$\text{nondecreasing convex} \circ \text{convex} = \text{convex}$
$\alpha \cdot \text{convex} = \text{convex}$ for $\alpha > 0$

If CVXPY cannot verify convexity via DCP rules, it raises DCPError even if the problem is actually convex.

# DCP-compliant:
cp.norm(x, 1)           # convex
cp.quad_form(x, P)      # convex if P is PSD
cp.log_sum_exp(x)       # convex

# NOT DCP-compliant (even if convex):
cp.sqrt(cp.sum_squares(x))  # use cp.norm(x, 2) instead

Think of DCP as a type system for convexity. It trades generality for reliability: if DCP accepts your problem, it is guaranteed convex.

Definition:
Common CVXPY Atoms

CVXPY provides a library of atoms — functions with known convexity:

Atom	Formula	Curvature
`cp.norm(x, p)`	$\\|\mathbf{x}\\|_p$	Convex
`cp.sum_squares(x)`	$\sum x_i^2$	Convex
`cp.quad_form(x, P)`	$\mathbf{x}^T\mathbf{P}\mathbf{x}$	Convex (P PSD)
`cp.log(x)`	$\log(x)$	Concave
`cp.exp(x)`	$e^x$	Convex
`cp.log_sum_exp(x)`	$\log\sum e^{x_i}$	Convex
`cp.lambda_max(X)`	$\lambda_{\max}(\mathbf{X})$	Convex
`cp.lambda_min(X)`	$\lambda_{\min}(\mathbf{X})$	Concave
`cp.trace(X)`	$\mathrm{tr}(\mathbf{X})$	Affine

Definition:
Semidefinite Programming (SDP) in CVXPY

An SDP optimizes over positive semidefinite (PSD) matrices:

$\min_{\mathbf{X}} \mathrm{tr}(\mathbf{C}\mathbf{X}) \quad \text{s.t.} \quad \mathrm{tr}(\mathbf{A}_i \mathbf{X}) = b_i, \; \mathbf{X} \succeq 0$

In CVXPY:

X = cp.Variable((n, n), symmetric=True)
constraints = [X >> 0]  # PSD constraint
constraints += [cp.trace(A_i @ X) == b_i for ...]
prob = cp.Problem(cp.Minimize(cp.trace(C @ X)), constraints)
prob.solve(solver=cp.SCS)

SDPs arise in relaxations of combinatorial problems (MAX-CUT), robust beamforming, and covariance estimation.

Definition:
Second-Order Cone Programming (SOCP)

An SOCP involves second-order cone constraints:

$\|\mathbf{A}_i \mathbf{x} + \mathbf{b}_i\|_2 \le \mathbf{c}_i^T \mathbf{x} + d_i$

In CVXPY, SOCP constraints arise naturally from norm expressions:

x = cp.Variable(n)
constraints = [cp.norm(A @ x + b, 2) <= c @ x + d]

SOCP is more general than LP (linear programming) and QP (quadratic programming) but less general than SDP. Many practical problems — robust least squares, Markowitz portfolio optimization, antenna beamforming — are naturally SOCPs.

Theorem: Strong Duality for Convex Problems

For a convex optimization problem satisfying Slater's condition (there exists a strictly feasible point), strong duality holds:

$p^\star = d^\star$

where $p^\star$ is the primal optimal value and $d^\star$ is the dual optimal value. The dual variables at optimality are the Lagrange multipliers.

Strong duality means you can solve either the primal or the dual and get the same optimal value. CVXPY makes both primal and dual variables available after solving.

Example: LASSO Regression with CVXPY

Solve the LASSO problem $\min_{\mathbf{x}} \frac{1}{2}\|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 + \lambda \|\mathbf{x}\|_1$ for sparse signal recovery.

Solution

CVXPY implementation

import cvxpy as cp
import numpy as np

np.random.seed(42)
m, n = 50, 200  # underdetermined
A = np.random.randn(m, n)
x_true = np.zeros(n)
x_true[:10] = np.random.randn(10)  # 10 nonzero
b = A @ x_true + 0.1 * np.random.randn(m)

lam = 0.1
x = cp.Variable(n)
objective = cp.Minimize(
    0.5 * cp.sum_squares(A @ x - b) + lam * cp.norm(x, 1)
)
prob = cp.Problem(objective)
prob.solve()

print(f"Status: {prob.status}")
print(f"Nonzeros (>0.01): {np.sum(np.abs(x.value) > 0.01)}")
print(f"Recovery error: {np.linalg.norm(x.value - x_true):.4f}")

Regularization path

Sweep $\lambda$ from large (all zeros) to small (least squares):

lambdas = np.logspace(-3, 1, 50)
nnz = []
for lam_val in lambdas:
    lam_param = cp.Parameter(nonneg=True, value=lam_val)
    obj = cp.Minimize(0.5*cp.sum_squares(A@x-b) + lam_param*cp.norm(x,1))
    cp.Problem(obj).solve(warm_start=True)
    nnz.append(np.sum(np.abs(x.value) > 0.01))

Example: SDP for Maximum Cut Relaxation

Relax the MAX-CUT problem on a graph with $n=6$ nodes using semidefinite programming.

Solution

Formulation

The SDP relaxation of MAX-CUT is: $\max \frac{1}{4}\sum_{(i,j) \in E} w_{ij}(1 - X_{ij})$ subject to $X_{ii} = 1$ , $\mathbf{X} \succeq 0$ .

import cvxpy as cp
import numpy as np

n = 6
np.random.seed(42)
W = np.random.rand(n, n)
W = (W + W.T) / 2
np.fill_diagonal(W, 0)

X = cp.Variable((n, n), symmetric=True)
objective = cp.Maximize(
    0.25 * cp.sum(cp.multiply(W, 1 - X))
)
constraints = [X >> 0]
constraints += [X[i, i] == 1 for i in range(n)]

prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.SCS)
print(f"SDP upper bound: {prob.value:.4f}")

Randomized rounding

Extract a cut via Goemans-Williamson rounding:

L = np.linalg.cholesky(X.value + 1e-6*np.eye(n))
best_cut = 0
for _ in range(1000):
    r = np.random.randn(n)
    signs = np.sign(L @ r)
    cut_val = 0.25 * np.sum(W * (1 - np.outer(signs, signs)))
    best_cut = max(best_cut, cut_val)
print(f"Best cut found: {best_cut:.4f}")

LASSO Regularization Path

Explore how the LASSO solution changes as the regularization parameter $\\lambda$ varies from strong (all zeros) to weak (least squares).

Parameters

CVXPY Examples

python

LASSO, SDP, SOCP examples with CVXPY including warm starts and parameter sweeps.

# Code from: ch08/python/cvxpy_examples.py
# Load from backend supplements endpoint

Quick Check

Which of these is NOT a valid DCP expression in CVXPY?

cp.norm(x, 1) + cp.sum_squares(A @ x)

cp.sqrt(cp.sum_squares(x))

cp.quad_form(x, P) where P is PSD

cp.log_sum_exp(x)

Correction:

cp.sqrt(cp.sum_squares(x))

sqrt is concave and increasing, applied to a convex argument. DCP requires nondecreasing+convex or nonincreasing+concave. Use cp.norm(x, 2) instead.

Common Mistake: Reformulating to Satisfy DCP Rules

Mistake:

Writing cp.sqrt(x @ x) instead of cp.norm(x, 2). Both compute $\|\mathbf{x}\|_2$ , but the first violates DCP (concave of convex) while the second is a recognized convex atom.

Correction:

Use CVXPY's built-in atoms whenever possible. Common reformulations:

$\sqrt{\mathbf{x}^T\mathbf{x}} \to$ cp.norm(x, 2)
$\|\mathbf{x}\|_2^2 \to$ cp.sum_squares(x)
$\max(f, g) \to$ cp.maximum(f, g) (both must be convex)
Minimize $\|\mathbf{x}\|_2 \to$ minimize cp.sum_squares(x) (equivalent)

Key Takeaway

Use CVXPY for convex problems, SciPy for non-convex. CVXPY guarantees global optimality for convex problems and catches non-convex formulations at construction time. For non-convex problems, fall back to scipy.optimize.minimize with multiple random restarts.

Disciplined Convex Programming (DCP)

A ruleset for verifying convexity of optimization problems by tracking the curvature (convex/concave/affine) and sign of every sub-expression.

Related: Convex Function

Convex Function

A function $f$ satisfying $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda) f(y)$ for all $x, y$ and $\lambda \in [0,1]$ .

Semidefinite Program (SDP)

An optimization problem where the variable is a symmetric matrix constrained to be positive semidefinite, with a linear objective and affine constraints.

Historical Note: CVXPY and the Convex Optimization Revolution

2000s

Stephen Boyd and Lieven Vandenberghe's textbook Convex Optimization (2004) made the theory accessible. Michael Grant's CVX (2004, MATLAB) and Steven Diamond's CVXPY (2016, Python) turned the theory into practical tools. The key insight was DCP: instead of checking convexity of arbitrary functions (undecidable in general), restrict to compositions of known-convex atoms.

Hierarchy of Convex Problem Classes

Class	Objective	Constraints	Solver	Complexity
LP	Linear	Linear	HiGHS (simplex/IPM)	Polynomial
QP	Quadratic (convex)	Linear	OSQP	Polynomial
SOCP	Linear	SOC + linear	ECOS, SCS	Polynomial
SDP	Linear (trace)	PSD + affine	SCS, MOSEK	Polynomial
GP	Posynomial	Posynomial	ECOS (after transform)	Polynomial

Convex Optimization with CVXPY