Convex Optimization Problems

A convex optimization problem (also called a convex program) is an optimization problem of the standard form

where the objective $f_0$ and every inequality-constraint function $f_i$ are convex functions, and every equality constraint $h_j$ is affine (linear plus a constant). The feasible set $\mathcal{F} = \{x : f_i(x) \le 0 \ \forall i, \ h_j(x) = 0 \ \forall j\}$ is automatically a convex set, because sublevel sets of convex functions are convex and affine equality constraints define hyperplanes, and an intersection of convex sets is convex. The decision variable $x \in \mathbb{R}^n$ ranges over this feasible set, and the goal is to find $x^\star \in \mathcal{F}$ achieving the smallest possible value of $f_0$. The optimal value is denoted $p^\star = f_0(x^\star)$, and a point achieving it is called a global minimizer. Crucially, restricting attention to convex $f_i$ (rather than allowing arbitrary constraint functions) is what guarantees $\mathcal{F}$ is convex; convexity of the feasible set together with convexity of $f_0$ is the entire source of the good behavior of these problems. Two further pieces of vocabulary matter. A point $x$ is a local minimizer if $f_0(x) \le f_0(y)$ for all feasible $y$ in some neighborhood of $x$. The problem is said to satisfy Slater's condition if there exists a strictly feasible point — one satisfying every inequality constraint with strict inequality (and the equality constraints exactly). Slater's condition is the standard regularity assumption that makes duality theory (below) airtight. Many ML objectives fit this template directly: minimizing squared error subject to an $\ell_2$-norm ball (ridge regression as a constrained program), minimizing hinge loss subject to margin constraints (SVMs), or minimizing negative log-likelihood over probability simplices (maximum likelihood for discrete models).

The "mechanism" of a convex program is not a single algorithm but a characterization: a system of conditions that a point must satisfy if and only if it is optimal. Solvers (gradient descent, interior-point methods, coordinate descent) are procedures for finding a point that satisfies these conditions; this article focuses on the conditions themselves, since they are what "convexity" buys you.

Step 1 — Unconstrained case. If there are no constraints ($\mathcal{F} = \mathbb{R}^n$) and $f_0$ is differentiable, the first-order condition is

For a convex function this is not merely necessary (as it is for any smooth function) — it is also sufficient for global optimality. This equivalence fails completely for non-convex functions, where $\nabla f_0(x)=0$ only identifies a critical point (which could be a saddle or local min/max).

Step 2 — Constrained, differentiable case (first-order optimality condition). For a general convex feasible set $\mathcal{F}$ and differentiable convex $f_0$, $x^\star$ is optimal if and only if

Geometrically: there is no feasible direction that is a descent direction. The gradient "points against" every feasible perturbation.

Step 3 — Lagrangian and dual function. For the general standard form with inequality and equality constraints, define the Lagrangian

with dual variables (Lagrange multipliers) $\lambda_i \ge 0$ and $\nu_j \in \mathbb{R}$ free. The dual function

is always concave in $(\lambda,\nu)$ — even if the primal problem were not convex — because it is a pointwise infimum of affine functions of $(\lambda, \nu)$.

Step 4 — Weak duality. For any feasible $x$ and any $\lambda \ge 0$,

since $f_i(x)\le 0$, $\lambda_i \ge 0$ implies $\lambda_i f_i(x) \le 0$, and $h_j(x) = 0$ kills the equality terms. Taking the supremum over dual variables and infimum over primal feasible $x$ gives

This holds unconditionally, for convex or non-convex problems — it is why duality is often used to certify lower bounds even for hard combinatorial relaxations.

Step 5 — Strong duality and KKT conditions. When the primal problem is convex and Slater's condition holds, strong duality holds: $d^\star = p^\star$, and the optimal primal-dual pair $(x^\star, \lambda^\star, \nu^\star)$ satisfies the Karush-Kuhn-Tucker (KKT) conditions: 1. Primal feasibility: $f_i(x^\star) \le 0$, $h_j(x^\star)=0$. 2. Dual feasibility: $\lambda_i^\star \ge 0$. 3. Complementary slackness: $\lambda_i^\star f_i(x^\star) = 0$ for all $i$. 4. Stationarity: $\nabla_x L(x^\star,\lambda^\star,\nu^\star) = 0$, i.e.

