Formula & theorem reference

By definition, \lambda is an eigenvalue of A exactly when there exists a nonzero vector \mathbf{x} with A\mathbf{x} = \lambda\mathbf{x}. Move everything to one side. Since \lambda\mathbf{x} = \lambda I\mathbf{x}, this rearranges to A\mathbf{x} - \lambda I\mathbf{x} = \mathbf{0}, \qquad\text{i.e.}\qquad (A - \lambda I)\mathbf{x} = \mathbf{0}. So \lambda is an eigenvalue of A precisely when the homogeneous system (A - \lambda I)\mathbf{x} = \mathbf{0} has a solution \mathbf{x} other than the trivial one — equivalently, precisely when \text{Nul}(A - \lambda I) contains more than just \mathbf{0}.

A square matrix has a nontrivial null space if and only if it fails to be invertible: if A - \lambda I were invertible, multiplying both sides of (A - \lambda I)\mathbf{x} = \mathbf{0} by (A - \lambda I)^{-1} would force \mathbf{x} = \mathbf{0}, ruling out a nonzero solution. So a nonzero \mathbf{x} can exist only when A - \lambda I is singular.

Finally, a square matrix is singular exactly when its determinant is zero. Chaining the equivalences together: \lambda \text{ is an eigenvalue of } A \iff (A-\lambda I)\mathbf{x} = \mathbf{0} \text{ has a nontrivial solution} \iff \det(A - \lambda I) = 0.

Sanity check: take A = I, the identity matrix. Then A - \lambda I = (1-\lambda)I, and \det\left((1-\lambda)I\right) = (1-\lambda)^n, which vanishes only at \lambda = 1. That matches the identity matrix's only eigenvalue: every nonzero vector satisfies I\mathbf{x} = 1\cdot\mathbf{x}, so \lambda = 1 is the sole eigenvalue, exactly as the characteristic equation predicts.

(\Leftarrow) Orthogonal diagonalizability forces symmetry. Suppose A = QDQ^{\mathsf T} with Q orthogonal and D diagonal. Diagonal matrices equal their own transpose, and transposing a product reverses the order of its factors, so A^{\mathsf T} = (QDQ^{\mathsf T})^{\mathsf T} = (Q^{\mathsf T})^{\mathsf T}D^{\mathsf T}Q^{\mathsf T} = QDQ^{\mathsf T} = A. So A is symmetric. The rest of the proof handles the harder direction.

Symmetric matrices have only real eigenvalues. Let \lambda be an eigenvalue of A, allowing for the moment that it might be complex, with eigenvector v (possibly with complex entries), so Av = \lambda v. Let \bar v denote the entrywise complex conjugate of v, and consider the scalar \bar v^{\mathsf T} A v. Computing it one way, \bar v^{\mathsf T} A v = \bar v^{\mathsf T}(\lambda v) = \lambda (\bar v^{\mathsf T} v) = \lambda \lVert v \rVert^2, since \bar v^{\mathsf T} v = \sum_i \overline{v_i} v_i = \sum_i |v_i|^2 = \lVert v \rVert^2 is real and positive (v \neq 0, being an eigenvector). Computing the same scalar the other way, using A^{\mathsf T} = A and that \bar v^{\mathsf T} A v is a 1\times 1 matrix and so equal to its own transpose, \bar v^{\mathsf T} A v = \left(\bar v^{\mathsf T} A v\right)^{\mathsf T} = v^{\mathsf T} A^{\mathsf T} \bar v = v^{\mathsf T} A \bar v. Taking the complex conjugate of Av = \lambda v gives A\bar v = \bar\lambda \bar v (since A has real entries, conjugation passes through it untouched), so v^{\mathsf T} A \bar v = v^{\mathsf T}(\bar\lambda \bar v) = \bar\lambda (v^{\mathsf T}\bar v) = \bar\lambda \lVert v\rVert^2, using v^{\mathsf T}\bar v = \overline{\bar v^{\mathsf T} v} = \lVert v\rVert^2 again. The two computations of \bar v^{\mathsf T} A v must agree: \lambda \lVert v \rVert^2 = \bar\lambda \lVert v \rVert^2. Since \lVert v \rVert^2 \neq 0, this forces \lambda = \bar\lambda, i.e. \lambda is real. So every eigenvalue of A is real, and consequently every eigenvalue has a real eigenvector (a real matrix minus a real multiple of I_n has a real null space).

Eigenvectors for distinct eigenvalues are orthogonal. Let Av_1 = \lambda_1 v_1 and Av_2 = \lambda_2 v_2 with \lambda_1 \neq \lambda_2. Using symmetry, \lambda_1 (v_1 \cdot v_2) = (Av_1) \cdot v_2 = v_1^{\mathsf T}A^{\mathsf T} v_2 = v_1^{\mathsf T}Av_2 = v_1 \cdot (Av_2) = \lambda_2(v_1 \cdot v_2). So (\lambda_1 - \lambda_2)(v_1 \cdot v_2) = 0, and since \lambda_1 \neq \lambda_2, this forces v_1 \cdot v_2 = 0.

Building Q by induction on n. The base case n=1 is trivial: any 1\times 1 matrix is already diagonal, and Q = [1] is orthogonal. For the inductive step, assume every symmetric (n-1)\times(n-1) matrix is orthogonally diagonalizable, and let A be a symmetric n \times n matrix. By the real-eigenvalue fact above, A has a real eigenvalue \lambda_1 with a real, nonzero eigenvector; rescale it to a unit vector q_1, so Aq_1 = \lambda_1 q_1 and \lVert q_1 \rVert = 1. Extend \{q_1\} to an orthonormal basis \{q_1, q_2, \dots, q_n\} of \mathbb{R}^n (extend to any basis and apply Gram–Schmidt, which leaves q_1 fixed since it is already a unit vector orthogonal to nothing else yet chosen), and let P be the orthogonal matrix with these vectors as columns.

The subspace W = \operatorname{span}(q_2,\dots,q_n) = q_1^\perp is invariant under A: for w \in W, (Aw)\cdot q_1 = w \cdot (Aq_1) = w \cdot (\lambda_1 q_1) = \lambda_1(w\cdot q_1) = 0, using symmetry in the first step exactly as above, so Aw is again orthogonal to q_1, i.e. Aw \in W. Consequently P^{\mathsf T}AP has the block form P^{\mathsf T}AP = \begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix} for some symmetric (n-1)\times(n-1) matrix A_1: the first column of P^{\mathsf T}AP is P^{\mathsf T}(Aq_1) = P^{\mathsf T}(\lambda_1 q_1) = \lambda_1 e_1 (since P^{\mathsf T}q_1 = e_1, q_1 being the first column of the orthogonal matrix P), giving the zero block below \lambda_1; and P^{\mathsf T}AP is symmetric because A is, which forces the zero block to the right of \lambda_1 as well. By the inductive hypothesis, A_1 = Q_1D_1Q_1^{\mathsf T} for some orthogonal (n-1)\times(n-1) matrix Q_1 and diagonal D_1. Setting Q = P\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix}, \qquad D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & D_1 \end{bmatrix}, the block-diagonal factor is orthogonal (its columns are orthonormal, being e_1 together with the orthonormal columns of Q_1), so Q is a product of orthogonal matrices and hence orthogonal itself. Unwinding the block product, Q^{\mathsf T}AQ = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}P^{\mathsf T}AP\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & Q_1^{\mathsf T}A_1Q_1 \end{bmatrix} = D, so A = QDQ^{\mathsf T} with Q orthogonal and D diagonal, completing the induction.

