Convex Optimization

In a convex problem, the objective function is convex and the feasible set is a convex set. This geometry ensures that a local minimum is automatically a global minimum. For portfolio managers, this means the solver finds the single best allocation, not just a good one. This property is critical when minimizing portfolio variance subject to a target return, as there is no ambiguity about the solution's quality.

A function f is convex if its second derivative is non-negative, meaning the line segment between any two points lies above the graph. In finance, portfolio variance (xᵀΣx) is a classic convex function because the covariance matrix Σ is positive semi-definite. Other examples include:

• Linear transaction costs
• Negative logarithmic utility for growth-optimal portfolios
• CVaR (Conditional Value-at-Risk) when expressed as a minimization

The feasible set contains all portfolios satisfying the constraints. A set is convex if a straight line connecting any two valid portfolios remains entirely within the set. Standard constraints that preserve convexity include:

• Linear equality constraints: Full investment (∑wᵢ = 1)
• Linear inequality constraints: No short-selling (wᵢ ≥ 0), sector exposure limits
• Second-order cone constraints: Tracking error bounds Non-convex constraints like cardinality limits (max 20 assets) break this guarantee.

Every convex optimization problem has a dual problem that provides a lower bound to the primal objective. At optimality, the duality gap is zero. This is computationally powerful: the dual variables represent shadow prices of constraints. In portfolio optimization, the dual variable for the full-investment constraint reveals the sensitivity of the optimal variance to a marginal relaxation of that constraint, offering economic insight alongside the numerical solution.

Convex problems are solvable in polynomial time using interior-point methods. Unlike non-convex problems that may require exhaustive search or heuristics, convex solvers exhibit deterministic convergence. For a portfolio with n assets, the computational complexity is typically O(n³) for a one-time covariance matrix factorization, after which re-optimization with updated expected returns is extremely fast. This enables near-real-time rebalancing.

Modern modeling frameworks like CVXPY and Convex.jl enforce convexity through a rule system called DCP. Users express problems using a library of atomic functions known to be convex, concave, or affine. The framework verifies the composition rules before passing the problem to a solver. This prevents the costly error of attempting to solve a non-convex problem with a convex solver, a common pitfall when adding complex constraints like cardinality limits.

A specific class of convex optimization where the objective function is quadratic and constraints are linear. In portfolio theory, QP is the workhorse for solving Mean-Variance Optimization (MVO) problems.

• Minimizes: w^T Σ w - λ μ^T w (variance minus expected return)
• Subject to: sum of weights = 1, no short-selling constraints
• Solvers like OSQP and CVXOPT exploit the convex structure for fast convergence
• Guarantees a unique global solution when the covariance matrix Σ is positive semi-definite

An extension of convex optimization that handles constraints involving Euclidean norms. SOCP is essential for robust portfolio optimization where uncertainty in expected returns is modeled.

• Captures constraints like ||Ax + b||₂ ≤ c^T x + d
• Used in robust MVO to handle estimation errors in μ and Σ
• Enables modeling of transaction costs with piecewise-linear functions
• Interior-point methods solve SOCP problems in polynomial time

A generalization of linear programming where the variable is a positive semidefinite matrix. SDP arises in finance when optimizing over correlation matrices or constructing risk models.

• Constraint: X ⪰ 0 (X is positive semidefinite)
• Used to find the nearest valid correlation matrix when empirical estimates are noisy
• Applies Random Matrix Theory (RMT) denoising to covariance estimation
• Solver example: SDPT3, SeDuMi

The theoretical backbone of convex optimization that pairs every primal problem with a dual problem. Strong duality holds for convex problems under Slater's condition, meaning the optimal duality gap is zero.

• Lagrangian: L(x, λ, ν) = f₀(x) + Σ λᵢ fᵢ(x) + Σ νᵢ hᵢ(x)
• Dual function: g(λ, ν) = infₓ L(x, λ, ν) — always concave
• KKT conditions provide necessary and sufficient optimality certificates
• Enables decomposition methods for large-scale portfolio problems

The dominant algorithmic family for solving convex optimization problems. Unlike the simplex method, interior-point methods traverse the interior of the feasible region using barrier functions.

• Primal-dual path-following is the most widely used variant
• Complexity: O(√n log(1/ε)) iterations for linear programs
• The logarithmic barrier -Σ log(-fᵢ(x)) keeps iterates strictly feasible
• Powers modern solvers: MOSEK, Gurobi, ECOS

A class of risk measures satisfying monotonicity, translation invariance, and convexity. Unlike Value-at-Risk, convex risk measures like Conditional Value-at-Risk (CVaR) can be optimized using convex programming.

• CVaR minimization can be formulated as a linear program
• Coherent risk measures are a subset that also satisfy positive homogeneity
• Entropic risk measure: ρ(X) = (1/γ) log E[exp(-γX)] — convex and smooth
• Enables risk budgeting with convex constraints