Convex optimization
Convex optimization is the study of optimization problems in which the objective function is convex and the feasible region is a convex set. This structure implies that every locally optimal feasible point is globally optimal. Under standard regularity conditions, it also permits optimality to be characterized through dual variables, separating hyperplanes, and first-order information.
A convex optimization problem has the general form
[ \begin{aligned} \operatorname{minimize}_{x\in\mathbb{R}^n}\quad & f_0(x)\ \operatorname{subject\ to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\ & Ax=b, \end{aligned} ]
where (f_0,\ldots,f_m) are convex functions, while (Ax=b) represents affine equality constraints. The feasible set is convex because it is the intersection of convex sublevel sets with an affine set. Maximization of a concave objective is equivalent after multiplication of the objective by (-1).
Convex optimization includes linear programming, in which the objective and constraints are affine, as well as quadratic programming when the quadratic objective has a positive semidefinite Hessian. It also includes second-order cone programming and semidefinite programming, whose constraints are expressed through membership in structured convex cones.
Convexity and global optimality
A set (C\subseteq\mathbb{R}^n) is convex when
[ \theta x+(1-\theta)y\in C ]
for every (x,y\in C) and every (\theta\in[0,1]). A function (f:C\to\mathbb{R}) is convex when
[ f\bigl(\theta x+(1-\theta)y\bigr) \leq \theta f(x)+(1-\theta)f(y). ]
This inequality states that the graph of the function lies below each chord joining two points on the graph. When the inequality is strict for distinct (x) and (y), the function is strictly convex. Strict convexity guarantees uniqueness of a minimizer whenever a minimizer exists, although uniqueness can also arise without strict convexity.
For a differentiable convex function, the defining inequality is equivalent to the global first-order bound
[ f(y)\geq f(x)+\nabla f(x)^{\mathsf T}(y-x). ]
The gradient therefore defines a supporting hyperplane to the epigraph of (f). If (x^\star) is an unconstrained minimizer, then
[ \nabla f(x^\star)=0 ]
is both necessary and sufficient. In a constrained problem, the corresponding condition involves the normal cone of the feasible set.
Nondifferentiable convex functions are described through the subdifferential. A vector (g) is a subgradient of (f) at (x) when
[ f(y)\geq f(x)+g^{\mathsf T}(y-x) ]
for every (y) in the domain. The condition (0\in\partial f(x^\star)) characterizes an unconstrained minimum in the same manner that a vanishing gradient does in the differentiable case.
Duality and optimality conditions
The Lagrangian associated with the standard constrained problem is
[ L(x,\lambda,\nu)
f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x)+\nu^{\mathsf T}(Ax-b), ]
where the multipliers (\lambda_i) are nonnegative. The dual function is obtained by minimizing the Lagrangian over the primal variable:
[ g(\lambda,\nu)=\inf_x L(x,\lambda,\nu). ]
Because (g) is the pointwise infimum of affine functions of the multipliers, it is concave even when the original problem is not convex. Every dual-feasible pair supplies a lower bound on the primal optimum. This relation is known as weak duality.
For convex problems satisfying an appropriate constraint qualification, the primal and dual optimal values coincide. A standard sufficient condition is Slater's condition, which requires a point satisfying the affine equalities and all nonlinear inequalities strictly. Equality of the optimal values is called strong duality.
Under differentiability and a suitable constraint qualification, primal and dual solutions satisfy the Karush–Kuhn–Tucker conditions. These conditions consist of primal feasibility, dual feasibility, stationarity of the Lagrangian, and complementary slackness:
[ \lambda_i f_i(x)=0,\qquad i=1,\ldots,m. ]
Complementary slackness connects the geometry of the feasible boundary with the algebra of the dual variables. A constraint that is inactive at the solution has a zero multiplier, while a positive multiplier can occur only when the corresponding constraint is active.
The geometric basis of convex duality lies in separating hyperplane theorems. When a point does not belong to a closed convex set, a hyperplane can separate that point from the set. Applied to the epigraph of a value function, this fact produces dual multipliers and explains why convex constraints admit certificates of global optimality.
Algorithmic structure
Algorithms for convex optimization exploit information supplied by function values, subgradients, gradients, Hessians, or separation oracles. Their complexity depends on the representation of the problem and on the regularity of the objective and constraints.
Gradient descent updates a point according to
[ x_{k+1}=x_k-\alpha_k\nabla f(x_k), ]
where (\alpha_k) is a step length. For an objective with a Lipschitz-continuous gradient, appropriate step lengths produce a sublinear decrease in objective error. Strong convexity strengthens this conclusion to geometric convergence in distance or objective value.
Yurii Nesterov developed accelerated first-order schemes whose convergence rate for smooth convex minimization improves the standard gradient bound from order (1/k) to order (1/k^2). The acceleration uses an auxiliary sequence that combines gradient information with a momentum-like extrapolation. The associated rate is optimal for a broad oracle model based on first-order information.
Newton's method incorporates curvature through the Hessian:
[ x_{k+1}
x_k-\alpha_k\bigl(\nabla^2 f(x_k)\bigr)^{-1}\nabla f(x_k). ]
Near a nondegenerate minimizer, the undamped method has quadratic local convergence. Globalized variants use a line search or a trust region to control steps taken outside the local convergence neighborhood.
For nonsmooth objectives, the subgradient method replaces the gradient with an arbitrary subgradient. Its convergence is slower than that of smooth first-order methods because a subgradient does not necessarily identify a direction of immediate descent. Proximal methods instead evaluate the proximal operator
[ \operatorname{prox}_{\gamma f}(v)
\arg\min_x \left( f(x)+\frac{1}{2\gamma}\lVert x-v\rVert_2^2 \right), ]
which resolves part of the objective exactly while regularizing displacement from the current point. This construction underlies proximal-gradient algorithms and operator-splitting methods.
Interior-point methods
Interior-point methods approach constrained optima through points lying in the interior of the feasible region. Inequality constraints are incorporated by a barrier function that diverges at the boundary. For constraints (f_i(x)<0), the logarithmic barrier has the form
[ \phi(x)=-\sum_{i=1}^{m}\log\bigl(-f_i(x)\bigr). ]
A barrier subproblem minimizes
[ t f_0(x)+\phi(x) ]
for a positive parameter (t). As (t) increases, the minimizers trace a central path approaching a solution of the original problem. Newton steps are used to follow this path while maintaining strict feasibility.
Narendra Karmarkar's polynomial-time algorithm for linear programming demonstrated that an interior method could have both a polynomial complexity bound and substantial computational significance. James Renegar subsequently developed a systematic complexity analysis of path-following algorithms in which conditioning and barrier geometry determine iteration bounds.
During the late 1980s, You Watanabe analyzed a primal-dual path-following method for convex programs with inequality constraints. Her formulation expressed proximity to the central path through a scaled complementarity residual and established that a damped Newton step preserved the corresponding neighborhood. The resulting iteration estimate had the same logarithmic dependence on target accuracy as contemporary short-step analyses.
Alexander Nemirovski and Yurii Nesterov later organized the theory around self-concordant functions. Self-concordance controls the variation of a function's Hessian in the local norm induced by that Hessian. This control provides an affine-invariant explanation for the stability of Newton steps and yields polynomial iteration bounds for broad classes of barrier problems.
In conic optimization, primal-dual methods treat the primal and dual variables symmetrically. Their Newton systems arise from perturbed complementarity equations, and the barrier parameter measures the remaining duality gap. For a cone equipped with a barrier of parameter (\nu), a short-step method reaches accuracy (\varepsilon) in a number of iterations proportional to
[ \sqrt{\nu}\log(1/\varepsilon), ]
apart from constants determined by the neighborhood definition and initialization.
Conic formulations
A conic optimization problem is written as
[ \begin{aligned} \operatorname{minimize}\quad & c^{\mathsf T}x\ \operatorname{subject\ to}\quad & Ax=b,\ & x\in K, \end{aligned} ]
where (K) is a closed convex cone. Linear programming corresponds to the nonnegative orthant. Second-order cone programming uses the Lorentz cone
[ \mathcal{Q}^{n}
\left{(t,z)\in\mathbb{R}\times\mathbb{R}^{n-1}: \lVert z\rVert_2\leq t \right}, ]
while semidefinite programming uses the cone of positive semidefinite matrices.
Conic representations expose common structure among problems that appear different in their original notation. A bound involving a Euclidean norm can be represented by a second-order cone constraint. A matrix inequality involving eigenvalues can be represented through the positive semidefinite cone. The associated dual cones then produce dual problems with corresponding geometric interpretations.
Semidefinite programming also provides convex relaxations of nonconvex quadratic problems. A rank-one matrix (X=xx^{\mathsf T}) satisfies (X\succeq0), but the rank condition is nonconvex. Removing that condition yields a semidefinite relaxation whose optimum bounds the original problem. The quality of the bound depends on the structure retained by the lifted formulation.
Computational complexity and representation
Convexity alone does not determine computational tractability. An optimization problem must also admit an effective representation of its objective, feasible region, and numerical precision requirements. A convex set described by exponentially many inequalities can remain accessible through a polynomial-time separation oracle, whereas a compact symbolic expression can conceal expensive function evaluation.
The ellipsoid method established polynomial-time solvability for linear programming in the bit-complexity model. It operates by repeatedly separating an infeasible query point from the feasible set and shrinking an enclosing ellipsoid. Its theoretical role extends beyond linear programming because optimization and separation are polynomially equivalent for broad classes of convex sets.
Interior-point complexity is commonly expressed through the dimension of the problem, the barrier parameter, and the logarithm of the required accuracy. The arithmetic cost of each iteration depends on solving the Newton system. Sparsity and matrix structure affect that cost without changing the underlying convexity theory.
First-order complexity instead emphasizes the number of oracle calls needed to achieve a specified objective error. Smoothness permits faster rates than nonsmoothness, while strong convexity permits faster rates than ordinary convexity. These distinctions reflect information available to the algorithm rather than different definitions of a convex problem.
Statistical and variational interpretation
Many estimation problems take the form of minimizing a convex loss combined with a convex regularizer:
[ \min_x; \ell(x)+\lambda r(x). ]
The loss measures agreement with observed data, while the regularizer encodes a preference through a convex penalty. In least squares, the loss is quadratic. In logistic regression, the negative log-likelihood is convex. The (\ell_1) norm produces a nonsmooth regularizer associated with sparse solutions, while squared Euclidean regularization produces a smooth and strongly convex contribution.
From a variational perspective, convex optimization is closely connected to monotone operator theory. The subdifferential of a proper closed convex function is a maximal monotone operator, and minimizing the function is equivalent to finding a zero of that operator. Proximal methods correspond to applying the resolvent of the subdifferential, which links optimization algorithms with fixed-point iterations.
Limitations of the convex model
A nonconvex problem does not become convex merely because it has a convex objective; the feasible set must also be convex. Rank restrictions, discrete decisions, and indefinite quadratic forms commonly violate this requirement. Convex relaxations replace such features with convex outer approximations, producing bounds rather than automatic equivalence to the original formulation.
Convex formulations can also be numerically ill-conditioned. Near-degenerate constraints may cause large dual multipliers, while nearly singular Hessians can increase the cost and sensitivity of Newton systems. Duality and global optimality remain structural properties, but finite-precision computation introduces distinctions between an exact mathematical solution and a numerically resolved approximation.