Sanity check: take the symmetric matrix A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. Its characteristic equation is (2-\lambda)^2 - 1 = 0, so \lambda_1 = 3 and \lambda_2 = 1 — both real, as guaranteed. Solving (A-3I)v=0 gives v_1 = (1,1), and (A-I)v=0 gives v_2 = (1,-1); these two are orthogonal (v_1 \cdot v_2 = 1 - 1 = 0), exactly as the theorem predicts for eigenvectors of distinct eigenvalues. Normalizing gives q_1 = \frac{1}{\sqrt2}(1,1) and q_2 = \frac{1}{\sqrt2}(1,-1), and setting Q = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \\ 1/\sqrt2 & -1/\sqrt2 \end{bmatrix}, D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, a direct multiplication confirms QDQ^{\mathsf T} = A.

Parametrize the constraint curve near (a,b) by arc length, \mathbf{r}(t) = (x(t), y(t)), with \mathbf{r}(0) = (a,b) — this is possible precisely because \nabla g(a,b) \neq \mathbf{0}, which keeps the level curve g=k smooth with a well-defined tangent there. Restrict f to the curve: h(t) = f(x(t), y(t)). If f has a local extremum at (a,b) subject to the constraint, then h has an ordinary single-variable local extremum at t=0, so h'(0) = 0. The chain rule expands that as h'(0) = f_x(a,b)\,x'(0) + f_y(a,b)\,y'(0) = \nabla f(a,b)\cdot \mathbf{r}'(0) = 0, meaning \nabla f(a,b) is perpendicular to the curve's tangent vector \mathbf{r}'(0) at that point. But \nabla g(a,b) is also perpendicular to the same tangent vector — that's what it means for g=k to be a level curve of g. Two vectors both perpendicular to the same tangent line in the plane must be parallel to each other, so \nabla f(a,b) = \lambda \nabla g(a,b) for some scalar \lambda.

Assume (a,b)\neq(0,0) (otherwise z is the same constant everywhere and every point, vertices included, is trivially optimal). Suppose z attains its maximum at some feasible point P.

P can't be an interior point. If P is interior, every point close enough to P in every direction is still feasible. Moving a tiny step from P in the direction (a,b) changes z by a positive amount (that's what (a,b)\neq(0,0) buys), producing a nearby feasible point with a strictly larger z — contradicting that P was already maximal.

So P sits on the boundary — either at a vertex (done), or in the interior of an edge joining two vertices V_1 and V_2. Along that edge, every point is (1-t)V_1+tV_2 for some t\in[0,1], and because z is linear, z\big((1-t)V_1+tV_2\big) = (1-t)\,z(V_1) + t\,z(V_2), an affine function of t alone. An affine function on [0,1] reaches its largest value at t=0 or t=1 — the two endpoints — unless it's constant on the whole interval, in which case z(V_1)=z(V_2)=z(P) too. Either way, some vertex achieves a value at least as large as z(P)'s, and since P was already maximal, that vertex ties or matches it.

The minimum case is identical with every inequality reversed.

This is an informal justification sketch, not a full proof — see the statement above for why a complete proof is out of scope for this course.

Fix a finite search space X and a finite set of possible objective values Y. An objective function is any assignment f:X\to Y; there are |Y|^{|X|} of them, and "averaged over all objective functions" means averaged uniformly over this entire set, including every wildly discontinuous, non-smooth, adversarially scrambled assignment along with every well-behaved one.

An optimization algorithm that doesn't re-visit points, after k steps, has produced a sequence of (point, value) pairs. The key observation is this: because the average is taken over literally every possible assignment f:X\to Y, for any fixed sequence of points the algorithm might choose to visit, the sequence of values f assigns to them is equally likely to be any of the |Y|^k possible value-sequences — the average washes out any information the algorithm's choice of which points to visit could have used, because nothing about f correlates the value at one unvisited point with the value at another once f ranges uniformly over every possibility. A clever traversal order, a gradient- following heuristic, a random walk — none of these can systematically land on better values sooner than any other fixed traversal, precisely because "systematically better" would require the objective functions being averaged over to share some structure the strategy exploits, and by construction the average includes every structure-breaking permutation of f's values with equal weight.

Consequently, the average (over all f) of any performance statistic that depends only on the values an algorithm has seen (like "best value found after k steps") is the same for every non-repeating algorithm. This is the sense in which "no algorithm is better than any other, averaged over all problems" — real problems are never drawn uniformly from this set (a real objective has continuity, smoothness, or other exploitable structure), which is exactly why algorithm choice still matters in practice: an algorithm wins by assuming the structure a specific problem actually has.

FONC. Suppose x^* is a local minimum but \nabla f(x^*) \ne \mathbf{0}. Let d = -\nabla f(x^*), a nonzero vector. Taylor's theorem gives, for small \alpha>0, f(x^*+\alpha d) = f(x^*) + \alpha\, \nabla f(x^*)^\top d + o(\alpha) = f(x^*) - \alpha\, \|\nabla f(x^*)\|^2 + o(\alpha). Since \|\nabla f(x^*)\|^2 > 0, the linear term is strictly negative, and for all sufficiently small \alpha>0 it dominates the o(\alpha) remainder. So f(x^*+\alpha d) < f(x^*) for such \alpha, contradicting that x^* is a local minimum. Hence \nabla f(x^*)=\mathbf 0.

SONC. Suppose \nabla f(x^*)=\mathbf 0 but H(x^*) is not positive semidefinite: there is a direction d with d^\top H(x^*) d < 0. The second-order Taylor expansion around x^*, using \nabla f(x^*)=\mathbf 0, is f(x^*+\alpha d) = f(x^*) + \tfrac{1}{2}\alpha^2\, d^\top H(x^*) d + o(\alpha^2). Since d^\top H(x^*) d < 0, the quadratic term is strictly negative and dominates the remainder for small \alpha, so f(x^*+\alpha d) < f(x^*) arbitrarily close to x^* — contradicting a local minimum. Hence H(x^*)\succeq 0.

