Fact-checked by Grok 2 weeks ago

Conic optimization

Conic optimization is a class of convex optimization problems that generalize linear programming (LP) by incorporating constraints defined over convex cones, allowing the modeling of a broader range of nonlinear convex problems while maintaining computational tractability. Formally, it seeks to minimize (or maximize) a linear objective function c^\top x subject to the constraints Ax = b and x \in \mathcal{K}, where A is a linear map, b is a vector, and \mathcal{K} is a closed convex cone in a finite-dimensional real vector space.^[1] This framework encompasses several important subclasses, including linear programming (when \mathcal{K} is the nonnegative orthant \mathbb{R}^n_+), second-order cone programming (SOCP, using the second-order or Lorentz cone), and semidefinite programming (SDP, with the cone of positive semidefinite matrices).^[2] The modern formulation of conic optimization emerged in the late 20th century as an extension of convex optimization. In the 1990s, researchers such as Yu. Nesterov and A. Nemirovski developed the theoretical foundations, introducing self-dual or symmetric cones and demonstrating that certain conic problems could be solved in polynomial time using interior-point methods (IPMs).^[2] These advances built on earlier progress in LP and SDP, with key contributions from F. Alizadeh and D. Goldfarb on SDP feasibility and efficiency.^[2] Duality plays a central role, with strong duality holding under mild conditions like Slater's, enabling the formulation of primal-dual pairs that facilitate numerical solution and sensitivity analysis.^[1] Key cones in conic optimization include the nonnegative cone \mathbb{R}^n_+, the second-order cone \mathcal{Q}^{n+1} = \{ (t, x) \in \mathbb{R} \times \mathbb{R}^n : \|x\|_2 \leq t \} for quadratic constraints, and the positive semidefinite cone \mathcal{S}^n_+ of n \times n symmetric matrices with nonnegative eigenvalues, which captures spectral properties and matrix inequalities.^[2] More general cones, such as copositive and completely positive cones, extend applicability to nonconvex problems via relaxations, though they often lack efficient polynomial-time solvers. Algorithms primarily rely on IPMs, which exploit the self-concordance of barrier functions for cones like those in SOCP and SDP, achieving high precision in practice; specialized software such as MOSEK, SDPT3, and CSDP implements these methods.^[2] Applications of conic optimization span operations research, engineering, and finance, including robust portfolio optimization (via SOCP for risk measures like variance), sensor network localization (SDP for semidefinite relaxations), and combinatorial problems such as the maximum cut or stable set via SDP hierarchies.^[2] It also enables sum-of-squares hierarchies for polynomial optimization and global approximations of nonconvex sets, making it a versatile tool for approximation algorithms in theoretical computer science.^[1]

Introduction

Definition

Conic optimization is a framework within convex optimization that addresses problems involving linear objectives and constraints defined over convex cones, generalizing classical linear programming to handle a broader class of convex constraints. It formulates optimization tasks where the feasible set is the intersection of an affine subspace and a nonempty closed convex cone, enabling the modeling of nonlinear relationships in a structured, computationally tractable manner.^[3]^[4] The standard primal form of a conic optimization problem is to minimize the linear [objective c^T x](/page/objective_%5C(%20c) subject to the linear equality constraints Ax = b and the membership constraint x \in K, where x \in \mathbb{R}^n is the decision variable, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R}^n, and K \subseteq \mathbb{R}^n is a convex cone.^[5]^[3] This setup distinguishes conic optimization from linear programming, which emerges as a special case when K is the non-negative orthant \mathbb{R}^n_+.^[4] In contrast to quadratic programming, which typically features a quadratic objective or constraints, conic optimization preserves a linear objective while accommodating more general convex constraints through the cone K.^[5] A key motivation for conic optimization is its capacity to represent nonlinear constraints—such as those involving norms or positive semidefiniteness—in a convex form that supports efficient interior-point methods via self-concordant barrier functions.^[6] These barriers, introduced by Nesterov and Nemirovski, ensure polynomial-time solvability for problems over cones with suitable barrier parameters, facilitating applications in fields like control and machine learning.^[6]

Historical Background

Conic optimization developed as a generalization of linear programming, providing a framework for optimizing linear functions over convex cones rather than polyhedra. This extension built on the polynomial-time solvability of linear programming, first established by Leonid Khachiyan's 1979 ellipsoid method, which demonstrated that linear programs could be solved efficiently despite earlier pessimistic views on computational complexity. The foundational advances in conic optimization occurred in the 1980s, with early contributions from Jonathan Borwein and Henry Wolkowicz on facial reduction techniques. These methods addressed infeasibility and degeneracy in convex programs by iteratively reducing the feasible set to its minimal face, enabling more stable and efficient numerical solutions for problems over general convex sets. Borwein and Wolkowicz's work, published in 1981, laid the groundwork for handling pathological cases in optimization, influencing later developments in conic settings. The modern theory of conic optimization took shape in the late 1980s and early 1990s through the efforts of Yurii Nesterov and Arkadi Nemirovski, who introduced self-concordant barrier functions and interior-point methods adaptable to general convex cones. Their 1994 monograph formalized polynomial-time interior-point algorithms for a broad class of cone programs, shifting the focus from the ellipsoid method's theoretical efficiency to practical, high-performance solvers. Key milestones followed, including Farid Alizadeh's 1991 PhD work and subsequent 1995 paper, which positioned semidefinite programming as a powerful conic extension with applications to combinatorial optimization via interior-point techniques. In 2001, Aharon Ben-Tal and Arkadi Nemirovski's book further formalized conic quadratic programming, emphasizing its role in robust optimization and engineering applications through detailed analysis and algorithms. These developments marked the transition to polynomial-time solvability for diverse cone classes, establishing conic optimization as a cornerstone of convex optimization.

