Optimization

Y. Eddie Lu, Summer 2026

ECON 8001 course index · Lecture 6 of 8

Orientation

What problem does optimization solve?

An economic model often asks for the best feasible action: a portfolio, production plan, contract, or equilibrium choice. Calculus can characterize an interior candidate, but a candidate need not exist, be feasible, be unique, or be optimal. This page separates the tasks:

1. existence: does an optimum occur in the feasible set?
2. characterization: what must an interior or regular constrained optimum satisfy?
3. classification: do those candidates give local maxima, minima, or neither?
4. global conclusion: what additional structure compares all feasible points?

This page develops Chapter 4, Sections 4.1 through 4.5: existence, unconstrained optimization, equality constraints, KKT conditions for inequalities, and mixed constraints. Convexity and maximum theorems come on later pages. Do not silently import their global conclusions into the local calculus results here.

Where this sits

Optimization uses compactness and continuity from Topology, and derivatives and Hessians from Differentiation. Its curvature tests use the quadratic forms developed in Linear algebra: matrices.

Prerequisite retrieval

For a scalar function \(f:\mathbb R^n\to\mathbb R\), its gradient is a column vector \(\nabla f(x)\in\mathbb R^n\), its derivative is the row \(Df(x)=\nabla f(x)^{\mathsf{T}}\), and its Hessian is an \(n\times n\) matrix \(D^2f(x)\). For a symmetric \(H\), the scalar \(z^{\mathsf{T}}Hz\) measures curvature in direction \(z\in\mathbb R^n\).

Retrieval check. Why cannot \(z^{\mathsf{T}}Hz\) be called a vector?

Show answer

If \(z\) is \(n\times1\) and \(H\) is \(n\times n\), then \((1\times n)(n\times n)(n\times1)\) has dimension \(1\times1\). It is a scalar.

1. Existence: attaining rather than merely approaching a value

Weierstrass extreme-value theorem (Theorem 4.1.1)

Assumptions. \(\varnothing\ne X\subseteq\mathbb R^n\) is compact and \(f:X\to\mathbb R\) is continuous.

Conclusion. There are \(x^{\max},x^{\min}\in X\) such that, for every \(x\in X\),

\[ f(x^{\max})\ge f(x)\ge f(x^{\min}). \]

This is an existence theorem. It makes no uniqueness claim and supplies no formula for an optimizer. In Euclidean space, compactness means closed and bounded.

Show proof

Proof strategy. Continuity on compact \(X\) makes \(f(X)\) bounded: otherwise an unbounded sequence of function values would have inputs with a convergent subsequence, whose images converge and hence are bounded. Thus \(s=\sup f(X)\) is finite. Choose \(x_j\in X\) with \(f(x_j)\to s\). Compactness gives a convergent subsequence \(x_{j_\ell}\to x^{\max}\in X\); continuity gives \(f(x_{j_\ell})\to f(x^{\max})\), hence \(f(x^{\max})=s\). Apply the same argument to \(-f\) for a minimum.

Example: a compact portfolio constraint

Suppose \(M\ge1/\sqrt n\) and \(X=\{w\in\mathbb R^n:\mathbf1^{\mathsf{T}}w=1,\ \|w\|\le M\}\), with \(f\) continuous. The vector \(\mathbf1/n\) belongs to \(X\), so the set is nonempty. The affine equality set is closed, the ball is closed and bounded, so their intersection is compact. A maximum exists. This says nothing yet about how to find it.

Each hypothesis matters

• On \(X=(0,1)\), \(f(x)=x\) is continuous and bounded above, but no maximum is attained because the feasible set misses \(1\).
• On \(X=\mathbb R\), \(f(x)=x\) is continuous but has no maximum because the set is unbounded and the objective can keep rising.
• On \(X=[0,1]\), define \(f(0)=0\) and \(f(x)=1/x\) for \(x>0\). The domain is compact, but \(f\) is not continuous and has no maximum.

Retrieval check: Phase 2 preview. If \(f\) is strictly concave on a compact convex feasible set, what does Weierstrass supply and what does strict concavity add?

Show answer

Weierstrass supplies existence when \(f\) is continuous. Strict concavity can add uniqueness of a maximizer on a convex feasible set, but neither property is part of Theorem 4.1.1 itself.

2. Unconstrained local optimization

Definition 4.2.1: local, strict local, and global optima

Let \(X\subseteq\mathbb R^n\) and \(f:X\to\mathbb R\).

