The Central Idea
Optimization can be viewed as a sequence of improving decisions.
Starting from an initial point
\[ \mathbf{x}_0, \]an iterative method generates
\[ \mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3, \ldots \]with the goal of approaching an optimizer
\[ \mathbf{x}^*. \]Gradient-based methods choose these updates using derivatives of the objective function.
Why Use Numerical Optimization?
Some optimization problems can be solved exactly by algebra or calculus. Many others cannot.
Numerical methods become especially important when:
- the objective contains many variables;
- stationary equations cannot be solved symbolically;
- the objective comes from data or simulation;
- the model is too large for direct analytical methods;
- an approximate solution is sufficient or necessary.
The Gradient
For a differentiable function
\[ f(x_1,\ldots,x_n), \]the gradient is
\[ \boxed{ \nabla f(\mathbf{x}) = \begin{bmatrix} \frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ \vdots\\ \frac{\partial f}{\partial x_n} \end{bmatrix} }. \]The gradient collects all first-order partial derivative information into one vector.
Direction of Steepest Increase
At a point where
\[ \nabla f(\mathbf{x})\ne\mathbf{0}, \]the gradient points in the direction of greatest local increase of the objective.
Therefore,
\[ \boxed{ -\nabla f(\mathbf{x}) } \]points in the direction of greatest local decrease.
Directional Derivatives
If \(\mathbf{u}\) is a unit vector, then the directional derivative is
\[ D_{\mathbf{u}}f = \nabla f\cdot\mathbf{u}. \]The largest possible directional derivative occurs when \(\mathbf{u}\) points in the gradient direction.
The most negative directional derivative occurs in the opposite direction.
Gradient Descent
For minimization, the most basic gradient method is gradient descent.
Its update rule is
\[ \boxed{ \mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k\nabla f(\mathbf{x}_k) }. \]The positive quantity \(\alpha_k\) is the step size or learning rate.
Gradient Ascent
For maximization, we can move with the gradient rather than against it:
\[ \boxed{ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k\nabla f(\mathbf{x}_k) }. \]This is called gradient ascent.
One-Variable Gradient Descent
In one variable, gradient descent becomes
\[ \boxed{ x_{k+1} = x_k - \alpha_k f'(x_k) }. \]If the derivative is positive, the update moves left.
If the derivative is negative, the update moves right.
Example: One Step of Gradient Descent
Consider
\[ f(x)=x^2. \]Then
\[ f'(x)=2x. \]Start at
\[ x_0=4 \]with
\[ \alpha=0.1. \]Then
\[ x_1 = 4-0.1(8) = 3.2. \]The first step moves closer to the minimizer
\[ x^*=0. \]Continuing the Example
At
\[ x_1=3.2, \]the derivative is
\[ f'(3.2)=6.4. \]Therefore,
\[ x_2 = 3.2-0.1(6.4) = 2.56. \]The iterates continue moving toward zero.
The Role of the Step Size
The search direction tells us where to move.
The step size tells us how far to move.
Both matter.
\[ \boxed{ \text{new point} = \text{current point} + \text{step size}\times\text{search direction} }. \]Step Size Too Small
If \(\alpha_k\) is extremely small, each iteration moves only a short distance.
The method may still converge, but progress can be unnecessarily slow.
Step Size Too Large
If \(\alpha_k\) is too large, the method may overshoot the minimum.
The iterates can oscillate, become unstable, or even diverge.
A good search direction cannot compensate for an arbitrarily poor step size.
Fixed Step Sizes
The simplest method uses
\[ \alpha_k=\alpha \]for every iteration.
Fixed step sizes are easy to implement, but their success depends strongly on the scale and curvature of the objective.
Diminishing Step Sizes
Some methods use step sizes that become smaller over time:
\[ \alpha_0, \alpha_1, \alpha_2, \ldots \]with
\[ \alpha_k\to0. \]This can help stabilize convergence in certain deterministic and stochastic settings.
Line Search
Instead of fixing the step size in advance, a line search chooses a useful value of \(\alpha\) along a search direction.
If the current point is \(\mathbf{x}_k\) and the direction is \(\mathbf{d}_k\), consider
\[ \phi(\alpha) = f(\mathbf{x}_k+\alpha\mathbf{d}_k). \]The line search seeks an \(\alpha\) that sufficiently improves \(\phi\).
Exact Line Search
An exact line search chooses
\[ \boxed{ \alpha_k = \operatorname*{arg\,min}_{\alpha\ge0} f(\mathbf{x}_k+\alpha\mathbf{d}_k) }. \]This can be mathematically attractive but may be too expensive in large numerical problems.
Inexact Line Search
Practical algorithms often seek a step that is good enough rather than perfectly optimal along the line.
Inexact line searches balance computational cost against objective improvement.
Backtracking Line Search
A simple strategy begins with a trial step and repeatedly reduces it until the objective decreases sufficiently.
Conceptually:
- choose an initial step size;
- test the new point;
- if the decrease is insufficient, shrink the step;
- repeat until the step is acceptable.
Descent Directions
A vector \(\mathbf{d}\) is a descent direction at \(\mathbf{x}\) if
\[ \boxed{ \nabla f(\mathbf{x})^T\mathbf{d}<0 }. \]For sufficiently small positive steps, moving in such a direction decreases the objective.
Why the Negative Gradient Is a Descent Direction
Choose
\[ \mathbf{d} = -\nabla f. \]Then
\[ \nabla f^T\mathbf{d} = -\|\nabla f\|^2. \]If the gradient is nonzero,
\[ -\|\nabla f\|^2<0. \]Therefore, the negative gradient is always a descent direction away from stationary points.
Stationary Points and Stopping
At a stationary point,
\[ \nabla f(\mathbf{x})=\mathbf{0}. \]The basic gradient-descent direction then disappears.
This makes the gradient norm a natural stopping measure.
Gradient-Norm Stopping Rule
A common termination condition is
\[ \boxed{ \|\nabla f(\mathbf{x}_k)\| \le\varepsilon } \]for a chosen tolerance \(\varepsilon>0\).
A small gradient suggests approximate stationarity.
Other Stopping Criteria
Algorithms may also stop when:
- the objective changes very little;
- the decision vector changes very little;
- a maximum number of iterations is reached;
- a computational budget is exhausted;
- several stopping conditions are satisfied together.
Small Gradient Does Not Always Mean Global Optimality
A small gradient indicates approximate stationarity.
In a nonconvex problem, a stationary point may be:
- a local minimum;
- a local maximum;
- a saddle point.
Convexity or other structure is needed for stronger conclusions.
Gradient Descent on Convex Functions
If the objective is convex and sufficiently smooth, properly chosen gradient-descent steps can converge toward a global minimizer.
Convexity removes the danger of converging to an inferior local minimum.
Strong Convexity and Faster Guarantees
Strongly convex functions curve upward by a definite amount.
Under suitable smoothness and step-size conditions, gradient descent on a strongly convex objective can converge geometrically toward the unique global minimizer.
Lipschitz Gradients
Many convergence results assume the gradient does not change too abruptly.
A common condition is
\[ \boxed{ \|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\| \le L\|\mathbf{x}-\mathbf{y}\| }. \]The constant \(L\) controls how rapidly the gradient can vary.
Conditioning
Some objectives curve very differently in different directions.
Their level sets may be long and narrow rather than nearly circular.
Gradient descent can then zigzag and converge slowly.
This behavior is associated with poor conditioning.
Scaling Matters
Suppose one variable naturally varies around
\[ 10^{-3} \]while another varies around
\[ 10^6. \]The resulting numerical geometry can make a single step-size rule inefficient.
Rescaling variables can substantially improve optimization performance.
Preconditioning
A more general strategy changes the geometry of the search so that difficult directions are better balanced.
An update might take the form
\[ \boxed{ \mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k P_k \nabla f(\mathbf{x}_k) } \]where \(P_k\) adjusts the search direction.
Newton's Method
Gradient descent uses first-order information.
Newton's method also uses curvature.
In several variables, the Newton step satisfies
\[ \boxed{ \mathbf{x}_{k+1} = \mathbf{x}_k - H_f(\mathbf{x}_k)^{-1} \nabla f(\mathbf{x}_k) } \]when the Hessian is invertible and the step is appropriate.
Where Newton's Method Comes From
Near \(\mathbf{x}_k\), approximate the objective by a quadratic model:
\[ f(\mathbf{x}_k+\mathbf{p}) \approx f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T\mathbf{p} + \frac12 \mathbf{p}^T H_f(\mathbf{x}_k) \mathbf{p}. \]Minimizing this quadratic approximation produces the Newton direction.
Newton Direction
Rather than explicitly forming a matrix inverse, numerical methods typically solve
\[ \boxed{ H_f(\mathbf{x}_k)\mathbf{p}_k = -\nabla f(\mathbf{x}_k) }. \]The update is then
\[ \mathbf{x}_{k+1} = \mathbf{x}_k+\mathbf{p}_k \]or a damped version of this step.
Advantages of Newton's Method
Near a well-behaved minimizer, Newton's method can converge much faster than ordinary gradient descent.
It automatically accounts for differences in curvature among directions.
Costs of Newton's Method
Newton's method can be expensive because it requires:
- second derivatives;
- storage of a Hessian matrix;
- solution of a linear system at each iteration.
These costs can become substantial in high-dimensional problems.
Newton Steps Can Fail Far from the Solution
If the Hessian is indefinite or the quadratic approximation is poor, a full Newton step may not decrease the objective.
Practical algorithms therefore combine Newton directions with line searches, trust regions, or other safeguards.
Quasi-Newton Methods
Quasi-Newton methods attempt to capture the advantages of Newton's method without computing the exact Hessian at every step.
They build an approximation to the Hessian or its inverse using changes in gradients and iterates.
BFGS
One of the most widely used quasi-Newton algorithms is BFGS.
It updates a curvature approximation using information from consecutive iterates.
BFGS is often effective for smooth, medium-scale unconstrained optimization.
Limited-Memory BFGS
In very large problems, storing a full matrix can be impractical.
L-BFGS stores only a limited history of vectors and reconstructs the needed curvature information implicitly.
This makes it useful for high-dimensional optimization.
Conjugate-Gradient Methods
For quadratic objectives and related large systems, conjugate-gradient ideas choose search directions that avoid repeatedly undoing progress made in earlier directions.
These methods connect optimization with numerical linear algebra.
Momentum
Some first-order methods add part of the previous motion to the new update.
A simple momentum scheme has the form
\[ \mathbf{v}_{k+1} = \beta\mathbf{v}_k - \alpha\nabla f(\mathbf{x}_k), \] \[ \mathbf{x}_{k+1} = \mathbf{x}_k+\mathbf{v}_{k+1}. \]Momentum can reduce oscillation and accelerate travel through long, shallow directions.
Accelerated Gradient Methods
More advanced first-order methods use carefully designed momentum-like updates to improve convergence rates on convex problems.
Nesterov-type acceleration is a central example.
Stochastic Gradient Methods
When the objective is a sum over many observations,
\[ f(\mathbf{x}) = \frac{1}{N} \sum_{i=1}^{N} f_i(\mathbf{x}), \]evaluating the full gradient can be expensive.
Stochastic gradient methods approximate it using one observation or a smaller subset.
Mini-Batch Gradients
A compromise between a full gradient and a single-observation gradient is a mini-batch gradient.
It averages derivative information over a selected subset of the data.
Mini-batch methods are widely used in data-intensive optimization.
Noise in Stochastic Optimization
A stochastic gradient generally does not equal the exact gradient at every iteration.
The resulting noise can make the path fluctuate, but it can greatly reduce the cost of each step.
Automatic Differentiation
Modern computational systems often obtain gradients using automatic differentiation.
Rather than approximating derivatives by finite differences, automatic differentiation systematically applies derivative rules through the sequence of operations used to evaluate the objective.
Finite-Difference Gradients
When analytic or automatic derivatives are unavailable, a derivative can be approximated numerically.
In one variable,
\[ f'(x) \approx \frac{f(x+h)-f(x)}{h}. \]Such approximations are useful but introduce truncation and roundoff errors.
Gradient Checking
In computational work, finite differences can be used to check an analytically or automatically computed gradient.
Large disagreement can reveal implementation errors.
Gradient Methods with Constraints
A direct gradient step may leave a constrained feasible region.
Constrained variants therefore modify the update using methods such as:
- projection;
- penalty functions;
- barrier methods;
- augmented Lagrangians;
- sequential quadratic programming.
Projected Gradient Descent
If \(C\) is a feasible set, a projected gradient method takes a gradient step and then returns to the feasible region:
\[ \boxed{ \mathbf{x}_{k+1} = \Pi_C \left( \mathbf{x}_k - \alpha_k\nabla f(\mathbf{x}_k) \right) }. \]Here \(\Pi_C\) denotes projection onto \(C\).
Penalty Methods
A constrained problem can sometimes be converted into an unconstrained problem by penalizing constraint violations.
For a constraint
\[ g(\mathbf{x})=0, \]one might minimize
\[ f(\mathbf{x}) + \rho[g(\mathbf{x})]^2, \]where \(\rho>0\) controls the penalty strength.
Barrier Methods
Barrier methods discourage the iterates from approaching or crossing the boundary of an inequality constraint.
They are central to many interior-point optimization algorithms.
Search Paths and Level Sets
It is often useful to imagine an optimization method moving across level sets of the objective.
Gradient descent crosses contours approximately in the direction of their normal vectors.
Curvature-aware methods modify this direction to better match the shape of the objective landscape.
Local Models
Gradient-based optimization relies on local approximation.
First-order methods use
\[ f(\mathbf{x}+\mathbf{p}) \approx f(\mathbf{x}) + \nabla f(\mathbf{x})^T\mathbf{p}. \]Second-order methods add curvature through the Hessian.
Convergence
An iterative sequence converges to \(\mathbf{x}^*\) if
\[ \mathbf{x}_k\to\mathbf{x}^* \]as
\[ k\to\infty. \]Optimization theory studies both whether convergence occurs and how quickly it occurs.
Convergence Rate
Two methods may both converge but require very different numbers of iterations.
Convergence-rate analysis measures how quickly the error
\[ \|\mathbf{x}_k-\mathbf{x}^*\| \]or objective gap
\[ f(\mathbf{x}_k)-f(\mathbf{x}^*) \]decreases.
Iteration Cost Versus Number of Iterations
A sophisticated method may use fewer iterations but require more work per iteration.
A simpler method may require many cheap iterations.
Practical optimization compares total computational cost, not iteration count alone.
Initialization
Every iterative optimization method requires a starting point.
\[ \mathbf{x}_0. \]In convex problems, different reasonable starting points may still lead toward the same global solution.
In nonconvex problems, initialization can strongly affect the final result.
Multiple Starts
One practical strategy for nonconvex optimization is to run a local method from several initial points.
The resulting solutions can then be compared.
This does not guarantee global optimality, but it can reduce dependence on one initial guess.
Common Error: Using the Wrong Sign
For minimization, ordinary gradient descent uses
\[ -\nabla f. \]Moving in the positive gradient direction performs local ascent instead.
Common Error: Choosing a Step Size Without Checking Behavior
A large step can increase the objective even when the search direction is locally descending.
Step-size selection is part of the method, not an afterthought.
Common Error: Treating a Small Gradient as Proof of a Minimum
A small gradient indicates approximate stationarity.
It does not distinguish a minimum from a maximum or saddle point in a general nonconvex problem.
Common Error: Ignoring Scaling
Poorly scaled variables can cause slow zigzagging, numerical instability, and difficulty choosing a useful step size.
Rescaling or preconditioning may substantially improve performance.
Common Error: Comparing Methods by Iteration Count Alone
One Newton iteration can be much more expensive than one gradient-descent iteration.
Computational comparisons should include derivative costs, linear solves, memory use, and total runtime.
Common Error: Ignoring Constraints
An unconstrained gradient step can produce an infeasible point.
Constrained problems require a method that respects or restores feasibility.
A Reliable Gradient-Based Optimization Workflow
- Define the objective function and domain.
- Determine whether the problem is unconstrained or constrained.
- Compute or approximate the gradient.
- Inspect convexity, curvature, and scaling when possible.
- Choose an initial point.
- Select a search direction.
- Select a step-size strategy.
- Generate the next iterate.
- Check objective improvement and feasibility.
- Monitor the gradient norm and iterate changes.
- Adjust scaling, step sizes, or the method when progress is poor.
- Stop when a justified tolerance or resource limit is reached.
- Verify and interpret the resulting solution.
Practice 1: Compute a Gradient
Find
\[ \nabla f \]for
\[ f(x,y)=x^2+3y^2. \]Practice 2: Descent Direction
At
\[ (2,-1), \]find the negative-gradient direction for
\[ f(x,y)=x^2+y^2. \]Practice 3: One Gradient Step
Let
\[ f(x)=x^2, \]with
\[ x_0=5 \]and
\[ \alpha=0.1. \]Compute \(x_1\).
Practice 4: Gradient Ascent
Write the general gradient-ascent update for maximizing
\[ f(\mathbf{x}). \]Practice 5: Stationarity
Find the stationary point of
\[ f(x,y)=x^2+y^2-4x+6y. \]Practice 6: Descent Test
Suppose
\[ \nabla f= \begin{bmatrix} 3\\ 4 \end{bmatrix} \]and
\[ \mathbf{d} = \begin{bmatrix} -1\\ -1 \end{bmatrix}. \]Is \(\mathbf{d}\) a descent direction?
Practice 7: Newton Step
For
\[ f(x)=x^2-6x+10, \]write the one-variable Newton optimization update and compute the next iterate from
\[ x_0=0. \]Practice 8: Step Size
Explain why an excessively large learning rate can cause gradient descent to fail.
Practice 9: Convexity and Gradient Descent
Why is gradient descent conceptually safer on a convex objective than on a general nonconvex objective?
Practice 10: Identify the Error
A student reaches a point where
\[ \|\nabla f\| \]is very small and declares that the point must be the global minimum.
Explain the error.
Practice Answers
Practice 1
The partial derivatives are
\[ f_x=2x \]and
\[ f_y=6y. \]Therefore,
\[ \boxed{ \nabla f = \begin{bmatrix} 2x\\ 6y \end{bmatrix} }. \]Practice 2
The gradient is
\[ \nabla f= \begin{bmatrix} 2x\\ 2y \end{bmatrix}. \]At \((2,-1)\),
\[ \nabla f= \begin{bmatrix} 4\\ -2 \end{bmatrix}. \]Therefore, the negative-gradient direction is
\[ \boxed{ \begin{bmatrix} -4\\ 2 \end{bmatrix} }. \]Practice 3
Since
\[ f'(x)=2x, \]we have
\[ f'(5)=10. \]Therefore,
\[ x_1 = 5-0.1(10) = \boxed{4}. \]Practice 4
\[ \boxed{ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k\nabla f(\mathbf{x}_k) }. \]Practice 5
The gradient is
\[ \nabla f = \begin{bmatrix} 2x-4\\ 2y+6 \end{bmatrix}. \]Set it equal to zero:
\[ 2x-4=0, \qquad 2y+6=0. \]Therefore,
\[ \boxed{(x,y)=(2,-3)}. \]Practice 6
Compute
\[ \nabla f^T\mathbf{d} = 3(-1)+4(-1) = -7. \]Since
\[ -7<0, \]we have
\[ \boxed{ \mathbf{d}\text{ is a descent direction} }. \]Practice 7
We have
\[ f'(x)=2x-6 \]and
\[ f''(x)=2. \]Newton's update is
\[ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}. \]Starting at \(x_0=0\),
\[ x_1 = 0 - \frac{-6}{2} = \boxed{3}. \]Practice 8
A very large step can jump past a minimizer, increase the objective, produce oscillation, or cause the iterates to diverge.
Practice 9
For a convex objective, every local minimum is global.
Therefore, moving toward a local minimum does not risk settling at an inferior local valley.
Practice 10
A small gradient shows only approximate stationarity.
In a nonconvex problem, the point could be a local maximum or saddle point. Even if it is a local minimum, global optimality requires additional justification.
What to Remember
Gradient-based methods turn derivative information into iterative search.
- the gradient points toward greatest local increase;
- the negative gradient provides a natural descent direction;
- gradient descent repeatedly moves against the gradient;
- gradient ascent repeatedly moves with the gradient;
- step size strongly affects stability and speed;
- line searches choose useful step lengths adaptively;
- Newton methods incorporate Hessian curvature;
- quasi-Newton methods approximate curvature information;
- convexity provides global guarantees unavailable in general nonconvex problems;
- scaling, initialization, stopping rules, and computational cost all affect practical performance.
The basic iterative pattern is
\[ \boxed{ \text{evaluate local information} \;\rightarrow\; \text{choose a direction} \;\rightarrow\; \text{choose a step} \;\rightarrow\; \text{repeat} }. \]Where We Go Next
Gradient-based methods assume that decision variables move through a continuous space in which small changes and derivatives are meaningful. Many optimization problems, however, involve both continuous quantities and discrete choices such as whole units, yes-or-no decisions, routes, schedules, assignments, and configurations.
The next lesson, Discrete and Continuous Optimization, compares these two settings and explains how the nature of the decision space changes the methods available for finding optimal solutions.