Convex Optimization

Why It Matters

Convex optimization is the backbone of modern machine learning. Every local minimum of a convex function is a global minimum, making these problems tractable and reliable. SVMs, linear regression, logistic regression, LASSO, ridge regression, and many neural network subproblems are all convex. Understanding convexity is the single most important concept for anyone building or analyzing optimization-based ML systems.

Convex optimization bridges pure mathematics and practical ML engineering. While non-convex problems (like training deep neural networks) dominate headlines, convex problems form the foundation: they have efficient solvers with provable guarantees, they appear as subroutines in larger algorithms, and many heuristics for non-convex problems work by solving convex relaxations. Mastering this topic means understanding why some optimization problems are "easy" and others are "hard," and having the tools to transform hard problems into tractable ones.

Convex Set

DfConvex Set

A set $C \subseteq \mathbb{R}^n$ is convex if for all $x, y \in C$ and all $\theta \in [0, 1]$ :

\theta x + (1 - \theta) y \in C

Geometrically, this means the line segment connecting any two points in $C$ lies entirely within $C$ . There are no "dents," indentations, or holes.

Intuition

Imagine drawing a rubber band around the boundary of the set. If the rubber band touches every point on the boundary without cutting through the interior, the set is convex. A circle is convex; a crescent moon is not. The intersection of any collection of convex sets is convex, which is a powerful tool for constructing complex convex feasible regions.

ThExamples of Convex Sets

Set	Description	Convex?
$\mathbb{R}^n$	Entire Euclidean space	Yes
Halfspace $\{x : a^Tx \leq b\}$	Linear inequality	Yes
Hyperplane $\{x : a^Tx = b\}$	Linear equality	Yes
Ball $\{x : \\|x - c\\|_2 \leq r\}$	Euclidean ball	Yes
Nonnegative orthant $\mathbb{R}^n_+$	$\{x : x_i \geq 0\}$	Yes
Simplex $\Delta_n$	$\{x : x_i \geq 0, \sum x_i = 1\}$	Yes
Positive semidefinite cone $\mathcal{S}^n_+$	$\{X : X \succeq 0\}$	Yes
Set with a bite taken out	$\{x : \\|x\\|_2 \leq 1\} \setminus \{x : \\|x\\|_2 \leq 0.5\}$	No

Problem: Is the Intersection Convex?

Is the set $C = \{x \in \mathbb{R}^2 : x_1^2 + x_2^2 \leq 1, \; x_1 + x_2 \geq 1\}$ convex?

Solution

Yes. The set $C$ is the intersection of a disk $\{x : x_1^2 + x_2^2 \leq 1\}$ (convex) and a halfspace $\{x : x_1 + x_2 \geq 1\}$ (convex). The intersection of convex sets is convex. Geometrically, $C$ is a circular segment.

Convex Function

DfConvex Function

A function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if its domain $\text{dom}(f)$ is a convex set and for all $x, y \in \text{dom}(f)$ and $\theta \in [0, 1]$ :

f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y)

This is the epigraph condition: the line segment connecting $(x, f(x))$ and $(y, f(y))$ lies on or above the graph of $f$ . A function is concave if $-f$ is convex.

Intuition

A convex function curves "upward" everywhere. If you stand on the graph and look along the curve, the ground always rises in both directions. This means there are no "dips" that create local minima distinct from the global minimum. The epigraph $\{(x, t) : f(x) \leq t\}$ is a convex set — this connects convex functions to convex sets.

First-Order Condition

ThFirst-Order Optimality Condition

A differentiable function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if and only if for all $x, y \in \text{dom}(f)$ :

f(y) \geq f(x) + \nabla f(x)^T (y - x)

The tangent hyperplane at any point lies on or below the graph. This is the global linear lower bound characterization. Moreover, $x^*$ is a global minimum of a convex function $f$ if and only if:

\nabla f(x^*) = 0

Second-Order Condition

ThSecond-Order Condition

A twice-differentiable function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if and only if its Hessian is positive semidefinite everywhere:

\nabla^2 f(x) \succeq 0 \quad \forall x \in \text{dom}(f)

For strict convexity, we need $\nabla^2 f(x) \succ 0$ (positive definite) everywhere. For functions of one variable, this reduces to $f''(x) \geq 0$ .

