Convex optimization (${\inf }_{z\in C}f(z)$)

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

For positive existing stakes $s_i$ and budget $b$, maximizing ${\sum }_i{p}_i{x}_i/(s_i+x_i)$ is equivalent to minimizing ${\sum }_i{p}_i{s}_i/(s_i+x_i)$. A positive multiplier $\tau$ chosen so that ${\sum }_i{x}_i=b$ gives the displayed allocation. Each coordinate minimizes $p_i{s}_i/(s_i+x)+\tau x$ on $x\ge 0$, which proves global optimality by Lagrangian sufficiency theorem. Its active set is ordered by $p_i/s_i$. Zero existing stakes require a separate payoff convention and can cause nonattainment; the positive-stake formula should not be extended through undefined ratios.

A separation oracle either certifies that a supplied point belongs to a convex feasible set or returns a violated linear inequality whose half-space contains the whole feasible set. Its running time can be small even when the set has exponentially many defining inequalities. Together with rational encoding bounds and an outer bound, this permits polynomial time ellipsoid method feasibility and optimization.

After testing nonnegative edge coordinates and any explicit box or budget inequalities, treat those coordinates as lengths. A shortest path of length below one supplies a violated path inequality; a minimum length at least one certifies all path inequalities. If no source-to-target path exists, all those inequalities are vacuous. Thus a polynomial time shortest path problem calculation separates an exponentially constrained linear program.

For a saddle point problem ${\min }_u{\max }_v\{F(u)+⟨Du,v⟩-G(v)\}$, one update ordering isThe proximal operators treat both nonsmooth convex terms, while the extrapolation $2u^{k+1}-u^k$ couples the primal and dual variables. The primal objective is $F(u)+G^{\ast }(Du)$, with $G^{\ast }$ the convex conjugate. A dual-first ordering is obtained by exchanging roles; consistent indexing is needed when comparing the formulas.

For proper lower semicontinuous convex functions on finite-dimensional Hilbert spaces, a nonempty saddle point set, and constant positive steps satisfying the displayed inequality, the primal-dual hybrid gradient method with extrapolation parameter one converges to a saddle point. The strict condition controls the bilinear coupling by the operator norm. It does not remove the need for existence of a saddle point. The fixed-step theorem and assumptions are recalled in Malitsky and Pock, A first-order primal-dual algorithm with linesearch, Section 1.

This is a proper convex function that has degree-one positive homogeneity, with $J(0)=0$. It need not be even or nonnegative; linear functionals are examples. Its subdifferential satisfiesThe two tests $z=0$ and $z=2u$ prove equality; the subgradient inequality then gives the global upper bound. Conversely that bound and equality prove the subgradient condition. Hence a subgradient at $u$ also supports every nonnegative multiple of $u$. Requiring $J(-u)=J(u)$ gives an absolutely one-homogeneous functional.

A nonzero $u$ satisfying this relation, with $Ku\ne 0$, generalizes the eigenfunction of an absolutely one-homogeneous functional to the quadratic geometry induced by the forward map. Pairing with $u$ yields $\lambda =J(u)/\Vert Ku{\Vert }^2$. With unit data norm it is a generalized singular vector. If $\lambda >0$, $0\le \alpha \lambda \le 1$ and the exact data are $Ku$, the vector $(1-\alpha \lambda )u$ minimizes the quadratic variational regularization objective. Substitute its raywise subgradient into the subgradient optimality condition. Every minimizing branch has the same predicted data, and injectivity of $K$ gives equality of vectors. The Bregman distance along this ray is zero even though the reconstruction is shrunk. For nonnegative $J$ the branch continues as $(1-\alpha \lambda {)}_{+}u$; nonnegativity supplies $0\in \partial J(0)$ for the threshold argument.

Background on these generalized singular vectors: Benning and Burger, Ground States and Singular Vectors of Convex Variational Regularization Methods.

Optimization of a linear function subject to affine constraints and membership in a closed convex cone. Choosing the positive semidefinite cone gives semidefinite programming; other choices include copositive optimization and completely positive optimization. Dual cones produce scalar-product bounds on feasible objectives.

For a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $b\in {\mathbb{R}}^m$, exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1{)}^T$ is obtained with $z=(1,1{)}^T$.

Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.

