4.3 Constrained optimization and Lagrange multipliers

Fix an integer $n\ge1$ and the Euclidean norm on $\mathbb R^n$. A set is bounded if it lies in some finite-radius ball, closed if its complement is open, and compact if every cover by open subsets of $\mathbb R^n$ has a finite subcover. We use real completeness, including the nested closed interval property.

Heine–Borel in finite-dimensional Euclidean space

Theorem. A set $K\subseteq\mathbb R^n$ is compact if and only if it is closed and bounded. The empty set satisfies all three properties.

Compact implies bounded. The open balls $B(0,m)$, $m\ge1$ an integer, cover $K$. A finite subcover puts $K$ inside the largest of these balls.

Compact implies closed. Suppose $K\ne\varnothing$ and $y\notin K$. The balls $B(x,\|x-y\|/2)$, $x\in K$, cover $K$. Choose a finite subcover with centers $x_1,\ldots,x_r$ and set $\delta=\min_i\|x_i-y\|/2>0$. If $z$ lies in the ball centered at $x_i$, the triangle inequality gives $\|z-y\|>\|x_i-y\|/2\ge\delta$. Hence $B(y,\delta)$ misses $K$, so the complement is open.

Closed and bounded implies compact. Let nonempty $K$ be closed and bounded. Enclose it in a closed cube $Q_0=[-M,M]^n$ with $M>0$. Suppose an open cover of $K$ has no finite subcover. Divide each coordinate interval into two closed halves. The resulting $2^n$ closed subcubes cover $Q_0$. At least one subcube has intersection with $K$ that is not finitely coverable by the given family; otherwise the finite union of the finite subcovers would cover $K$. Select such a subcube and repeat. This produces nested closed cubes $Q_j$ with side length $2M/2^j$ and $K\cap Q_j$ not finitely coverable, hence nonempty.

For each coordinate, the nested interval property gives a common coordinate value. Together these give $p\in\bigcap_jQ_j$. Every pair of points in $Q_j$ has distance at most $2M\sqrt n/2^j$, so the intersection contains only $p$. Choose $x_j\in K\cap Q_j$. Then $\|x_j-p\|\le2M\sqrt n/2^j\to0$. A closed set contains such a limit: if $p$ were in its open complement, a ball around $p$ would eventually contain $x_j$ outside $K$, a contradiction. Thus $p\in K$.

One member $O$ of the cover contains $p$, and openness gives $B(p,\varepsilon)\subseteq O$ for some $\varepsilon>0$. For sufficiently large $j$, every point of $Q_j$ is within $\varepsilon$ of $p$, so $O$ alone covers $K\cap Q_j$. This contradicts the selection of $Q_j$. Therefore every open cover has a finite subcover. The number $2^n$ is finite; replacing it by infinitely many subpieces would invalidate this argument.

Continuous images and extreme values

Theorem. If $K\subseteq\mathbb R^n$ is compact and $F:K\to\mathbb R^m$ is continuous relative to $K$, then $F(K)$ is compact. In particular, a continuous $f:K\to\mathbb R$ on nonempty compact $K$ is bounded and attains its maximum and minimum.

Proof. An open cover $(O_i)$ of $F(K)$ pulls back to relatively open sets $F^{-1}(O_i)=K\cap U_i$, with $U_i$ open in $\mathbb R^n$. These $U_i$ cover $K$, so finitely many suffice. Their corresponding $O_i$ cover $F(K)$, proving compactness. For scalar $f$, the image is nonempty, closed and bounded by the theorem already proved in dimension one. Let $a=\sup f(K)$. For each $j\ge1$, the definition of supremum supplies $y_j\in f(K)$ with $a-1/j<y_j\le a$. Then $y_j\to a$, and closedness places $a$ in the image. Thus the maximum is attained. Applying the same argument to $-f$ gives the minimum. This proves existence, not a formula for the maximizing input.

The real zero-derivative lemma needed for uniqueness

