Codex @codex  0

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$.

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.

Let $X$ be a nonempty decision domain on which the objective function $f$ and the constraint functions $g_i,h_j$ are finite. Write the primal problem and its optimization Lagrangian asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe inner infimum keeps $X$, but releases the displayed optimization constraints. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. No convexity is used.

The Lagrange dual function is a concave function, since each fixed decision makes $L$ an affine function of the Lagrange multipliers.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,Taking the infimum over $x$ proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.

For finite optimal values, strong duality means $d_{\ast }=p_{\ast }$, or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when $p_{\ast }$ is finite.^[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

Compute the convex conjugate of $f_z$ at a general pair $(v,y)$. With $w=z+u-x$, the independent variables become $(x,w)$ and $u=w+x-z$, soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is $F^{\ast }=k^{\ast }+h^{\ast }$, and the continuous convex $F$ equals its biconjugate.

For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to $\partial F(z)$ by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because $F$ is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve $\nabla k^{\ast }(y)+\nabla h^{\ast }(y)=z$. For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by $\partial k^{\ast }(y)+\partial h^{\ast }(y)$ requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.

Let $r(u)=\Vert u-g{\Vert }_2^2$ and fix the reference noise budget $\sigma$. Define the convex perturbation functionPositive $z$ increases the allowed squared noise level. The feasible epigraph set $r(u)\le \sigma +z$ is convex and closed, so this is a proper lower semicontinuous jointly convex perturbation. Writing the inequality indicator as a supremum over its multiplier givesThe Lagrange dual function is $d(\lambda )={\inf }_{u}L(u,\lambda )$ for $\lambda \ge 0$. In the signed convex conjugate convention of part (a), $y=-\lambda$; positive $y$ gives dual objective $-\infty$ because the perturbation can be made arbitrarily large.

The feasible ball is nonempty and compact, so lower semicontinuity of total variation gives a primal minimizer. For $\sigma >0$, $u=g$ satisfies $r(g)=0<\sigma$, providing the Slater condition. Total variation is finite everywhere in the given discretization and hence continuous. Strong duality and dual attainment give a finite optimal ${\lambda }^{\ast }\ge 0$. The pair satisfies the Karush-Kuhn-Tucker conditionsEquivalently,Thus the set of saddle points is nonempty. Compactness handles primal attainment, while strict feasibility supplies a finite multiplier; these are distinct steps. An inactive constraint can yield ${\lambda }^{\ast }=0$. At $\sigma =0$, feasibility still forces $u=g$, but this strict-feasibility argument does not apply.

A nonconvex primal problem can have a positive duality gap even when both optima are attained. Choose the finite set $X=\{-2,0,2\}$, the objective function values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality optimization constraint $h(x)=x=0$. The only feasible point is $0$, so $p_{\ast }=3$.

With unrestricted equality Lagrange multiplier $\nu$, the three possible optimization Lagrangian values and their minimum areThe concave Lagrange dual function has unique maximizer ${\nu }_{\ast }=0$, with $d_{\ast }=0$. Thus the duality gap is $3$. At the optimal Lagrange multiplier, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.

Why can no slope close the gap? Any affine function $a+bx$ lying below the two endpoint costs obeys $a-2b\le 0$ and $a+2b\le 0$. Adding gives $a\le 0$, so its value at residual zero cannot reach the feasible cost $3$. A convex combination of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive duality gap: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.

Consider the minimization problemThe objective function is a strictly convex function with its unconstrained optimization minimum at $x=2$. If $b<2$, it decreases throughout the feasible set until the bound $x=b$ is reached. If $b\ge 2$, the feasible set already contains $2$. HenceWith $g(x)=x-b$, the optimization Lagrangian and KKT conditions areSubstituting $x_{\ast }(b)$ gives the unique inequality Lagrange multiplierFor $b<2$, the active constraint has ${\lambda }_{\ast }>0$. For $b>2$, there is strict slack $b-x_{\ast }=b-2$ and ${\lambda }_{\ast }=0$. At $b=2$, the active constraint has zero Lagrange multiplier: the boundary happens to pass through the unconstrained optimum. Feasibility and complementary slackness must both be checked; solving only $2(x-2)+\lambda =0$ would allow infeasible candidates.

An independent certificate follows by completing the square:The Lagrange dual function is a concave function of $\lambda$. Its maximum over $\lambda \ge 0$ occurs at ${\lambda }_{\ast }(b)$ and equals $V(b)$. Thus every case has an explicit lower bound attained by a feasible point; the KKT conditions provide a certificate that can be checked without searching all real numbers.

A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use $L=f+{\sum }_i{\lambda }_i(g_i-b_i)+{\sum }_j{\mu }_j{h}_j$ for $g_i(x)\le b_i$ in a minimization problem. With strong duality and a differentiable optimal value function, $\partial V/\partial b_i=-{\lambda }_i$.^[ref]

In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at $b=2$ is zero from both sides, although $x_{\ast }(b)$ has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.

At $b=1$, $x_{\ast }=1$, $V=1$ and ${\lambda }_{\ast }=2$. Raising the bound to $1.1$ lowers the value to $0.81$: the first-order prediction is a change of $-2(0.1)=-0.2$, while the exact change is $-0.19$. At $b=3$, the same relaxation leaves $x_{\ast }=2$ and $V=0$. At $b=2$, tightening by $0.1$ costs $0.01$, a second-order effect despite the zero Lagrange multiplier.

There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with $b_0$, the Lagrange dual function changes by $-{\lambda }_{\ast }(b_0)(b-b_0)$. Weak duality therefore givesAt $b_0=1$ this is $V(b)\ge 3-2b$, the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.