Mathematical Foundations

Convex Cones

A convex cone is a subset K \subseteq \mathbb{R}^n that is closed under nonnegative linear combinations, meaning for all x, y \in K and \theta, \lambda \geq 0, the point \theta x + \lambda y \in K.^[7] This structure combines the properties of a cone, which is closed under positive scaling, with convexity, ensuring that the set remains invariant under addition and scaling by nonnegative scalars.^[7] Common examples include the nonnegative orthant \mathbb{R}^n_+ = \{ x \in \mathbb{R}^n \mid x_i \geq 0, \, i=1,\dots,n \}, which captures componentwise nonnegativity, and the positive semidefinite cone S^n_+ = \{ X \in \mathbb{S}^n \mid X \succeq 0 \}, consisting of symmetric matrices with nonnegative eigenvalues.^[7] Convex cones exhibit several important properties that underpin their utility in optimization. Convexity follows directly from the definition, guaranteeing that any line segment between points in the cone lies within it.^[7] A cone is pointed if it contains no line through the origin, formally K \cap (-K) = \{0\}, which prevents the inclusion of both a vector and its negative except at zero.^[7] Solidity requires the cone to have a nonempty interior, \operatorname{int} K \neq \emptyset, enabling the distinction between weak and strict inequalities.^[7] The facial structure refers to the exposed faces of the cone, which are subcones arising from intersections with supporting hyperplanes, providing a hierarchical decomposition that aids in analyzing constraint boundaries.^[7] A proper cone integrates these attributes by being convex, closed, pointed, and solid.^[8] The dual cone of K is defined as K^* = \{ y \in \mathbb{R}^n \mid y^T x \geq 0 \ \forall x \in K \}, which is itself a closed convex cone representing the set of linear functionals nonnegative on K.^[7] Self-dual cones satisfy K = K^*, a symmetry that simplifies duality mappings; notable instances are \mathbb{R}^n_+ and S^n_+, where the inner product aligns with the cone's ordering.^[7] Pointedness and solidity are dual properties: the dual of a pointed cone is solid, and vice versa.^[9] In optimization, convex cones define feasible sets through generalized inequalities x \preceq_K y if y - x \in K, ensuring these sets are convex and thus permitting global optima for convex objectives over them.^[7] This convexity facilitates efficient solvability via interior-point methods and guarantees strong duality under conditions like Slater's, where a strictly feasible point exists in the interior of the cone-constrained set.^[7]

Standard Formulations

The standard formulation of a conic optimization problem in primal form is given by

\begin{align*} \min &\quad \mathbf{c}^\top \mathbf{x} \\ \text{s.t.} &\quad A \mathbf{x} = \mathbf{b}, \\ &\quad \mathbf{x} \in [K](/page/K), \end{align*}

where \mathbf{x} \in \mathbb{R}^n is the optimization variable, \mathbf{c} \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, and \mathbf{b} \in \mathbb{R}^m are problem data, and K \subseteq \mathbb{R}^n is a proper convex cone (closed, convex, pointed, and with nonempty interior).^[10] The corresponding dual problem, derived via Lagrangian relaxation, takes the form

\begin{align*} \max &\quad \mathbf{b}^\top \mathbf{y} \\ \text{s.t.} &\quad A^\top \mathbf{y} + \mathbf{s} = \mathbf{c}, \\ &\quad \mathbf{s} \in K^*, \end{align*}

where \mathbf{y} \in \mathbb{R}^m and \mathbf{s} \in \mathbb{R}^n are the dual variables, and K^* = \{ \mathbf{z} \in \mathbb{R}^n \mid \mathbf{z}^\top \mathbf{x} \geq 0 \ \forall \mathbf{x} \in K \} denotes the dual cone of K.^[10] This duality links the primal minimization to a maximization over the dual cone, reflecting the conic structure's convexity. Under Slater's condition, which requires the existence of a strictly feasible point \mathbf{x}^\circ \in \mathrm{int}(K) satisfying A \mathbf{x}^\circ = \mathbf{b}, strong duality holds: the primal and dual optimal values are equal, provided the primal value is finite.^[10] Infeasibility and unboundedness of the primal can be detected using generalizations of Farkas' lemma to cones. Specifically, the primal is infeasible if and only if there exists \mathbf{y} \in \mathbb{R}^m such that A^\top \mathbf{y} \in K^* and \mathbf{b}^\top \mathbf{y} < 0; unboundedness occurs if there exists a recession direction \mathbf{d} \in K with A \mathbf{d} = \mathbf{0} and \mathbf{c}^\top \mathbf{d} < 0.^[10] These alternatives provide certificates for solver termination without solving the full problem.

Problem Variants

Linear Conic Programs

Linear conic programs, often abbreviated as CLPs, generalize classical linear programming by incorporating convex cone constraints while maintaining a linear objective function. The standard formulation is to minimize \mathbf{c}^T \mathbf{x} subject to A\mathbf{x} = \mathbf{b} and \mathbf{x} \in K, where A is a linear map from a finite-dimensional space to \mathbb{R}^m, \mathbf{b} \in \mathbb{R}^m, and K is a closed convex cone. This form defines the feasible set as the intersection of an affine subspace with the cone K, capturing a broad class of convex constraints in a unified manner.^[11] When the cone K = \mathbb{R}^n_+, the nonnegative orthant, the problem reduces to a classical linear program, which is solvable in polynomial time using methods like the simplex algorithm or interior-point methods. This reduction highlights CLPs as a natural extension of linear programming, preserving the linearity of the objective and constraints while expanding the feasible region's structure through general cones. Seminal work by Nesterov and Nemirovski established the framework for such generalizations. CLPs are polynomial-time solvable provided the cone K admits a self-concordant barrier function, enabling efficient interior-point algorithms that achieve an \epsilon-optimal solution in O(\sqrt{\nu} \log(1/\epsilon)) iterations, where \nu is the barrier parameter measuring the cone's complexity (e.g., \nu = n for the nonnegative orthant in \mathbb{R}^n). This complexity bound, derived from path-following interior-point methods, ensures practical scalability for moderate-sized problems. A representative application arises in portfolio optimization, where conic constraints on returns can enforce robustness to uncertainty, such as minimizing risk subject to expected return thresholds defined over conic sets rather than simple linear bounds.^[11]