• \(x^*\in X\) is a local maximum if some \(\varepsilon>0\) satisfies \(f(x^*)\ge f(x)\) for every \(x\in X\cap B_\varepsilon(x^*)\).
• It is a strict local maximum if the inequality is strict for every \(x\in X\cap B_\varepsilon(x^*)\setminus\{x^*\}\).
• It is a global maximum if \(f(x^*)\ge f(x)\) for every \(x\in X\).

Replace \(\ge\) by \(\le\) for minima. The feasible set remains part of every definition: local means local within \(X\).

First-order necessary condition (Theorem 4.2.2)

Assumptions. \(X\subseteq\mathbb R^n\) is open, \(f:X\to\mathbb R\) is differentiable at \(x^*\in X\), and \(x^*\) is a local maximum or local minimum.

Conclusion. \(Df(x^*)=0\), equivalently \(\nabla f(x^*)=0\).

Show proof

Proof strategy. For each \(v\in\mathbb R^n\), the one-variable function \(q(t)=f(x^*+tv)\) has a local extremum at \(0\) for small \(t\), because \(X\) is open. Its derivative is \(q'(0)=Df(x^*)v\). At a one-variable local extremum, \(q'(0)=0\). Since this is true for every \(v\), \(Df(x^*)=0\).

The word necessary has direction

At a local optimum in the interior, the necessary condition is

\[ \nabla f(x^*)=0. \]

