Classical Optimization: Unconstrained Problems
Strip away the constraints and optimization becomes pure calculus. At the bottom of a valley the ground is level — so the first thing to look for is where the slope vanishes. This chapter turns that instinct into method: find the stationary points where the gradient is zero, then read the curvature — the second derivative in one dimension, the Hessian in many — to sort the minima from the maxima and the saddles. It is the analytical backbone every numerical method in Part 5 quietly relies on.
- The first-order necessary condition \(\nabla f(x^\star) = 0\), and what a stationary point is.
- The second-order conditions that classify a stationary point as a minimum, maximum, or saddle.
- How to solve the single-variable case with \(f'=0\) and the second-derivative (and higher-order) test.
- How to solve the multivariable case with \(\nabla f = 0\) and the Hessian.
- Testing a Hessian for definiteness — via eigenvalues and via Sylvester's leading-principal-minor criterion.
- Why, for a convex \(f\), any stationary point is automatically the global minimum.
The Unconstrained Problem
The simplest optimization problem has no constraints at all — we are free to roam the whole space:
This looks special, but it is the foundation of everything. Many real problems are unconstrained — fitting a curve to data by least squares, tuning parameters to minimize an error. Many others become unconstrained after the constraints are folded in with Lagrange multipliers (Chapter 5) or after substitution. And every numerical algorithm in Part 5, however sophisticated, is ultimately hunting for the same thing this chapter defines with calculus: a point where the function stops decreasing.
The geometric intuition is decisive. At the lowest point of a smooth valley the tangent plane is horizontal — the slope in every direction is zero. Reverse it: wherever the function is genuinely at a local minimum (or maximum), its slope must vanish. That single observation is the first-order condition.
The First-Order Necessary Condition
A point where the gradient is zero is called a stationary (or critical) point. Every interior local minimum or maximum of a differentiable function is stationary — so stationarity is a necessary condition we screen candidates with.
In one variable this is simply \(f'(x^\star) = 0\). Solving it gives the candidate points; it does not yet tell you which are minima. A saddle and an inflection are stationary too, so a second test is always needed.
Second-Order Conditions
Curvature decides the type. At a stationary point, if the function curves upward in every direction it is a minimum; downward in every direction, a maximum; up in some and down in others, a saddle point. Curvature is measured by the second derivative in 1-D and by the Hessian matrix \(\nabla^2 f\) in \(n\)-D.
| At a stationary point | 1-D test | \(n\)-D test | Type |
|---|---|---|---|
| curves up everywhere | \(f'' > 0\) | \(\nabla^2 f \succ 0\) (PD) | Local minimum |
| curves down everywhere | \(f'' < 0\) | \(\nabla^2 f \prec 0\) (ND) | Local maximum |
| up in some, down in others | — | \(\nabla^2 f\) indefinite | Saddle point |
| flat to second order | \(f'' = 0\) | \(\nabla^2 f\) semidefinite (singular) | Inconclusive |
The Single-Variable Case
For \(f(x)\) of one variable, the recipe is short: solve \(f'(x) = 0\) for the stationary points, then classify each with \(f''\). When \(f''(x^\star) = 0\) the test is silent, and we fall back on the higher-order test: examine successive derivatives until one is non-zero.
If \(k\) is even and \(f^{(k)} > 0\), it is a local minimum; if \(k\) even and \(f^{(k)} < 0\), a local maximum. If \(k\) is odd, it is an inflection (not an extremum). Example: \(f(x)=x^4\) has \(f'=f''=f'''=0\) at \(0\) but \(f^{(4)}=24>0\) — a minimum.
The Multivariable Case
For \(f(x_1,\dots,x_n)\), set the gradient to zero — that is a system of \(n\) equations in \(n\) unknowns — to find the stationary points, then evaluate the Hessian at each and test its definiteness. Geometrically, the gradient points in the direction of steepest increase, so at a minimum it must be the zero vector: there is no uphill direction left to point in.
Testing a Hessian for Definiteness
Everything hinges on the sign character of the Hessian. Two practical tests decide it. The eigenvalue test: all eigenvalues positive ⇒ positive definite (min); all negative ⇒ negative definite (max); mixed signs ⇒ indefinite (saddle). Sylvester's criterion avoids eigenvalues by checking the leading principal minors \(D_1, D_2, \dots\): the matrix is positive definite iff every \(D_k > 0\).
| \(\det H = ac - b^2\) | \(a\) | Conclusion |
|---|---|---|
| \(> 0\) | \(> 0\) | Positive definite → local minimum |
| \(> 0\) | \(< 0\) | Negative definite → local maximum |
| \(< 0\) | any | Indefinite → saddle point |
| \(= 0\) | any | Semidefinite → test inconclusive |
Convexity and Global Optima
The second-order test certifies a local optimum. Chapter 3 supplies the bridge to a global one. If \(f\) is convex, its first-order condition of convexity says \(f(y) \ge f(x^\star) + \nabla f(x^\star)^{\mathsf T}(y - x^\star)\); at a stationary point the gradient term is zero, so \(f(y) \ge f(x^\star)\) for all \(y\). The stationary point is the global minimum, no comparison of candidates required.
This is why the classical method is not merely a screening step for convex problems — it is the complete answer. Solve \(\nabla f = 0\), confirm convexity (Hessian PSD everywhere), and you are done. For non-convex \(f\), you must find all stationary points and compare their values.
Worked Examples
Problem. Find and classify the stationary points of \(f(x) = x^3 - 3x\).
Solution. \(f'(x) = 3x^2 - 3 = 0 \Rightarrow x = \pm 1\). The curvature is \(f''(x) = 6x\).
Neither is global: as \(x \to \pm\infty\), \(f \to \pm\infty\), so the function is unbounded. This is the hallmark of a non-convex problem — a local minimum that is not the end of the story.
Problem. Classify the stationary point of \(f(x) = x^4\).
Solution. \(f'(x) = 4x^3 = 0 \Rightarrow x = 0\), but \(f''(0) = 12x^2\big|_0 = 0\) — inconclusive. Apply the higher-order test: \(f'''(0) = 0\) and \(f^{(4)}(0) = 24 > 0\). The first non-zero derivative is of order \(4\) (even, positive), so \(x = 0\) is a local (indeed global) minimum.
Problem. Minimize \(f(x,y) = x^2 + y^2 - 4x - 6y + 13\).
Solution. Set the gradient to zero:
The Hessian is positive definite (and constant), so \(f\) is convex — \((2,3)\) is the global minimum, with \(f(2,3) = 0\).
Problem. Classify the stationary point of \(f(x,y) = x^2 - y^2\).
Solution. \(\nabla f = (2x, -2y) = 0 \Rightarrow (0,0)\). The Hessian is \(\mathrm{diag}(2, -2)\), with \(\det H = -4 < 0\): indefinite. So \((0,0)\) is a saddle — a minimum along the \(x\)-axis but a maximum along the \(y\)-axis, and no extremum at all.
Problem. Minimize \(f(x,y) = x^2 + xy + y^2 - 3x\).
Solution. \(\nabla f = (2x + y - 3,\ x + 2y) = 0\). From the second equation \(x = -2y\); substituting, \(2(-2y) + y - 3 = 0 \Rightarrow y = -1,\ x = 2\). The Hessian is
Both leading minors are positive, so \(H\) is positive definite and \((2, -1)\) is a (global, since \(f\) is convex) minimum with \(f = 4 + 1 \cdot(-2\cdot? )\)… evaluating, \(f(2,-1) = 4 - 2 + 1 - 6 = -3\).
Problem. Profit from two ad channels is \(P(x,y) = 40x + 50y - x^2 - y^2 - xy\) (₹ thousands). Find the spend that maximizes it.
Solution. \(\nabla P = (40 - 2x - y,\ 50 - 2y - x) = 0\) gives \(2x + y = 40\) and \(x + 2y = 50\); solving, \(x = 10,\ y = 20\). The Hessian is
So the maximum profit is at \((10, 20)\), giving \(P = 400 + 1000 - 100 - 400 - 200 = 700\) (i.e. ₹7 lakh). Negative definiteness confirms it is a genuine peak, not a saddle.
Chapter Summary
Screen candidates with the first-order condition \(\nabla f(x^\star) = 0\) (in 1-D, \(f'=0\)).
\(f'' > 0\) or \(\nabla^2 f \succ 0\) → min; \(< 0\) or \(\prec 0\) → max; indefinite → saddle.
If \(f''=0\), the first non-zero derivative decides: even & positive → min, even & negative → max, odd → inflection.
Eigenvalue signs, or Sylvester's minors. For 2×2: \(\det H > 0,\ a > 0\) → min; \(\det H < 0\) → saddle.
If \(f\) is convex, a stationary point is the global minimum — no candidate comparison needed.
Find all stationary points and compare values; watch for unboundedness.
Problems
For each item, find the stationary point(s), then classify using the appropriate order of test. Difficulty rises down the list.
- Find and classify the stationary points of \(f(x) = x^3 - 6x^2 + 9x + 2\).
- Classify the stationary point of \(f(x) = x^4 - 4x^3\) using the higher-order test where needed.
- Minimize \(f(x) = x + \dfrac{1}{x}\) for \(x > 0\); confirm your answer with \(f''\).
- Find the stationary point of \(f(x,y) = x^2 + 4y^2 - 2x + 8y + 5\) and classify it.
- Show that \(f(x,y) = x^3 - 3xy + y^3\) has stationary points at \((0,0)\) and \((1,1)\); classify each.
- Use Sylvester's criterion to classify the stationary point of \(f(x,y) = 2x^2 + 2xy + 3y^2 - 4x - 6y\).
- Determine the nature of the Hessian \(\begin{bmatrix} 3 & 2 \\ 2 & 1 \end{bmatrix}\) and state what it implies for the stationary point.
- A rectangular open-top box of volume 32 must use the least material. Express surface area as a function of two variables and minimize (this is unconstrained after using the volume relation).
- Fit the best constant \(c\) to data \(a_1,\dots,a_n\) by minimizing \(S(c) = \sum_i (c - a_i)^2\); show \(c^\star\) is the mean.
- For \(f(x,y) = e^{x^2 + y^2}\), find the stationary point and argue (using convexity/monotonicity) that it is a global minimum.
- Explain, with a sketch, why solving \(\nabla f = 0\) alone can return a saddle point, and how the Hessian rules it out.
- Find and classify all stationary points of \(f(x,y) = x^2 y - x^2 - y^2\); for each, state which second-order test you used and whether the point is a local min, max, or saddle. Then explain why none of them is a global minimum over \(\mathbb{R}^2\).