Second-Order Cone Programs

Second-order cone programming (SOCP) encompasses convex optimization problems where the feasible region is defined by the intersection of affine subspaces and Cartesian products of second-order cones, also known as Lorentz cones. The Lorentz cone \mathcal{L}^{n} in \mathbb{R}^{n} is given by \mathcal{L}^{n} = \{ (x, t) \in \mathbb{R}^{n-1} \times \mathbb{R} \mid \|x\|_2 \leq t \}, where \| \cdot \|_2 denotes the Euclidean norm. This structure bridges linear programming, which uses simpler polyhedral cones, and semidefinite programming, which involves more general spectrahedral cones, by incorporating quadratic constraints via norms.^[12]^[13] A standard formulation of an SOCP minimizes a linear objective subject to second-order cone inequalities of the form \|A_i x + b_i\|_2 \leq c_i^\top x + d_i for i = 1, \dots, m, along with possible linear equality constraints Ax = b. Here, x \in \mathbb{R}^n is the decision variable, c \in \mathbb{R}^n defines the objective \min c^\top x, and the matrices A_i, vectors b_i, c_i, and scalars d_i parameterize the constraints. This form naturally arises in problems requiring bounds on Euclidean norms of affine expressions, ensuring convexity since the feasible set is the intersection of second-order cones with an affine space.^[14]^[15] To express this standard form in conic form, introduce auxiliary variables t_i = c_i^\top x + d_i for each i, transforming each inequality \|A_i x + b_i\|_2 \leq t_i into the membership constraint (t_i, A_i x + b_i) \in \mathcal{L}^{k_i + 1}, where k_i is the row dimension of A_i. The full problem then becomes \min c^\top x subject to Ax = b and x augmented with the t_i belonging to the product of second-order cones \mathcal{L}^{k_1 + 1} \times \cdots \times \mathcal{L}^{k_m + 1}. This mapping, sometimes involving a rotational transformation for equivalent hyperbolic representations, aligns SOCP directly with the general conic optimization framework over Cartesian products of Lorentz cones.^[14]^[12] SOCP formulations are particularly suited to robust optimization tasks, such as ensuring linear constraints hold under ellipsoidal uncertainties bounded by norms, and to control problems involving stability margins or norm-based performance guarantees. These applications leverage the efficiency of SOCP solvers for handling such constraints without resorting to higher-dimensional semidefinite relaxations.^[16]

Advanced Forms

Semidefinite Programs

Semidefinite programming (SDP) is a subfield of conic optimization that involves optimizing a linear function over the cone of positive semidefinite matrices. In standard form, an SDP seeks to minimize the trace inner product \mathbf{C} \bullet \mathbf{X} subject to linear equality constraints \mathbf{A}_i \bullet \mathbf{X} = b_i for i = 1, \dots, m, and the semidefiniteness constraint \mathbf{X} \succeq 0, where \mathbf{X} is an n \times n symmetric matrix variable, \mathbf{C} and \mathbf{A}_i are given symmetric matrices, b_i are scalars, and the inner product is defined as \mathbf{A} \bullet \mathbf{B} = \trace(\mathbf{A}^\top \mathbf{B}).^[17] This formulation generalizes linear programming by replacing nonnegativity constraints on vector entries with positive semidefiniteness on matrix entries, enabling the modeling of problems involving quadratic forms and eigenvalues.^[18] The feasible region of an SDP is a spectrahedron, defined by the intersection of the semidefinite cone \mathbb{S}^n_+ = \{ \mathbf{X} \in \mathbb{S}^n \mid \mathbf{X} \succeq 0 \} with affine subspaces, where \mathbb{S}^n denotes the space of n \times n symmetric matrices equipped with the trace inner product. The semidefinite cone \mathbb{S}^n_+ is convex, closed, pointed, full-dimensional in \mathbb{S}^n, and self-dual under this inner product, meaning its dual cone coincides with itself: (\mathbb{S}^n_+)^* = \mathbb{S}^n_+.^[19] Its facial structure is determined by linear subspaces L \subseteq \mathbb{R}^n, where the faces consist of matrices whose range is contained in L, providing a rich geometric framework that influences the structure of SDP feasible sets.^[20] In the standard conic form, the linear mappings \mathbf{A}_i \bullet \mathbf{X} are implemented via symmetric matrix coefficients, ensuring compatibility with the symmetric structure of \mathbb{S}^n.^[17] Semidefinite programs can be solved in polynomial time using interior-point methods, which exploit the self-duality and barrier functions of \mathbb{S}^n_+ to achieve convergence in a number of iterations bounded by O(\sqrt{n} \log(1/\epsilon)) for accuracy \epsilon, with each iteration requiring O(m n^2) arithmetic operations in unstructured cases, where m is the number of equality constraints.^[18] Compared to second-order cone programs, SDPs involve higher-dimensional variables since the semidefinite cone lives in a space of dimension n(n+1)/2, leading to increased computational demands for large n, despite the shared polynomial solvability.^[18]