The converse fails. For \(f(x)=x^3\), \(f'(0)=0\), but values on either side of zero are both larger and smaller than \(f(0)\). A stationary point is a candidate, not a classification.

Definition 4.2.3: stationary point

A point \(x^*\) is stationary when \(Df(x^*)=0\). It need not be an optimum and, if \(X\) is not open, an optimum can occur at a boundary point with nonzero gradient.

Example: a boundary maximum has no zero gradient

On \(X=[0,1]\), maximize \(f(x)=x\). The global maximum is \(x^*=1\), but \(f'(1)=1\). The first-order theorem does not apply because \(1\) is not an interior point of an open feasible domain.

Second-order conditions

Second-order conditions (Theorem 4.2.4)

Assumptions. \(X\subseteq\mathbb R^n\) is open, \(f:X\to\mathbb R\) is \(C^2\), and \(x^*\) is stationary.

Necessary conclusions.

1. A local maximum implies \(D^2f(x^*)\) is negative semidefinite.
2. A local minimum implies \(D^2f(x^*)\) is positive semidefinite.

Sufficient conclusions.

3. If \(D^2f(x^*)\) is negative definite, then \(x^*\) is a strict local maximum.
4. If \(D^2f(x^*)\) is positive definite, then \(x^*\) is a strict local minimum.

The distinction between semidefinite and definite is the distinction between a test that a true optimum must pass and one that proves a strict local result. The semidefinite cases are inconclusive.

Worked calculation: solve the FOC, then use the SOC

Maximize

\[ f(x,y)=6x+4y-x^2-2y^2 \]

over \(\mathbb R^2\).

Step 1: solve the first-order conditions. Because the domain is open, an interior optimum must satisfy

\[ \begin{aligned} \frac{\partial f}{\partial x}&=6-2x=0,\\ \frac{\partial f}{\partial y}&=4-4y=0. \end{aligned} \]

Hence the only stationary point is

\[ (x^*,y^*)=(3,1). \]

Step 2: classify the candidate with the Hessian. We have

\[ D^2f(x,y)= \begin{pmatrix} -2&0\\ 0&-4 \end{pmatrix}. \]

For every nonzero direction \(z=(z_1,z_2)^{\mathsf{T}}\),

\[ z^{\mathsf{T}}D^2f(x,y)z=-2z_1^2-4z_2^2<0. \]

The Hessian is negative definite, so \((3,1)\) is a strict local maximum.

Step 3: check the result independently. Completing squares gives

\[ f(x,y)=11-(x-3)^2-2(y-1)^2\le11. \]

Equality holds only at \((3,1)\). Thus the same point is the unique global maximum. The FOC found the candidate; the SOC classified it; completing squares established the global claim.

Examples: strict curvature and a flat test

• \(f(x,y)=-x^2-2y^2\) has Hessian \(\operatorname{diag}(-2,-4)\), negative definite at \((0,0)\), so \((0,0)\) is a strict local maximum.
• \(f(x)=x^4\) has \(f'(0)=0\) and \(f''(0)=0\), yet \(0\) is a strict local minimum.
• \(f(x)=-x^4\) has the same zero second derivative at \(0\), yet it is a strict local maximum.

Thus a zero or merely semidefinite Hessian does not classify a stationary point.

For a \(C^2\) scalar objective, Taylor’s expansion near a stationary point is

\[ \begin{aligned} f(x^*+h) &=f(x^*)\\ &\quad+\frac12h^{\mathsf{T}}D^2f(x^*)h\\ &\quad+o(\|h\|^2). \end{aligned} \]

The sign of this quadratic form gives the proof idea for the sufficient parts. Negative definiteness makes the leading nonzero change negative in every direction; positive definiteness reverses the sign.

3. Equality constraints and regularity

Let \(g=(g_1,\ldots,g_k)^{\mathsf{T}}:\mathbb R^n\to\mathbb R^k\) and let \(c\in\mathbb R^k\). The equality-constrained feasible set is

\[C=U\cap\{x\in\mathbb R^n:g(x)=c\},\]

where \(U\subseteq\mathbb R^n\) is open. Its geometry, near a regular point, is governed by the \(k\times n\) Jacobian \(Dg(x)\).

Constraint qualification: full row rank

The equality constraints satisfy the regularity condition at \(x^*\) when

\[\operatorname{rank}Dg(x^*)=k.\]

Thus \(k\le n\), the \(k\) constraint gradients are linearly independent, and \(Dg(x^*)\) has full row rank. This condition allows the feasible set to have a well-defined tangent space of dimension \(n-k\). If the rank condition fails, the point is singular and must be checked directly; the multiplier equations need not hold there.

Lagrange multiplier theorem (Theorem 4.3.1)

Let \(f:\mathbb R^n\to\mathbb R\) and \(g_i:\mathbb R^n\to\mathbb R\) be \(C^1\).

Assumptions. \(x^*\) is a local maximum or minimum of \(f\) on \(C\) and \(\operatorname{rank}Dg(x^*)=k\).

Conclusion. There is \(\lambda^*\in\mathbb R^k\) such that

\[ Df(x^*)=\lambda^{*\mathsf T}Dg(x^*). \tag{L} \]

Equivalently, in gradient form,

\[ \nabla f(x^*)=Dg(x^*)^{\mathsf{T}}\lambda^*. \]

In (L), the left side is \(1\times n\). Since \(\lambda^{*\mathsf T}\) is \(1\times k\) and \(Dg\) is \(k\times n\), the product is conformable. In gradient form \(Dg^{\mathsf{T}}\lambda^*\) is \(n\times1\).

Every feasible first-order displacement \(z\) satisfies \(Dg(x^*)z=0\). At an optimum, the objective’s gradient must have zero inner product with every such \(z\). Linear algebra then says it lies in the row space of \(Dg(x^*)\), namely the span of the constraint gradients. The multipliers give its coordinates in that span.

A multiplier can fail when regularity fails

Minimize \(f(x)=x\) subject to \(g(x)=x^2=0\). The only feasible point is \(0\), so it is both a constrained maximum and minimum. But \(Dg(0)=0\), and the equation \(Df(0)=\lambda Dg(0)\) would read \(1=0\). The rank condition is not decoration.

The Lagrangian and candidate equations

Choose the convention

\[ L(x;\lambda)=f(x)-\lambda^{\mathsf{T}}(g(x)-c). \]

Then (L) and feasibility become the system

\[ \begin{aligned} D_xL(x;\lambda)&=0,\\ g(x)&=c. \end{aligned} \]

The sign convention is arbitrary if used consistently. It changes the sign of \(\lambda\), not the set of candidate \(x\) values.

Example: maximum on a circle

Maximize \(f(x_1,x_2)=x_1+x_2\) subject to \(g(x)=x_1^2+x_2^2=1\). With \(L=x_1+x_2-\lambda(x_1^2+x_2^2-1)\), the equations are

\[ \begin{aligned} 1-2\lambda x_1&=0,\\ 1-2\lambda x_2&=0,\\ x_1^2+x_2^2&=1. \end{aligned} \]

They give \((x_1,x_2)=\pm(1,1)/\sqrt2\). Comparing objective values identifies the positive point as the global maximum and the negative point as the global minimum. The multiplier equations alone identify candidates, not which one wins.

Retrieval check. In the circle example, why is the gradient of \(f\) not required to be zero at the constrained optimum?

Show answer

Feasible moves are restricted to the circle. The correct condition is that \(\nabla f\) lies in the span of \(\nabla g\), not that it vanishes. A nonzero gradient can point normal to the feasible curve.

4. Tangent spaces and constrained curvature

Definition: tangent vectors and tangent space

A tangent vector at a feasible point \(x^*\) is a velocity \(z=\gamma'(0)\) of a differentiable feasible curve \(\gamma\) with \(\gamma(0)=x^*\). At a regular feasible point, define

\[ T(x^*)=\{z\in\mathbb R^n:Dg(x^*)z=0\}. \]

It is the kernel of the \(k\times n\) Jacobian \(Dg(x^*)\).

Regular-level tangent theorem

If \(g\) is \(C^1\) near \(x^*\), \(g(x^*)=c\), and \(\operatorname{rank}Dg(x^*)=k\), then the nearby level set \(\{x:g(x)=c\}\) is a \(C^1\) manifold of dimension \(n-k\) and its tangent space is \(\ker Dg(x^*)\). Thus every feasible curve velocity lies in \(T(x^*)\), and every \(z\in T(x^*)\) is the velocity of some local feasible curve.

For the unit circle \(g(x)=x_1^2+x_2^2\), at \(x^*\) we have

\[ Dg(x^*)=2(x_1^*,x_2^*). \]

The tangent space is

\[ T(x^*)={z:x_1^*z_1+x_2^*z_2=0\}. \]

The tangent space is one-dimensional. One nonzero tangent vector spans it, which is why checking that vector and its scalar multiples is enough on a circle. This shortcut fails when \(\dim T(x^*)>1\).

Equality-constrained second-order conditions (Theorem 4.3.4)

Let \(f,g_1,\ldots,g_k\) be \(C^2\). Suppose \((x^*,\lambda^*)\) satisfies feasibility, the Lagrange first-order condition, and \(\operatorname{rank}Dg(x^*)=k\). Let \(L\) be the Lagrangian above.

Necessary conclusions.

1. A constrained local maximum at \(x^*\) implies \(z^{\mathsf{T}}D^2_{xx}L(x^*;\lambda^*)z\le0\) for every \(z\in T(x^*)\).
2. A constrained local minimum implies the same quadratic form is at least zero for every \(z\in T(x^*)\).

Sufficient conclusions.

3. If the quadratic form is strictly negative for every nonzero \(z\in T(x^*)\), then \(x^*\) is a strict constrained local maximum.
4. If it is strictly positive for every nonzero \(z\in T(x^*)\), then \(x^*\) is a strict constrained local minimum.

All curvature claims are restricted to \(T(x^*)\). Curvature in a direction that violates the constraints says nothing about nearby feasible values.

Necessary versus sufficient: do not reverse the arrows

A constrained local maximum implies

\[ Q(z)\le0 \quad\text{for every }z\in T(x^*). \]

In the other direction, if

\[ Q(z)<0 \quad\text{for every nonzero }z\in T(x^*), \]

then the point is a strict constrained local maximum.

where \(Q(z)=z^{\mathsf{T}}D^2_{xx}L(x^*;\lambda^*)z\). A merely nonpositive quadratic form is necessary but generally not sufficient.

A concrete constrained curvature calculation

Consider \(f(x_1,x_2)=x_1^2+2x_2^2\) on the unit circle. At a stationary point \(x^*=(1,0)\), use \(L=f-\lambda(x_1^2+x_2^2-1)\). The first-order condition gives \(\lambda^*=1\), hence

\[D^2_{xx}L(x^*;\lambda^*)= \begin{pmatrix}0&0\\0&2\end{pmatrix}.\]

The tangent space is \(T(x^*)=\{(0,t)^{\mathsf{T}}:t\in\mathbb R\}\). For a nonzero tangent vector \(z=(0,t)^{\mathsf{T}}\),

\[z^{\mathsf{T}}D^2_{xx}Lz=2t^2>0.\]

Therefore \((1,0)\) is a strict constrained local minimum. The ambient Hessian of \(f\) is positive definite too, but that fact is not the method: the theorem asks for the Lagrangian Hessian on feasible directions.

Testing one direction is not enough in a higher-dimensional tangent space

Suppose \(T(x^*)\subseteq\mathbb R^3\) has dimension two. Finding one tangent direction \(v\) with \(Q(v)<0\) does not prove a constrained local maximum: another independent tangent direction may have \(Q(w)>0\). To show a constrained saddle, exhibit one feasible tangent direction of each sign. To prove strict curvature, establish the sign for all nonzero tangent directions.

5. Inequality constraints and KKT conditions

Why an inequality needs a new multiplier rule

Consider

\[ \begin{aligned} &\max_{x_1,x_2} &&-(x_1-2)^2-(x_2-2)^2\\ &\text{s.t.} &&x_1+x_2\le2. \end{aligned} \]

The unconstrained maximizer \((2,2)\) is infeasible. The constrained maximizer is \((1,1)\), where the gradient is \((2,2)^{\mathsf{T}}\), not zero. It points in the normal direction to the binding boundary. A nonnegative multiplier records how strongly that boundary restrains the objective.

Definition: active constraint and slack

Let \(h=(h_1,\ldots,h_l):\mathbb R^n\to\mathbb R^l\) and impose \(h(x)\le c\) componentwise.

For a feasible point \(x^*\):

1. the slack of constraint \(i\) is \(c_i-h_i(x^*)\ge0\);

2. constraint \(i\) is active when \(h_i(x^*)=c_i\);

3. the active set is

   \[ A(x^*)=\{i:h_i(x^*)=c_i\}. \]

Complementary slackness pairs pressure with scarcity

An inactive constraint leaves room for a small move, so its multiplier must be zero. A positive multiplier can occur only when the constraint binds. The product of multiplier and slack encodes both cases in one equation.

KKT sign dictionary for maximization

The convention on this page is:

• maximize \(f(x)\);

• write every inequality as \(h_i(x)\le c_i\);

• use

  \[ L(x;\lambda) =f(x)-\sum_i\lambda_i\bigl(h_i(x)-c_i\bigr); \]

• require \(\lambda_i\ge0\).

Stationarity then reads

\[ \nabla f(x^*) =\sum_i\lambda_i^*\nabla h_i(x^*). \]

The multiplier is nonnegative because the objective gradient at a constrained maximum is a nonnegative combination of the outward normals \(\nabla h_i(x^*)\).

Two common translations are:

1. A lower bound \(q(x)\ge b\) becomes \(-q(x)\le-b\). Its Lagrangian term is \(+\lambda[q(x)-b]\).

2. For a minimization problem with \(h_i(x)\le c_i\), the usual convention is \(L_{\min}=f+\sum_i\lambda_i(h_i-c_i)\) with \(\lambda_i\ge0\). In fact,

   \[ L_{\min}(f,\lambda) =-L_{\max}(-f,\lambda). \]

   The Hessian sign test reverses as well: a strict local minimum requires positive curvature on the relevant directions.

Do not memorize a multiplier sign without the objective direction, inequality direction, and displayed Lagrangian. Those three choices determine the sign.

KKT necessary conditions for inequalities (Theorem 4.4.1)

Assumptions. Let \(f:\mathbb R^n\to\mathbb R\) and \(h_i:\mathbb R^n\to\mathbb R\) be \(C^1\). Suppose \(x^*\) is a local maximizer of \(f\) on

\[ F=\{x\in\mathbb R^n:h(x)\le c\}. \]

Assume the gradients of the active constraints are linearly independent:

\[ \operatorname{rank}Dh_{A(x^*)}(x^*)=|A(x^*)|. \]

Conclusion. There is \(\lambda^*\in\mathbb R^l\) such that:

1. primal feasibility

   \[ h(x^*)\le c; \]

2. stationarity

   \[ Df(x^*)=\lambda^{*\mathsf{T}}Dh(x^*); \]

3. dual feasibility, for \(i=1,\ldots,l\),

   \[ \lambda_i^*\ge0; \]

4. complementary slackness, for \(i=1,\ldots,l\),

   \[ \lambda_i^*\bigl[c_i-h_i(x^*)\bigr]=0. \]

The rank condition is the linear independence constraint qualification, or LICQ. It is a condition on the active gradients only. Inactive constraints do not define the local boundary at \(x^*\).

Show proof strategy

The feasible first-order directions form a cone cut out by the active gradients. At a local maximum, no feasible direction can have a positive directional derivative. A finite-dimensional separation result represents \(Df(x^*)\) as a nonnegative combination of the active constraint gradients. Assign multiplier zero to every inactive constraint. This gives stationarity, dual feasibility, and complementary slackness.

The separation step is the inequality analogue of the normal-space argument behind equality-constrained multipliers.

Worked calculation: solve KKT by active-set cases

Consider

\[ \begin{aligned} &\max_{x,y} &&-(x-2)^2-y^2\\ &\text{s.t.} &&x\le1,\\ &&&y\le2. \end{aligned} \]

Both constraints already have the form \(h_i\le c_i\). With multipliers \(\lambda_1,\lambda_2\ge0\), use

\[ \begin{aligned} L(x,y;\lambda_1,\lambda_2) &=-(x-2)^2-y^2\\ &\quad-\lambda_1(x-1)\\ &\quad-\lambda_2(y-2). \end{aligned} \]

The KKT conditions are:

1. Stationarity

   \[ \begin{aligned} -2(x-2)-\lambda_1&=0,\\ -2y-\lambda_2&=0. \end{aligned} \]

2. Primal feasibility: \(x\le1\) and \(y\le2\).

3. Dual feasibility: \(\lambda_1\ge0\) and \(\lambda_2\ge0\).

4. Complementary slackness: \(\lambda_1(1-x)=0\) and \(\lambda_2(2-y)=0\).

Now solve the cases without guessing:

• If \(y=2\) were active, stationarity would give \(\lambda_2=-4\), violating dual feasibility. Therefore it is inactive. Complementary slackness gives \(\lambda_2=0\), and stationarity gives \(y=0\).
• If \(x<1\) were inactive, then \(\lambda_1=0\) and stationarity would give \(x=2\), violating primal feasibility. Therefore it is active: \(x=1\), and stationarity gives \(\lambda_1=2\).

The only KKT point is

\[ (x^*,y^*;\lambda_1^*,\lambda_2^*)=(1,0;2,0). \]

The active set is \(A(x^*)=\{1\}\). Since \(\nabla h_1=(1,0)^{\mathsf{T}}\ne0\), the active-gradient matrix has rank one, so LICQ holds.

Substitution verifies zero stationarity residuals, primal feasibility, nonnegative multipliers, and both complementary-slackness products. The binding \(x\) constraint has a positive multiplier; the slack \(y\) constraint has multiplier zero.

KKT conditions are necessary here, not automatically sufficient

Theorem 4.4.1 says that every regular local maximum satisfies the KKT conditions.

A KKT point can fail to maximize a nonconcave objective. Global concavity and convex feasibility can turn KKT conditions into a global certificate, but that is a separate result.

Minimization sign convention

To minimize \(f\) under \(h(x)\le c\), apply the maximization theorem to \(-f\). With the Lagrangian convention used here, this changes the sign of the objective term. Do not change the sign of a multiplier condition by memory; write the chosen Lagrangian first and differentiate it.

Second-order conditions and the critical cone

Let

\[ L(x;\lambda)=f(x)-\lambda^{\mathsf{T}}(h(x)-c). \]

Among the active constraints, define the strongly active set

\[ B(x^*,\lambda^*)=\{i\in A(x^*):\lambda_i^*>0\}. \]

Definition: critical cone

Using the usual feasible-direction convention for \(h(x)\le c\), \(C(x^*,\lambda^*)\) is the set of \(z\in\mathbb R^n\) satisfying:

1. \(Dh_i(x^*)z=0\) for \(i\in B(x^*,\lambda^*)\).
2. \(Dh_i(x^*)z\le0\) for \(i\in A(x^*)\setminus B(x^*,\lambda^*)\).

Strongly active constraints must remain tangent in a critical direction. A weakly active constraint, whose multiplier is zero, may move into its feasible side.

Stationarity makes every critical direction neutral to first order:

\[ \begin{aligned} Df(x^*)z &=\sum_i\lambda_i^*Dh_i(x^*)z\\ &=0. \end{aligned} \]

For strongly active constraints, \(Dh_i(x^*)z=0\). Every other multiplier is zero, so no term remains in the sum.

Sign convention in the Section 4.4 slides

The slides write \(Dh_i(x^*)z\ge0\) for weakly active constraints. Their \(z\) is the negative of the standard feasible direction used above. The two cones are negatives of each other, and

\[ (-z)^{\mathsf{T}}D_{xx}^2L(-z) =z^{\mathsf{T}}D_{xx}^2Lz. \]

Therefore the second-order sign test is identical under either convention.

Inequality-constrained second-order conditions (Theorem 4.4.5)

Assumptions. The functions \(f,h_1,\ldots,h_l\) are \(C^2\), \((x^*,\lambda^*)\) satisfies KKT, and LICQ holds at \(x^*\).

Necessary conclusion. If \(x^*\) is a constrained local maximum, then, for every \(z\in C(x^*,\lambda^*)\),

\[ z^{\mathsf{T}}D_{xx}^2L(x^*;\lambda^*)z\le0. \]

Sufficient conclusion. If, for every nonzero \(z\in C(x^*,\lambda^*)\),

\[ z^{\mathsf{T}}D_{xx}^2L(x^*;\lambda^*)z<0, \]

then \(x^*\) is a strict constrained local maximum.

The critical cone replaces the equality-constrained tangent space. It keeps only directions that are feasible to first order and neutral with respect to the first-order objective change.

Worked calculation: SOC on the KKT critical cone

Continue the preceding KKT example. Only the first constraint is active, and \(\lambda_1^*=2>0\). Thus it is strongly active. A critical direction \(z=(z_1,z_2)^{\mathsf{T}}\) must satisfy

\[ z_1=0. \]

Hence

\[ C(x^*,\lambda^*) =\{(0,t)^{\mathsf{T}}:t\in\mathbb R\}. \]

The constraints are linear, so they add no curvature to the Lagrangian:

\[ D^2_{xx}L(x^*;\lambda^*)=-2I_2. \]

For every nonzero critical direction \(z=(0,t)^{\mathsf{T}}\),

\[ z^{\mathsf{T}}D^2_{xx}Lz=-2t^2<0. \]

The strict inequality-constrained SOC therefore proves that \((1,0)\) is a strict constrained local maximum.

As a global check, \(x\le1\) makes \(x=1\) the feasible point closest to \(2\), and \(y=0\) maximizes \(-y^2\) while satisfying \(y\le2\). Thus \((1,0)\) is also the unique global maximum. The SOC itself gives only the strict local conclusion.

Retrieval check. Why does an inactive constraint have multiplier zero?

Show answer

Its slack is positive. Complementary slackness requires \(\lambda_i^*[c_i-h_i(x^*)]=0\), so the multiplier must be zero.

6. Mixed equality and inequality constraints

Consider

\[ \begin{aligned} &\max_x && f(x)\\ &\text{s.t.}&& g(x)=b,\\ &&&h(x)\le c. \end{aligned} \]

where \(g:\mathbb R^n\to\mathbb R^k\) and \(h:\mathbb R^n\to\mathbb R^l\).

Use separate multipliers:

\[ \begin{aligned} L(x;\mu,\lambda) &=f(x)-\mu^{\mathsf{T}}(g(x)-b)\\ &\quad-\lambda^{\mathsf{T}}(h(x)-c). \end{aligned} \]

The equality multiplier \(\mu\in\mathbb R^k\) is unrestricted in sign. The inequality multiplier \(\lambda\in\mathbb R^l\) must be nonnegative.

KKT necessary conditions for mixed constraints (Theorem 4.5.1)

Assumptions. The objective and constraints are \(C^1\), \(x^*\) is a local maximum, and the gradients of all equality constraints together with the active inequality constraints are linearly independent.

Conclusion. There are \(\mu^*\in\mathbb R^k\) and \(\lambda^*\in\mathbb R^l\) such that:

1. \(g(x^*)=b\) and \(h(x^*)\le c\);
2. \(D_xL(x^*;\mu^*,\lambda^*)=0\);
3. \(\lambda_i^*\ge0\) for every inequality constraint;
4. \(\lambda_i^*[c_i-h_i(x^*)]=0\) for every inequality constraint.

Equality constraints are always active. Inequality constraints enter the local normal space only when they bind.

Mixed-constraint second-order conditions (Theorem 4.5.2)

Define the critical cone by requiring

1. \(Dg(x^*)z=0\) for every equality constraint;
2. \(Dh_i(x^*)z=0\) for each active inequality with \(\lambda_i^*>0\);
3. \(Dh_i(x^*)z\le0\) for each active inequality with \(\lambda_i^*=0\).

Under \(C^2\) smoothness, KKT, and LICQ:

• a local maximum requires \(z^{\mathsf{T}}D_{xx}^2Lz\le0\) for every critical direction;
• strict negativity for every nonzero critical direction is sufficient for a strict local maximum.

One cone combines both kinds of local restriction

Equality constraints remove directions in both signs, so they impose tangent equalities. A binding inequality removes only the direction that exits the feasible set. Complementary slackness determines whether that one-sided restriction matters to the first-order objective.

KKT calculation blueprint

1. Put every inequality in one declared direction, here \(h_i(x)\le c_i\).
2. Check primal feasibility and identify the active set.
3. Check LICQ using the equality and active-inequality gradients.
4. Write the Lagrangian and its sign convention.
5. Solve stationarity, dual feasibility, and complementary slackness together.
6. Discard candidates that violate primal or dual feasibility.
7. For a second-order claim, construct the critical cone and test the Lagrangian Hessian only on that cone.
8. State whether the condition used is necessary or sufficient.

Do not guess which inequalities bind

An inequality may be active with a zero multiplier, active with a positive multiplier, or inactive with a zero multiplier. Solve cases systematically and check every candidate against all KKT conditions.

Assumption audit

1. Existence: compact \(X\) and continuous \(f\) imply that maxima and minima are attained.
2. Interior first-order condition: an open domain and differentiability imply a zero gradient at an unconstrained local optimum.
3. Equality multiplier condition: \(C^1\) constraints and full row rank give a Lagrange multiplier at a regular local constrained optimum.
4. KKT condition: \(C^1\) constraints and LICQ give stationarity, dual feasibility, and complementary slackness at a regular local optimum.
5. Necessary constrained curvature: \(C^2\) smoothness, KKT, and LICQ imply a semidefinite sign on the tangent space or critical cone.
6. Sufficient constrained curvature: a strict sign on every nonzero tangent or critical direction gives a strict local result.

Do not treat these rows as interchangeable. Weierstrass does not yield first order conditions at a boundary. Lagrange conditions do not establish existence. A stationary point and semidefinite Hessian do not classify an optimum.

Calculation blueprints

Unconstrained problem

1. State the domain and whether the question is local or global.
2. For an interior candidate, solve \(\nabla f(x)=0\).
3. Compute the Hessian and test definiteness at each candidate.
4. If a global claim is needed, separately establish existence and compare candidates or bring in an appropriate global theorem.

Equality-constrained problem

1. Write \(g(x)=c\) with \(g:\mathbb R^n\to\mathbb R^k\) and check dimensions.
2. Check feasibility and \(\operatorname{rank}Dg(x)=k\) at each candidate. If rank fails, treat that singular point directly rather than applying the multiplier equations.
3. Form \(L(x;\lambda)=f(x)-\lambda^{\mathsf{T}}(g(x)-c)\).
4. Solve \(D_xL=0\) and \(g(x)=c\) at regular candidates.
5. Find \(T(x^*)=\ker Dg(x^*)\).
6. Evaluate the scalar quadratic form \(z^{\mathsf{T}}D^2_{xx}L(x^*;\lambda^*)z\) for every tangent direction.
7. State the theorem part used and its implication direction.

Inequality or mixed-constraint problem

1. Standardize the inequality directions and write the Lagrangian convention.
2. Identify active constraints and check LICQ.
3. Solve primal feasibility, stationarity, dual feasibility, and complementary slackness together.
4. Build the critical cone at each surviving candidate.
5. Test the Lagrangian Hessian on that cone.
6. State the exact necessary or sufficient result used.

Exit tickets

1. Give one example where an objective has a finite supremum but no maximum. Name the failed existence hypothesis.
2. For \(f(x,y)=x^2-y^2\), classify the stationary point at \((0,0)\).
3. With one equality constraint in \(\mathbb R^3\), what dimension should the regular tangent space have?
4. In a constrained problem, why is a positive curvature direction outside \(T(x^*)\) irrelevant to the second-order theorem?
5. For a maximization problem with \(h_i(x)\le c_i\), what sign must the KKT multiplier have, and when must it equal zero?

Show answer

1. \(f(x)=x\) on \((0,1)\) has supremum \(1\) but no maximum; compactness fails.
2. The Hessian \(\operatorname{diag}(2,-2)\) is indefinite, so \((0,0)\) is a saddle, not a local optimum. 3. It has dimension \(3-1=2\). 4. It is not the velocity of a feasible curve to first order, so the theorem does not compare nearby feasible objective values in that direction. 5. The multiplier is nonnegative, and complementary slackness forces it to zero whenever the constraint is inactive.

Mastery checklist

• I can distinguish existence, a first-order characterization, and a sufficient local classification.
• I can state every compactness and continuity hypothesis in Weierstrass.
• I know why an unconstrained FOC needs an open domain.
• I can state the direction of each unconstrained SOC implication.
• I can form a Lagrangian with conformable dimensions.
• I can compute a tangent space and restrict the Lagrangian Hessian to it.
• I know why one tangent direction is insufficient unless the tangent space is one-dimensional.
• I can distinguish primal feasibility, dual feasibility, stationarity, and complementary slackness.
• I can identify an active set and construct the KKT critical cone.
• I can state the KKT and second-order implication directions for pure inequality and mixed constraints.