Convex optimization

A convex optimization problem minimizes a convex objective over a convex set, possibly with convex constraints:

where and the are convex, the are affine, and is a convex set (often or a subspace).

The most common practical form:

with convex and linear constraints.

Intuition

Convex optimization is the "well-posed" case of optimization: there are no trapped local minima. If you find a point where the gradient vanishes (unconstrained) or KKT conditions hold (constrained), you have the global minimum.

This is why problems as diverse as least squares, ridge regularization, mean-variance allocation, and SVMs rely on this structure: reliable, often unique solutions with proven algorithms.

Why convexity is enough

Prerequisites (see Convexity and Derivatives, gradient, and Hessian):

intersection of convex constraints = convex domain;
sum of convex functions = convex objective;
every local minimum of a convex function on a convex domain is global.

Practical consequence: no aggressive multi-start or escape heuristics needed to avoid local minima — difficulty comes mainly from scale, conditioning, and computational cost.

Standard forms

Type	Form	Comment
Linear program (LP)	s.t.	Linear objective and constraints; convex special case
Quadratic program (QP)	s.t. linear constraints,	OLS, ridge, Markowitz
Conic program (SOCP, SDP)	Constraints on norms or matrices	Robustness, risk constraints, advanced finance
Unconstrained minimization	with convex	Gradient descent, Newton

Optimality conditions

If is convex and differentiable, a point is optimal if and only if:

For a convex problem with qualified constraints, Karush-Kuhn-Tucker conditions are necessary and sufficient:

Multipliers measure the marginal cost of a constraint: slightly relaxing an active constraint shifts the optimum by roughly .

With equality constraints only (), form the Lagrangian:

The optimum satisfies and . With inequalities, Lagrange multipliers generalize via KKT.

Duality

Every convex problem (primal) has an associated dual problem, often simpler to optimize or interpret:

the dual provides a lower bound on the primal optimum (weak duality always holds);
under strong duality (Slater, constraint qualification), primal optimum = dual optimum;
dual multipliers are the dual problem's variables.

Classic example: in SVM, the dual turns a constrained problem into maximization over multipliers , with a sparse solution (support vectors).

Examples

Problem	Convex formulation	Link
Least squares (OLS)		Linear regression
Ridge		Strictly convex QP; regularized Hessian
Lasso		Convex but non-smooth; subgradient or prox
Markowitz	s.t.	QP; mean-variance allocation
Soft-margin SVM	Hinge minimization + margin violation penalty	Convex; duality and support vectors

Algorithms (overview)

Method	Idea	When to use
Gradient descent		High dimension, smooth objective; see Gradient descent
Newton / quasi-Newton	Uses curvature ( or BFGS approximation)	Fast convergence near optimum; costly in high dimension
Interior-point methods	Stay inside domain, barrier on constraints	Large-scale LP, QP, SDP
Proximal / ADMM	Split smooth objective and non-smooth term or constraints	Lasso, structured constraints, distributed problems

Applications

Statistics: MLE with convex constraints, ridge/lasso, quantile regression (via LP reformulation).
Machine learning: SVM, logistic regression (convex in ), regularization.
Finance: efficient frontier, risk parity under linear constraints, robust optimization.
Engineering: resource allocation, convex discrete control, constrained calibration.

See Gradient descent for algorithm details; Newton and quasi-Newton remain on the Optimization hub.

Limits and pitfalls

Situation	Issue	Consequence
Non-convex objective	Neural networks, clustering	Local minima; no global guarantee
Non-convex constraints	Cardinality, binary variables	NP-hard in general; convex relaxation needed
Ill-conditioned data	nearly singular	Unstable solution; regularization or constraints
Confusing convex and smooth	is convex but not differentiable	Classical gradient insufficient; subgradient or prox
Weak duality only	Nonzero primal-dual gap	Dual underestimates optimum; check Slater / qualification