Brief geometric proof. The two systems cannot both hold, because they would implyFor existence of a certificate when $b\notin K$, closedness of finitely generated cones makes $K$ a closed convex cone, so separation from a closed convex cone supplies $y^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. Concretely, let $p$ be the Euclidean projection onto a convex set of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_2^2<0$. In the example, $p=(0,1{)}^T$ and $y=(1,0{)}^T$. Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.

An original historical source is Julius Farkas's ^[ref]. The linked archival record verifies the author, title and publication details.

Suppose a linear program has a Farkas' lemma certificate $\lambda \ge 0$, $A^T\lambda \ge 0$, $b^T\lambda =-1$. A purported feasible point of $Ax\le b+\epsilon 1$, $x\ge 0$ would imply $0\le {\lambda }^{T}Ax\le -1+\epsilon {\sum }_i{\lambda }_i$. Hence every relaxation below the displayed positive threshold remains infeasible. For rational inputs, bounds on the encoding length of a certificate supply the precision gap used by the ellipsoid method.

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

Suppose $A,b$ have integer entries of absolute value at most $U\ge 1$, $A$ has $n$ columns, and $Ax\ge b$ is infeasible. A Farkas certificate for linear inequalities can be chosen with $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and the displayed lower bound. Normalize an infeasibility certificate to obtain the last equality, then maximize $b^T\lambda$ over the resulting compact linear polyhedron. A maximizing extreme point has at most $n+1$ positive entries: otherwise the augmented columns $(A_i^T,1)$ on its support would be dependent, allowing feasible perturbations in both directions. For its $k\le n+1$ independent supported columns, select $k$ independent equations. Cramer's rule expresses the supported entries with a common nonzero integer determinant denominator. That determinant has absolute value at most $k!U^k\le [(n+1)U{]}^{n+1}$. The positive value $b^T\lambda$ therefore has a positive integer numerator over a denominator of at most this size, proving the bound.

An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.

A primal-dual interior-point method solves perturbed KKT conditions while updating both the primal variables and Lagrange multipliers. For inequalities written as $c_i\ge 0$, a logarithmic-barrier path has positive $c_i,y_i$ and perturbed complementarity $c_i{y}_i=\mu$. A Newton system for these coupled equations gives primal and dual corrections together, with damping to preserve positivity. This can avoid explicitly forming the most ill-conditioned eliminated barrier Hessian, although scaling and regularity still matter.

A barrier function penalizes approaching the boundary of a feasible set from its interior, typically diverging to $+\infty$ there. An interior-point method minimizes the original objective function plus a positive multiple of this penalty, then reduces that multiple. The logarithmic barrier is the basic example for smooth inequality optimization constraints.

For optimization constraints $c_i(x)\ge 0$ and $\mu >0$, the logarithmic barrier objective is $f_{\mu }(x)=f(x)-\mu {\sum }_i\log c_i(x)$ on $D=\{x:c_i(x)>0\forall i\}$. Its derivatives are defined only on this strictly feasible open subset. One may extend its value to $+\infty$ off $D$ to formulate an extended-real convex function. The penalty alone is $-{\sum }_i\log c_i$, while $f_{\mu }$ includes the original objective function.

When $f$ is convex and each $c_i$ is concave, $D$ is a convex set andEvery term of this Hessian matrix is a positive semidefinite matrix, so $f_{\mu }$ is convex. Its critical point satisfies the stationarity part of the Karush-Kuhn-Tucker conditions with estimates ${\lambda }_i=\mu /c_i(x)>0$ and perturbed complementary slackness ${\lambda }_i{c}_i(x)=\mu$.

For symmetric $A$, every nonzero stationary point of this barrier lies in a negative-eigenvalue eigenspace: $Ax=\lambda x$, $\lambda <0$, $\Vert x{\Vert }^2=1+\mu /\lambda$. The origin is also stationary for every positive $\mu$ and must be considered separately. On a fixed nonzero branch, the Hessian has radial eigenvalue $4{\lambda }^2\Vert x{\Vert }^2/\mu$ and transverse eigenvalues $2({\lambda }_i-\lambda )$. A simple lowest negative eigenvalue gives a minimizing branch with a condition number growing as $1/\mu$; repeated lowest eigenvalues produce zero transverse curvature instead. Nevertheless the minimizing radius tends to one and the limiting vectors solve the constrained quadratic problem. The condition number measures numerical difficulty, not failure of the approximation principle.