For a convex program with differentiable functions, these four conditions are necessary and sufficient for global optimality — this is the workhorse fact used to derive closed-form or semi-closed-form solutions in ML (support vectors, dual SVM formulation, ridge/lasso stationarity equations). ```text ALGORITHM: Verify-KKT (certificate check, not a solver) Input: candidate point x, candidate multipliers λ (≥0), ν functions f0, f1..fm (convex), h1..hp (affine) 1. Feasibility check: for i in 1..m: if f_i(x) > 0: return "INFEASIBLE" for j in 1..p: if h_j(x) != 0: return "INFEASIBLE" 2. Dual feasibility: for i in 1..m: if λ_i < 0: return "NOT KKT" 3. Complementary slackness: for i in 1..m: if λ_i f_i(x) != 0: return "NOT KKT" 4. Stationarity: g <- grad(f0)(x) + sum_i λ_i grad(f_i)(x) + sum_j ν_j * grad(h_j)(x) if norm(g) > tolerance: return "NOT KKT" 5. All checks passed AND problem is convex with Slater's condition: return "x IS GLOBALLY OPTIMAL" ``` ```text ALGORITHM: Projected-Gradient (a generic solver exploiting convexity) Input: convex f0, convex feasible set F with projection oracle Π_F, step sizes η_t, initial point x0 in F for t = 0, 1, 2, ... until convergence: x_{t+1} <- Π_F( x_t - η_t * grad(f0)(x_t) ) return x_{t+1} ``` The projected-gradient method is a concrete solver: each step moves downhill along $-\nabla f_0$, then projects back onto $\mathcal{F}$ (projection onto a convex set is itself a well-posed convex problem, uniquely solvable). Because $f_0$ is convex, every iterate's objective value is compared against a single global optimum, so decreasing the objective always means making progress toward $x^\star$ — no risk of sliding into a different, worse basin.

Correctness — why local optimality implies global optimality. This is the theorem that justifies calling convexity "the great divide" in optimization. Suppose $x^\star$ is a local minimizer of a convex program but is not global: some feasible $y$ has $f_0(y) < f_0(x^\star)$. Consider the segment $z_t = (1-t)x^\star + t y$ for $t \in [0,1]$, which lies in $\mathcal{F}$ by convexity of the feasible set. By convexity of $f_0$,

As $t \to 0^+$, $z_t \to x^\star$, and $f_0(z_t) < f_0(x^\star)$ arbitrarily close to $x^\star$ — contradicting that $x^\star$ is a local minimum (which requires $f_0(x^\star) \le f_0(z)$ for all feasible $z$ near $x^\star$). Hence no such $y$ exists, and every local minimizer is global. This argument uses convexity of both $f_0$ and $\mathcal{F}$; if $\mathcal{F}$ were non-convex, the segment $z_t$ might leave the feasible set and the contradiction would evaporate.

Correctness — why the first-order condition is sufficient. Suppose $\nabla f_0(x^\star)^\top(y - x^\star) \ge 0$ for all feasible $y$. Convexity of $f_0$ gives the first-order global underestimate property:

Substituting the hypothesis, $f_0(y) \ge f_0(x^\star) + (\text{nonnegative quantity}) \ge f_0(x^\star)$ for every feasible $y$, so $x^\star$ is a global minimizer. This inequality is exactly the tangent-plane characterization of convexity, and it is where differentiable convexity earns its keep: a first-order (local, cheap-to-check) condition certifies a global (expensive-to-verify-by-brute-force) property.

Correctness — KKT sufficiency. Given a point and multipliers satisfying all four KKT conditions for a convex program, weak duality plus complementary slackness force

so all inequalities are equalities: $x^\star$ achieves $p^\star$, i.e., it is globally optimal, and simultaneously $d^\star = p^\star$ (strong duality is witnessed). This chain is the algebraic heart of why KKT works and why solving the dual problem (often easier, e.g., in SVMs) recovers the primal optimum.

Complexity. Convex optimization problems are not just theoretically nice — they are usually efficiently solvable. Key facts, stated honestly with their caveats:

• Interior-point methods solve smooth convex programs (with self-concordant barrier structure, e.g., linear and quadratic programs) to accuracy $\epsilon$ in $O(\sqrt{n} \log(1/\epsilon))$ Newton iterations, each iteration costing $O(n^3)$ for a dense linear solve of size $n$ — giving an overall polynomial-time algorithm. This is a fundamentally different complexity class from general non-convex optimization, which is NP-hard in the worst case (even for simple-looking non-convex quadratics).
• Gradient descent on an $L$-smooth convex function reaches $f_0(x_t) - p^\star \le \epsilon$ in $O(L/\epsilon)$ iterations; with additional $\mu$-strong convexity this improves to a linear (geometric) rate, $O(\kappa \log(1/\epsilon))$ where $\kappa = L/\mu$ is the condition number. (This is developed fully under Gradient Descent.)
• Space complexity for first-order methods is $O(n)$ per iterate (storing the current point and gradient); interior-point/Newton-type methods cost $O(n^2)$ space to store a Hessian or its factorization.
• Honesty about tradeoffs: convexity guarantees existence of an efficient certificate of optimality, not that every convex problem is trivial — large-scale semidefinite programs, for instance, are convex but expensive ($O(n^6)$-ish per iteration in naive interior-point implementations), motivating specialized first-order convex solvers (ADMM, proximal gradient) for ML-scale problems.
• Non-differentiable convex objectives (e.g., $\ell_1$ regularization, hinge loss) still admit optimality conditions, replacing the gradient with the subdifferential $\partial f_0(x^\star)$; the condition becomes $0 \in \partial f_0(x^\star) + N_{\mathcal F}(x^\star)$ (normal cone term for constraints), and this generalized KKT machinery is exactly what underlies lasso and soft-margin SVM theory.

Consider a small, concrete convex quadratic program:

This is a convex program: $f_0$ is a sum of squares (convex), $f_1$ is affine hence convex, feasible set is the half-plane $x_1+x_2 \ge 1$.

Step 1 — Lagrangian.

Step 2 — Stationarity.

Step 3 — Guess $\lambda > 0$ (constraint active) and check complementary slackness. Complementary slackness requires $\lambda(1 - x_1 - x_2) = 0$. If $\lambda > 0$, then $x_1 + x_2 = 1$ exactly. Substituting $x_1=x_2=\lambda/2$:

So $x_1 = x_2 = 1/2$, $\lambda^\star = 1$.

Step 4 — Verify all KKT conditions explicitly.

All four conditions hold, so by the sufficiency argument above, $x^\star = (0.5, 0.5)$ is globally optimal, with $p^\star = 0.5^2 + 0.5^2 = 0.5$.

Step 5 — Confirm via the dual function directly (independent check).

Minimizing over $x_1, x_2$ unconstrained (setting gradients to zero) gives $x_1 = x_2 = \lambda/2$, so

Maximizing over $\lambda \ge 0$: $dg/d\lambda = 1 - \lambda = 0 \Rightarrow \lambda^\star = 1$, giving $d^\star = 1 - 0.5 = 0.5$. Indeed $d^\star = p^\star = 0.5$ — strong duality holds, exactly as predicted, since this problem trivially satisfies Slater's condition (e.g., $x_1=x_2=1$ is strictly feasible: $1 - 1 - 1 = -1 < 0$). This second, independent computation via the dual function is a genuine correctness check, not a restatement — it confirms the primal answer using an entirely different optimization (a 1-dimensional concave maximization instead of a 2-dimensional constrained minimization).

Nesterov and Nemirovski's work is often considered the moment convex optimization became a unified, algorithmically complete field rather than a collection of special-case methods (simplex for linear programs, specific solvers for quadratic programs). Their complexity theory — proving that broad classes of convex programs admit polynomial-time algorithms via interior-point methods — is the theoretical result underlying modern solvers (e.g., those used inside SVM and portfolio-optimization software).

Convex optimization is the invisible backbone of a huge share of production ML and statistics software. Ridge regression and lasso are convex programs whose KKT conditions yield closed-form (ridge) or piecewise-linear (lasso, via subgradient KKT) solution paths, directly motivating Regularization Theory. Support vector machines are trained by solving the convex dual quadratic program; the KKT complementary-slackness condition is precisely what identifies which training points become "support vectors." Logistic regression MLE is a convex program (negative log-likelihood is convex in the weights), which is why Newton's method and gradient-based solvers reliably converge to the unique global optimum in standard packages (scikit-learn, glmnet, TensorFlow's convex solvers). Beyond core supervised learning, convex optimization underlies portfolio optimization in finance (Markowitz mean-variance optimization is a convex quadratic program), compressed sensing and sparse recovery (basis pursuit is a convex linear program relaxing an NP-hard $\ell_0$ problem), optimal control (model predictive control solves a convex quadratic program at every timestep), and network resource allocation (convex utility maximization for bandwidth allocation in networking). Interior-point solvers (CVXOPT, MOSEK, ECOS) and first-order solvers (proximal gradient, ADMM) that industry relies on are direct engineering realizations of the theory in this article. The broader theory of Gradient Descent as a practical algorithm, and the design of penalty terms studied in Regularization Theory, both draw their correctness guarantees from the convexity structure developed here.

Ask the tutor: How does adding an $\ell_1$ or $\ell_2$ penalty term change the KKT conditions of a regression problem, and why does that change produce sparsity in the lasso case?