Strict vs. Strong Convexity

Strict convexity ( $\nabla^2 f \succ 0$ ) guarantees a unique minimizer but says nothing about the "flatness" near the minimum. Strong convexity (defined below) adds a curvature lower bound and gives much stronger convergence guarantees.

Common Convex and Non-Convex Functions

Function	Convex?	Notes
$f(x) = c$	Yes	Constant functions are convex (and concave)
$f(x) = x^2$	Yes	Strictly convex
$f(x) = e^x$	Yes	Strictly convex, $f''(x) = e^x > 0$
$f(x) = -\log(x)$	Yes	Strictly convex on $(0, \infty)$
$f(x) = \\|x\\|$	Yes	Convex but not differentiable at 0
$f(x) = x^4$	Yes	Strictly convex, though $f''(0) = 0$
$f(x) = x^3$	No	Inflection point at $x = 0$
$f(x) = \sin(x)$	No	Concave and convex regions
$f(x) = 1/x$	No	On $\mathbb{R}$ ; convex on $(0, \infty)$
$f(X) = \log\det(X)$	Yes	On $\mathcal{S}^n_{++}$ (positive definite cone)
$f(x) = \\|x\\|_2^2 + \\|x\\|_1$	Yes	Sum of convex functions
$f(x) = x_1 x_2$	No	Bilinear (saddle-shaped)

Properties of Convex Functions

ThFundamental Properties of Convex Functions

Let $f, g$ be convex functions and $\alpha \geq 0$ .

1. Non-negative weighted sums are convex:

h(x) = \alpha f(x) + \beta g(x) \text{ is convex for } \alpha, \beta \geq 0

2. Pointwise maximum preserves convexity:

h(x) = \max(f(x), g(x)) \text{ is convex}

3. Affine composition preserves convexity:

h(x) = f(Ax + b) \text{ is convex}

4. Perspective scaling preserves convexity:

h(x, t) = t \cdot f(x/t) \text{ is convex on } \{(x, t) : t > 0\}

5. Partial minimization preserves convexity: If $g(x, y)$ is convex in $(x, y)$ and $C$ is a convex set, then $h(x) = \inf_{y \in C} g(x, y)$ is convex.

6. Supremum of convex functions is convex:

f(x) = \sup_{\alpha \in \mathcal{A}} f_\alpha(x) \text{ is convex if each } f_\alpha \text{ is convex}

7. Restriction to a line preserves convexity: $f$ is convex if and only if $g(t) = f(x + tv)$ is convex in $t$ for all $x \in \text{dom}(f)$ and all directions $v$ .

Building Complex Convex Functions

These closure properties are extraordinarily powerful. You can build complex convex functions from simple building blocks: norms, quadratics, logs, and exponentials. For example, $f(x) = \log(e^{x_1} + e^{x_2})$ is convex because it is the composition of the convex function $\log(\cdot)$ applied to the convex sum of exponentials (log-sum-exp). Most convex functions encountered in ML are constructed this way.

Strongly Convex Functions

DfStrongly Convex Function

A function $f: \mathbb{R}^n \to \mathbb{R}$ is $m$ -strongly convex ( $m > 0$ ) if for all $x, y \in \text{dom}(f)$ and $\theta \in [0, 1]$ :

f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y) - \frac{m}{2}\theta(1-\theta)\|x - y\|^2

Equivalently, a differentiable $f$ is $m$ -strongly convex if and only if:

f(y) \geq f(x) + \nabla f(x)^T(y - x) + \frac{m}{2}\|y - x\|^2 \quad \forall x, y

Or in terms of the Hessian: $\nabla^2 f(x) \succeq mI$ for all $x$ .

ThStrong Convexity Gives Linear Convergence

If $f$ is $m$ -strongly convex and $L$ -smooth (gradient is $L$ -Lipschitz), then gradient descent with step size $\alpha = 1/L$ satisfies:

f(x_k) - f^* \leq \left(\frac{L - m}{L + m}\right)^{2k} (f(x_0) - f^*)

The convergence rate $\rho = \frac{L-m}{L+m} < 1$ is linear. The condition number $\kappa = L/m$ controls the rate: smaller $\kappa$ means faster convergence.