Suppose strictly feasible stationary points of $f(x)-{\mu }_k{\sum }_j\log c_j(x)$ form a bounded sequence. Every cluster point satisfying the linear independence constraint qualification is a KKT point. Inactive multipliers tend to zero. The active gradients near the limit have uniformly bounded dual vectors, so pairing barrier stationarity with those vectors bounds the active multipliers. A convergent multiplier subsequence then gives stationarity, nonnegative multipliers and complementary slackness, since ${\lambda }_{k,j}{c}_j(x_k)={\mu }_k\to 0$. A stationarity residual tending to zero is also allowed.

This conclusion is stationarity, not global optimality. If the subproblems are globally minimized and strictly feasible points are dense in the feasible set, any cluster point is instead a global minimizer. Compare each barrier minimum with a fixed strictly feasible point; boundedness near the cluster point bounds $\log c_j(x_k)$ above. Taking the limit gives the objective comparison on strictly feasible points, then continuity and density extend it to all feasible points.

Let $c_i$ be concave and continuously differentiable, and let a strict feasible point $z$ satisfy $\delta ={\min }_i{c}_i(z)>0$. Suppose $x_k\to x_{\ast }$, $c_i(x_k)>0$, ${\mu }_k\to 0$, and the logarithmic barrier residuals $r_k=\nabla f(x_k)-{\sum }_i{\lambda }_{k,i}\nabla c_i(x_k)$ tend to zero, where ${\lambda }_{k,i}={\mu }_k/c_i(x_k)$. By concavity,The right-hand side is bounded when $\nabla f$ is continuous near $x_{\ast }$. Thus the nonnegative Lagrange multiplier estimates are bounded. A convergent subsequence gives ${\lambda }_{\ast }\ge 0$; passing to the limit in stationarity and ${\lambda }_{k,i}{c}_i(x_k)={\mu }_k$ proves the Karush-Kuhn-Tucker conditions at $x_{\ast }$. An inactive optimization constraint has $c_i(x_{\ast })>0$ and hence ${\lambda }_{k,i}\to 0$ even without selecting a subsequence. With a convex objective function, these conditions certify a global minimum. This result is conditional on the stated residual and primal convergence assumptions; it does not assert that every barrier subproblem has a minimizer.

Near an active constraint with limiting Lagrange multiplier ${\lambda }_i^{\ast }>0$, a convergent barrier sequence has $c_i(x_k)\sim {\mu }_k/{\lambda }_i^{\ast }$. Its Hessian matrix therefore contains the termFor a nonzero constraint gradient, this gives large curvature in a direction normal to the boundary. If a nonzero common tangent direction retains positive curvature of order one, while the remaining terms stay bounded, the condition number typically grows like $1/{\mu }_k$. This is a mechanism rather than a universal rate: there may be no tangent direction, all curvatures may grow together, or an active constraint may have zero limiting Lagrange multiplier.

For a linear program $\min \{c^{T}x:Ax=b,x\ge 0\}$ and its dual linear program, write $e=1$, $\bar{b}=b-Ae$, $\bar{c}=c-e$, and $\bar{z}=c^{T}e+1$. Introduce $x,s\ge 0$, $\tau ,\kappa ,\theta ,\rho \ge 0$, and a free multiplier $\lambda$ satisfyingThe point $x=s=e$, $\tau =\kappa =\theta =\rho =1$, $\lambda =0$ is strictly positive in all constrained coordinates. Multiplying the first three equations by ${\lambda }^T,x^T,\tau$ respectively and adding gives the displayed identity. Minimizing $\theta$ has value zero: primal-dual optimal solutions or certificates from Farkas' lemma give zero-$\theta$ solutions after selecting positive $\rho$ and scaling. At $\theta =0$, $\tau >0$ gives an optimal primal-dual pair by division by $\tau$, while $\kappa >0$ gives a primal infeasibility or dual infeasibility certificate. A point with $\tau =\kappa =0$ is not decisive; choosing a relative interior point of the optimal face of a linear program avoids that degeneracy because the face contains a point with $\tau +\kappa >0$.