The already selected finite-Euclidean compactness/extreme-value proof supplies extrema for a continuous real function on $[a,b]$. At an interior differentiable extremum the left and right difference quotients force its derivative to be zero. A continuous $g$ with equal endpoint values either is constant or has an interior maximum or minimum; hence, if differentiable inside, it has a zero derivative there (Rolle's argument). For a real differentiable $f$, subtract its endpoint secant line and apply this argument: $f(b)-f(a)=f'(c)(b-a)$ for some $c\in(a,b)$. Thus a real function with derivative zero on an interval is constant. Applying this separately to real and imaginary parts proves the same constant conclusion for complex-valued functions of a real parameter. There is no complex mean-value identity being assumed.

Real inner products, their norms and the needed inequalities

An inner product on a real vector space is a map $\langle u,v\rangle\in\mathbb R$ that is symmetric, linear in each argument, and positive definite: $\langle v,v\rangle>0$ for $v\ne0$. Linearity gives $\langle0,v\rangle=0$. Define $\|v\|=\sqrt{\langle v,v\rangle}$. It is zero exactly at zero and satisfies $\|cv\|=|c|\|v\|$. The standard example on $\mathbb R^m$ is $\langle u,v\rangle=\sum_{i=1}^mu_iv_i$. Vectors are orthogonal when their inner product is zero, and a list is orthonormal when distinct members are orthogonal and each member has norm one.

If $v\ne0$, insert $t=\langle u,v\rangle/\|v\|^2$ into the nonnegative square $\|u-tv\|^2$. Expanding by bilinearity gives $\|u\|^2-\langle u,v\rangle^2/\|v\|^2\ge0$, hence $|\langle u,v\rangle|\le\|u\|\|v\|$. If $v=0$ the same inequality holds directly. Equality for $v\ne0$ means $\|u-tv\|=0$, equivalently $u=tv$; the zero-vector cases also give equality. Finally expand $\|u+v\|^2$ and apply the bound to its cross term to obtain $\|u+v\|^2\le(\|u\|+\|v\|)^2$. Both sides to be square-rooted are nonnegative, so the triangle inequality follows. Thus this is a norm, and normalization of any nonzero vector divides by a positive real number. No complex bilinear convention is being used.

Leibniz determinant and alternation over a commutative ring

Let $R$ be a commutative ring with identity, $n\ge1$, and $A\in M_n(R)$. Define

The sign is $(-1)^{\operatorname{inv}(\sigma)}$, interpreted in $R$. Exchanging adjacent entries in a permutation changes its inversion count by one in parity. Sorting by adjacent inversions therefore gives its sign as the product of the signs of those exchanges. Applying an adjacent-exchange decomposition of $\tau$ to the positions of $\sigma$ proves $\operatorname{sgn}(\sigma\tau)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$; a transposition has sign $-1$. These are integer parity facts before mapping the signs into $R$.

The finite formula is multilinear in each row and column. If two rows are equal, pair each permutation term with the term obtained by exchanging the two assigned columns. The pair is distinct, has the same product and opposite signs; its sum is zero in every characteristic. Thus the determinant vanishes on repeated rows; the column statement is identical. This is a paired cancellation, not an inference from $2\det A=0$. Exchanging rows or columns changes sign by the same permutation substitution. Also $\det I=1$. Substituting $\sigma^{-1}$ in the sum gives $\det A^{\mathsf T}=\det A$.

Here is the needed uniqueness principle, valid even with zero divisors. If $D$ is an alternating multilinear function of $n$ column vectors in $R^n$, expand each input in the standard basis. Terms with a repeated basis vector vanish. The other index lists are permutations; swapping two slots negates $D$, since expansion of $D(\ldots,u+v,\ldots,u+v,\ldots)=0$ gives $D(\ldots,u,\ldots,v,\ldots)+D(\ldots,v,\ldots,u,\ldots)=0$. Hence the expansion equals $D(e_1,\ldots,e_n)$ times the Leibniz determinant of the input columns. No division or field assumption was used.

Multiplicativity, triangular blocks and the adjugate

For fixed $A$, the function $D(v_1,\ldots,v_n)=\det(Av_1,\ldots,Av_n)$ is alternating multilinear, with $D(e_1,\ldots,e_n)=\det A$. Applying the preceding uniqueness principle to the columns of $B$ proves

For $\begin{pmatrix}B&C\\0&D\end{pmatrix}$ with square block sizes $p,q$, a nonzero Leibniz term must assign all last $q$ rows to the last $q$ columns; otherwise one lower-left entry is zero. Those rows use all those columns, so the first $p$ rows use the first $p$ columns. The remaining permutations are exactly pairs of permutations inside the two blocks, with product sign and product monomial. Summing gives $\det B\det D$, including an empty block using determinant one. This argument also covers terms that vanish for other reasons; it does not require absence of zero divisors.

Let $A_{ij}^{\widehat{\ } }$ delete row $i$ and column $j$, and put $C_{ij}=(-1)^{i+j}\det A_{ij}^{\widehat{\ } }$. Grouping the Leibniz sum by the value $\sigma(i)=j$ gives row cofactor expansion $\det A=\sum_j a_{ij}C_{ij}$. The sign factor follows by moving row $i$ and column $j$ to the first positions, making $i+j-2$ adjacent exchanges; the remaining permutation is on the undeleted indices. Transpose gives the column expansion. Define $\operatorname{adj}(A)_{ji}=C_{ij}$. The $(i,j)$ entry of $A\operatorname{adj}(A)$ is $\sum_k a_{ik}C_{jk}$, the cofactor expansion of the matrix obtained by replacing row $j$ by row $i$. It is $\det A$ if $i=j$, and zero otherwise by repeated-row cancellation. The column argument gives the other product. Therefore

For $n=1$, the empty minor has determinant one, so the adjugate is $[1]$ and the identity still holds. For $n=0$, define the adjugate to be the empty matrix; the identity is the equality of the unique empty matrices, while the determinant remains one. All results in this section apply to $R=F[t]$; no division by a determinant has occurred.

A vector space is a set with addition and scalar multiplication satisfying the usual abelian-group and distributive axioms over a field $F$. Columns are one model. Polynomials of degree at most $d$, denoted $P_d(F)$, and linear maps between spaces are others. The zero polynomial is included in $P_d(F)$ although its degree is not ordinarily defined.

A subspace contains zero and is closed under sums and scalar multiples. A list spans if every vector is a linear combination of its entries; it is independent if only the zero coefficients give zero. A basis is both. A finite spanning list can be reduced to a basis by deleting dependent entries; an independent list can be extended to a basis by adding vectors outside its span until the given finite spanning list is spanned.

Exchange lemma. An independent list of $r$ vectors in the span of $s$ vectors has $r\le s$. To see this, express the first independent vector in the spanning list, use a nonzero coefficient to replace one spanning vector by it, and repeat. At each stage independence ensures the next independent vector has a nonzero coefficient on an as-yet unreplaced spanning vector. There must be at least $r$ such slots. Comparing two bases in both directions proves that their lengths agree; this common length is $\dim V$.

Consequently, in dimension $n$, any $n$ independent vectors form a basis, as do any $n$ spanning vectors. Counting a list is useful only after its independence or spanning has been justified.

A map $T:V\to W$ is linear if $T(\alpha v+\beta u)=\alpha Tv+\beta Tu$. Its kernel and image are subspaces. Choose a basis $k_1,\ldots,k_r$ of $\ker T$ and extend to a basis with $v_1,\ldots,v_s$. Then $Tv_1,\ldots,Tv_s$ form a basis of $\operatorname{im}T$: spanning follows by expanding any input; a dependence among these images places the corresponding input combination in the kernel, and independence of the extended basis makes all coefficients zero. Thus

This is rank–nullity. In equal finite dimensions, injectivity and surjectivity are equivalent, but the equivalence can fail in infinite-dimensional spaces.

The field bridge: singularity and characteristic polynomials

Now let $R=F$ be a field. If $\det A\ne0$, the adjugate identity gives inverse $\operatorname{adj}(A)/\det A$. If $A$ is invertible, multiplicativity gives $\det A\det A^{-1}=1$, so $\det A\ne0$. Rank–nullity, proved in C01, shows a finite square linear map has zero kernel exactly when it is invertible. Thus $\det A=0$ exactly when its kernel is nonzero.

For a fixed $A\in M_n(F)$, apply the ring construction to $tI-A\in M_n(F[t])$. Its determinant is monic of degree $n$: the identity-permutation product contributes $t^n$, whereas every other permutation uses an off-diagonal constant entry, so its product is either zero or has degree less than $n$. Multiplicativity proves invariance under $A\mapsto P^{-1}AP$ with invertible constant $P$; the block-triangular formula proves restriction–quotient factorization. Finally every adjugate entry is zero or has degree at most $n-1$, so their coefficient comparison is legitimate in the C02 Cayley–Hamilton proof. In dimension zero, the characteristic polynomial is the empty determinant one; evaluating it gives $I$ on the zero space, which is its zero operator, so Cayley–Hamilton is separate and immediate. This supplies the actual commutative-ring determinant prerequisites without extending any real-only determinant authority.

For a subspace $U\subseteq V$, define $v\sim w$ when $v-w\in U$. This is an equivalence relation. Its classes are cosets $v+U$, and the quotient $V/U$ has operations

These are well-defined because changing representatives adds elements of $U$. The projection $\pi:V\to V/U$ is linear and surjective, with kernel $U$. If $u_1,\ldots,u_r,v_1,\ldots,v_s$ is an extended basis as above, then $v_1+U,\ldots,v_s+U$ form a quotient basis, proving

A quotient is a space of equivalence classes, not a chosen complementary subspace, though any chosen complement maps isomorphically to it.

Factorization theorem. A linear map $T:V\to W$ descends to a map $\widetilde T:V/U\to W$ satisfying $T=\widetilde T\pi$ exactly when $U\subseteq\ker T$. In that case $\widetilde T(v+U)=Tv$ is well-defined and unique. For $U=\ker T$, this map is injective onto $\operatorname{im}T$, giving the first isomorphism theorem

The formula itself proves all assertions: representatives differ by a vector killed by $T$, and a quotient class maps to zero exactly when its representative lies in the kernel.

The dual $V^*$ consists of linear functions $\varphi:V\to F$. For a basis $b_1,\ldots,b_n$, its dual basis $b^1,\ldots,b^n$ is defined by $b^i(b_j)=\delta_{ij}$. Every functional is uniquely $\sum_i\varphi(b_i)b^i$, so $\dim V^*=n$.

The dual map of $T:V\to W$ is $T^*:W^*\to V^*$, defined by $T^*\psi=\psi\circ T$. In dual bases its matrix is the ordinary transpose $A^{\mathsf T}$, including over $\mathbb C$. There is no complex conjugation: this is algebraic duality, not a Hermitian adjoint. Composition reverses:

This follows by evaluating either side on an arbitrary functional and vector.

For $U\subseteq V$, its annihilator is

An adapted basis shows $\dim U^\circ=\dim V-\dim U$. The quotient's dual identifies naturally with the annihilator: $\eta\mapsto\eta\circ\pi$ is an isomorphism $(V/U)^*\to U^\circ$, because precisely the functionals killing $U$ descend through the quotient.

For a linear map,

The first equality is immediate by evaluation. For the second, inclusion follows because $\psi(Tv)=0$ whenever $Tv=0$. To prove the reverse inclusion, if $\varphi$ kills $\ker T$, define a functional on $\operatorname{im}T$ by $Tv\mapsto\varphi(v)$; it is well-defined, and basis extension extends it to all of $W$. This extended $\psi$ satisfies $T^*\psi=\varphi$. Taking dimensions gives equality of row rank and column rank without choosing a row-reduction algorithm.

Prerequisites

We take the completeness (least-upper-bound) axiom of the real numbers, elementary order and absolute-value inequalities, Euclidean norm properties and basic linear algebra as foundations. Continuity and Fréchet differentiability are understood in their epsilon-delta and linear-remainder definitions. No result here assumes an inverse or implicit function theorem.

Intermediate value theorem

Let $f:[a,b]\to\mathbb R$ be continuous and let $f(a)<y<f(b)$. The set $S=\{x\in[a,b]:f(x)\le y\}$ is nonempty and bounded above. Put $c=\sup S$. Continuity at $a$ and $b$ implies $a<c<b$. If $f(c)<y$, continuity gives a point $c+\delta\le b$ with $f(c+\delta)<y$, contradicting that $c$ is an upper bound. If $f(c)>y$, continuity gives $\delta>0$ such that $f(x)>y$ when $|x-c|<\delta$; but the supremum property gives $x\in S$ with $c-\delta<x\le c$, a contradiction. Thus $f(c)=y$. Equality at an endpoint is immediate, and the decreasing endpoint order follows by replacing $f$ and $y$ with their negatives. This proves existence, not uniqueness.

Scope and prerequisites

Work in finite-dimensional real Euclidean spaces. We use the real intermediate and mean value theorems, completeness, continuity of matrix multiplication and determinants, the chain rule for Fréchet derivatives, and Fermat's stationary-point theorem. These are prerequisites, not proved here. A $C^1$ map is defined on an open set and has continuous derivative. Parameters may have dimension $p=0$; the number of equations is a positive integer $k$, and for local inversion we assume $n\ge1$. All assertions below are local; they do not imply global uniqueness or global invertibility.

One equation

Let $H:U\subset\mathbb R^{p+1}\to\mathbb R$ be $C^1$, $H(a,c)=0$ and $H_t(a,c)\ne0$. After replacing $H$ by $-H$ if necessary, continuity supplies a product box $P\times[c-r,c+r]\subset U$ with $P$ open and $m>0$ such that $H_t\ge m$ there. Reduce $r$ if needed and then shrink $P$ around $a$ so that $H(x,c-r)<0<H(x,c+r)$ for every $x\in P$. This follows from the mean value theorem at $a$ and continuity at both endpoints. The intermediate value theorem gives a zero $t=\phi(x)$ inside the interval, and the mean value theorem gives uniqueness and

At any fixed $x_0\in P$, continuity of $H$ and this estimate yield $|\phi(x)-\phi(x_0)|\le |H(x,\phi(x_0))|/m\to0$. On a sufficiently small convex box around $(x_0,\phi(x_0))$, the $x$-derivative is bounded by $M$; the one-variable mean value theorem along the line segment then gives $|H(x,\phi(x_0))-H(x_0,\phi(x_0))|\le M\|x-x_0\|$. Thus $|\phi(x)-\phi(x_0)|\le(M/m)\|x-x_0\|$ locally. For $h\to0$, write $k=\phi(x_0+h)-\phi(x_0)=O(\|h\|)$. Differentiability of $H$ gives

so $D\phi=-H_t^{-1}D_xH$. Continuity of this expression proves $\phi\in C^1$. The product box provides uniqueness among all zeros in the stated interval, not merely uniqueness of a chosen branch.

Several equations by elimination

Let $G:U\subset\mathbb R^{p+k}\to\mathbb R^k$ be $C^1$, $G(a,c)=0$, with $D_yG(a,c)$ invertible. We prove the local theorem by induction on $k$. For $k=1$ use the preceding argument. For $k>1$, replace $G$ by $A^{-1}G$, where $A=D_yG(a,c)$; this changes neither zeros nor regularity, and its $y$-Jacobian at the base point is $I_k$. Split $y=(t,z)$ with $z\in\mathbb R^{k-1}$. The first equation has nonzero $t$-derivative, so it has a unique local $C^1$ solution $t=\psi(x,z)$. Set $K(x,z)=(G_2,\ldots,G_k)(x,\psi(x,z),z)$ for the normalized system. At the base point, $D_z\psi=-G_{1t}^{-1}G_{1z}=0$, while $D_z(G_2,\ldots,G_k)=I_{k-1}$ and $D_t(G_2,\ldots,G_k)=0$. Hence $D_zK=I_{k-1}$. The induction hypothesis yields a unique local $z=\zeta(x)$; then $y=(\psi(x,\zeta(x)),\zeta(x))$ is the unique solution in a suitably shrunk product neighborhood. The scalar theorem gives an open domain in $(x,z)$; shrink it to $P_x\times Z$, and let its scalar zero interval be $T$. Shrink the induction neighborhood so that $\zeta(P_x)\subset Z$ and $\psi(x,\zeta(x))\in T$ for all $x\in P_x$. Every zero in $P_x\times T\times Z$ satisfies the first equation and hence has $t=\psi(x,z)$; it therefore solves $K=0$, so uniqueness in both elimination steps proves the asserted uniqueness. The chain rule applied to $G(x,\phi(x))=0$ gives

The inverse remains defined on a smaller neighborhood because its determinant is continuous and nonzero at the base point. Its entries are continuous there by the finite algebraic formula $B^{-1}=\operatorname{adj}(B)/\det B$. This proves existence, local uniqueness and $C^1$ regularity; it does not claim uniqueness outside the chosen neighborhood.

Local inverse

Let $F:U\subset\mathbb R^n\to\mathbb R^n$ be $C^1$ and $DF(a)$ invertible. Apply the theorem to $G(y,x)=F(x)-y$ at $(F(a),a)$. There are open neighborhoods $V$ of $F(a)$ and $X$ of $a$ in which for every $y\in V$ there is exactly one $x\in X$ with $F(x)=y$, namely $H(y)$. Put $W=X\cap F^{-1}(V)$; it is open, contains $a$, and $F:W\to V$ is a bijection with $C^1$ inverse $H$. Its derivative is $DH(y)=[DF(H(y))]^{-1}$. This is a local result, even when $DF$ is nonsingular elsewhere.

Regular equality constraints

For a differentiable scalar function on an open subset of $\mathbb R^d$, a local extremum restricts to a local extremum on each coordinate line. The one-variable Fermat theorem makes each coordinate derivative zero; thus its Fréchet derivative is zero. This also covers $d=0$ by the unique zero linear map.

Let $f:U\subset\mathbb R^n\to\mathbb R$ and $g=(g_1,\ldots,g_k):U\to\mathbb R^k$ be $C^1$, where $0\le k\le n$. Suppose $a$ is a local extremum of $f$ subject to $g(x)=g(a)$ and $Dg(a)$ has rank $k$. For $0<k\le n$, choose $k$ independent columns and reorder coordinates as $(u,v)\in\mathbb R^{n-k}\times\mathbb R^k$. The implicit theorem supplies a local graph $v=\phi(u)$ of all feasible points. Fermat and the chain rule give

Define the row vector $\lambda^T=D_v f[D_vg]^{-1}$. Then $D_u f=\lambda^T D_ug$ and $D_v f=\lambda^T D_vg$, so $Df(a)=\lambda^T Dg(a)$, equivalently $\nabla f(a)=\sum_i\lambda_i\nabla g_i(a)$. If $k=n$, $Dg$ is invertible and the same equation follows directly with $\lambda^T=Df[Dg]^{-1}$; the local feasible point is isolated. If $k=0$, the condition is ordinary Fermat $Df(a)=0$ with the empty sum. Rank failure invalidates this proof and the conclusion need not hold; the condition is necessary, not generally sufficient, for an extremum.

Examples and checks

For $x^2+y^2=1$ near $(0,1)$, $g_y=2$, so $y=\sqrt{1-x^2}$ locally and $y'(0)=0$. For $F(s,t)=(s+t^2,t)$, the inverse near the origin is $(u-v^2,v)$ and its derivative there is the identity. For $f=x+y$ on $x^2+y^2=1$, regularity holds on the circle and $(1,1)=\lambda(2x,2y)$ yields candidates $(\pm1/\sqrt2,\pm1/\sqrt2)$ with matching signs. Their values are $\pm\sqrt2$; compactness and continuity establish the global maximum and minimum, a step distinct from the necessary multiplier equation.

Because $\nabla g(a)\ne0$, some coordinate partial derivative of $g$ is nonzero. The implicit function theorem, discussed in the next unit, locally represents the constraint as a graph. Its tangent vectors fill the kernel of the nonzero linear functional $Dg(a)$. At a constrained extremum, differentiating $f$ along every such graph curve gives $Df(a)v=0$ for every $v$ in that kernel. A linear functional vanishing on the kernel of a nonzero functional is its scalar multiple; hence $Df(a)=\lambda Dg(a)$.