Problem: Strong Convexity of Quadratic

Show that $f(x) = \frac{1}{2}x^TAx + b^Tx + c$ with $A \succ 0$ is $m$ -strongly convex where $m = \lambda_{\min}(A)$ .

Solution

The Hessian is $\nabla^2 f(x) = A$ . Since $A$ is positive definite with minimum eigenvalue $\lambda_{\min}(A) > 0$ , we have $A \succeq \lambda_{\min}(A) I$ . Thus $f$ is $\lambda_{\min}(A)$ -strongly convex. This gives linear convergence rate $\rho = \frac{\lambda_{\max}(A) - \lambda_{\min}(A)}{\lambda_{\max}(A) + \lambda_{\min}(A)}$ .

Convex Optimization Problem

DfConvex Optimization Problem

A convex optimization problem has the form:

\min_x f(x) \quad \text{s.t.} \quad g_i(x) \leq 0 \; (i = 1, \ldots, m), \quad h_j(x) = 0 \; (j = 1, \ldots, p)

where $f$ and each $g_i$ are convex functions, and each $h_j$ is affine (linear). The feasible set is convex (intersection of convex sets and hyperplanes), and the objective is convex over this set.

Why Affine Equality Constraints Only

Equality constraints must be affine because a nonlinear equality $h(x) = 0$ defines a non-convex feasible set (it's a lower-dimensional manifold with no "interior"). For example, $x^2 + y^2 = 1$ (a circle) is not a convex set — you can find two points on the circle whose midpoint is not on the circle.

ThKey Properties of Convex Optimization

1. Local = Global: Every local minimum of a convex problem is a global minimum.

2. Uniqueness: If $f$ is strictly convex, the minimizer $x^*$ is unique.

3. Optimality conditions: $x^*$ is optimal if and only if:

\nabla f(x^*)^T (y - x^*) \geq 0 \quad \forall y \in \mathcal{F}

where $\mathcal{F}$ is the feasible set. For unconstrained problems, this reduces to $\nabla f(x^*) = 0$ .

4. Computational tractability: Convex problems can be solved in polynomial time (in theory and practice) using interior-point methods.

5. Duality: The dual of a convex problem provides lower bounds, optimality certificates, and insight into constraint sensitivity.

Common Convex Problems

Linear Programming (LP)

DfLinear Program

A linear program has the form:

\min_x c^Tx \quad \text{s.t.} \quad Ax \leq b, \quad A_{eq}x = b_{eq}

The objective and constraints are all linear. LP is the simplest class of convex optimization and can be solved in polynomial time using interior-point methods (or the simplex method in practice).

LP Applications

LP appears in resource allocation, scheduling, network flow, production planning, and as a relaxation for combinatorial problems. The dual of an LP is also an LP (LP duality is exact).

Quadratic Programming (QP)

DfQuadratic Program

A quadratic program has the form:

\min_x \frac{1}{2}x^TQx + c^Tx \quad \text{s.t.} \quad Ax \leq b

where $Q \succeq 0$ (positive semidefinite) ensures convexity. If $Q \succ 0$ (positive definite), the problem is strictly convex.

QP Applications

Ridge regression ( $\min \|y - Xw\|^2 + \lambda\|w\|^2$ ) is an unconstrained QP. SVMs with linear kernel are QPs. Portfolio optimization (Markowitz) is a QP. Model predictive control (MPC) solves a QP at each time step.

Second-Order Cone Programming (SOCP)

DfSecond-Order Cone Program

An SOCP has the form:

\min_x c^Tx \quad \text{s.t.} \quad \|A_ix + b_i\|_2 \leq c_i^Tx + d_i \quad (i = 1, \ldots, m)

SOCPs generalize LPs and QPs. The constraint $\|Ax + b\|_2 \leq c^Tx + d$ is a second-order (Lorentz) cone constraint.

SOCP Applications

SOCPs arise in robust optimization (worst-case constraints), portfolio optimization with transaction costs, antenna design, and signal processing. Many problems that appear nonlinear can be reformulated as SOCPs.

Semidefinite Programming (SDP)

DfSemidefinite Program

An SDP has the form:

\min_X \text{tr}(CX) \quad \text{s.t.} \quad \text{tr}(A_iX) = b_i \; (i = 1, \ldots, m), \quad X \succeq 0

The variable $X$ is a symmetric positive semidefinite matrix. SDPs generalize LPs (when $X$ is diagonal) and are among the most powerful convex optimization formulations.

SDP Applications

SDPs appear in relaxation of combinatorial problems (MAX-CUT, graph coloring), control theory (LMI conditions), quantum information, and polynomial optimization. The Goemans-Williamson algorithm for MAX-CUT uses an SDP relaxation.

Problem Hierarchy

ThConvex Optimization Hierarchy

Each problem class is a special case of the one below it:

\text{LP} \subset \text{QP} \subset \text{SOCP} \subset \text{SDP} \subset \text{Conic}

Solvers like MOSEK and ECOS handle SOCPs and SDPs natively. For LPs, solvers like Gurobi and CLPK are extremely fast. CVXPY automatically transforms problems into the appropriate form.

Duality

DfLagrangian Dual

Given the convex optimization problem:

\min_x f(x) \quad \text{s.t.} \quad g_i(x) \leq 0 \; (i=1,\ldots,m), \quad h_j(x) = 0 \; (j=1,\ldots,p)

the Lagrangian is:

\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \nu_j h_j(x)

The Lagrangian dual function is:

g(\lambda, \nu) = \inf_{x \in \text{dom}(f)} \mathcal{L}(x, \lambda, \nu)

The dual problem is:

\max_{\lambda \geq 0, \, \nu} g(\lambda, \nu)

Intuition

The dual function $g(\lambda, \nu)$ provides a lower bound on the optimal value $p^*$ of the primal problem for any $\lambda \geq 0, \nu$ . By maximizing this lower bound, we find the tightest possible bound — this is the dual problem. The dual is always convex (even if the primal is not), because it is the pointwise infimum of affine functions in $(\lambda, \nu)$ .

Weak and Strong Duality

ThWeak and Strong Duality

Let $p^*$ be the optimal value of the primal and $d^*$ be the optimal value of the dual.

Weak Duality (always holds):

d^* \leq p^*

The dual optimal value is always a lower bound on the primal optimal value. The gap $p^* - d^*$ is called the duality gap.

Strong Duality (for convex problems under constraint qualifications):

d^* = p^*

Strong duality holds for convex problems when Slater's condition is satisfied: there exists a strictly feasible point $x$ with $g_i(x) < 0$ for all $i$ and $h_j(x) = 0$ for all $j$ .

KKT Conditions and Strong Duality

When strong duality holds, the KKT conditions are both necessary and sufficient for optimality. The dual variables $\lambda_i, \nu_j$ at the optimum are the Lagrange multipliers. Complementary slackness ( $\lambda_i g_i(x^*) = 0$ ) ensures that only active constraints have nonzero multipliers. The dual variables quantify how much the optimal value changes per unit relaxation of each constraint — they are shadow prices.

Dual Interpretation in ML

Dual Variables in Machine Learning

In SVMs, the dual variables $\alpha_i$ are nonzero only for support vectors. In regularization, the dual variable $\lambda$ represents the trade-off between fit and complexity. In fairness-constrained ML, dual variables measure the "cost of fairness" — how much accuracy is sacrificed per unit of fairness enforcement. Understanding duality gives you insight into which constraints are binding and which data points matter.

Python Implementation

Using CVXPY

import cvxpy as cp
import numpy as np

# ============================================
# Example 1: Linear Program
# Minimize cost subject to constraints
# ============================================

n = 4  # number of variables
c = np.array([1.0, 2.0, 3.0, 4.0])  # cost vector
A = np.array([[1, 1, 0, 0],
              [0, 0, 1, 1],
              [1, 0, 1, 0]])
b = np.array([10.0, 8.0, 12.0])

x = cp.Variable(n)
constraints = [A @ x <= b, x >= 0]
objective = cp.Minimize(c @ x)
prob = cp.Problem(objective, constraints)
prob.solve()

print(f"Status: {prob.status}")
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {x.value}")

# ============================================
# Example 2: Quadratic Program (Ridge Regression)
# ============================================

np.random.seed(42)
m, n = 50, 10
X = np.random.randn(m, n)
y = X @ np.random.randn(n) + 0.1 * np.random.randn(m)

w = cp.Variable(n)
lam = 0.5  # regularization parameter
objective = cp.Minimize(0.5 * cp.sum_squares(y - X @ w) + lam * cp.squares(w))
prob = cp.Problem(objective)
prob.solve()

print(f"\nRidge regression:")
print(f"Optimal w: {w.value[:3]}...")
print(f"Optimal loss: {prob.value:.4f}")

# ============================================
# Example 3: Second-Order Cone Program
# ============================================

x_socp = cp.Variable(3)
A_socp = np.array([[1, 0, 0], [0, 1, 0]])
b_socp = np.array([0.5, 0.5])
c_socp = np.array([1.0, 2.0, 3.0])

objective = cp.Minimize(c_socp @ x_socp)
constraints = [cp.norm(A_socp @ x_socp - b_socp, 2) <= 1.0]
prob = cp.Problem(objective, constraints)
prob.solve()

print(f"\nSOCP:")
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {x_socp.value}")

# ============================================
# Example 4: Semidefinite Program
# ============================================

X_sdp = cp.Variable((3, 3), symmetric=True)
C = np.array([[1, 0, 0], [0, 2, 0], [0, 0, 3]])
A1 = np.array([[1, 0, 0], [0, 0, 0], [0, 0, 0]])

objective = cp.Minimize(cp.trace(C @ X_sdp))
constraints = [cp.trace(A1 @ X_sdp) == 1, X_sdp >> 0]  # X >> 0 means PSD
prob = cp.Problem(objective, constraints)
prob.solve()

print(f"\nSDP:")
print(f"Optimal value: {prob.value:.4f}")
print(f"X is PSD: {np.all(np.linalg.eigvals(X_sdp.value) > -1e-8)}")

Using SciPy

from scipy.optimize import minimize, LinearConstraint, NonlinearConstraint

# ============================================
# Example 1: Unconstrained convex function
# ============================================

f = lambda x: (x[0] - 1)**2 + (x[1] - 2)**2
grad_f = lambda x: np.array([2*(x[0] - 1), 2*(x[1] - 2)])

result = minimize(f, x0=[0.0, 0.0], jac=grad_f, method='L-BFGS-B')
print(f"Unconstrained minimum: x = {result.x}, f(x) = {result.fun:.6f}")

# ============================================
# Example 2: Linear constraints (box constraints)
# ============================================

f2 = lambda x: (x[0] - 2)**2 + (x[1] - 3)**2
bounds = [(0, 4), (0, 4)]

result = minimize(f2, x0=[0, 0], bounds=bounds, method='L-BFGS-B')
print(f"Box-constrained: x = {result.x}, f(x) = {result.fun:.6f}")

# ============================================
# Example 3: Equality and inequality constraints
# ============================================

f3 = lambda x: x[0]**2 + x[1]**2 + x[2]**2
jac_f3 = lambda x: np.array([2*x[0], 2*x[1], 2*x[2]])

constraints = [
    {'type': 'eq', 'fun': lambda x: x[0] + x[1] + x[2] - 1},
    {'type': 'ineq', 'fun': lambda x: x[0] - 0.1},  # x[0] >= 0.1
    {'type': 'ineq', 'fun': lambda x: x[1] - 0.1},  # x[1] >= 0.1
]

result = minimize(f3, x0=[1/3, 1/3, 1/3], jac=jac_f3, constraints=constraints, method='SLSQP')
print(f"Constrained: x = {result.x}, f(x) = {result.fun:.6f}")

Applications in AI/ML

Support Vector Machines

SVM as Convex Optimization

The SVM primal problem is:

\min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^Tx_i + b) \geq 1 \; \forall i

