Duality
Optimization problems are often easier to analyze from a different angle. Duality formalizes this
idea. Every constrained optimization problem (the primal) has a companion problem (the dual)
that provides bounds on the optimal value, and sometimes solves the original problem exactly. This principle arises
throughout machine learning, convex analysis, and game theory, and it connects the
KKT conditions to algorithmic
efficiency.
Definition: Primal Problem
In constrained optimization, the primal problem is
\[
\begin{align*}
p^* &= \inf_{\mathbf{x}} f(\mathbf{x}) \\\\
&\text{subject to} \quad g_i(\mathbf{x}) \leq 0, \quad h_j(\mathbf{x}) = 0,
\end{align*}
\]
where \(f(\mathbf{x})\) is the objective function, \(g_i(\mathbf{x})\) are inequality constraints, and \(h_j(\mathbf{x})\)
are equality constraints. The optimal value \(p^*\) is the infimum of \(f\) over the feasible set. It may or
may not be attained.
To analyze this constrained problem, we encode the constraints into the objective via the
Lagrangian
\[
\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_i \lambda_i g_i(\mathbf{x}) + \sum_j \nu_j h_j(\mathbf{x}),
\]
where \(\lambda_i, \nu_j\) are the Lagrange multipliers. On the constrained-optimization page the inequality
multipliers are written \(\mu_i\) and the equality multipliers \(\lambda_j\). On this page we adopt instead the
convention standard in convex duality, in which \(\boldsymbol{\lambda}\) collects the inequality multipliers
and \(\boldsymbol{\nu}\) the equality multipliers. Taking the infimum of \(\mathcal{L}\) over \(\mathbf{x}\)
with the multipliers fixed produces a scalar-valued function of the multipliers alone:
Definition: Lagrange Dual Function
The Lagrange dual function associated with the primal problem is
\[
g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}).
\]
This is defined for arbitrary \((\boldsymbol{\lambda}, \boldsymbol{\nu}) \in \mathbb{R}^m \times \mathbb{R}^p\)
and takes values in \([-\infty, +\infty)\). Whenever \(\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})\)
is unbounded below in \(\mathbf{x}\), \(g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = -\infty\). The effective
domain of \(g\) is the set of multipliers for which this infimum is finite.
Definition: Dual Problem
The dual problem is
\[
d^* = \sup_{\boldsymbol{\lambda} \geq \mathbf{0}, \, \boldsymbol{\nu}} g(\boldsymbol{\lambda}, \boldsymbol{\nu}).
\]
The restriction \(\boldsymbol{\lambda} \geq \mathbf{0}\) (with \(\boldsymbol{\nu}\) unrestricted) will be justified
by the Weak Duality theorem below, which shows that under this restriction each \(g(\boldsymbol{\lambda}, \boldsymbol{\nu})\)
is a lower bound on \(p^*\). The dual problem then selects the best such bound. Since \(g\) is the pointwise
infimum of affine functions of \((\boldsymbol{\lambda}, \boldsymbol{\nu})\), it is always concave,
and this holds regardless of whether the primal is convex. The dual is therefore a concave maximization, structurally
a convex optimization problem over \((\boldsymbol{\lambda}, \boldsymbol{\nu})\).
This construction transforms our original problem into a framework where we can always find a guaranteed lower bound.
Regardless of the complexity or convexity of the primal problem, the dual problem provides a foundational limit on what
the optimal solution can be. This leads to one of the most fundamental results in optimization:
Theorem: Weak Duality
For any optimization problem (convex or not) with a valid Lagrangian formulation, the dual optimal value
\(d^*\) is a lower bound on the primal optimal value \(p^*\):
\[
d^* \leq p^*.
\]
Proof
Let \(\mathbf{x}\) be any primal-feasible point (so \(g_i(\mathbf{x}) \leq 0\) and \(h_j(\mathbf{x}) = 0\))
and let \((\boldsymbol{\lambda}, \boldsymbol{\nu})\) be any dual-feasible pair (so \(\lambda_i \geq 0\)). Because
\(\lambda_i \geq 0\) and \(g_i(\mathbf{x}) \leq 0\), each \(\lambda_i g_i(\mathbf{x}) \leq 0\). Because \(h_j(\mathbf{x}) = 0\),
each \(\nu_j h_j(\mathbf{x}) = 0\). Therefore
\[
\begin{align*}
\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})
&= f(\mathbf{x}) + \underbrace{\textstyle\sum_i \lambda_i g_i(\mathbf{x})}_{\leq \, 0}
+ \underbrace{\textstyle\sum_j \nu_j h_j(\mathbf{x})}_{= \, 0} \\\\
&\leq f(\mathbf{x}).
\end{align*}
\]
Since
\(g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\mathbf{x}'} \mathcal{L}(\mathbf{x}', \boldsymbol{\lambda}, \boldsymbol{\nu})\)
takes the infimum over all \(\mathbf{x}'\) (not only feasible ones), it is bounded above by the value
at our particular feasible \(\mathbf{x}\):
\[
g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) \leq f(\mathbf{x}).
\]
The right side \(f(\mathbf{x})\) does not depend on \((\boldsymbol{\lambda}, \boldsymbol{\nu})\), so taking
the supremum of the left side over dual-feasible \((\boldsymbol{\lambda}, \boldsymbol{\nu})\) preserves the
inequality: \(d^* \leq f(\mathbf{x})\).
The bound \(d^* \leq f(\mathbf{x})\) now holds for every primal-feasible \(\mathbf{x}\), so \(d^*\)
is a lower bound for the set \(\{f(\mathbf{x}) : \mathbf{x} \text{ is primal-feasible}\}\). By definition of
the infimum as the greatest
lower bound, and since \(p^* = \inf\{f(\mathbf{x}) : \mathbf{x} \text{ is primal-feasible}\}\), we conclude
\(d^* \leq p^*\). The inequality continues to hold in the degenerate cases by convention. If the primal is
infeasible we set \(p^* = +\infty\), and if \(p^* = -\infty\) (primal unbounded below) weak duality forces
\(d^* = -\infty\) as well.
The non-negative quantity \(p^* - d^*\) is called the duality gap. The gap need not be zero in
general, and non-convex problems frequently exhibit a strictly positive gap. Under favorable conditions it vanishes,
giving strong duality.
Theorem: Strong Duality (Slater's Condition)
Suppose the primal problem is convex, that is, \(f\) and \(g_i\) are convex and \(h_j\) are affine.
If Slater's condition holds, meaning there exists a strictly feasible point \(\mathbf{x}\)
with
\[
\begin{align*}
g_i(\mathbf{x}) &\lt 0 \text{ for all } i, \\\\
h_j(\mathbf{x}) &= 0 \text{ for all } j,
\end{align*}
\]
then strong duality holds: \(d^* = p^*\), and the dual optimum is attained when \(p^* \gt -\infty\).
Proof sketch. Consider the set
\(\mathcal{A} = \{(\mathbf{u}, t) : \exists \mathbf{x} \text{ with } g_i(\mathbf{x}) \leq u_i,\ h_j(\mathbf{x}) = 0,\ f(\mathbf{x}) \leq t\}\).
Convexity of \(f\) and \(g_i\) plus affinity of \(h_j\) make \(\mathcal{A}\) convex, and \((\mathbf{0}, p^*)\)
lies on its boundary. The supporting-hyperplane theorem then provides
\((\boldsymbol{\lambda}, \mu_0) \in \mathbb{R}^m \times \mathbb{R}\), not both zero, such that
\[
\boldsymbol{\lambda}^\top \mathbf{u} + \mu_0 t \geq \mu_0 p^* \quad \text{for all } (\mathbf{u}, t) \in \mathcal{A}.
\]
Since \(\mathcal{A}\) is unbounded in the positive \(\mathbf{u}\)- and \(t\)-directions (increasing any \(u_i\)
or \(t\) preserves membership), the coefficients must satisfy \(\boldsymbol{\lambda} \geq \mathbf{0}\) and
\(\mu_0 \geq 0\). Otherwise the inequality could be driven to \(-\infty\).
The key step is ruling out the degenerate case \(\mu_0 = 0\). Suppose \(\mu_0 = 0\). Then
\(\boldsymbol{\lambda} \neq \mathbf{0}\), \(\boldsymbol{\lambda} \geq \mathbf{0}\), and the supporting inequality
reduces to \(\boldsymbol{\lambda}^\top \mathbf{u} \geq 0\) for all \((\mathbf{u}, t) \in \mathcal{A}\). For every
\(\mathbf{x}\) with \(h_j(\mathbf{x}) = 0\) for all \(j\) (in particular every feasible \(\mathbf{x}\)), the point
\((\mathbf{g}(\mathbf{x}), f(\mathbf{x}))\) lies in \(\mathcal{A}\), so
\(\boldsymbol{\lambda}^\top \mathbf{g}(\mathbf{x}) \geq 0\). Applying this at Slater's strictly feasible point
\(\bar{\mathbf{x}}\), for which \(g_i(\bar{\mathbf{x}}) \lt 0\) for all \(i\),
\[
\boldsymbol{\lambda}^\top \mathbf{g}(\bar{\mathbf{x}}) = \sum_i \lambda_i \, g_i(\bar{\mathbf{x}}) \lt 0,
\]
since \(\boldsymbol{\lambda} \geq \mathbf{0}\), \(\boldsymbol{\lambda} \neq \mathbf{0}\), and every
\(g_i(\bar{\mathbf{x}}) \lt 0\). This strict inequality contradicts
\(\boldsymbol{\lambda}^\top \mathbf{g}(\bar{\mathbf{x}}) \geq 0\). Hence \(\mu_0 \gt 0\).
Normalizing \(\mu_0 = 1\), the supporting inequality yields \(g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \geq p^*\)
for an appropriate \(\boldsymbol{\nu} \in \mathbb{R}^p\), where the \(\boldsymbol{\nu}\) component is produced
by the affine span of the equality constraints. This step requires the relative-interior refinement of Slater's
condition, which treats affine \(h_j\) separately from nonlinear \(g_i\). Combined with weak duality, this
gives \(d^* \geq p^*\), hence \(d^* = p^*\).
Slater's condition is one of several sufficient conditions guaranteeing strong duality in the convex case. Others include
linearity of all constraints, which, for an objective defined on all of \(\mathbb{R}^n\), needs feasibility but not strict
feasibility, and various constraint qualifications. Non-convex problems may also enjoy strong duality in special cases, but
it is the exception rather than the rule.
When strong duality holds and both optima are attained, every dual optimal pair
\((\boldsymbol{\lambda}^*, \boldsymbol{\nu}^*)\) supplies multipliers for the
KKT conditions (written
\((\boldsymbol{\mu}^*, \boldsymbol{\lambda}^*)\) there) at every primal optimum, provided \(f\), \(g_i\), \(h_j\) are
differentiable. For a convex problem the KKT conditions are then also sufficient, so they are both necessary and
sufficient for primal-dual optimality.
Insight: Duality in Machine Learning
Duality is widely used in machine learning and statistical learning theory. In
kernel Support Vector Machines, the dual formulation is the
classical route to the kernel trick, allowing nonlinear classification in high-dimensional (or
infinite-dimensional) feature spaces without explicitly computing the mapping. In
regularization methods such as
Ridge
and Lasso, dual
formulations help derive generalization bounds and computationally efficient optimization algorithms. More broadly, many
adversarial and minimax training objectives can be interpreted through duality principles. These objectives include
Wasserstein GANs, which approximate the Kantorovich-Rubinstein dual of the 1-Wasserstein distance with a neural critic
constrained to be (approximately) Lipschitz.
Lipschitz Continuity
Duality characterizes the optimal value of a constrained problem, and it does so exactly when strong duality holds.
It does not tell us how fast an algorithm can reach it. Convergence rates depend on regularity properties
of the objective function, particularly how rapidly its gradient can change. Lipschitz continuity
provides the precise mathematical framework for bounding this rate of change, and it is the key assumption behind
most convergence guarantees in optimization.
Recall that a function \(f: X \to Y\) between metric spaces is
Lipschitz continuous
with constant \(L \geq 0\) if \(e(f(a), f(b)) \leq L \cdot d(a, b)\) for all \(a, b \in X\). This bounds the variation
of \(f\) uniformly in terms of the input distance, so \(f\) cannot change faster than linearly in \(d(a, b)\).
(Note that Lipschitz functions need not be bounded themselves. On \(\mathbb{R}\), the function \(f(s) = s\) is
Lipschitz with \(L = 1\) yet unbounded.)
In optimization, Lipschitz-type regularity underpins step-size selection, stability of iterative methods, and
quantitative convergence rates. See Continuity for the purely-analytic
development.
When the Lipschitz condition is applied to the gradient rather than the function
itself, we obtain the important notion of smoothness.
Definition: \(L\)-Smoothness
A continuously differentiable function \(f: \mathbb{R}^n \to \mathbb{R}\) is
\(L\)-smooth if its gradient is Lipschitz continuous with constant \(L\):
\[
\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \leq L \|\mathbf{x} - \mathbf{y}\| \quad \text{for all } \mathbf{x}, \mathbf{y} \in \mathbb{R}^n.
\]
This ensures that \(f\) does not curve too rapidly, allowing gradient-based methods to
converge predictably.
In gradient-based optimization, \(L\)-smoothness yields the descent lemma
\[
f(\mathbf{y}) \leq f(\mathbf{x}) + \nabla f(\mathbf{x})^\top (\mathbf{y} - \mathbf{x}) + \tfrac{L}{2} \|\mathbf{y} - \mathbf{x}\|^2,
\]
which follows from the fundamental theorem of calculus applied to \(\nabla f\) along the segment from \(\mathbf{x}\)
to \(\mathbf{y}\). No twice-differentiability is required.
In the \(C^2\) case, \(L\)-smoothness is equivalent to the two-sided spectral bound
\[
-LI \preceq \nabla^2 f(\mathbf{x}) \preceq LI,
\]
and for convex \(L\)-smooth \(f\) this sharpens to
\[
0 \preceq \nabla^2 f(\mathbf{x}) \preceq LI.
\]
While Lipschitz continuity of \(f\) limits how fast the function values can change, \(L\)-smoothness limits how
fast the gradient can change.
The descent lemma motivates the step size \(\alpha = 1/L\). Minimizing the right-hand side in \(\mathbf{y}\) at
\[
\mathbf{y} = \mathbf{x} - \alpha \nabla f(\mathbf{x})
\]
gives the largest guaranteed per-step decrease from the quadratic upper model alone, and this choice underlies
the standard sublinear convergence analysis for convex \(L\)-smooth functions.
We emphasize, however, that \(1/L\) is optimal only with respect to the upper model. It is not the step
size minimizing the actual convergence rate when additional structure (such as strong convexity) is available.
For the quadratic case analyzed below, \(L\) and the strong-convexity constant \(m\) introduced shortly can be taken
to be the largest and smallest eigenvalues \(\lambda_{\max}\) and \(\lambda_{\min}\) of the Hessian \(A\), and the sharpest
contraction is achieved by
\[
2/(\lambda_{\min} + \lambda_{\max}) = 2/(L + m).
\]
This choice is strictly larger than \(1/L\) when the condition number \(\kappa = L/m\) exceeds \(1\), and it
yields a better rate.
Gradient descent, also called steepest descent, starts from an initial point \(\mathbf{x}_0\) and iterates
\(\mathbf{x}_{t+1} = \mathbf{x}_t - \alpha \nabla f(\mathbf{x}_t)\). When \(f\) is convex with a minimizer
\(\mathbf{x}^*\) and the step size is \(\alpha = 1/L\), \(L\)-smoothness without strong convexity guarantees only
a sublinear rate for this method,
\[
f(\mathbf{x}_t) - f(\mathbf{x}^*) = O(1/t),
\]
which we state without proof. To obtain a linear rate, that is, geometric decay of the error, we additionally
need a lower curvature bound, captured by strong convexity.
For \(m \gt 0\), a function is \(m\)-strongly convex if \(f(\mathbf{x}) - \tfrac{m}{2}\|\mathbf{x}\|^2\) is convex,
equivalently \(\nabla^2 f(\mathbf{x}) \succeq m I\) in the twice-differentiable case. When \(f\) is both \(L\)-smooth
and \(m\)-strongly convex, it has a unique minimizer \(\mathbf{x}^*\), at which \(\nabla f(\mathbf{x}^*) = \mathbf{0}\)
because \(f\) is differentiable and the minimum is unconstrained, and steepest descent admits the linear bound
\[
\begin{align*}
f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*) &\leq \mu \, \bigl(f(\mathbf{x}_t) - f(\mathbf{x}^*)\bigr), \\\\
0 &\lt \mu \lt 1.
\end{align*}
\]
The constant \(\mu\) is the convergence rate, and it depends on the chosen step size.
With \(\alpha = 1/L\) the standard analysis gives \(\mu = 1 - m/L = 1 - 1/\kappa\) (Nesterov), while with \(\alpha = 2/(L + m)\)
the iterate contraction factor \(k = (\kappa-1)/(\kappa+1)\) yields a bound of the form
\[
\|\mathbf{x}_{t+1} - \mathbf{x}^*\| \leq k \|\mathbf{x}_t - \mathbf{x}^*\|.
\]
For general \(f\) we take it and the existence of \(\mathbf{x}^*\) for granted. For the quadratic objective the
bound is proved below.
On general \(L\)-smooth \(m\)-strongly convex \(f\), the usual way to convert the iterate bound into a
function-value statement uses the two-sided estimate
\[
\begin{align*}
f(\mathbf{x}) - f(\mathbf{x}^*) &\geq \tfrac{m}{2}\|\mathbf{x} - \mathbf{x}^*\|^2, \\\\
f(\mathbf{x}) - f(\mathbf{x}^*) &\leq \tfrac{L}{2}\|\mathbf{x} - \mathbf{x}^*\|^2,
\end{align*}
\]
valid at every \(\mathbf{x}\). The upper bound is the descent lemma with \((\mathbf{x}, \mathbf{y})\) replaced by
\((\mathbf{x}^*, \mathbf{x})\). For the lower bound, put \(\psi(\mathbf{x}) = f(\mathbf{x}) - \tfrac{m}{2}\|\mathbf{x}\|^2\)
and \(\varphi(\tau) = \psi(\mathbf{x}^* + \tau(\mathbf{x} - \mathbf{x}^*))\). The function \(\varphi\) is convex on
\(\mathbb{R}\), because \(\psi\) is convex and \(\tau \mapsto \mathbf{x}^* + \tau(\mathbf{x} - \mathbf{x}^*)\) is affine. The
first-order characterization of convexity
therefore gives \(\varphi(1) \geq \varphi(0) + \varphi'(0)\). By the chain rule,
\[
\begin{align*}
\varphi'(0)
&= \nabla \psi(\mathbf{x}^*)^\top (\mathbf{x} - \mathbf{x}^*) \\\\
&= \bigl(\nabla f(\mathbf{x}^*) - m\mathbf{x}^*\bigr)^\top (\mathbf{x} - \mathbf{x}^*) \\\\
&= -m\,(\mathbf{x}^*)^\top (\mathbf{x} - \mathbf{x}^*),
\end{align*}
\]
and expanding the inequality with this value gives the first line of the two-sided estimate.
For \(\alpha = 2/(L + m)\), combining the upper bound at \(\mathbf{x}_t\), the iterate bound applied \(t\) times,
and the lower bound at \(\mathbf{x}_0\) loses a factor of \(\kappa\) and gives only
\[
f(\mathbf{x}_t) - f(\mathbf{x}^*) \leq \kappa \, k^{2t} \bigl(f(\mathbf{x}_0) - f(\mathbf{x}^*)\bigr).
\]
To understand what determines \(\mu\) in the cleanest setting, we analyze the canonical case of a
quadratic objective. This is the simplest setting in which \(L\) and \(m\) are both exact and straightforward to
compute, and in which the iterate rate \(k\) and the function-value rate \(k^2\) are both attained exactly (no
\(\kappa\) loss).
Example: Quadratic Objective
Consider the quadratic loss function
\[
f(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^\top A \mathbf{x} + \mathbf{b}^\top \mathbf{x} + c,
\]
where \(A \in \mathbb{R}^{n \times n}\) is symmetric positive definite, \(\mathbf{b} \in \mathbb{R}^n\), and
\(c \in \mathbb{R}\). This function has a unique minimizer \(\mathbf{x}^* = -A^{-1}\mathbf{b}\). The quadratic case is the
canonical test bed for convergence rate analysis because the iteration map for steepest descent becomes affine, with a
linear part whose spectral properties directly expose the convergence factor.
To analyze the convergence of steepest descent on this quadratic, we first introduce the
concept of a contraction mapping, which provides the framework for linear convergence analysis.
Definition: Contraction (Optimization Convention)
Let \((M, d)\) be a metric space. A map \(T: M \to M\) is a contraction if there exists a
constant \(0 \leq k \lt 1\) such that
\[
d(T(\mathbf{x}), T(\mathbf{y})) \leq k \, d(\mathbf{x}, \mathbf{y}) \quad \text{for all } \mathbf{x}, \mathbf{y} \in M.
\]
The constant \(k\) is called the contraction factor.
A contraction is automatically a Lipschitz function with Lipschitz constant less than 1, hence
uniformly continuous
on its domain. If an iterative method satisfies this contraction property, the error shrinks by factor \(k\) at
every step, yielding geometric convergence.
Note on Terminology
We use contraction here in the sense standard to optimization and ML literature (for example, Murphy,
Probabilistic Machine Learning, 2022), namely \(k \lt 1\). Our pure-analysis pages follow the broader
convention where the unqualified term "contraction" allows \(k \leq 1\), and the strictly-less-than-one case is labelled
strong contraction. The two usages
agree on the Banach fixed-point result. Only the naming differs.
We can now state and prove the convergence rate of steepest descent on the canonical quadratic,
using the contraction framework developed above.
Theorem: Convergence Rate of Steepest Descent (Quadratic Case)
For the quadratic objective \(f(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^\top A \mathbf{x} + \mathbf{b}^\top \mathbf{x} + c\)
with \(A \in \mathbb{R}^{n \times n}\) symmetric positive definite,
steepest descent
\(\mathbf{x}_{t+1} = \mathbf{x}_t - \alpha \nabla f(\mathbf{x}_t)\) with any fixed step size
\(\alpha \in (0, 2/\lambda_{\max})\), started from any \(\mathbf{x}_0 \in \mathbb{R}^n\), converges linearly to the
unique minimizer
\(\mathbf{x}^* = -A^{-1}\mathbf{b}\). The step size that minimizes the worst-case contraction factor of the
iterate error is
\[
\alpha^* = \frac{2}{\lambda_{\min} + \lambda_{\max}},
\]
at which steepest descent satisfies the worst-case function-value bound
\[
\begin{align*}
f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*) &\leq \mu \, \bigl(f(\mathbf{x}_t) - f(\mathbf{x}^*)\bigr), \\\\
\mu &= \left(\frac{\kappa - 1}{\kappa + 1}\right)^2,
\end{align*}
\]
where \(\kappa = \lambda_{\max}/\lambda_{\min}\) is the
condition number
of \(A\), and \(\lambda_{\min}, \lambda_{\max}\) are the smallest and largest eigenvalues of \(A\). Since
\(A^\top A = A^2\) has eigenvalues \(\lambda_i^2\) and every \(\lambda_i \gt 0\), the singular values of \(A\) are its
eigenvalues, so this \(\kappa\) agrees with the singular-value definition.
Proof
The gradient of \(f\) is
\[
\nabla f(\mathbf{x}) = A\mathbf{x} + \mathbf{b} = A(\mathbf{x} - \mathbf{x}^*),
\]
using \(\mathbf{x}^* = -A^{-1}\mathbf{b}\). Substituting this gradient into the iteration gives
\[
\begin{align*}
\mathbf{x}_{t+1} - \mathbf{x}^*
&= (\mathbf{x}_t - \mathbf{x}^*) - \alpha A (\mathbf{x}_t - \mathbf{x}^*) \\\\
&= (I - \alpha A)(\mathbf{x}_t - \mathbf{x}^*).
\end{align*}
\]
The iteration is therefore an affine map whose linear part is \(I - \alpha A\). Because \(A\) is
symmetric it is
orthogonally diagonalizable.
Write \(A = Q \Lambda Q^\top\) with \(Q\) orthogonal and \(\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)\).
By the corollary on the
spectral norm of a symmetric matrix,
the \(\lambda_i\) are exactly the eigenvalues of \(A\). Moreover
\(I - \alpha A = Q(I - \alpha \Lambda)Q^\top\) is a factorization of the same kind for the symmetric
matrix \(I - \alpha A\), so the same corollary shows that \(\|I - \alpha A\|_2\) is the largest
absolute value of the diagonal entries \(1 - \alpha \lambda_i\):
\[
\|I - \alpha A\|_2 = \max_i |1 - \alpha \lambda_i|.
\]
The iteration is a contraction in the Euclidean norm precisely when \(\|I - \alpha A\|_2 \lt 1\), that is,
\[
|1 - \alpha \lambda_i| \lt 1 \quad \text{for all } i,
\]
which, since \(A\) is positive definite and hence has
strictly positive eigenvalues,
reduces to \(0 \lt \alpha \lt 2/\lambda_{\max}\).
We now minimize the contraction factor over \(\alpha \in (0, 2/\lambda_{\max})\). The contraction factor as
a function of \(\alpha\) is
\[
\max_i |1 - \alpha \lambda_i| = \max\bigl(1 - \alpha \lambda_{\min},\ \alpha \lambda_{\max} - 1\bigr),
\]
where we have used the identity \(|1 - \alpha \lambda_i| = \max(1 - \alpha \lambda_i,\ \alpha \lambda_i - 1)\).
Since \(\alpha \gt 0\), the term \(1 - \alpha \lambda_i\) is largest at \(\lambda_i = \lambda_{\min}\) and the term
\(\alpha \lambda_i - 1\) at \(\lambda_i = \lambda_{\max}\), so only the two extreme eigenvalues matter.
Of the two expressions in the displayed maximum, \(1 - \alpha \lambda_{\min}\) is decreasing in \(\alpha\)
and \(\alpha \lambda_{\max} - 1\) is increasing. Near \(\alpha = 0\) the first is the larger, and at
\(\alpha = 2/\lambda_{\max}\) the second equals \(1\) and exceeds the first, so, both being affine in \(\alpha\),
they meet inside the interval.
Their maximum is minimized at the meeting point:
\[
1 - \alpha^* \lambda_{\min} = \alpha^* \lambda_{\max} - 1,
\]
giving
\[
\alpha^* = \frac{2}{\lambda_{\min} + \lambda_{\max}}.
\]
Substituting back, the optimal contraction factor for the iterate error is
\[
\begin{align*}
k &= 1 - \alpha^* \lambda_{\min} \\\\
&= \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} \\\\
&= \frac{\kappa - 1}{\kappa + 1}.
\end{align*}
\]
Thus,
\[
\|\mathbf{x}_{t+1} - \mathbf{x}^*\|_2 \leq k \, \|\mathbf{x}_t - \mathbf{x}^*\|_2.
\]
Finally we translate the iterate contraction into a function-value rate. A direct computation using
\(\mathbf{x}^* = -A^{-1} \mathbf{b}\) shows
\[
f(\mathbf{x}) - f(\mathbf{x}^*) = \tfrac{1}{2}(\mathbf{x} - \mathbf{x}^*)^\top A (\mathbf{x} - \mathbf{x}^*).
\]
Using the orthogonal diagonalization \(A = Q \Lambda Q^\top\) from above, we have
\[
I - \alpha^* A = Q(I - \alpha^* \Lambda)Q^\top.
\]
Let \(\mathbf{z}_t := Q^\top(\mathbf{x}_t - \mathbf{x}^*)\). Then
\[
\mathbf{z}_{t+1} = (I - \alpha^* \Lambda) \mathbf{z}_t,
\]
that is,
\[
(\mathbf{z}_{t+1})_i = (1 - \alpha^* \lambda_i)(\mathbf{z}_t)_i,
\]
and
\[
\begin{align*}
f(\mathbf{x}_t) - f(\mathbf{x}^*)
&= \tfrac{1}{2} \mathbf{z}_t^\top \Lambda \mathbf{z}_t \\\\
&= \tfrac{1}{2} \sum_i \lambda_i (\mathbf{z}_t)_i^2.
\end{align*}
\]
Applying the iteration,
\[
\begin{align*}
f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*)
&= \tfrac{1}{2} \sum_i \lambda_i (\mathbf{z}_{t+1})_i^2 \\\\
&= \tfrac{1}{2} \sum_i (1 - \alpha^* \lambda_i)^2 \, \lambda_i \, (\mathbf{z}_t)_i^2.
\end{align*}
\]
Since \((1 - \alpha^* \lambda_i)^2 \leq k^2\) for every \(i\), we conclude
\[
\begin{align*}
f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*)
&\leq k^2 \cdot \tfrac{1}{2} \sum_i \lambda_i (\mathbf{z}_t)_i^2 \\\\
&= k^2 \bigl(f(\mathbf{x}_t) - f(\mathbf{x}^*)\bigr).
\end{align*}
\]
Hence
\[
\mu = k^2 = \left(\dfrac{\kappa - 1}{\kappa + 1}\right)^2.
\]
The bound is tight. By the defining equation of \(\alpha^*\), both \(\lambda_{\min}\) and \(\lambda_{\max}\) satisfy
\(|1 - \alpha^* \lambda| = k\). No other eigenvalue does, since for \(\lambda_{\min} \lt \lambda \lt \lambda_{\max}\) we have
\(1 - \alpha^* \lambda \lt 1 - \alpha^* \lambda_{\min} = k\) and \(\alpha^* \lambda - 1 \lt \alpha^* \lambda_{\max} - 1 = k\).
Equality in the function-value bound therefore holds at step \(t\) whenever \(\mathbf{z}_t\) has nonzero
components only along eigenvectors of \(A\) for \(\lambda_{\min}\) and \(\lambda_{\max}\). By the componentwise
recursion above, this support condition persists for all \(t\) once \(\mathbf{z}_0\) satisfies it, and every
initial point does so when \(A\) has at most two distinct eigenvalues (in particular when \(n = 2\)). If instead
\(\mathbf{z}_t\) has a nonzero component along an eigenvector whose eigenvalue is neither \(\lambda_{\min}\) nor
\(\lambda_{\max}\), the gap \(f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*)\) is smaller than \(k^2\) times the gap
\(f(\mathbf{x}_t) - f(\mathbf{x}^*)\).
Problems with low condition numbers (\(\kappa\) close to 1) converge rapidly, while ill-conditioned problems (\(\kappa \gg 1\))
converge slowly. This is why preconditioning, which transforms the problem to reduce \(\kappa\),
is a central technique in numerical optimization.
Insight: Condition Number in Deep Learning
The condition number governs training dynamics far beyond quadratic objectives. In deep learning, the effective
condition number of the loss landscape's Hessian strongly influences how well gradient-based optimizers perform.
Adam and other adaptive methods implicitly apply a diagonal preconditioner by maintaining per-parameter
learning rates, which can reduce the effective condition number when the curvature is roughly aligned with the
coordinate axes. Batch normalization empirically accelerates training. Subsequent analysis attributes
this to a smoothing effect on the loss landscape rather than to the originally proposed "internal covariate shift"
mechanism. In that account, the smoothing reduces the Lipschitz constants of both the loss and its gradient.
Understanding \(\kappa\) helps explain why some architectures train easily while others require careful hyperparameter
tuning.
Interactive Duality Visualization
The demo below instantiates the theory on a two-variable linear program: minimize \(c_1 x_1 + c_2 x_2 + c_3\)
subject to \(A\mathbf{x} \leq \mathbf{b}\) and \(\mathbf{x} \geq \mathbf{1}\). We work through the Lagrangian
exactly as above, with multipliers \(\boldsymbol{\lambda} \geq \mathbf{0}\) for \(A\mathbf{x} \leq \mathbf{b}\)
and \(\boldsymbol{\mu} \geq \mathbf{0}\) for the lower bounds. Stationarity forces
\(\boldsymbol{\mu} = \mathbf{c} + A^\top \boldsymbol{\lambda}\), and the dual becomes another two-variable linear
program over \(\boldsymbol{\lambda}\).
The tool solves the primal and the dual independently, so the theorems of this page are checked live
rather than assumed. The duality gap \(|p^* - d^*|\) is displayed and verified to vanish (strong duality holds
for every feasible, bounded linear program, and no Slater-type strict feasibility is needed when all constraints
are affine), and the four complementary-slackness products \(\lambda_i s_i\) (with \(s_i\) the slack in the \(i\)-th
row of \(A\mathbf{x} \leq \mathbf{b}\)) and \(\mu_i (x_i - 1)\) are tabulated, each vanishing at joint optimality.
The primal and dual are displayed side by side, and the interaction happens directly on the primal canvas.
Drag a constraint line to translate it (changing \(b_i\)), or grab the \(-\mathbf{c}\) arrow and rotate the objective.
Rotating \(\mathbf{c}\) is where linear programming shows its character. The optimum does not drift continuously but
hops from vertex to vertex, and at the same moment \(\boldsymbol{\lambda}^*\) slides along the boundary of the dual
region. Active constraints are drawn thick. Watch a constraint light up whenever its multiplier \(\lambda_i\) is positive,
and the complementary-slackness chips flip in real time. Try the presets. With positive costs the optimum sits at the corner
\((1,1)\) and \(\boldsymbol{\lambda}^* = \mathbf{0}\) with \(\boldsymbol{\mu}^* = \mathbf{c}\), so the bound constraints do
all the work. With the default constraints, rotate the objective until \(-\mathbf{c}\) points strictly between the two
constraint normals, and the optimum jumps to the intersection of the two constraints, where \(\boldsymbol{\lambda}^*\)
becomes strictly positive and \(\boldsymbol{\mu}^*\) vanishes, exactly as complementary slackness dictates.
Using the fine-tune sliders, setting a column of \(A\) to zero while the corresponding cost is negative makes the primal
unbounded whenever it is feasible (\(p^* = -\infty\)) with the dual reported infeasible, and shrinking \(b_1\) until the
primal is infeasible (\(p^* = +\infty\)) makes the dual unbounded, provided the dual is feasible, a condition that does not
involve \(\mathbf{b}\). Weak duality forces the first pairing, since an unbounded primal leaves no dual-feasible point, and
linear-programming duality accounts for the second.