Glossary term
Convex Optimization
A class of optimization problems in which the objective function and feasible set are convex, guaranteeing that any local minimum is also the global minimum.
Definition
conceptConvex optimization is the subfield of optimization concerned with problems in which the objective function is convex and the feasible set is a convex set, ensuring that every local minimum is a global minimum and that efficient algorithms can find the exact solution.
Convexity is a central structural property in optimization because, under the usual assumptions, it collapses the distinction between local and global optima. Problems that can be recognised or reformulated as convex can often be solved reliably to global optimality or certified accuracy, but scalability still depends on problem structure, conditioning, sparsity, and solver choice. The class of convex optimization problems includes linear programming, quadratic programming, second-order cone programming, and semidefinite programming — a hierarchy of increasingly general structures with specialised algorithms.
A function f: \mathbb{R}^n \to \mathbb{R} is convex if, for any two points x and y and any \theta \in [0, 1]:
Geometrically, this means the chord connecting any two points on the graph of f lies above or on the graph — the function curves upward. A set \mathcal{C} \subseteq \mathbb{R}^n is convex if for any two points x, y \in \mathcal{C}, the line segment \theta x + (1-\theta) y also belongs to \mathcal{C} for all \theta \in [0,1].
A convex optimization problem has a convex objective function and a convex feasible set (defined by convex inequality constraints and linear equality constraints). The fundamental theorem of convex optimization states that every local minimum of a convex problem is also a global minimum. This is because convexity rules out isolated non-global local minima: any feasible line segment from a local optimum to a supposedly better feasible point would immediately create a nearby improving direction.
The convex hierarchy
Convex optimization encompasses a structured hierarchy of problem classes, each with its own geometric properties and specialised algorithms.
Linear programming (LP) is the simplest class: the objective and all constraints are linear. The feasible set is a polyhedron. The optimal solution, if it exists, lies at a vertex of the polyhedron. LP problems are solved by the simplex method (which moves along edges of the polyhedron) or interior-point methods (which traverse the interior), both capable of solving problems with millions of variables and constraints.
Quadratic programming (QP) allows a convex quadratic objective with linear constraints. If the objective Hessian is positive semidefinite, the problem is convex. QP is the subproblem solved at each iteration of sequential quadratic programming (SQP) for nonlinear programs, and is also the core computation in support vector machine training.
Second-order cone programming (SOCP) generalises QP by allowing constraints that define second-order (Lorentz) cones. It encompasses robust linear programming, portfolio optimisation with uncertainty, and many geometry and engineering design problems.
Semidefinite programming (SDP) replaces scalar inequality constraints with matrix positive semidefiniteness constraints (X \succeq 0). It is a broad and powerful convex class, but scalability depends strongly on matrix size, sparsity, and solver method. SDP arises in control (LMI-based controller design), combinatorial relaxations, and quantum information.
Duality
Every convex optimization problem has an associated dual problem. The dual is always convex and its optimal value provides a lower bound on the primal optimal value. For convex problems satisfying a constraint qualification (Slater’s condition), strong duality holds: the primal and dual optimal values are equal, and the dual solution provides the Lagrange multipliers (KKT multipliers) at the primal optimum. Duality is exploited algorithmically in interior-point methods and in decomposition algorithms for large-scale problems.
Recognising and reformulating convexity
Many engineering problems that appear non-convex can be reformulated as convex by a change of variables or by recognising hidden convex structure. A classical example is geometric programming: the original problem is non-convex in the natural variables, but a logarithmic change of variables transforms it into a convex problem. Disciplined convex programming (DCP) — implemented in tools such as CVXPY and CVX — provides a formal grammar of convex-preserving operations that allows engineers to construct and verify convex formulations without manual analysis.
Limitations
Not all engineering problems are convex. Structural topology optimization, combinatorial scheduling, parameter estimation for nonlinear models, and neural network training are inherently non-convex. For these, convex relaxations (replacing the non-convex feasible set with a convex superset) can provide bounds on the global optimum, and local methods such as gradient descent and SQP find good local solutions but cannot guarantee global optimality.