This is a convex QP. The dual is also a convex QP, and complementary slackness reveals that only support vectors ( $\alpha_i > 0$ ) determine the decision boundary. The kernel trick works because the dual depends only on dot products $x_i^Tx_j$ .

Ridge Regression (Tikhonov Regularization)

Ridge Regression

w^* = \arg\min_w \|y - Xw\|_2^2 + \lambda\|w\|_2^2

Here,

$X$ =Design matrix (n x p)
$y$ =Response vector (n x 1)
$\lambda$ =Regularization strength
$w$ =Parameter vector (p x 1)

The closed-form solution is $w^* = (X^TX + \lambda I)^{-1}X^Ty$ . This is a strictly convex problem (quadratic with $X^TX + \lambda I \succ 0$ ), guaranteeing a unique global minimum. Ridge regression is an unconstrained QP and is convex for any $\lambda > 0$ .

LASSO Regression

w^* = \arg\min_w \|y - Xw\|_2^2 + \lambda\|w\|_1

Here,

$\|w\|_1$ =L1 norm inducing sparsity
$\lambda$ =Regularization strength

LASSO is convex (the L1 norm is convex) but not differentiable at $w_i = 0$ . It promotes sparsity — many coefficients are driven exactly to zero, performing automatic feature selection. The proximal gradient method (ISTA/FISTA) is the standard solver.