General Conic Programs

General conic programs generalize the conic optimization framework by allowing the constraint cone K to be any proper convex cone, beyond the standard positive orthant, second-order Lorentz, or positive semidefinite cones, thereby enabling the representation of a wide variety of nonlinear convex constraints through affine mappings. The canonical form is to minimize c^\top x subject to F(x) \in K, where F is affine and K is closed, convex, pointed, and solid (with nonempty interior).^[5] This formulation unifies linear, second-order cone, and semidefinite programs under a single structure when K is chosen accordingly, while extending to more complex cones for advanced modeling.^[2] Non-standard cones, such as the exponential and power cones, extend the modeling capabilities of general conic programs to handle functions involving exponentials, logarithms, and powers that are not representable with simpler cones.^[5] The three-dimensional exponential cone is defined as the closure of \{(x, y, z) \in \mathbb{R}^3 \mid y > 0, \, y \exp(x/y) \leq z\}, which captures constraints like relative entropy terms of the form x \log(x/y).^[21] Similarly, the power cone, often formulated in three dimensions as \{(x, y, z) \in \mathbb{R}^3_+ \mid z \geq x^\alpha y^{1-\alpha}, \, \alpha \in (0,1)\}, facilitates the representation of p-norms for p \neq 2, such as |t| \geq \|u\|_p for general p > 1.^[22] A key challenge in solving general conic programs over non-standard cones lies in constructing self-concordant barrier functions, which are essential for the efficiency of interior-point methods, as they ensure polynomial-time solvability when the barrier parameter \nu is bounded. For the exponential cone, a 3-self-concordant barrier function is -\log(y \log(z/y) - x) - \log y - \log z, enabling robust numerical implementation in solvers like MOSEK.^[23] For the power cone, barriers with parameter \nu = 3 have been developed, improving upon earlier \nu = 4 constructions and supporting extensions to generalized power cones.^[22] The modeling power of general conic programs is particularly evident in reformulating geometric programs and hyperbolic constraints into conic form, where exponential cones handle posynomial inequalities via logarithmic transformations, and power cones represent generalized means or hypograph constraints like \left( \sum_i x_i^p \right)^{1/p} \leq t.^[24] This allows convex optimization solvers to tackle problems originally posed in non-convex forms, such as resource allocation or circuit design, by exploiting the rich structure of these cones.^[5]

Duality Theory

Primal-Dual Framework

In conic optimization, the primal-dual framework establishes a symmetric relationship between a minimization problem and its maximization counterpart, enabling the analysis of optimality and sensitivity through paired structures. The standard primal conic program is formulated as minimizing \mathbf{c}^\top \mathbf{x} subject to A \mathbf{x} = \mathbf{b} and \mathbf{x} \in \mathcal{K}, where A is a linear mapping, \mathbf{b} is a vector in the range space, \mathbf{c} is the objective coefficient vector, and \mathcal{K} is a closed convex cone. The associated dual program maximizes \mathbf{b}^\top \mathbf{y} subject to A^\top \mathbf{y} + \mathbf{s} = \mathbf{c} and \mathbf{s} \in \mathcal{K}^*, where \mathbf{y} is the dual variable and \mathcal{K}^* denotes the dual cone. This pair satisfies the relation that the primal optimal value is at least the dual optimal value under feasibility, forming the basis for duality theory in conic settings.^[25] A key element of this framework is the central path, which parameterizes a trajectory of approximate solutions converging to the optimum as a barrier parameter approaches zero. For a given \mu > 0, the central path consists of points (\mathbf{x}(\mu), \mathbf{y}(\mu), \mathbf{s}(\mu)) satisfying the primal feasibility A \mathbf{x}(\mu) = \mathbf{b}, dual feasibility A^\top \mathbf{y}(\mu) + \mathbf{s}(\mu) = \mathbf{c}, and the centering condition \mathbf{x}(\mu)^\top \mathbf{s}(\mu) = \mu, with \mathbf{x}(\mu) \in \text{int}(\mathcal{K}) and \mathbf{s}(\mu) \in \text{int}(\mathcal{K}^*). As \mu \to 0^+, these points approach the primal-dual optimal solutions, providing a smooth path that underlies path-following algorithms for solving conic programs. This structure generalizes the central path from linear programming to broader conic forms, leveraging barrier functions for self-concordance to ensure convergence properties.^[26] The symmetry inherent in the primal-dual framework is particularly pronounced when embedding problems into self-dual cones, allowing unified treatment of diverse conic programs. Self-dual cones satisfy \mathcal{K} = \mathcal{K}^* under an appropriate inner product, such as the nonnegative orthant, second-order cone, and semidefinite cone. The homogeneous self-dual embedding reformulates the primal-dual pair as a single convex feasibility problem in a product space: find a nonzero vector in the intersection of a linear subspace and a self-dual cone, which encodes both problems symmetrically. This approach facilitates solving via operator-splitting methods, providing certificates of optimality, infeasibility, or unboundedness without distinguishing primal from dual, and extends to nonsymmetric cones through homogenization.^[27] Weak duality, a foundational result in this framework, asserts that for any primal feasible \mathbf{x} and dual feasible (\mathbf{y}, \mathbf{s}), the inequality \mathbf{c}^\top \mathbf{x} \geq \mathbf{b}^\top \mathbf{y} holds, establishing an upper bound on the dual objective by the primal. To prove this, note that dual feasibility implies \mathbf{s} = \mathbf{c} - A^\top \mathbf{y} \in \mathcal{K}^*, so \mathbf{x}^\top \mathbf{s} \geq 0 since \mathbf{x} \in \mathcal{K}. Substituting yields \mathbf{x}^\top (\mathbf{c} - A^\top \mathbf{y}) \geq 0, or \mathbf{c}^\top \mathbf{x} \geq \mathbf{x}^\top A^\top \mathbf{y} = (A \mathbf{x})^\top \mathbf{y} = \mathbf{b}^\top \mathbf{y}, relying solely on the nonnegativity of the duality pairing in cone properties. This proof extends the linear programming case and holds without regularity assumptions, underscoring the robustness of conic duality.^[25]

