Unconstrained Nonlinear Optimization
Once the objective is nonlinear and there are no constraints to worry about, optimization becomes a hunt across a smooth multidimensional surface for its lowest point. This chapter lays the analytical foundation for that hunt: the gradient and Hessian that describe local slope and curvature, the Taylor model that turns any smooth function into a local paraboloid, the optimality conditions that certify a point as a minimum, the role of convexity in promoting a local minimum to a global one, and the general iterative-descent framework — pick a descent direction, take a step, repeat — that every algorithm in the next chapter is built on.
- The unconstrained problem — minimising a smooth function \(F(\mathbf{x})\) over all of \(\mathbb{R}^n\).
- The gradient \(\nabla F\) and Hessian \(\nabla^2 F\), and the local Taylor model they build.
- First- and second-order optimality conditions — stationary points and positive-definite Hessians.
- Convexity and why it turns any local minimum into a global one.
- Quadratic forms and how definiteness distinguishes a minimum, maximum, or saddle.
- The iterative-descent framework and the rates of convergence (linear, superlinear, quadratic).
The Unconstrained Problem
An unconstrained nonlinear optimization problem asks for the point that minimises a real-valued function of several variables, with no restrictions on where that point may lie. Formally, we seek \(\mathbf{x}^\star \in \mathbb{R}^n\) minimising \(F(\mathbf{x})\), where \(F\) is (usually) smooth and nonlinear. Maximising \(F\) is the same task applied to \(-F\), so it is enough to study minimisation.
Two flavours of solution must be kept apart. A local minimiser \(\mathbf{x}^\star\) is lowest only within some neighbourhood — \(F(\mathbf{x}^\star) \le F(\mathbf{x})\) for all \(\mathbf{x}\) near \(\mathbf{x}^\star\). A global minimiser is lowest everywhere — \(F(\mathbf{x}^\star) \le F(\mathbf{x})\) for all \(\mathbf{x}\). Calculus, working only from local slope and curvature, can certify local minima directly; promoting a local minimum to a global one generally requires an extra structural property, and the cleanest such property is convexity (Section 19-4).
Gradient, Hessian & Taylor Models
Local behaviour of a smooth \(F\) is captured by two derivatives. The gradient \(\nabla F(\mathbf{x})\) is the vector of first partials; it points in the direction of steepest increase, and its negative points steepest downhill. The Hessian \(\nabla^2 F(\mathbf{x})\) is the symmetric matrix of second partials; it measures curvature — how the slope itself changes.
For twice-continuously-differentiable \(F\), mixed partials are equal, so the Hessian is symmetric. These two objects assemble into the second-order Taylor model, the single most useful approximation in nonlinear optimization: near a point \(\mathbf{x}_k\), \(F\) looks like a paraboloid.
The linear term \(\nabla F^{\top}\mathbf{p}\) is the first-order change predicted by the slope; the quadratic term \(\tfrac12\mathbf{p}^{\top}\mathbf{H}\mathbf{p}\) is the curvature correction. Almost every method in the next chapter works by minimising this local model, taking the resulting step, rebuilding the model, and repeating.
Optimality Conditions
How do we know a point is a minimum? The Taylor model answers directly. At a candidate \(\mathbf{x}^\star\), if the gradient were nonzero the linear term would let us decrease \(F\) by stepping in the direction \(-\nabla F\). So a minimum must kill the linear term — it must be a stationary point.
Every local minimiser of a differentiable \(F\) is a stationary point. The converse fails — stationary points also include maxima and saddles — so this condition is necessary, not sufficient.
To distinguish the three kinds of stationary point we turn to curvature. With \(\nabla F(\mathbf{x}^\star) = \mathbf{0}\), the Taylor model reduces to \(F(\mathbf{x}^\star + \mathbf{p}) \approx F(\mathbf{x}^\star) + \tfrac12\mathbf{p}^{\top}\mathbf{H}(\mathbf{x}^\star)\mathbf{p}\). The point is a strict local minimum exactly when that quadratic term is positive for every nonzero \(\mathbf{p}\) — i.e. when the Hessian is positive definite.
| Hessian at stationary point | Definiteness | Classification |
|---|---|---|
| All eigenvalues \(> 0\) | Positive definite | Strict local minimum |
| All eigenvalues \(< 0\) | Negative definite | Strict local maximum |
| Mixed signs | Indefinite | Saddle point |
| Eigenvalues \(\ge 0\), some \(= 0\) | Positive semidefinite | Inconclusive (test fails) |
Convexity & Global Optimality
The optimality conditions above are purely local. Convexity is the bridge to global statements. A function \(F\) is convex if the line segment between any two points on its graph never dips below the graph:
For a twice-differentiable function there is a clean equivalent test: \(F\) is convex on a region iff its Hessian is positive semidefinite everywhere on that region, and strictly convex if the Hessian is positive definite. The payoff is the single most important fact in unconstrained optimization:
If \(F\) is convex, the first-order condition \(\nabla F(\mathbf{x}^\star) = \mathbf{0}\) is not just necessary but sufficient for a global minimum. If \(F\) is strictly convex, that global minimiser is unique. This is why detecting convexity is often the first thing a modeller checks.
Quadratic Forms & Definiteness
The quadratic function is the workhorse of the whole subject: it is exactly the Taylor model, and every method is tested first on it. A general quadratic form in \(n\) variables can be written with a symmetric matrix \(\mathbf{A}\):
Here \(\nabla^2 q = \mathbf{A}\) is constant, so a quadratic's curvature is fixed everywhere and its character is decided entirely by the definiteness of \(\mathbf{A}\). Definiteness is read off the eigenvalues (all of which are real because \(\mathbf{A}\) is symmetric), or, for small matrices, from the signs of the leading principal minors (Sylvester's criterion).
| Property of \(\mathbf{A}\) | Eigenvalue test | Sylvester (leading minors) | Shape of \(q\) |
|---|---|---|---|
| Positive definite | all \(\lambda_i > 0\) | all leading minors \(> 0\) | Bowl — unique minimum |
| Positive semidefinite | all \(\lambda_i \ge 0\) | all leading minors \(\ge 0\) | Trough — minima along a line |
| Indefinite | mixed signs | minors change sign | Saddle — no minimum |
| Negative definite | all \(\lambda_i < 0\) | signs alternate \(-,+,-\dots\) | Dome — unique maximum |
Descent Directions & Iterative Descent
Except for quadratics, we cannot solve \(\nabla F(\mathbf{x}) = \mathbf{0}\) in closed form. Instead we iterate: from a current point \(\mathbf{x}_k\), pick a direction that goes downhill, step along it, and repeat. A direction \(\mathbf{d}_k\) is a descent direction if moving along it lowers \(F\) for small enough steps — which, by the first-order Taylor term, means it makes an obtuse angle with the gradient:
The most obvious descent direction is the negative gradient, \(\mathbf{d}_k = -\nabla F(\mathbf{x}_k)\), which is the direction of steepest local decrease. Every unconstrained method fits the same skeleton — the general iterative-descent scheme — differing only in how \(\mathbf{d}_k\) is chosen and how the step length \(\alpha_k\) is found:
Choose a descent direction \(\mathbf{d}_k\); find a step \(\alpha_k > 0\) by a line search (Chapter 18); update; stop when \(\lVert \nabla F(\mathbf{x}_k)\rVert \le \varepsilon\). The direction is this chapter's business; the step length is the previous chapter's.
Rate of Convergence
Two methods can both reach the minimum yet differ enormously in how fast the error shrinks. The rate of convergence compares the error at successive iterates, \(e_k = \lVert \mathbf{x}_k - \mathbf{x}^\star \rVert\), through the limiting ratio
| Type | Order \(p\) | Constant \(C\) | Flavour |
|---|---|---|---|
| Linear | \(1\) | \(0 < C < 1\) | Error shrinks by a fixed factor each step (e.g. steepest descent) |
| Superlinear | \(1\) | \(C = 0\) | Faster than any fixed factor (e.g. quasi-Newton) |
| Quadratic | \(2\) | \(C < \infty\) | Correct digits roughly double each step (Newton's method) |
Linear convergence with a factor near \(1\) can crawl — steepest descent slows badly on ill-conditioned problems whose contours are long, thin ellipses. Newton's method, which minimises the full quadratic model each step, converges quadratically near the solution but pays for a Hessian. The methods of Chapter 20 are essentially a spectrum of trades between these extremes: cheap-but-linear at one end, expensive-but-quadratic at the other.
Worked Examples
Problem. Find and classify the stationary point of \(F(x,y) = x^2 + y^2 - 4x - 6y + 13\).
Solution. \(\nabla F = (2x - 4,\ 2y - 6)\). Setting it to zero gives \(x = 2,\ y = 3\). The Hessian is \(\mathbf{H} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\), whose eigenvalues \(2, 2\) are both positive — positive definite. So \((2,3)\) is a strict local minimum, and since \(F\) is quadratic with positive-definite Hessian it is also the unique 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) = \mathbf{0}\) gives the single stationary point \((0,0)\). The Hessian \(\mathbf{H} = \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix}\) has eigenvalues \(+2\) and \(-2\) — mixed signs, so it is indefinite. The point is a saddle: a minimum along \(x\) but a maximum along \(y\). The first-order test alone would have flagged it as a candidate; only curvature reveals it is not a minimum.
Problem. Is \(F(x,y) = x^2 + xy + y^2\) convex? Find its global minimiser.
Solution. \(\mathbf{H} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\) is constant. Leading minors: \(2 > 0\) and \(\det = 4 - 1 = 3 > 0\), so by Sylvester's criterion \(\mathbf{H}\) is positive definite everywhere — \(F\) is strictly convex. Then \(\nabla F = (2x + y,\ x + 2y) = \mathbf{0}\) gives \(x = y = 0\), the unique global minimum \(F(0,0) = 0\). Convexity guarantees no other minimum exists.
Problem. Minimise \(q(\mathbf{x}) = \tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x} - \mathbf{b}^{\top}\mathbf{x}\) with \(\mathbf{A} = \begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\), \(\mathbf{b} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\).
Solution. \(\mathbf{A}\) is positive definite (minors \(4 > 0\), \(\det = 11 > 0\)), so a unique minimum exists at \(\mathbf{x}^\star = \mathbf{A}^{-1}\mathbf{b}\). With \(\mathbf{A}^{-1} = \tfrac{1}{11}\begin{bmatrix} 3 & -1 \\ -1 & 4 \end{bmatrix}\), \(\mathbf{x}^\star = \tfrac{1}{11}(3 - 2,\ -1 + 8) = \tfrac{1}{11}(1,\ 7) \approx (0.091,\ 0.636)\).
Problem. At a point where \(\nabla F = (2,\ -1)\), test whether \(\mathbf{d} = (-1,\ -1)\) and \(\mathbf{d}' = (1,\ 1)\) are descent directions.
Solution. Use the sign of \(\nabla F^{\top}\mathbf{d}\). For \(\mathbf{d}\): \((2)(-1) + (-1)(-1) = -2 + 1 = -1 < 0\) — a valid descent direction. For \(\mathbf{d}'\): \((2)(1) + (-1)(1) = 2 - 1 = 1 > 0\) — this points uphill, so it is not a descent direction.
Problem. For \(F(x,y) = x^2 + 2y^2\), take one steepest-descent step from \(\mathbf{x}_0 = (1,1)\) using an exact line search.
Solution. \(\nabla F = (2x,\ 4y) = (2,4)\), so \(\mathbf{d}_0 = -(2,4)\). Along the line, \(\phi(\alpha) = (1-2\alpha)^2 + 2(1-4\alpha)^2\). Setting \(\phi'(\alpha) = -4(1-2\alpha) - 16(1-4\alpha) = -20 + 72\alpha = 0\) gives \(\alpha_0 = \tfrac{20}{72} = \tfrac{5}{18} \approx 0.278\). Then \(\mathbf{x}_1 = (1 - 2\alpha_0,\ 1 - 4\alpha_0) \approx (0.444,\ -0.111)\), and \(F\) drops from \(3\) to about \(0.22\) — the direction came from this chapter, the step length from Chapter 18.
Chapter Summary
Minimise a smooth \(F(\mathbf{x})\) over \(\mathbb{R}^n\); local minima come from calculus, global minima need extra structure.
The gradient gives slope, the Hessian gives curvature, and together they build the local quadratic Taylor model.
\(\nabla F = \mathbf{0}\) is necessary; a positive-definite Hessian at that point is sufficient for a strict local minimum.
A positive-semidefinite Hessian everywhere means convex — and for convex \(F\), local minima are global.
Eigenvalue signs (or leading minors) sort a stationary point into minimum, maximum, or saddle.
Iterate \(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k\mathbf{d}_k\) with \(\nabla F^{\top}\mathbf{d}_k < 0\); convergence is linear, superlinear, or quadratic.
Problems
For each, compute the gradient and Hessian where needed, apply the optimality conditions, and state the classification. Difficulty rises down the list.
- State the first- and second-order necessary conditions for \(\mathbf{x}^\star\) to be a local minimiser of a twice-differentiable \(F\).
- Explain why the first-order condition \(\nabla F = \mathbf{0}\) is necessary but not sufficient, giving a one-dimensional example.
- Compute the gradient and Hessian of \(F(x,y) = 3x^2 + 2xy + 2y^2 - 4x + 2y\).
- Find all stationary points of \(F(x,y) = x^2 + y^2 - 4x - 6y + 13\) and classify each using the Hessian.
- Show that \(F(x,y) = x^2 - y^2\) has a saddle point at the origin, and describe its behaviour along the two axes.
- Use Sylvester's criterion to decide whether \(\mathbf{A} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\) is positive definite, and hence whether \(q(\mathbf{x}) = \tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\) is convex.
- Prove that if \(F\) is convex then any local minimiser is a global minimiser.
- Write the second-order Taylor expansion of \(F(x,y) = e^{x} + y^2\) about the origin.
- For \(q(\mathbf{x}) = \tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x} - \mathbf{b}^{\top}\mathbf{x}\) with \(\mathbf{A} = \begin{bmatrix} 5 & 2 \\ 2 & 4 \end{bmatrix}\), \(\mathbf{b} = (3, 1)^{\top}\), find the minimiser \(\mathbf{x}^\star = \mathbf{A}^{-1}\mathbf{b}\).
- At a point with \(\nabla F = (3, -2)\), determine which of \(\mathbf{d}_1 = (-1, -1)\), \(\mathbf{d}_2 = (-1, 2)\), \(\mathbf{d}_3 = (2, 3)\) are descent directions.
- Take one steepest-descent step with exact line search for \(F(x,y) = x^2 + 3y^2\) from \(\mathbf{x}_0 = (2, 1)\), and confirm \(F\) decreased.
- Define linear, superlinear, and quadratic convergence, and explain why steepest descent struggles on ill-conditioned (long, thin) contours while Newton's method does not.