Logistic Regression

Logistic Regression as Convex Optimization

The negative log-likelihood for logistic regression is:

f(w) = -\sum_{i=1}^{n} \left[ y_i \log(\sigma(w^Tx_i)) + (1-y_i)\log(1-\sigma(w^Tx_i)) \right]

This is convex in $w$ (though nonlinear), and is a fundamental building block of ML pipelines. It can be solved by gradient descent, Newton's method, or interior-point methods.

Neural Network Training (Non-Convex but Informed)

Convexity in Deep Learning

Training a neural network is non-convex — the loss landscape has many local minima and saddle points. However, convex optimization concepts still apply: (1) many local minima are nearly as good as the global minimum; (2) batch normalization and skip connections make the landscape "more convex"; (3) second-order methods use Hessian information; (4) convex relaxations provide bounds on the global minimum.

Common Mistakes

Mistake	Why It's Wrong	Correct Approach
Assuming $f''(x) > 0$ means convex everywhere	$f''(x) \geq 0$ is necessary for convexity, but a function can be convex even if $f'' = 0$ at isolated points (e.g., $f(x) = x^4$ )	Check $\nabla^2 f(x) \succeq 0$ for all $x$ in the domain
Confusing convex and concave	Many people mix up "convex up" vs "convex down"	Convex = bowl-shaped (holds water); concave = umbrella-shaped
Treating local minima as global minima in non-convex problems	Local minima in non-convex problems may be far from global minima	Use convex relaxations, multi-start, or second-order methods
Forgetting that equality constraints must be affine	$h(x) = x^2 + y^2 - 1 = 0$ does NOT define a convex feasible set	Nonlinear equalities create non-convex manifolds
Ignoring Slater's condition	Strong duality requires strict feasibility	Verify $\exists x: g_i(x) < 0$ and $h_j(x) = 0$
Assuming all norms lead to convex problems	Some non-convex norms (like $L_0$ ) do not	Use $L_1$ , $L_2$ , or other convex norms
Using gradient descent without checking Lipschitz continuity	Non-Lipschitz gradients can cause divergence	Verify or bound the Lipschitz constant $L$
Not checking if the Hessian is PSD	Using Newton's method on a non-convex function may find saddle points	Check eigenvalues of $\nabla^2 f$ or use trust-region methods
Assuming the sum of convex functions is always strictly convex	Sum of convex functions is convex, but may not be strictly convex	$f(x) = x^4 + (-x^4) = 0$ is convex but not strictly convex
Forgetting perspective scaling	$f(x/t) \cdot t$ is convex in $(x, t)$ but many miss this	Use perspective to handle fractional objectives