Duality Conditions

In conic optimization, strong duality holds when the optimal values of the primal and dual problems coincide, ensuring zero duality gap and attainment of optima under appropriate conditions. A key sufficient condition for strong duality is Slater's condition, which requires the existence of a strictly feasible point in the primal feasible set, meaning there exists x such that Ax = b and x \in \mathrm{ri}(K), and feasibility of the dual problem. This condition guarantees that both problems attain their optima if feasible, as established in the framework of general convex conic programs.^[25] For second-order cone and semidefinite programs, Slater's condition is particularly effective due to the rich interior structure of these cones, leading to reliable numerical duality in practice. When strict feasibility fails, the feasible sets may lie on lower-dimensional faces of the cone, potentially causing duality gaps or unattainability. Facial reduction addresses this by iteratively identifying exposed faces of the cone that contain the feasible set, reducing the problem dimension to restore strict feasibility and ensure strong duality. The process begins by finding a reducing certificate, a direction in the dual cone orthogonal to the affine constraints, which exposes a proper face; repeating this yields a minimal face representation. The singularity degree of the problem is defined as the minimal number of such reduction steps needed to reach the minimal face containing the feasible set, quantifying the extent of irregularity. This technique is crucial for ill-posed conic problems, such as those with singular data in semidefinite programming, where it can dramatically improve solver stability and convergence. Zero duality gap is assured under qualifiable constraints, such as when the primal and dual feasible sets have nonempty relative interiors intersecting appropriately with the affine space, but failures can occur in cones lacking solid interiors. For instance, the exponential cone, a proper cone defined as the closure of \{(x,y,z) \in \mathbb{R}^3 \mid y e^{x/y} \leq z, y > 0\}, can exhibit positive duality gaps when neither the primal nor dual problem is strictly feasible, highlighting the need for cone-specific regularity checks like Slater's condition even in proper cones such as the nonnegative orthant or positive semidefinite cone.^[5] At optimality, the Karush-Kuhn-Tucker (KKT) conditions for conic programs adapt the classical framework to include conic feasibility: primal feasibility Ax = b, x \in K; dual feasibility A^T y + s = c, s \in K^*; stationarity A^T y + s = c; and cone complementarity x \perp s, meaning \langle x, s \rangle = 0 with both x \in K and s \in K^*. These conditions are necessary and sufficient for optimality under strict feasibility, providing a certificate of solution quality analogous to linear programming. In the primal-dual framework, the central path approaches points satisfying these KKT conditions, aiding theoretical analysis of convergence.

Solution Approaches

Interior-Point Methods

Interior-point methods for conic optimization rely on barrier functions to navigate the interior of the feasible cone while approaching the optimal solution. These methods transform the conic program—typically formulated as minimizing a linear objective subject to linear equality constraints and a conic inequality—by incorporating a logarithmic barrier term that penalizes proximity to the boundary of the cone K. Specifically, the barrier subproblem is to minimize c^\top x + \mu \nu \psi_K(x), where \psi_K is a self-concordant barrier function for the cone K, \mu > 0 is the barrier parameter that decreases over iterations, and \nu is the complexity parameter of the barrier measuring its self-concordance degree. For the standard linear program over the nonnegative orthant, \nu = n where n is the dimension; for second-order cone programs, \nu = 2 per cone; and for semidefinite programs over m \times m positive semidefinite matrices, \nu = m. The central path of solutions to these barrier subproblems, parameterized by \mu, converges to the optimal set as \mu \to 0. Path-following algorithms approximate points on this central path using Newton steps to solve the optimality conditions of the barrier subproblem. The self-concordance property of \psi_K—which bounds the third derivative relative to the second—ensures that these Newton steps are affine-invariant and damped appropriately, maintaining progress toward the path without line searches in short-step variants. This framework, introduced for general convex cones with universal self-concordant barriers, guarantees polynomial-time convergence when \nu is moderate. Primal-dual interior-point methods extend this approach by simultaneously optimizing over primal and dual variables, leveraging the conic duality framework to solve the linearized Karush-Kuhn-Tucker (KKT) conditions. These methods compute search directions (\Delta x, \Delta y, \Delta s) by solving a symmetric linear system derived from the Newton equations for the joint barrier function on the primal cone K and dual cone K^*, often using Nesterov-Todd scaling for self-dual cones to ensure centrality.^[28] This scaling preserves the self-concordance and enables full-step or predictor-corrector variants that avoid adaptive damping.^[28] The convergence of these methods is polynomial, requiring O(\sqrt{\nu} \log(1/\epsilon)) iterations to achieve an \epsilon-optimal solution, where each iteration solves a linear system of size comparable to the problem dimension. This bound holds for path-following schemes with self-concordant barriers and extends to primal-dual methods under similar assumptions. For instance, in semidefinite programming, the iteration complexity is O(\sqrt{m} \log(1/\epsilon)), establishing the practical efficiency of these algorithms for moderate-sized problems.

Cutting-Plane Methods