SOSC. Suppose \nabla f(x^*) = \mathbf 0 and H(x^*)\succ 0. Positive definiteness means there is m>0 with d^\top H(x^*) d \ge m\|d\|^2 for every direction d. The same second-order expansion gives, for any d\ne\mathbf 0 and small \alpha, f(x^*+\alpha d) - f(x^*) = \tfrac12\alpha^2\, d^\top H(x^*) d + o(\alpha^2) \ge \tfrac12 m\alpha^2\|d\|^2 + o(\alpha^2). For \alpha small enough the \tfrac12 m\alpha^2\|d\|^2 term dominates the remainder, so the right side is strictly positive. Hence f(x^*+\alpha d) > f(x^*) for every direction d and every sufficiently small step, which is exactly the definition of a strict local minimum.

Write e_n = x_n - x^*. By the definition of Newton's update and using g(x^*) = 0, e_{n+1} = x_{n+1}-x^* = x_n - x^* - \frac{g(x_n)}{g'(x_n)} = e_n - \frac{g(x_n) - g(x^*)}{g'(x_n)} = \frac{g'(x_n)e_n - \big(g(x_n)-g(x^*)\big)}{g'(x_n)}.

Now expand g(x^*) as a second-order Taylor series of g around x_n (valid since g is twice differentiable, with the Lagrange remainder form using the Lipschitz bound on g''): g(x^*) = g(x_n) + g'(x_n)(x^*-x_n) + \tfrac12 g''(\xi_n)(x^*-x_n)^2 for some \xi_n between x_n and x^*. Since g(x^*)=0 and x^*-x_n=-e_n, rearranging gives g(x_n) - g'(x_n)e_n = -\tfrac12 g''(\xi_n) e_n^2, i.e. g'(x_n)e_n - g(x_n) = \tfrac12 g''(\xi_n)e_n^2. Substituting into the expression for e_{n+1} above: e_{n+1} = \frac{\tfrac12 g''(\xi_n)\, e_n^2}{g'(x_n)}.

Because g' is continuous and g'(x^*)\ne 0, there is a neighborhood of x^* on which |g'(x)| \ge \tfrac12|g'(x^*)|>0; and because g'' is Lipschitz (hence continuous), it is bounded by some constant \bar M near x^*. Choosing x_0 (hence every subsequent x_n, by induction, provided they stay in this neighborhood) close enough to x^* that both bounds apply, we get |e_{n+1}| = \frac{|g''(\xi_n)|}{2|g'(x_n)|}\,|e_n|^2 \le \underbrace{\frac{\bar M}{|g'(x^*)|}}_{=:C} |e_n|^2. This is the claimed bound. (A standard companion argument, omitted here, confirms that if x_0 is close enough that C|e_0|<1, the sequence |e_n| in fact shrinks to 0, so the iterates stay in the neighborhood where the bound applies at every step — quadratic convergence is a local, not global, guarantee.)

Direct, for the convex case. Let m = E[X]. Because g is convex, its graph lies on or above every one of its tangent lines — in particular the tangent line at the single point x=m: g(x) \geq g(m) + g'(m)(x-m) \quad \text{for all } x (if g isn't differentiable at m, any supporting line at that point works the same way). Take the expectation of both sides over X: E[g(X)] \geq E\big[g(m) + g'(m)(X-m)\big] = g(m) + g'(m)\big(E[X]-m\big). Since m = E[X], the term E[X]-m is exactly 0, so the right side collapses to g(m) = g(E[X]): E[g(X)] \geq g(E[X]). The concave case follows by applying this result to -g, which is convex whenever g is concave, and flipping the sign back.

(\Rightarrow) Suppose f is convex. Fix x,y\in S and t\in(0,1]. Convexity applied to the two points x and y gives f\big(x+t(y-x)\big) = f\big((1-t)x+ty\big) \le (1-t)f(x)+tf(y). Rearrange: \frac{f(x+t(y-x)) - f(x)}{t} \le f(y)-f(x). As t\to 0^+, the left side is exactly the directional derivative of f at x in the direction y-x, which for a differentiable f equals \nabla f(x)^\top(y-x). Taking the limit (the inequality is preserved since it holds for every t\in(0,1]) gives \nabla f(x)^\top(y-x) \le f(y)-f(x), i.e. f(y) \ge f(x) + \nabla f(x)^\top(y-x), as claimed.

(\Leftarrow) Suppose the tangent-plane inequality holds at every pair of points in S. Fix x,y\in S and t\in[0,1], and let z=(1-t)x+ty\in S (convex S guarantees z\in S). Apply the hypothesis twice, once with the pair (z,x) and once with (z,y): f(x) \ge f(z) + \nabla f(z)^\top(x-z), \qquad f(y) \ge f(z) + \nabla f(z)^\top(y-z). Multiply the first by (1-t), the second by t, and add: (1-t)f(x)+tf(y) \ge f(z) + \nabla f(z)^\top\Big[(1-t)(x-z)+t(y-z)\Big]. The bracketed term is (1-t)x+ty - z = z-z = \mathbf 0 by the definition of z, so the gradient term vanishes and (1-t)f(x)+tf(y) \ge f(z) = f\big((1-t)x+ty\big), which is exactly the definition of convexity.

This proof builds on the first-order convexity condition (see first-order-convexity-condition): f convex \iff f(y)\ge f(x)+\nabla f(x)^\top(y-x) for all x,y\in S.

(\Rightarrow) Suppose f is convex, fix x\in S and any direction d, and let y=x+td for small t>0 (small enough that y\in S, possible since S is open). Taylor's theorem gives f(x+td) = f(x) + t\,\nabla f(x)^\top d + \tfrac12 t^2\, d^\top H(x)\, d + o(t^2). The first-order convexity condition applied to this same pair states f(x+td) \ge f(x) + \nabla f(x)^\top(td) = f(x) + t\,\nabla f(x)^\top d. Substituting the Taylor expansion's left side: f(x) + t\,\nabla f(x)^\top d + \tfrac12 t^2\, d^\top H(x)\, d + o(t^2) \ge f(x) + t\,\nabla f(x)^\top d, which simplifies to \tfrac12 t^2\, d^\top H(x)\, d + o(t^2) \ge 0. Dividing by t^2>0 and letting t\to0^+ (so o(t^2)/t^2\to0) gives d^\top H(x)\,d \ge 0. Since x\in S and direction d were arbitrary, H(x)\succeq 0 throughout S.

(\Leftarrow) Suppose H(z)\succeq 0 for every z\in S. Fix x,y\in S; since S is convex the segment z(t) = x+t(y-x), t\in[0,1], stays in S. Define \varphi(t) = f(z(t)). By the chain rule, \varphi'(t) = \nabla f(z(t))^\top(y-x) and \varphi''(t) = (y-x)^\top H(z(t)) (y-x) \ge 0 for every t, since H(z(t))\succeq 0 on S. A single-variable function with \varphi''\ge0 everywhere on [0,1] is convex on that interval (a standard single- variable fact: \varphi' is nondecreasing, so the tangent-line-below-graph argument for one variable applies to \varphi term by term). In particular, at t=0,1 convexity of \varphi gives, for x,y\in S, \varphi(1) \ge \varphi(0) + \varphi'(0)(1-0) \;\Longrightarrow\; f(y) \ge f(x) + \nabla f(x)^\top(y-x). This is exactly the first-order convexity condition for f, which is equivalent to f being convex on S.