Interview Questions

Q1: What is the difference between convex and strictly convex?

Answer

A convex function satisfies $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$ . A strictly convex function satisfies the strict inequality $f(\theta x + (1-\theta)y) < \theta f(x) + (1-\theta)f(y)$ for $\theta \in (0,1)$ and $x \neq y$ . Convexity guarantees local = global; strict convexity additionally guarantees the global minimum is unique. However, strict convexity does not imply strong convexity — $f(x) = x^4$ is strictly convex but not strongly convex (the Hessian vanishes at 0).

Q2: Why are convex problems easier to solve than non-convex problems?

Answer

Convex problems have three key properties: (1) every local minimum is a global minimum, so first-order methods (gradient descent) can find the optimum without getting stuck in local minima; (2) the KKT conditions are necessary and sufficient for optimality, providing a verifiable optimality certificate; (3) polynomial-time algorithms exist (interior-point methods). Non-convex problems may have exponentially many local minima, no efficient way to certify global optimality, and can be NP-hard in the worst case.

Q3: What is Slater's condition and why does it matter?

Answer

Slater's condition requires the existence of a strictly feasible point: $\exists x$ in the relative interior of $\text{dom}(f)$ such that $g_i(x) < 0$ for all inequality constraints and $h_j(x) = 0$ for all equality constraints. When Slater's condition holds for a convex problem, strong duality holds ( $p^* = d^*$ ), meaning the dual optimal value equals the primal optimal value and the duality gap is zero. This enables: (1) recovering the primal solution from the dual; (2) using dual methods to solve the primal; (3) obtaining sensitivity information from dual variables. For linear programs, strong duality always holds (no Slater's condition needed).

Q4: How does strong convexity improve convergence?

Answer

Strong convexity ( $\nabla^2 f \succeq mI$ ) ensures the gradient grows linearly away from the optimum: $\|\nabla f(x)\| \geq m\|x - x^*\|$ . This gives linear convergence for gradient descent with rate $\rho = \frac{L-m}{L+m}$ , compared to sublinear $O(1/k)$ for general convex functions. The condition number $\kappa = L/m$ controls the rate: $\kappa = 1$ (perfectly conditioned) gives immediate convergence; large $\kappa$ gives slow convergence. Preconditioning reduces $\kappa$ by transforming the problem.

Q5: Explain the dual of an SVM and its significance.

Answer

The SVM primal maximizes the margin $\frac{2}{\|w\|}$ subject to $y_i(w^Tx_i + b) \geq 1$ . Introducing dual variables $\alpha_i \geq 0$ and applying KKT yields the dual: $\max_\alpha \sum \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i\alpha_j y_iy_j x_i^Tx_j$ subject to $\alpha_i \geq 0$ and $\sum \alpha_iy_i = 0$ . Significance: (1) it depends only on dot products, enabling the kernel trick; (2) complementary slackness ( $\alpha_i > 0$ only for support vectors) identifies which training points matter; (3) the dual is a QP with $n$ variables, independent of the feature dimension — useful when $n \ll d$ .

Q6: What happens when strong duality does not hold?

Answer

When strong duality fails, there is a nonzero duality gap $p^* - d^* > 0$ . The dual provides a lower bound but not the exact value. This can happen when: (1) the problem is not convex (Slater's condition is sufficient but not necessary for convex problems); (2) the problem is convex but Slater's condition fails (no strictly feasible point exists); (3) the problem involves integer constraints (combinatorial optimization). In practice, the duality gap can be used as a stopping criterion for interior-point methods — terminate when $p^* - d^* < \epsilon$ .

Practice Problems

Problem 1: Verify Convexity

Convexity Check

Show that $f(x, y) = e^{x+y} + x^2 + y^2$ is convex on $\mathbb{R}^2$ .

Solution

Compute the Hessian:

\nabla^2 f = \begin{pmatrix} e^{x+y} + 2 & e^{x+y} \\ e^{x+y} & e^{x+y} + 2 \end{pmatrix}

The eigenvalues of $\begin{pmatrix} a & b \\ b & a \end{pmatrix}$ are $a + b$ and $a - b$ where $a = e^{x+y} + 2$ and $b = e^{x+y}$ .

Eigenvalues: $\lambda_1 = 2e^{x+y} + 2 > 0$ and $\lambda_2 = 2 > 0$ .

Since $\nabla^2 f \succ 0$ everywhere, $f$ is strictly convex.

Problem 2: Duality Gap

Non-Convex Problem

Consider $f(x) = x^3$ on the interval $[-1, 1]$ . What can you say about the duality gap if we form a Lagrangian dual?

Solution

$f(x) = x^3$ is not convex (it has an inflection point at $x = 0$ ). The unconstrained minimum on $[-1, 1]$ is at $x = -1$ with $f(-1) = -1$ . However, since the problem is non-convex, we cannot guarantee that the dual provides a tight lower bound — there may be a duality gap. The KKT conditions may identify saddle points or local minima that are not global.

Problem 3: Ridge Regression Closed Form

Derive Ridge Regression Solution

Derive the closed-form solution for $w^* = \arg\min_w \|y - Xw\|^2 + \lambda\|w\|^2$ .

Solution

Expand the objective:

f(w) = y^Ty - 2y^TXw + w^TX^TXw + \lambda w^Tw

Take the gradient and set to zero:

\nabla f(w) = -2X^Ty + 2X^TXw + 2\lambda w = 0

X^TXw + \lambda w = X^Ty

(X^TX + \lambda I)w = X^Ty

w^* = (X^TX + \lambda I)^{-1}X^Ty

This exists for all $\lambda > 0$ because $X^TX + \lambda I \succ 0$ . The problem is strictly convex, so this is the unique global minimum.

Problem 4: Strong Convexity Certificate

Strong Convexity of Logistic Loss

Show that the logistic loss $\ell(z) = \log(1 + e^{-z})$ is convex but not strongly convex.

Solution

First derivative: $\ell'(z) = \frac{-e^{-z}}{1 + e^{-z}} = -\sigma(-z)$ .

Second derivative: $\ell''(z) = \sigma(z)(1 - \sigma(z))$ where $\sigma(z) = \frac{1}{1+e^{-z}}$ .

Since $\sigma(z) \in (0, 1)$ , we have $\ell''(z) > 0$ for all $z$ , so the logistic loss is strictly convex.

However, $\ell''(z) \to 0$ as $|z| \to \infty$ (since $\sigma(z)(1-\sigma(z)) \to 0$ ). There is no $m > 0$ such that $\ell''(z) \geq m$ for all $z$ . Therefore the logistic loss is convex and strictly convex, but not strongly convex.

Quick Reference

Key Takeaways

Convex Set: A set $C$ is convex if every convex combination $\theta x + (1-\theta)y \in C$ for $\theta \in [0,1]$ . Intersections of convex sets are convex.
Convex Function: $f$ is convex if $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$ . First-order condition: tangent hyperplanes are global underestimators. Second-order: $\nabla^2 f(x) \succeq 0$ .
Strong Convexity: $f$ is $m$ -strongly convex if $\nabla^2 f(x) \succeq mI$ . This gives linear convergence rate $\rho = \frac{L-m}{L+m}$ for gradient descent.
Convex Optimization Problem: Minimize convex $f$ subject to convex $g_i \leq 0$ and affine $h_j = 0$ . Every local minimum is a global minimum.
Problem Hierarchy: LP $\subset$ QP $\subset$ SOCP $\subset$ SDP. Each class includes the previous one.
Duality: The Lagrangian dual provides a lower bound. Strong duality ( $d^* = p^*$ ) holds for convex problems under Slater's condition.
KKT Conditions: Stationarity, primal feasibility, dual feasibility ( $\lambda \geq 0$ ), and complementary slackness ( $\lambda_i g_i = 0$ ) are necessary and sufficient for optimality when strong duality holds.
Applications: SVMs (QP with kernel trick), ridge regression (closed-form QP), LASSO (convex but non-smooth), logistic regression (convex nonlinear).
Python: Use CVXPY for modeling and solving convex problems; use SciPy for smaller problems with manual constraint specification.
Key Insight: Convexity is the dividing line between "tractable" and "intractable" optimization. If your problem is convex, you can solve it efficiently and certify global optimality.

Cross-References

Constrained Optimization: KKT conditions, penalty methods, and interior-point methods -> Constrained Optimization
Gradient Descent: First-order methods for convex optimization -> Gradient Descent
Newton's Method: Second-order methods using Hessian curvature -> Newton's Method
Linear Algebra: Positive Definite Matrices: Hessian and PSD conditions for convexity -> Positive Definite
Linear Algebra: Norms: Norms used in regularization constraints -> Norms
Matrix Calculus: Derivatives of matrix-valued functions for SDP and SVM -> Matrix Calculus
Linear Programming: Specialized methods for LP problems -> Linear Programming
Quadratic Programming: Specialized methods for QP problems -> Quadratic Programming
Lagrange Multipliers: Foundation for duality and KKT -> Lagrange Multipliers
Multivariable Calculus: Gradients, Jacobians, and Hessians -> Multivariable Calculus