Convex optimization is a branch of mathematical optimization concerned with minimizing a convex function over a convex feasible set. Its defining property is that every local minimum is also a global minimum. This distinguishes it from general nonlinear optimization, where locally optimal solutions may be globally suboptimal. Convexity also makes certain first-order optimality conditions sufficient, providing a foundation for both mathematical analysis and numerical solution methods. (mit.edu)
Mathematical formulation
A set (C\subseteq\mathbb{R}^n) is a convex set if it contains the entire line segment between any two of its points: [ \theta x+(1-\theta)y\in C \quad\text{for }x,y\in C,\quad 0\leq\theta\leq1. ] A function (f:C\to\mathbb{R}) is convex when [ f(\theta x+(1-\theta)y) \leq \theta f(x)+(1-\theta)f(y). ] Thus, its value at an interpolated point does not exceed the corresponding interpolation of endpoint values. Differentiability is not required. (mit.edu)
A standard constrained formulation is [ \begin{aligned} \operatorname{minimize}_{x}\quad &f_0(x)\ \operatorname{subject\ to}\quad &f_i(x)\leq0,\quad i=1,\ldots,m,\ &Ax=b, \end{aligned} ] where the objective function (f_0) and inequality functions (f_i) are convex on a common convex domain. The equality constraints are affine. Their intersection with the convex inequality sublevel sets is convex, so the formulation defines a convex optimization problem. Maximizing a concave function over a convex set is equivalent after negating the objective. (web.stanford.edu)
Optimality and duality
For a differentiable convex function, the gradient supplies a global lower bound: [ f(y)\geq f(x)+\nabla f(x)^{T}(y-x). ] Consequently, an unconstrained stationary point, where (\nabla f(x)=0), is globally optimal. Over a convex set (C), the corresponding condition is [ \nabla f(x)^{T}(y-x)\geq0 \quad\text{for every }y\in C. ] Unlike in general nonlinear optimization, this condition is sufficient as well as necessary. (mit.edu)
Lagrangian duality associates the constrained problem with [ L(x,\lambda,\nu) =f_0(x)+\sum_i\lambda_i f_i(x)+\nu^{T}(Ax-b). ] Taking the infimum over (x) produces a dual function. Maximizing this function with (\lambda_i\geq0) gives the dual problem, whose feasible values are lower bounds on the primal minimum. The difference between optimal primal and dual values is the duality gap. (see.stanford.edu)
Strong duality means that this gap is zero. It holds under suitable constraint qualifications, notably Slater’s condition: in its standard form, an equality-feasible point lies in the relative interior of the common domain and satisfies all inequality constraints strictly. For differentiable convex problems, the Karush–Kuhn–Tucker conditions—primal feasibility, dual feasibility, stationarity, and complementary slackness—are sufficient for optimality; suitable qualifications also make them necessary. (see.stanford.edu)
Important problem classes
Linear programming uses affine objectives and affine constraints. Convex quadratic programming allows an objective [ \tfrac12x^{T}Qx+c^{T}x, ] with (Q) symmetric and positive semidefinite, together with affine constraints. These classes illustrate how convexity can be checked through explicit algebraic structure. (web.stanford.edu)
Second-order cone programming includes norm constraints such as [ |Ax+b|_2\leq c^{T}x+d. ] Semidefinite programming minimizes a linear objective subject to positive-semidefiniteness constraints on affine combinations of symmetric matrices. It generalizes several familiar optimization formulations and is used in engineering analysis and design. (web.stanford.edu)
Recognizing these standard forms is important because their structure supports specialized solvers, duality theory, and complexity analysis. An application may require reformulation before its convex structure becomes apparent. (stanford.edu)
Numerical methods
Gradient descent updates an unconstrained iterate by [ x_{k+1}=x_k-\alpha_k\nabla f(x_k). ] For convex objectives with a gradient satisfying Lipschitz continuity, appropriate step sizes yield convergence guarantees. Under standard assumptions, the objective error decreases at an (O(1/k)) rate. Strong convexity permits geometric convergence with suitable step sizes. These guarantees depend on smoothness and curvature, not convexity alone. (mit.edu)
Projected gradient methods restore feasibility by projecting the gradient step onto a closed convex set. Proximal gradient methods address composite objectives (f+g), where (f) is smooth and (g) may be nonsmooth. They combine a gradient step for (f) with a proximal minimization for (g), making them useful when the nonsmooth component has a tractable proximal operator. (ocw.mit.edu)
Newton’s method uses second-order information, while interior-point methods solve constrained problems through barrier or primal–dual formulations. Many standard convex problem classes admit polynomial-time complexity guarantees under specified assumptions. Practical performance nevertheless depends on dimension, numerical conditioning, sparsity, and the cost of evaluating or solving the underlying subproblems. (ocw.mit.edu)
Applications and scope
Convex optimization supports machine learning, statistics, signal processing, communications, and control theory. Least-squares fitting, convex loss minimization, and suitable regularization penalties provide important statistical examples. Its engineering applications include resource allocation, circuit design, and system analysis. (web.stanford.edu)
For nonconvex problems, a convex relaxation replaces difficult constraints or objective structure with a tractable convex approximation. Such formulations can supply bounds and approximate solutions, but do not automatically recover an optimum of the original problem. In particular, a convex relaxation of integer programming may return fractional rather than integer decisions. (stanford.edu)
Convexity should therefore be distinguished from a blanket guarantee of easy computation: the representation of the problem, requested accuracy, and available computational access remain essential parts of its computational complexity. (stanford.edu)