Step 1 — weak duality (always true, no convexity needed). Define the Lagrangian L(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^\top(Ax-b) and the dual function g(\lambda,\nu) = \inf_x L(x,\lambda,\nu). For any \lambda\ge0 and any primal-feasible x, every term \lambda_i f_i(x)\le0 and \nu^\top(Ax-b)=0, so L(x,\lambda,\nu)\le f_0(x); taking the infimum over x preserves this, so g(\lambda,\nu)\le f_0(x) for every feasible x, hence g(\lambda,\nu)\le p^* for every dual-feasible (\lambda,\nu) — this is weak-duality-lp's general (nonlinear) counterpart, and gives d^*=\sup g \le p^* always.

Step 2 — Slater's condition closes the gap. Consider the set in \mathbb{R}^m\times\mathbb{R} \mathcal A = \{(u,t) : \exists x,\ Ax=b,\ f_i(x)\le u_i\ \forall i,\ f_0(x)\le t\}. Convexity of each f_i makes \mathcal A convex: given (u,t),(u',t')\in \mathcal A witnessed by x,x', the point x''=\theta x+(1-\theta)x' satisfies Ax''=b and, by convexity of each f_i, f_i(x'')\le \theta f_i(x)+(1-\theta)f_i(x') \le \theta u_i+(1-\theta)u_i', so (\theta u+(1-\theta)u',\, \theta t+(1-\theta)t')\in\mathcal A.

The point (\mathbf 0, p^*) is not in the interior of \mathcal A: any (u,t) with every u_i<0 and t<p^* in \mathcal A would exhibit a feasible x (since u_i<0 forces f_i(x)\le u_i<0) with f_0(x)\le t<p^*, contradicting p^*'s definition as the infimum. So (\mathbf 0,p^*) lies on the boundary of (the closure of) \mathcal A, and by the supporting-hyperplane theorem there is a nonzero (\lambda,\mu)\in\mathbb{R}^m\times\mathbb{R} with \lambda\ge0,\mu\ge0 such that \mu\, t + \lambda^\top u \ \ge\ \mu\, p^* \qquad \text{for every } (u,t)\in\mathcal A. \qquad(\ast)

Step 3 — \mu>0, using Slater. Suppose instead \mu=0. Then (\ast) reads \lambda^\top u \ge 0 for every u with u_i \ge f_i(x) for some feasible x; in particular at the Slater point \tilde x, u=f(\tilde x) gives \lambda^\top f(\tilde x)\ge0. But f_i(\tilde x)<0 for every i and \lambda\ge0 with \lambda\ne0 (since (\lambda,\mu)\ne0 and \mu=0) forces \lambda^\top f(\tilde x) < 0 — contradiction. So \mu>0, and dividing (\ast) by \mu we may take \mu=1 without loss of generality: t+\lambda^\top u \ge p^* for every (u,t)\in\mathcal A, with \lambda\ge0.

Step 4 — this \lambda is dual optimal with no gap. Taking, for any feasible x, u=f(x) and t=f_0(x) (a valid element of \mathcal A) gives f_0(x) + \lambda^\top f(x) \ge p^* for every x satisfying Ax=b — and since this only used Ax=b, it in fact holds with some matching \nu absorbed into the affine part, i.e. \inf_{x} \{f_0(x)+\lambda^\top f(x) + \nu^\top(Ax-b)\} \ge p^* for the appropriate \nu, i.e. g(\lambda,\nu)\ge p^*. Combined with weak duality (g(\lambda,\nu)\le p^* always), this forces g(\lambda,\nu)=p^* exactly — strong duality, with (\lambda,\nu)=(\lambda^*,\nu^*) dual optimal.

Step 5 — KKT necessity follows. Let x^* be primal optimal. Since g(\lambda^*,\nu^*)=f_0(x^*) (both equal p^*) and g(\lambda^*,\nu^*)=\inf_x L(x,\lambda^*,\nu^*)\le L(x^*,\lambda^*,\nu^*) = f_0(x^*)+\sum_i\lambda_i^* f_i(x^*), and \sum_i\lambda_i^*f_i(x^*)\le0 (feasibility and \lambda^*\ge0), the whole chain f_0(x^*) = g(\lambda^*,\nu^*) \le L(x^*,\lambda^*,\nu^*) \le f_0(x^*) must be equality throughout. Equality in \sum_i\lambda_i^*f_i(x^*)\le 0 term by term (each term is \le0) forces \lambda_i^* f_i(x^*)=0 for every i — complementary slackness. And x^* minimizing L(x,\lambda^*,\nu^*) over x (equality g(\lambda^*,\nu^*)= L(x^*,\lambda^*,\nu^*) with g defined as the infimum) at a differentiable L forces \nabla_x L(x^*,\lambda^*,\nu^*)=\mathbf 0 — stationarity. Both together with \lambda^*\ge0 (dual feasibility) and x^* feasible (primal feasibility) are exactly the KKT conditions, and they hold at every primal optimum whenever Slater's condition holds — necessity, not just sufficiency.

Primal feasibility (2) holds automatically since x^* is feasible.

A geometric fact used below. Call d a first-order feasible direction at x^* if \nabla f_i(x^*)^\top d < 0 for every active i\in \mathcal A(x^*) and \nabla h_j(x^*)^\top d = 0 for every j — to first order, moving from x^* along d strictly decreases every active inequality constraint (keeping it feasible) and stays on the equality constraints' tangent space. Under LICQ, the implicit function theorem lets any such d be realized by an actual feasible curve x(t) with x(0)=x^* and x'(0)=d that satisfies h_j(x(t))=0 exactly (not just to first order) and f_i(x(t))<0 for small t>0: intuitively, the active h_j's linearly independent gradients let a small correction term of order t^2 be added to x^*+td to snap the curve back onto \{h_j=0\} without disturbing the strict inequality constraints, which have first-order slack. If x^* is a local minimum, no such curve can have f_0(x(t))<f_0(x^*) for small t>0, so \left.\frac{d}{dt}\right|_{t=0}f_0(x(t)) = \nabla f_0(x^*)^\top d \ge 0. So: no first-order feasible direction d can also satisfy \nabla f_0(x^*)^\top d < 0.