An auxiliary conic optimization problem searches for strict feasibility before following a central path. Given $e\in \mathrm{int}K$, minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$ has a strict feasible start for sufficiently large $t$. Any feasible solution with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible. Equality constraints and dual feasibility require their corresponding auxiliary procedures.

A convex three-times differentiable barrier $F$ is self-concordant whenA barrier of parameter $\nu$ additionally satisfies $|DF(x)[h]|\le \sqrt{\nu D^{2}F(x)[h,h]}$ and diverges at the domain boundary. Logarithmically homogeneous cone barriers satisfy $F(tx)=F(x)-\nu \log t$. The orthant barrier $-{\sum }_i\log x_i$ has parameter equal to the dimension, while the Lorentz-cone barrier $-\log (t^2-\Vert z{\Vert }^2)$ on $t>\Vert z\Vert$ has parameter two. Their Hessians define Dikin ellipsoids and control interior Newton steps.

A cone barrier with this scaling law satisfies $⟨\nabla F(s),s⟩=-\nu$ and $\nabla F(ts)=t^{-1}\nabla F(s)$. Therefore a central path with $y=-\mu \nabla F(s)$ has primal-dual gap $\nu \mu$. A product of orthant and Lorentz cone canonical barriers adds their parameters.

For a logarithmically homogeneous barrier on a proper cone, the convex conjugate with reversed argument defines a barrier on the interior dual cone. The inverse gradient relation makes $y=-\mu \nabla F(s)$ equivalent to $s=-\mu \nabla F_{†}(y)$. This gives a joint primal-dual central path without assuming the barrier is identical on a self-dual cone.

For a nondegenerate self-concordant barrier, the open local Hessian ballis contained in its barrier domain. This is the Dikin ellipsoid. It supplies a quantitative way to ensure that a damped Newton method stays interior, without relying on Euclidean distance to a possibly curved boundary.

For a strictly feasible primal-dual conic optimization problem and a logarithmically homogeneous barrier, the central path consists of solutionsThe primal-dual gap is $⟨s,y⟩=\nu \mu$. Existence requires appropriate feasibility and boundedness hypotheses, rather than merely a full-rank constraint matrix. Linearizing these equations gives a central-path Newton system.

At a target barrier parameter $\mu$, let $r_p=Ax-b-s$, $r_d=A^{\top }y-c$, $r_c=y+\mu \nabla F(s)$. The Newton direction solvesFull column rank of $A$ and a positive-definite barrier Hessian give a positive-definite reduced matrix. Backtracking must keep both cone variables interior; solving the linear equations alone does not guarantee that a full step stays inside the cones.

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

Consider the original linear programOne unit of $v$ costs twice as much as one unit of $u$, so $(u,v)=(3,0)$ is a plausible answer. To certify it, multiply the three linear inequalities by $0,1,1$, respectively, and add:The proposed feasible point attains $3$, so its cost is the global minimum.

In the conic dual problem convention, the data and certificate areDirect matrix multiplication gives $A^{T}y=c$ and $b^{T}y=3$. At $x=(3,0{)}^T$, the slack variable is $s=(3,0,0{)}^T$, so $s^{T}y=0$. The first linear inequality has positive slack and zero multiplier; the two positively weighted linear inequalities are tight. This is complementary slackness.

The entire dual feasible set can also be read off: write $y=(1-r,2-r,r{)}^T$ with $0\le r\le 1$. Then $A^{T}y=c$ and $b^{T}y=3r$. Maximizing this lower bound gives $r=1$. A point such as $r=1/2$ is still a valid certificate of the weaker bound $u+2v\ge 3/2$.

A curved feasible set can have the same certificate structure. ConsiderWrite $x=(t,z{)}^T$ and use the second-order cone $K=\{(s_0,s_1,s_2):s_0\ge \sqrt{s_1^2+s_2^2}\}$. In this coordinate ordering,Self-duality of a second-order cone makes $K^{\ast }=K$. The equality $A^{T}y=c$ forces $y_0=1$ and $y_2=0$, leaving $-1\le y_1\le 1$. Its dual objective function is $b^{T}y=-y_1$, maximized at $y=(1,-1,0{)}^T$. Thus every feasible point satisfies $t\ge 1$, and $(t,z)=(1,0)$ attains that bound: $\boxed{p_{\ast }=d_{\ast }=1}$.