Cutting-plane methods provide an alternative to interior-point techniques for solving conic optimization problems, particularly when self-concordant barrier functions for the cone are unavailable or difficult to compute. These methods iteratively refine an outer approximation of the feasible set or the objective function by adding linear inequalities, known as cutting planes, generated via separation or subgradient oracles that certify infeasibility or provide gradient information at trial points. By relying on such oracles rather than smooth barrier functions, cutting-plane approaches can handle a broad class of convex cones, including those arising in semidefinite and more general conic programs.^[29] The ellipsoid method represents a foundational cutting-plane algorithm applicable to conic programs through the use of a separation oracle for the cone. It initializes a large ellipsoid containing the feasible region and, at each iteration, queries the oracle at the ellipsoid's center; if the point is infeasible, a separating hyperplane (cut) is added, and the ellipsoid is updated to a smaller one containing the intersection of the previous ellipsoid with the half-space defined by the cut. This process reduces the ellipsoid's volume by a factor of at most $1 - \frac{1}{2n} per step, where n is the dimension, ensuring polynomial-time convergence to an \epsilon-optimal solution in O(n^2 \log(1/\epsilon)) iterations. Despite its theoretical efficiency, the method is impractical for large-scale conic problems due to the high per-iteration cost of ellipsoid updates and the quadratic dependence on dimension.^[30]^[31] Bundle methods extend cutting-plane ideas to nonsmooth convex minimization, approximating the objective (often the dual) with a piecewise linear lower bound constructed from a bundle of subgradients obtained at previous points, then solving a quadratic subproblem to select the next trial point and add new cuts if needed. In the context of conic optimization, the spectral bundle method adapts this framework for semidefinite programs by incorporating eigenvalue-based approximations in the dual, where cutting planes are derived from subproblems involving the maximum eigenvalue of affine matrix functions, enabling efficient handling of large-scale structured instances. This approach stabilizes the quadratic model with proximity terms to ensure descent and global convergence.^[32] The analytic center cutting-plane method focuses on feasibility problems in conic programs by maintaining a polyhedral outer approximation of the feasible set and computing its analytic center—the maximizer of the logarithmic barrier over the current approximation—as the trial point. For semidefinite programs, if the center violates feasibility, a semidefinite cut is generated via an oracle and added to tighten the approximation, with all iterates maintained as positive definite matrices to facilitate numerical stability. The method requires O^*(m^3 / \epsilon^2) total cuts in the worst case to find a point within distance \epsilon of the feasible set, where m is the matrix dimension. This framework generalizes to arbitrary conic programs using conic cuts, bounding the number of Newton steps needed to recover the analytic center after each cut addition.^[33]^[34] A key advantage of cutting-plane methods, including the ellipsoid, bundle, and analytic center variants, is their applicability to conic programs over cones lacking efficient self-concordant barriers, such as the copositive cone, where interior-point methods falter. For copositive optimization, these techniques approximate the cone with inner and outer polyhedral relaxations via simplicial partitions, iteratively adding cuts to refine the approximation until convergence, enabling solutions to problems with thousands of variables that would otherwise be intractable.^[35]

Applications

Engineering Design

Conic optimization plays a pivotal role in engineering design, particularly in fields requiring robust performance under uncertainty, such as control systems and structural engineering. By formulating design problems as semidefinite programs (SDPs) or second-order cone programs (SOCPs), engineers can optimize complex constraints that ensure stability, efficiency, and reliability in physical systems. These methods leverage the convex nature of conic forms to provide globally optimal solutions, often outperforming traditional heuristic approaches in handling nonlinearities and uncertainties. In robust control design, SDPs are extensively used to guarantee system stability via Lyapunov functions, where linear matrix inequalities (LMIs) model the constraints. A key application involves minimizing the H-infinity norm of a transfer function to achieve robust performance against disturbances; this is formulated as an SDP by seeking a positive semidefinite matrix that satisfies LMI conditions derived from the system's state-space representation. For instance, in aerospace applications like aircraft autopilot design, this approach ensures the closed-loop system remains stable for all perturbations within a bounded uncertainty set, as demonstrated in early works on LMI-based control synthesis. The resulting controllers often yield significant improvements in disturbance rejection compared to classical methods in benchmark tests. Sensor network localization problems, which determine the positions of nodes based on distance measurements, are effectively solved using SOCPs to minimize positioning errors under noisy constraints. The formulation treats distances as second-order cone constraints, where the objective is to minimize the sum of squared errors between measured and estimated distances, subject to hyperbolic inequalities ensuring geometric consistency. This approach is particularly valuable in wireless sensor networks for environmental monitoring or structural health assessment, where it enables accurate 3D localization. Seminal implementations have shown that SOCP-based methods converge faster and achieve lower localization errors than least-squares alternatives, especially in non-convex scenarios approximated via convex relaxations. For truss design in structural engineering, SDP relaxations address stress and stability constraints by enforcing positive semidefiniteness on the stiffness matrix, allowing optimization of member cross-sections to minimize weight while satisfying equilibrium and buckling conditions. The problem is cast as an SDP where the dual form provides bounds on the feasible stress distributions, ensuring the structure remains semidefinite under load variations. This technique has been applied to bridge and tower designs, yielding lightweight configurations that meet safety margins over linear programming approximations, as validated in finite element simulations. By relaxing non-convex quadratic constraints into semidefinite ones, these methods provide tight approximations to the global optimum, facilitating practical implementations in civil engineering software. Antenna array design for beamforming utilizes SOCPs to optimize signal patterns under power and interference constraints, formulating the beamformer weights as variables in a second-order cone to maximize the signal-to-interference-plus-noise ratio (SINR). The constraints model the array's response as norms bounded by cones, enabling robust designs that maintain directivity in the presence of steering errors or jammers. In radar and communication systems, such as 5G base stations, this results in beam patterns with enhanced sidelobe suppression, improving coverage and reducing interference in multi-user scenarios. SOCP solvers efficiently handle these problems for arrays with dozens of elements, outperforming SDP alternatives in computational speed for real-time applications.