Gordan's theorem of the alternative (a classical consequence of the separating-hyperplane theorem, used here as a known result): for vectors a_1,\dots,a_k\in\mathbb R^n, exactly one of the following holds — either there is d with a_\ell^\top d < 0 for every \ell, or there are \mu_1,\dots,\mu_k\ge0, not all zero, with \sum_\ell \mu_\ell a_\ell = \mathbf 0.

Apply Gordan's theorem to the list of vectors a_0=\nabla f_0(x^*), a_i=\nabla f_i(x^*) for i\in\mathcal A(x^*), and — splitting each equality constraint into the pair of inequalities h_j\le0,\ -h_j\le0, both active at x^* — a_{j+}=\nabla h_j(x^*), a_{j-}=-\nabla h_j(x^*) for each j. The previous paragraph shows the "there is d with every a_\ell^\top d<0" branch is impossible: such a d would be a first-order feasible direction (the two opposite-signed rows for each h_j force \nabla h_j(x^*)^\top d = 0 exactly, and a_i^\top d<0 for active i is the inequality condition) with \nabla f_0(x^*)^\top d<0, which was just ruled out. So the second branch holds: there exist \lambda_0\ge0, \lambda_i\ge0 (i\in\mathcal A(x^*)), \mu_j^+,\mu_j^-\ge0, not all zero, with \lambda_0\nabla f_0(x^*) + \sum_{i\in\mathcal A(x^*)}\lambda_i\nabla f_i(x^*) + \sum_j (\mu_j^+-\mu_j^-)\nabla h_j(x^*) = \mathbf 0. Write \nu_j=\mu_j^+-\mu_j^- (an unrestricted-sign real number, since \mu_j^\pm\ge0 independently).

\lambda_0>0. If \lambda_0=0, the display becomes \sum_i\lambda_i\nabla f_i(x^*)+\sum_j\nu_j\nabla h_j(x^*)=\mathbf 0 with (\lambda_{\mathcal A(x^*)},\nu) not all zero (since not everything among \lambda_0,\lambda_i,\mu_j^\pm is zero, and \lambda_0=0) — a nontrivial linear dependence among \{\nabla f_i(x^*):i\in\mathcal A(x^*)\}\cup \{\nabla h_j(x^*)\}, contradicting LICQ. So \lambda_0>0; divide the whole display by \lambda_0 to normalize \lambda_0=1.

Assemble the multipliers. Set \lambda_i^*=\lambda_i/\lambda_0 for i\in\mathcal A(x^*) and \lambda_i^*=0 for i\notin\mathcal A(x^*), and \nu_j^*=\nu_j/\lambda_0. The normalized display is exactly stationarity (1). Dual feasibility (3), \lambda_i^*\ge0, holds by construction for active i and trivially (0\ge0) for inactive i. Complementary slackness (4) holds because for active i, f_i(x^*)=0 so \lambda_i^*f_i(x^*)=0 regardless of \lambda_i^*'s value, and for inactive i, \lambda_i^*=0 makes the product 0 regardless of f_i(x^*)'s value.

Assume (a,b)\neq(0,0) (otherwise z is the same constant everywhere and every point, vertices included, is trivially optimal). Suppose z attains its maximum at some feasible point P.

P can't be an interior point. If P is interior, every point close enough to P in every direction is still feasible. Moving a tiny step from P in the direction (a,b) changes z by a positive amount (that's what (a,b)\neq(0,0) buys), producing a nearby feasible point with a strictly larger z — contradicting that P was already maximal.

So P sits on the boundary — either at a vertex (done), or in the interior of an edge joining two vertices V_1 and V_2. Along that edge, every point is (1-t)V_1+tV_2 for some t\in[0,1], and because z is linear, z\big((1-t)V_1+tV_2\big) = (1-t)\,z(V_1) + t\,z(V_2), an affine function of t alone. An affine function on [0,1] reaches its largest value at t=0 or t=1 — the two endpoints — unless it's constant on the whole interval, in which case z(V_1)=z(V_2)=z(P) too. Either way, some vertex achieves a value at least as large as z(P)'s, and since P was already maximal, that vertex ties or matches it.

The minimum case is identical with every inequality reversed.

Let x^* be any optimal solution (one exists: P is nonempty, bounded, and closed, and a linear function is continuous, so the extreme-value theorem guarantees a minimizer over P). Suppose, for contradiction, that x^* is not an extreme point. Then x^* = \theta y + (1-\theta)z for some y,z\in P with y\ne z and \theta\in(0,1), i.e. x^* sits strictly inside a line segment [y,z]\subseteq P. Extend that segment to the full line through x^* in the direction d = z-y \ne \mathbf 0: points x^*+td for t ranging over some interval around 0 (at least covering t\in[-\theta,\,1-\theta], which recovers y and z) also satisfy A(x^*+td) = Ax^* + tAd. Since both y=x^*-\theta d and z=x^*+(1-\theta)d satisfy Ay=Az=b, subtracting gives Ad=\mathbf 0 — so A(x^*+td)=b for every t, not just the two endpoints.

Because P is bounded, the set of t for which x^*+td\ge\mathbf 0 (the only constraint left to satisfy) is itself a bounded closed interval [t_{\min}, t_{\max}] containing 0 in its interior (since x^*+td\ge0 holds at t=-\theta<0 and t=1-\theta>0, both nonzero, 0 is interior to the feasible range of t). At the two endpoints t=t_{\min} and t=t_{\max}, at least one coordinate of x^*+td hits exactly 0 (that's what makes the interval closed and bounded there) — call these boundary points x^-=x^*+t_{\min}d and x^+=x^*+t_{\max}d, both in P.

Now evaluate the objective along this segment: $c^\top(x^+td) = c^\top x^

• t,(c^\top d), a linear (hence monotone or constant) function of t. Since t=0 lies strictly between t_{\min} and t_{\max}, and a linear function of one variable attains its minimum over a closed interval at an endpoint, at least one of x^-,x^+ achieves objective value c^\top x^* + t(c^\top d) \le c^\top x^ for the appropriate endpoint's t — i.e. c^\top x^- \le c^\top x^ or c^\top x^+\le c^\top x^. Since x^ was already optimal, this endpoint must in fact achieve *equality*: x^- or x^+$ is another optimal solution.

This new optimal point has at least one more coordinate pinned to 0 than x^* had reason to (the coordinate that hit its bound at t_{\min} or t_{\max}), i.e. it satisfies at least one more of the constraints x_k\ge0 with equality. Repeating this argument — replace the current optimal point with a boundary point along some direction that keeps it optimal, gaining one more tight nonnegativity constraint each time — can only happen finitely many times, since there are only n coordinates to pin to 0 and a point with n linearly independent tight constraints (enough to pin down a unique point, together with Ax=b) admits no further nontrivial direction d to move along at all — that point is an extreme point by construction, and it is still optimal by the chain of equalities above.

Let z^*_M denote the Big-M problem's optimal value, achieved at a solution with \sum_i a_i^* = s > 0. Suppose, for contradiction, that the original LP (feasible region F, ignoring the artificial variables entirely) is in fact feasible: there is a point \bar x\in F. Then setting every artificial variable to 0 and using \bar x's coordinates gives a feasible point of the Big-M problem too (the artificial variables were only needed to reach an initial basic feasible solution mechanically; any point feasible for the original constraints trivially satisfies the same constraints with all a_i=0 added in). At this point, the Big-M objective equals c^\top \bar x + M\cdot 0 = c^\top\bar x, some finite number independent of M.

Because the Big-M solution is optimal, its value z^*_M must be at most this candidate's value: z^*_M \le c^\top \bar x. But the Big-M solution's own value decomposes as z_M^* = c^\top x^* + Ms for its own x^* and penalty total s>0. So c^\top x^* + Ms \le c^\top \bar x. The coefficients c and the feasible region are fixed, independent of M; only M itself was chosen large. Since s>0 is a fixed positive number (the actual penalty incurred at the reported optimum) and c^\top x^*, c^\top\bar x are both bounded by fixed constants (say |c^\top x^*|, |c^\top\bar x| \le K for some K depending only on the problem data, not on M, over the relevant bounded region), the inequality c^\top x^*+Ms\le c^\top\bar x \le K forces M \le \frac{K - c^\top x^*}{s} \le \frac{2K}{s}, a bound that does not grow with M. This contradicts the standing assumption that M was chosen larger than any such fixed bound (the whole point of "sufficiently large M" in the Big-M method's setup: chosen bigger than any finite quantity the rest of the problem could produce). The contradiction shows \bar x cannot exist — the original LP has no feasible point.

This is a proof sketch, naming the shape of the real argument rather than carrying out every step — see the note above for why the complete version is out of scope here.

Suppose, for contradiction, that Bland's rule still allows cycling: a finite sequence of pivots returns to a previously visited basis, and (since a cycle only happens when the objective value is unchanging across the whole loop — any strictly improving pivot could never be revisited) every pivot in the cycle is degenerate, meaning the leaving variable's value is already 0 before it leaves. Let t be the largest index of any variable that both enters the basis at some point in the cycle and leaves it at some (possibly different) point in the cycle — such a variable exists because the basis returns to its starting point, so every variable that ever enters during the cycle must also leave at some point during it.

Consider the specific pivot in the cycle where x_t leaves the basis (call this tableau's basis B, with entering variable x_s at that step), and the pivot where x_t enters (a different tableau in the cycle, with basis B'). The heart of the argument is a case analysis comparing the reduced-cost row of x_t across these two tableaus, using the fact that both correspond to feasible bases with the same objective value (degeneracy) and that t was chosen as the largest such index: Bland's smallest-index tie-breaking rule, applied to both the entering choice (smallest index among negative reduced costs) and the leaving choice (smallest index among tied ratio-test rows), forces every other variable with index less than t that appears in the relevant rows to have a reduced cost or ratio that is not more favorable than x_t's at the step where x_t is passed over — combined with the algebraic identity relating a reduced cost in one tableau to a nonnegative combination of the pivot row's entries from the other tableau (standard simplex tableau bookkeping), this forces a specific reduced cost that Bland's rule required to be \ge0 for eligibility to instead be forced strictly negative — a direct contradiction of what "eligible to enter under Bland's rule" meant at that step.

That contradiction rules out the existence of any degenerate cycle under Bland's rule. Since a non-degenerate pivot always strictly decreases the objective (so it can never revisit an earlier, strictly-worse basis), and there are only finitely many bases total for a given LP (choosing m basic variables from n total is a finite combinatorial choice), the simplex method under Bland's rule can only take finitely many pivots before terminating — either at an optimal basis or a certificate of unboundedness.

Let x be primal-feasible (Ax\ge b, x\ge0) and y dual-feasible (A^\top y\le c, y\ge0). Start from the primal feasibility inequality Ax\ge b. Since y\ge0, multiplying both sides by y^\top preserves the inequality direction (a nonnegative vector dotted into a componentwise inequality preserves it): y^\top(Ax) \ \ge\ y^\top b. Now start from dual feasibility, A^\top y \le c, i.e. c - A^\top y \ge \mathbf 0. Since x\ge0, dotting with x^\top preserves the inequality: x^\top(c - A^\top y) \ \ge\ 0 \quad\Longrightarrow\quad x^\top c \ \ge\ x^\top A^\top y. But x^\top A^\top y = (Ax)^\top y = y^\top(Ax) (transposing a scalar changes nothing), so this reads c^\top x \ge y^\top(Ax). Chaining the two displayed inequalities: c^\top x \ \ge\ y^\top(Ax) \ \ge\ y^\top b = b^\top y.

This proof leans on the simplex method's own termination guarantee (see blands-rule-anti-cycling: under Bland's rule, simplex always terminates in finitely many pivots at an optimal basis whenever one exists) rather than re-deriving that fact here.

Convert the primal to standard equality form by subtracting a surplus vector s\ge0: Ax - s = b, x,s\ge0, minimize c^\top x. Since the primal is feasible and bounded, the simplex method (Bland's rule, terminating finitely) reaches an optimal basic feasible solution x^* with optimal basis B (the columns of [A\ {-I}] corresponding to the basic variables). At termination, simplex's optimality test says every non-basic variable's reduced cost is nonnegative: \bar c_j = c_j - c_B^\top B^{-1}A_j \ \ge\ 0 \quad\text{for every column } A_j \text{ of } [A\ {-I}].

Define y^* := (B^{-1})^\top c_B = (c_B^\top B^{-1})^\top, a vector in \mathbb R^m (one entry per constraint row). Check dual feasibility: for every original column A_j of A, the reduced-cost condition reads c_j - (y^*)^\top A_j \ge 0, i.e. (y^*)^\top A_j \le c_j for every j — stacking over all j, this is exactly A^\top y^* \le c. For every slack/surplus column (the -e_i columns of -I), the reduced-cost condition reads 0 - (y^*)^\top(-e_i) \ge 0, i.e. y_i^*\ge0 — exactly dual feasibility's nonnegativity requirement. So y^* is dual-feasible.

Now compute the dual objective at y^*: because x^* is a basic feasible solution with B x_B^* = b (i.e. x_B^* = B^{-1}b, and every non-basic entry of x^* is 0), b^\top y^* = (Bx_B^*)^\top y^* = (x_B^*)^\top B^\top y^* = (x_B^*)^\top c_B = c_B^\top x_B^* = c^\top x^* (the middle step uses B^\top y^* = B^\top(B^{-1})^\top c_B = c_B directly from y^*'s definition, and the last step uses that x^*'s non-basic entries, where c contributes nothing extra, are all 0). So the dual objective at the feasible point y^* equals the primal optimal value exactly: b^\top y^* = c^\top x^* = p^*.

By weak duality, b^\top y^*\le p^* always — but here it's already equality, and weak duality also says no dual-feasible point can exceed p^*, so y^* is in fact dual-optimal: d^* = b^\top y^* = p^*.

Start from the same two chained inequalities used to prove weak duality (weak-duality-lp): for primal-feasible x and dual-feasible y, c^\top x - b^\top y = \underbrace{x^\top(c-A^\top y)}_{\ge 0 \text{ (each term } x_j(c_j-A_j^\top y)\ge0\text{)}} \ + \ \underbrace{y^\top(Ax-b)}_{\ge 0 \text{ (each term } y_i(A_ix-b_i)\ge0\text{)}}. (This is exactly the algebra from the weak-duality proof, kept in unexpanded form: both bracketed sums are sums of nonnegative terms, since x,y\ge0 and c-A^\top y\ge0, Ax-b\ge0 by feasibility.)

(\Leftarrow) If every term in both sums is individually 0 — which is exactly the complementary slackness conditions stated above — then the whole right side is 0, so c^\top x = b^\top y. Weak duality already guarantees b^\top y\le d^*\le p^*\le c^\top x for the true optimal values p^*,d^*; combined with c^\top x=b^\top y this forces c^\top x = p^* and b^\top y=d^* exactly — both x and y are optimal.

(\Rightarrow) Conversely, suppose x and y are both optimal. By strong duality (strong-duality-lp, which applies since a feasible, bounded LP has p^*=d^*), c^\top x = p^* = d^* = b^\top y, so the left side of the display above is 0. But the right side is a sum of two sums, each made of individually nonnegative terms (x_j(c_j-A_j^\top y)\ge0 and y_i(A_ix-b_i)\ge0, from feasibility as noted above); a sum of nonnegative terms can only equal 0 if every term is individually 0. That is exactly the complementary slackness conditions.

The base case V_0(s)=0 holds by definition (zero stages left means the process has already ended, so no further cost can be incurred from any state).

For k\ge1, fix a state s. Any sequence of k actions a_0,a_1,\dots,a_{k-1} starting from s produces a total cost g(s,a_0) + g(s_1,a_1) + \cdots + g(s_{k-1},a_{k-1}), where s_1=T(s,a_0), s_2=T(s_1,a_1), etc. Split off the first term: this equals g(s,a_0) + \big[g(s_1,a_1)+\cdots+g(s_{k-1},a_{k-1})\big], and the bracketed remainder is exactly the total cost of a (k-1)-action sequence starting from s_1=T(s,a_0).

(\le) Fix any action a for the first step, and let s_1=T(s,a). Whatever (k-1)-step sequence achieves the optimal remaining cost V_{k-1}(s_1) from s_1, prepending action a produces a valid k-step sequence from s with total cost exactly g(s,a)+V_{k-1}(s_1). Since V_k(s) is the minimum over all k-step sequences from s, and this is one particular such sequence, V_k(s) \ \le\ g(s,a) + V_{k-1}\big(T(s,a)\big) \quad \text{for every } a. Taking the minimum over a on the right preserves the inequality: V_k(s) \le \min_a\big[g(s,a)+V_{k-1}(T(s,a))\big].

(\ge) Conversely, let a_0^\dagger,\dots,a_{k-1}^\dagger be a sequence achieving the optimum V_k(s) (one exists over a finite action/stage structure), with s_1^\dagger = T(s,a_0^\dagger). Its total cost is g(s,a_0^\dagger) + \big[g(s_1^\dagger,a_1^\dagger)+\cdots\big], and the bracketed remainder is the cost of some (k-1)-step sequence from s_1^\dagger — so it can be no smaller than the optimal remaining cost from s_1^\dagger, namely V_{k-1}(s_1^\dagger) (by definition, V_{k-1} is the minimum over every such sequence). Hence V_k(s) = g(s,a_0^\dagger) + \big[\text{that remainder}\big] \ \ge\ g(s,a_0^\dagger) + V_{k-1}(s_1^\dagger) \ \ge\ \min_a\big[g(s,a)+V_{k-1}(T(s,a))\big], the last step because a_0^\dagger is one particular choice of a, no better than the minimum over all of them.

Combining both directions gives equality: V_k(s) = \min_a\big[g(s,a)+V_{k-1}(T(s,a))\big].

Primal feasibility (2) holds automatically since x^* is feasible.

A geometric fact used below. Call d a first-order feasible direction at x^* if \nabla f_i(x^*)^\top d < 0 for every active i\in \mathcal A(x^*) and \nabla h_j(x^*)^\top d = 0 for every j — to first order, moving from x^* along d strictly decreases every active inequality constraint (keeping it feasible) and stays on the equality constraints' tangent space. Under LICQ, the implicit function theorem lets any such d be realized by an actual feasible curve x(t) with x(0)=x^* and x'(0)=d that satisfies h_j(x(t))=0 exactly (not just to first order) and f_i(x(t))<0 for small t>0: intuitively, the active h_j's linearly independent gradients let a small correction term of order t^2 be added to x^*+td to snap the curve back onto \{h_j=0\} without disturbing the strict inequality constraints, which have first-order slack. If x^* is a local minimum, no such curve can have f_0(x(t))<f_0(x^*) for small t>0, so \left.\frac{d}{dt}\right|_{t=0}f_0(x(t)) = \nabla f_0(x^*)^\top d \ge 0. So: no first-order feasible direction d can also satisfy \nabla f_0(x^*)^\top d < 0.

Gordan's theorem of the alternative (a classical consequence of the separating-hyperplane theorem, used here as a known result): for vectors a_1,\dots,a_k\in\mathbb R^n, exactly one of the following holds — either there is d with a_\ell^\top d < 0 for every \ell, or there are \mu_1,\dots,\mu_k\ge0, not all zero, with \sum_\ell \mu_\ell a_\ell = \mathbf 0.

Apply Gordan's theorem to the list of vectors a_0=\nabla f_0(x^*), a_i=\nabla f_i(x^*) for i\in\mathcal A(x^*), and — splitting each equality constraint into the pair of inequalities h_j\le0,\ -h_j\le0, both active at x^* — a_{j+}=\nabla h_j(x^*), a_{j-}=-\nabla h_j(x^*) for each j. The previous paragraph shows the "there is d with every a_\ell^\top d<0" branch is impossible: such a d would be a first-order feasible direction (the two opposite-signed rows for each h_j force \nabla h_j(x^*)^\top d = 0 exactly, and a_i^\top d<0 for active i is the inequality condition) with \nabla f_0(x^*)^\top d<0, which was just ruled out. So the second branch holds: there exist \lambda_0\ge0, \lambda_i\ge0 (i\in\mathcal A(x^*)), \mu_j^+,\mu_j^-\ge0, not all zero, with \lambda_0\nabla f_0(x^*) + \sum_{i\in\mathcal A(x^*)}\lambda_i\nabla f_i(x^*) + \sum_j (\mu_j^+-\mu_j^-)\nabla h_j(x^*) = \mathbf 0. Write \nu_j=\mu_j^+-\mu_j^- (an unrestricted-sign real number, since \mu_j^\pm\ge0 independently).

\lambda_0>0. If \lambda_0=0, the display becomes \sum_i\lambda_i\nabla f_i(x^*)+\sum_j\nu_j\nabla h_j(x^*)=\mathbf 0 with (\lambda_{\mathcal A(x^*)},\nu) not all zero (since not everything among \lambda_0,\lambda_i,\mu_j^\pm is zero, and \lambda_0=0) — a nontrivial linear dependence among \{\nabla f_i(x^*):i\in\mathcal A(x^*)\}\cup \{\nabla h_j(x^*)\}, contradicting LICQ. So \lambda_0>0; divide the whole display by \lambda_0 to normalize \lambda_0=1.

Assemble the multipliers. Set \lambda_i^*=\lambda_i/\lambda_0 for i\in\mathcal A(x^*) and \lambda_i^*=0 for i\notin\mathcal A(x^*), and \nu_j^*=\nu_j/\lambda_0. The normalized display is exactly stationarity (1). Dual feasibility (3), \lambda_i^*\ge0, holds by construction for active i and trivially (0\ge0) for inactive i. Complementary slackness (4) holds because for active i, f_i(x^*)=0 so \lambda_i^*f_i(x^*)=0 regardless of \lambda_i^*'s value, and for inactive i, \lambda_i^*=0 makes the product 0 regardless of f_i(x^*)'s value.

This is an informal justification sketch, not a full proof — see the statement above for why a complete proof is out of scope for this course.

Fix a finite search space X and a finite set of possible objective values Y. An objective function is any assignment f:X\to Y; there are |Y|^{|X|} of them, and "averaged over all objective functions" means averaged uniformly over this entire set, including every wildly discontinuous, non-smooth, adversarially scrambled assignment along with every well-behaved one.

An optimization algorithm that doesn't re-visit points, after k steps, has produced a sequence of (point, value) pairs. The key observation is this: because the average is taken over literally every possible assignment f:X\to Y, for any fixed sequence of points the algorithm might choose to visit, the sequence of values f assigns to them is equally likely to be any of the |Y|^k possible value-sequences — the average washes out any information the algorithm's choice of which points to visit could have used, because nothing about f correlates the value at one unvisited point with the value at another once f ranges uniformly over every possibility. A clever traversal order, a gradient- following heuristic, a random walk — none of these can systematically land on better values sooner than any other fixed traversal, precisely because "systematically better" would require the objective functions being averaged over to share some structure the strategy exploits, and by construction the average includes every structure-breaking permutation of f's values with equal weight.

Consequently, the average (over all f) of any performance statistic that depends only on the values an algorithm has seen (like "best value found after k steps") is the same for every non-repeating algorithm. This is the sense in which "no algorithm is better than any other, averaged over all problems" — real problems are never drawn uniformly from this set (a real objective has continuity, smoothness, or other exploitable structure), which is exactly why algorithm choice still matters in practice: an algorithm wins by assuming the structure a specific problem actually has.

This is an informal justification sketch, not a full proof — see the statement above for why a complete proof is out of scope for this course.

Fix a finite search space X and a finite set of possible objective values Y. An objective function is any assignment f:X\to Y; there are |Y|^{|X|} of them, and "averaged over all objective functions" means averaged uniformly over this entire set, including every wildly discontinuous, non-smooth, adversarially scrambled assignment along with every well-behaved one.

An optimization algorithm that doesn't re-visit points, after k steps, has produced a sequence of (point, value) pairs. The key observation is this: because the average is taken over literally every possible assignment f:X\to Y, for any fixed sequence of points the algorithm might choose to visit, the sequence of values f assigns to them is equally likely to be any of the |Y|^k possible value-sequences — the average washes out any information the algorithm's choice of which points to visit could have used, because nothing about f correlates the value at one unvisited point with the value at another once f ranges uniformly over every possibility. A clever traversal order, a gradient- following heuristic, a random walk — none of these can systematically land on better values sooner than any other fixed traversal, precisely because "systematically better" would require the objective functions being averaged over to share some structure the strategy exploits, and by construction the average includes every structure-breaking permutation of f's values with equal weight.

Consequently, the average (over all f) of any performance statistic that depends only on the values an algorithm has seen (like "best value found after k steps") is the same for every non-repeating algorithm. This is the sense in which "no algorithm is better than any other, averaged over all problems" — real problems are never drawn uniformly from this set (a real objective has continuity, smoothness, or other exploitable structure), which is exactly why algorithm choice still matters in practice: an algorithm wins by assuming the structure a specific problem actually has.

This is an informal justification sketch, not a full proof — see the statement above for why a complete proof is out of scope for this course.

Fix a finite search space X and a finite set of possible objective values Y. An objective function is any assignment f:X\to Y; there are |Y|^{|X|} of them, and "averaged over all objective functions" means averaged uniformly over this entire set, including every wildly discontinuous, non-smooth, adversarially scrambled assignment along with every well-behaved one.

An optimization algorithm that doesn't re-visit points, after k steps, has produced a sequence of (point, value) pairs. The key observation is this: because the average is taken over literally every possible assignment f:X\to Y, for any fixed sequence of points the algorithm might choose to visit, the sequence of values f assigns to them is equally likely to be any of the |Y|^k possible value-sequences — the average washes out any information the algorithm's choice of which points to visit could have used, because nothing about f correlates the value at one unvisited point with the value at another once f ranges uniformly over every possibility. A clever traversal order, a gradient- following heuristic, a random walk — none of these can systematically land on better values sooner than any other fixed traversal, precisely because "systematically better" would require the objective functions being averaged over to share some structure the strategy exploits, and by construction the average includes every structure-breaking permutation of f's values with equal weight.

Consequently, the average (over all f) of any performance statistic that depends only on the values an algorithm has seen (like "best value found after k steps") is the same for every non-repeating algorithm. This is the sense in which "no algorithm is better than any other, averaged over all problems" — real problems are never drawn uniformly from this set (a real objective has continuity, smoothness, or other exploitable structure), which is exactly why algorithm choice still matters in practice: an algorithm wins by assuming the structure a specific problem actually has.