Financial Modeling

Conic optimization plays a pivotal role in financial modeling, particularly in addressing uncertainties inherent in market dynamics and asset behaviors. In portfolio optimization, second-order cone programming (SOCP) extends the classical Markowitz mean-variance framework by incorporating transaction costs through norm-based approximations. Linear transaction costs can be modeled directly within the optimization, leading to tractable SOCP formulations that balance expected returns against risk while penalizing excessive trading. For instance, fixed and proportional costs are handled via additional linear constraints, ensuring the problem remains convex and solvable efficiently.^[36] Semidefinite programming (SDP) finds application in option pricing through convex relaxations that provide tight bounds without relying on specific stochastic models. For American options, which allow early exercise and introduce non-convexity, SDP relaxations leverage moment problems to derive upper and lower price bounds by optimizing over positive semidefinite matrices representing feasible distributions. These relaxations exploit the dual structure to ensure no-arbitrage conditions, offering model-free guarantees on pricing accuracy. Similarly, SDP is used for volatility bounds, where it solves semidefinite programs to estimate implied volatility surfaces consistent with observed option prices, aiding in calibration and risk assessment. Seminal work demonstrates that cutting-plane algorithms enhance SDP efficiency for these bounds, achieving near-optimal solutions for multi-asset options.^[37] Risk measures in finance, such as conditional value-at-risk (CVaR), admit conic representations that facilitate robust portfolio decisions under tail risks. CVaR, which captures expected losses beyond a value-at-risk threshold, can be reformulated as an SOCP when integrated with mean-variance objectives, allowing optimization over second-order cones to minimize downside risk while maximizing returns. This conic form enables efficient handling of joint constraints on expected shortfall and variance. For robust hedging, SOCP models uncertainty in asset returns via ellipsoidal sets, formulating superhedging strategies that protect against worst-case scenarios; for example, hedging an index option involves solving an SOCP to minimize the maximum hedging error over uncertain return distributions. These approaches ensure portfolios are resilient to model misspecification, with duality providing interpretable certificates of robustness.^[38]^[39] In credit risk management, SDP supports covariance estimation under stress testing by enforcing positive semidefiniteness on estimated matrices, crucial for simulating correlated defaults in portfolios. Stress scenarios often distort historical covariances, leading to non-positive semidefinite estimates; SDP resolves this by solving trace-minimization problems over the semidefinite cone to project data onto feasible matrices while preserving key statistical properties. This is particularly valuable in regulatory stress tests, where accurate covariance informs capital requirements for credit portfolios exposed to economic shocks. Applications demonstrate that SDP-based estimators reduce estimation errors in high-dimensional settings, improving the reliability of value-at-risk projections for credit exposures.^[40]

References

[1]
[PDF] A ten page introduction to conic optimization
1.1. Optimization and computational hardness. Optimization is about maximizing or minimizing a function over a set.
[2]
[PDF] A Guide to Conic Optimisation and its Applications
In this invited pa- per, we give a gentle introduction to conic optimisation, followed by a survey of applications in OR and related areas.
[3]
[PDF] Lecture 6 Conic optimization - MIT
Feb 29, 2024 · 1 Conic optimization A conic optimization problem is a nonlinear optimization problem whose feasible set is the intersec- tion between an ...
[4]
[PDF] Differentiating Through a Conic Program - Stanford University
May 23, 2019 · A cone program is an optimization problem in which the objective is to minimize a linear function over the intersection of a subspace and a ...<|control11|><|separator|>
[5]
[PDF] 15. Conic optimization
Outline. • conic linear program. • examples. • modeling. • duality. Page 7 ... Definition: for α = (α1,α2,...,αm) > 0 and m. P i=1 αi = 1. Kα = (x, y) ∈ R m.
[6]
[PDF] Interior-point methods for optimization
To contrast with the general case, Nesterov and. Nemirovski listed a considerable number of important problems where com- putationally tractable self-concordant ...
[7]
[PDF] Convex Optimization
This book is about convex optimization, a special class of mathematical optimiza- tion problems, which includes least-squares and linear programming ...
[8]
[PDF] CS295: Convex Optimization
A set C is a convex cone if it is convex and a cone, i.e., x1,x2 ∈ C ... Definition (dual cones). Let K be a cone. The set. K∗ = {y ∣ xT y ≥ 0 ∀x ...
[9]
[PDF] Conic optimization: an elegant framework for convex optimization
The additional notions of solidness and pointedness also behave well when taking the dual of a convex cone: indeed, these two properties are dual to each other ...
[10]
8 Duality in conic optimization — MOSEK Modeling Cookbook 3.4.0
Duality theory is a rich and powerful area of convex optimization, and central to understanding sensitivity analysis and infeasibility issues.
[11]
[PDF] Conic Linear Programming - Stanford University
graduate student, Farid Alizadeh. He, working then on combinatorial optimiza- tion, introduced me “semidefinite optimization” or linear programming over the.
[12]
[PDF] Second-order cone programming - Department of Statistics
Aug 18, 2001 · Second-order cone programming (SOCP) problems are convex optimization problems in which a linear function is minimized over the intersection ...
[13]
[PDF] SOCP and SDP 6.1 Recap 6.2 Second-order Cone Optimization
Feb 2, 2012 · In this lecture we focus on a cone that involves second-order cones only (second-order cone programming, or SOCP) or the semi-definite cone only ...
[14]
3 Conic quadratic optimization — MOSEK Modeling Cookbook 3.4.0
We leave it for the reader to check that the intersection of convex cones is a convex cone; this property enables us to assemble complicated optimization models ...
[15]
[PDF] 16 Linear programming, second-order cone programming, semidef
A linear program in standard form is an optimization problem of the form min ... A second-order cone program (SOCP) is an optimization problem of the form.
[16]
[PDF] Applications of second-Order cone programming '
The main goal of the Paper is to present an overview of examples and appli- cations of second-Order cone programming. We Start in Section 2 by describing.
[17]
[PDF] Introduction to Semidefinite Programming (SDP)
With this notation, we are now ready to. define a semidefinite program. A semidefinite program (SDP) is an opti- mization problem of the form: SDP : minimize C ...
[18]
[PDF] Semidefinite Programming - Stanford University
Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial ...
[19]
Chapter 2 Semidefinite Optimization
... Formulation and Duality. Semidefinite programs (SDPs) are linear optimization problems over spectrahedra. A standard SDP in primal form is written as p⋆=minX∈ ...
[20]
Semidefinite programming - ScienceDirect.com
Mar 16, 2002 · Consequently, the facial structure of the semidefinite cone has a strong influence on the facial structure of the feasible set. One such ...
[21]
5 Exponential cone optimization — MOSEK Modeling Cookbook 3.4.0
### Summary of Exponential Cone from https://docs.mosek.com/modeling-cookbook/expo.html
[22]
[PDF] On self-concordant barriers for generalized power cones
Jan 30, 2018 · In the study of interior-point methods for nonsymmetric conic optimization and their applications, Nesterov [5] introduced the power cone, ...
[23]
https://www.seas.ucla.edu/~vandenbe/236C/lectures/barriers.pdf
[24]
[PDF] Conic Geometric Programming - People
Oct 2, 2013 · We introduce and study conic geometric programs (CGPs), which are convex optimization problems that unify geometric programs (GPs) and conic ...
[25]
[PDF] Conic Programming
The first topic we will discuss in the course is conic programming, which is a valu- able tool for the study of quantum information.<|control11|><|separator|>
[26]
[PDF] A Homogeneous Interior-Point Algorithm for Nonsymmetric Convex ...
Nesterov proposed in [16] a barrier function for the three-dimensional power cone with parameter ν = 4. Our computational experience shows that Fα is better ...
[27]
[PDF] Conic Optimization via Operator Splitting and Homogeneous Self ...
Jul 25, 2016 · Abstract We introduce a first order method for solving very large convex cone programs. The method uses an operator splitting method, ...
[28]
Primal-Dual Interior-Point Methods for Self-Scaled Cones - SIAM.org
In this paper we continue the development of a theoretical foundation for efficient primal-dual interior-point algorithms for convex programming problems ...Missing: Nemirovski | Show results with:Nemirovski<|separator|>
[29]
[PDF] Localization and Cutting-Plane Methods
The goal of cutting-plane and localization methods is to find a point in a convex set X ⊆ Rn, which we call the target set, or, in some cases, to determine ...
[30]
The Ellipsoid Method - PubsOnLine
In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This.Missing: URL | Show results with:URL
[31]
[PDF] Oracles, Ellipsoid method and their uses in convex optimization
To sum up, the importance of the Ellipsoid method is that it allows you to see at a glance that a convex optimization problem is solvable in polynomial time: ( ...
[32]
A Spectral Bundle Method for Semidefinite Programming - SIAM.org
We present a method that allows us to compute acceptable approximations to the optimal solution of large problems within reasonable time.
[33]
An Analytic Center Cutting Plane Method for Semidefinite Feasibility ...
All iterates generated by the algorithm are positive definite matrices. The algorithm has a worst-case complexity of O*(m3/ε2) on the total number of cuts to be ...
[34]
An Analytic Center Cutting Plane Approach for Conic Programming
Aug 1, 2008 · We generalize the results obtained for the linear programming (LP), semidefinite programming (SDP), and second-order core programming (SOCP) ...<|separator|>
[35]
[PDF] Copositive Programming – a Survey - Optimization Online
As far as we are aware, there are two approaches to solve copositive pro- grams directly: one is a feasible descent method in the completely positive cone C∗, ...
[36]
[PDF] Portfolio optimization with linear and fixed transaction costs
We consider the problem of portfolio selection, with transaction costs and constraints on exposure to risk. Linear transaction costs, bounds on the vari-.
[37]
[PDF] Robust Optimization Approaches for Portfolio Selection - arXiv
Oct 26, 2020 · Many robust portfolio allocation problems can be formulated as Second Order Cone Programming (SOCP) problems [13]. 2.2 Robust Linear ...
[38]
Financial applications of semidefinite programming: a review and ...
Sep 27, 2019 · Gotoh, J., and H. Konno, 2002, Bounding option prices by semidefinite programming: a cutting plane algorithm, Management Science 48, 665–678.
[39]
Portfolio optimization using second order conic programming ...
Mar 22, 2020 · We demonstrate that, when using CVaR, several common nonlinear models can be expressed as second order cone programming problems and therefore ...
[40]
Robust One-Period Option Hedging | Operations Research
... robust problem is a second-order cone program that can be solved efficiently. We apply the approach to find an optimal portfolio to hedge an index option.
[41]
[PDF] Covariance Matrix Estimation for Interest-Rate Risk Modeling via ...
We propose a convex optimization (semi-definite programming) formulation for this estimation problem, and develop efficient algorithms. We apply our framework ...