Convexity, gradient methods, and unconstrained optimisation

A gradient supplies local sensitivity; an optimiser uses that information to seek a smaller objective. Whether a method descends, converges, preserves its domain or reaches a global minimiser depends on additional assumptions. This lesson proves convexity and descent statements, analyses quadratic eigenmodes exactly, and contrasts them with stopping and Newton failures that can appear in a numerical training loop.

Retrieval check: use Module13 symmetric eigenmodes and positive-definite quadratic forms, and Module18 column gradients, Hessians and loss reductions. The descent proof uses the mean value theorem from Module16, so an extra integration prerequisite is unnecessary. Labs use NumPy on the tested course baseline.

An optimisation problem specifies an objective f and a feasible domain D, and asks to minimise f(x) over x∈D. In an unconstrained problem D is often all of Rⁿ, or an open natural domain such as positive inputs for a logarithm. “Unconstrained” does not permit evaluating outside the function’s domain. A global minimiser x* belongs to D and has f(x*)≤f(x) for every feasible x. The infimum is the greatest lower bound of objective values and need not be attained by any feasible point. An algorithm approaching that bound does not by itself produce an attained minimiser.

For f(x)=x on(0,1), the infimum is zero but no minimiser exists. For exp(x) on R, the infimum is also zero and is approached only as x→−∞. Neither example is repaired by a small derivative or a long finite trace. For f(x)=−x² on R, there is no finite lower bound, so the optimisation problem is unbounded below. Conversely, on a nonempty compact feasible set a continuous real objective attains its minimum by the extreme value theorem. Domain, boundedness and attainment are mathematical properties of the problem before a solver is chosen.

A local minimiser compares feasible points within some neighbourhood; it can have larger objective than another feasible region. Strict local minimality uses strict inequality for nearby distinct feasible points. A stationary point is an interior differentiable point with zero gradient and is only a candidate. A boundary minimiser may instead have a nonzero gradient, and a kink minimiser may lack a classical gradient. Section3 separates these cases, while the next module develops constraints and their boundary conditions systematically.

Objective scale matters. Multiplying f by a positive constant preserves its minimisers but scales its gradient and Hessian, so a fixed step size or gradient tolerance changes meaning. Adding a constant preserves every derivative and minimiser while altering reported objective values. Two training logs cannot be compared without their reductions and scales; a low numerical objective does not alone imply accurate parameters or good predictions. Mathematical optimisation error is also different from model generalisation, which later statistical modules address.

Coordinate changes have related but distinct effects. If z=Sx for invertible S and the objective is re-expressed as g(z)=f(S⁻¹z), feasible points and minimisers correspond exactly. Euclidean gradient steps in z generally map back to a matrix-scaled update in x, not the original scalar-step gradient method. If only some terms are transformed, such as features without adjusting a penalty, the objective itself may change. Specify whether a scaling is a reparameterisation of one problem or a new modelling choice.

An implementation should state its initial point, step selection, accepted objective and termination quantity. A maximum iteration count terminates an attempt; a small update, gradient norm or objective change certifies only what a theorem and tolerance contract connect to it. The labs provide counterexamples before any broad claim about practical neural-network training. Numerical success on a handful of starts does not establish an unconditional global guarantee for arbitrary nonconvex objectives.

A set D is convex when every segment(1−t)x+ty with x,y∈D,t∈[0,1] stays in D. A function f on a convex domain is convex when f((1−t)x+ty)≤(1−t)f(x)+tf(y). The graph lies below its endpoint chords. Strict convexity makes the inequality strict for distinct points and0<t<1. Convexity is a global segment property and does not require smoothness: |x| is convex despite its kink. Smoothness alone does not imply convexity, as −x² shows.

Finite Jensen extends the two-point definition: for nonnegative weights α_i summing to one, f(Σα_i x_i)≤Σα_i f(x_i). Prove by induction: remove zero weights, combine the first k−1 points with their total weight, apply the two-point inequality with the last point, then use the induction hypothesis for the normalised earlier weights. If the earlier total is zero, only the last point contributes and equality is immediate. This is an algebraic weighted-average result here; expectations and infinite mixtures later require their own model and integrability assumptions.

For differentiable f on an open convex domain, convexity is equivalent to the first-order supporting inequality f(y)≥f(x)+∇f(x)ᵀ(y−x). From convexity, apply the segment inequality at x+t(y−x), rearrange to bound its forward difference quotient by f(y)−f(x), and let t↓0. Conversely, assume the supporting inequality for all pairs. At z=(1−t)x+ty, write it for x and y relative to z, weight the two inequalities, and the gradient terms cancel. This recovers convexity. The criterion is about every pair on the domain, not one tangent sample.

For C² f on an open convex domain, positive-semidefinite Hessian everywhere is equivalent to convexity. Along any segment, the scalar second derivative is dᵀH(x+td)d≥0, so its first derivative is nondecreasing by the mean value theorem. This supplies the supporting inequality along each segment. Conversely, convexity makes symmetric second differences f(x+td)−2f(x)+f(x−td) nonnegative; division by t² and the second-order limit yield dᵀH(x)d≥0 for every direction. A positive-semidefinite Hessian at one point alone is only local curvature information.

A function is μ-strongly convex, μ>0, when f−(μ/2)‖x‖² is convex on its convex domain. For differentiable f the supporting inequality becomes f(y)≥f(x)+∇f(x)ᵀ(y−x)+(μ/2)‖y−x‖². C² Hessians satisfying H(x)≽μI everywhere give this property. Strong convexity supplies a uniform quadratic margin, while strict convexity only requires strict chords without a shared μ. For example x⁴ is strictly convex on R but has zero second derivative at zero and is not uniformly strongly convex there with any positive μ.

Nonnegative sums of convex functions and affine composition preserve convexity by applying the defining inequalities. A negative multiple can reverse the inequality, so weights need their sign condition. The maximum of finitely many convex functions is convex: each function’s segment value is bounded by a weighted endpoint value, and then by the weighted maxima. This explains why useful convex objectives can have nonsmooth boundaries; first-order smooth methods need the additional differentiability conditions stated in their own guarantees.

At an interior differentiable local minimiser, every directional first-order rate is zero, so the gradient vanishes. For C² objectives, a positive-definite Hessian at a stationary point gives a strict local minimum; a negative-definite Hessian gives a maximum; an indefinite Hessian gives a saddle. These follow from the second-order model and its uniform remainder control. A semidefinite Hessian with zero directions is inconclusive: higher-order terms may decide either way. These tests classify neighbourhood behaviour, not arbitrary distant points.

Convexity changes the certificate. If a differentiable convex objective on an open convex domain has ∇f(x*)=0, its supporting inequality gives f(y)≥f(x*) for every feasible y, so the point is globally optimal. Every local minimiser of a convex function is also global even without differentiability: a lower distant value would force lower values on arbitrarily short segments leaving the alleged local minimum. Strict convexity makes an attained minimiser unique, since two distinct equal minima would have a strictly lower midpoint. None of these properties by itself guarantees that a minimiser exists on an open or unbounded domain.

Strong convexity adds quantitative control when an unconstrained minimiser x* exists. Apply its supporting inequalities in both directions and add them to obtain (∇f(x)−∇f(x*))ᵀ(x−x*)≥μ‖x−x*‖². Since the minimiser gradient is zero, Cauchy–Schwarz gives ‖x−x*‖≤‖∇f(x)‖/μ. The strong-convexity lower model also gives f(x*)≥f(x)−‖∇f(x)‖²/(2μ), by minimising the quadratic in displacement, hence objective gap≤‖∇f(x)‖²/(2μ). These are error bounds under uniform μ and attainment, not interpretations of any tiny gradient in any model.

For f(x)=10⁻¹²(x−100)², μ=2·10⁻¹². At x=0 the gradient is−2·10⁻¹⁰, easily below tolerance10⁻⁶, while solution distance is100. The proved distance bound is exactly100. To certify distance≤.01 through this criterion, gradient norm must be≤μ(.01)=2·10⁻¹⁴. The objective gap at zero is numerically small, so a solver may satisfy a stated objective-gap tolerance while failing a parameter-distance tolerance. Decide which quantity the user actually needs rather than declare every small number “converged.”

For merely convex functions, small gradients need additional scale information to bound objective gap. The supporting inequality gives f(x)−f(x*)≤∇f(x)ᵀ(x−x*)≤‖∇f(x)‖‖x−x*‖. A known distance bound R supplies gap≤R‖∇f(x)‖; without R or stronger structure, the gradient norm alone does not determine a useful uniform gap certificate. Nonconvex stationary points need classification or separate global evidence instead of this convex supporting argument.

Constraints further change necessary conditions. On[0,∞), f(x)=x is minimised at zero with gradient one; feasible directions cannot point left, so the unconstrained zero-gradient condition is irrelevant. This lesson’s global stationary certificate presumes an interior unconstrained minimiser and a convex domain where its supporting inequality applies. Next module will replace those assumptions with explicit constraint and multiplier conditions, rather than force a boundary optimum to have zero ordinary gradient.

Gradient descent uses x_new=x−η∇f(x) with η>0. The negative gradient is a Euclidean steepest first-order direction when nonzero, but a finite step can overshoot or leave the domain. A step rule must control that finite change rather than infer descent from the infinitesimal direction alone. Suppose the gradient is L-Lipschitz, L>0, over a convex region containing the entire segment from x to y: ‖∇f(y)−∇f(x)‖≤L‖y−x‖. Then f(y)≤f(x)+∇f(x)ᵀ(y−x)+(L/2)‖y−x‖², the descent lemma.

Here is a proof requiring only the mean value theorem. Let d=y−x and φ(t)=f(x+td)−f(x)−t∇f(x)ᵀd−(L/2)t²‖d‖² on[0,1]. Its derivative is[∇f(x+td)−∇f(x)]ᵀd−Lt‖d‖²≤0 by Cauchy–Schwarz and the Lipschitz bound. Hence φ is nonincreasing and φ(1)≤φ(0)=0. This produces the finite-change inequality without an unstated integration prerequisite. The segment must stay in the region where the gradient bound is known.

For constant admissible η and an objective bounded below, summing the decrease inequality yields Σ‖g_k‖²≤[f(x₀)−f_inf]/[η(1−Lη/2)]. Therefore gradient norms tend to zero if all assumptions continue to hold. The smallest squared gradient among the first K iterates is at most the same numerator divided by K times the coefficient. This is a stationary-residual guarantee, not proof of a global minimum, convergence of the actual input sequence, or suitability for an arbitrary nonconvex network without the hypotheses.

Convexity and an attained minimiser add an objective rate. With η=1/L, write e_k=x_k−x*. The squared-distance recurrence and supporting inequality give ‖e_{k+1}‖²≤‖e_k‖²−(2/L)(f_k−f*)+‖g_k‖²/L². Descent bounds the last term by(2/L)(f_k−f_{k+1}), so f_{k+1}−f*≤(L/2)(‖e_k‖²−‖e_{k+1}‖²). Sum over steps; because objectives decrease, the last gap is no larger than their average. Thus f_k−f*≤L‖e₀‖²/(2k), k≥1. This proof states both existence and smooth convexity rather than attaching an O(1/k) label to every experiment.

If the objective is also μ-strongly convex, Section3 gives ‖g‖²≥2μ(f−f*). Combined with η=1/L descent, the gap shrinks by at most the factor1−μ/L per step. The bound is a theorem under global or invariant-domain hypotheses; an estimated local curvature at one iterate does not automatically establish a uniform μ or L. On a positive-definite quadratic the exact eigenmode analysis below provides a more detailed parameter-error rate.

Backtracking can choose a step without a known global L. Start with a direction p satisfying gᵀp<0, an initial α>0, shrink factor β∈(0,1) and Armijo constant c∈(0,1). Accept only when the trial is in the domain and f(x+αp)≤f(x)+cαgᵀp. Differentiability makes the directional quotient tend to gᵀp, which is strictly below c gᵀp, so sufficiently small positive α succeeds in an open neighbourhood. This proves finite termination in exact arithmetic under a genuine descent direction; it does not make a non-descent Newton direction acceptable or prove global convergence by itself.

Practical line searches use a finite attempt limit and numerical tolerances. If no trial succeeds, report failure rather than mark the last rejected point accepted. A tiny accepted step may reflect steep curvature, domain restrictions or inaccurate direction information; movement alone does not certify a small gradient or solution error. State the accepted inequality and termination reason, especially when objective evaluations have rounding or simulation noise.

For f(x)=(1/2)xᵀAx−bᵀx with symmetric positive-definite A, its unique minimiser solves Ax*=b and gradient is A(x−x*). Error e_k=x_k−x* obeys e_{k+1}=(I−ηA)e_k. In an orthonormal eigenbasis, each scalar mode evolves as c_{i,k+1}=(1−ηλ_i)c_{i,k}. Convergence for every initial error requires every multiplier’s magnitude below one. Since all λ_i>0, the exact constant-step interval is0<η<2/λ_max. This is a necessary and sufficient guarantee for this full quadratic family, stronger than interpreting a general sufficient bound as necessary everywhere.

At η=2/λ_max, an excited top mode alternates with unchanged magnitude. Above it that mode grows. An initial error with zero component in an unstable mode may still converge along other modes, so one lucky trace cannot prove global stability. At η=0 no error changes. These boundary cases parallel the scalar Euler factors in Module17 and the matrix dynamics in Module13. The mathematical guarantee quantifies over all starting errors, rather than just the one used in a plot.

Let ρ=max_i|1−ηλ_i|. Orthogonality gives ‖e_k‖≤ρ^k‖e₀‖. Since objective gap is(1/2)Σλ_i c_{i,k}², it is at mostρ^{2k} times the initial gap. With spectral interval[μ,L], the optimal constant worst-case step is2/(μ+L), balancing1−ημ and−(1−ηL). The worst factor becomes(L−μ)/(L+μ)=(κ−1)/(κ+1), where κ=L/μ. Absolute value of an affine multiplier is largest at an interval endpoint, so intermediate eigenvalues do not worsen that bound. If μ=L, step1/L gives zero factor and solves the quadratic in one step.

Poor conditioning makes scalar steps slow. For A=diag(1,100), using η=1/L=.01 kills the stiff mode immediately but leaves the slow factor.99. After200 steps an initial slow component one is about.13398. The balanced step2/101 instead gives both magnitudes99/101, reducing the full error faster while allowing sign alternation in the stiff mode. A step.1 has stiff factor−9 and diverges even though the low-curvature direction behaves reasonably. One coordinate’s improvement cannot certify the full update.

For z=Sx and g(z)=f(S⁻¹z), the transformed Hessian is S⁻ᵀA S⁻¹. Taking S=diag(1,10) for diag(1,100) makes it identity. A unit gradient step in z solves this quadratic immediately; mapped back, it is x_new=x−S⁻¹S⁻ᵀ∇f(x), a preconditioned update. The transformation preserves the objective’s meaning when every term and parameter interpretation are transformed consistently. It changes the coordinate metric and the algorithm; it is not a claim that every feature normalisation automatically improves every statistical model.

A positive-semidefinite singular quadratic has different conditions. If b lies in the column space of A, minimisers form x*+N(A); positive eigenmodes can converge with suitable steps while null components of the starting point remain unchanged. If b has a nonzero component along a null vector n, the objective along tn contains the unbounded linear term−t bᵀn, so there is no finite minimiser. Simply inverting nonzero curvature or adding a small diagonal must not conceal that problem-level distinction.

Newton’s method uses a quadratic local model and solves H(x)p=−∇f(x), then proposes x+p. Solve the linear system rather than explicitly forming H⁻¹; this preserves the mathematical action while allowing appropriate numerical solvers. For a symmetric positive-definite H and nonzero gradient, gᵀp=−pᵀHp<0, so the Newton direction descends locally. A full unit step still needs domain and finite-decrease checks away from a regime where a convergence theorem applies.

A singular Hessian can give no unique direction or an inconsistent Newton system. In the flat convex example H=diag(2,0),g=(−2,0), a minimum-norm solution p=(1,0) exists; starting at(0,5) reaches the minimiser(1,5), preserving the flat coordinate. Minimum-norm direction is not the same as minimum-norm minimiser. If the gradient has a component outside the Hessian’s image, no exact solution exists. A least-squares direction then solves a different local approximation and requires a descent check before use.

Damping can replace H by H+δI, chosen to be positive definite, to obtain a descent direction. This modifies the local step model; it does not automatically mean the original objective has been replaced by a ridge-regularised objective. If regularisation is actually added to f, its gradient changes too and must be differentiated consistently. For nonconvex functions, safeguards can prevent an uphill proposal while still offering no unconditional global solution theorem.

Coordinate descent updates one parameter while holding others fixed. For the positive-definite quadratic, minimising along coordinate i gives x_i_new=x_i−g_i/A_{ii}, since the one-dimensional curvature is A_{ii}>0. Each exact coordinate update decreases f by g_i²/(2A_{ii}), unless that coordinate gradient is zero. A cyclic sweep uses newly updated values in later coordinates, so it is not identical to a simultaneous diagonal-preconditioned gradient step using the old vector everywhere. Convergence conclusions require an appropriate update schedule and problem assumptions, not just coordinatewise progress in a finite run.

For A=[[3,1],[1,3]],b=(2,−1), starting at zero, coordinate-one minimisation gives x₁=2/3. The next coordinate uses this fresh value and solves x₁+3x₂=−1, yielding x₂=−5/9. The sweep decreases the objective but does not reach(7/8,−5/8) immediately; future sweeps continue. Newton solves the coupled system at once, while gradient descent uses one scalar step across all directions. These methods spend different computational effort per update, so iteration counts alone are not a fair cost comparison.

Near a nondegenerate minimiser, Newton can have quadratic local convergence when the Hessian is sufficiently regular, invertible nearby, and the start lies in the valid neighbourhood. This lesson states that qualified result rather than asserting it for singular minima, distant starts or arbitrary networks. The exact quadratic example is stronger and fully proved here because the local quadratic model equals the entire objective. Backtracking may help reach a suitable regime, but a theorem about the local regime is not itself a theorem about reaching it from every start.

Termination should name the accepted accuracy quantity. Objective change can be tiny because of rounding, flat directions or step damping. A small gradient can reflect objective scaling, as Lab3 demonstrates. A small update can be manufactured by a tiny step. If strong convexity, a curvature interval or another error bound is proved, translate the computed residual into the requested distance or gap and include numerical error allowances. Otherwise report the actual residual, step and reason for stopping as evidence with its stated scope.

Optimising a training objective also does not settle predictive usefulness. The objective may be misspecified, data may differ at evaluation, and a mathematically global training minimiser can generalise poorly. Those are later modelling and statistical questions. Here the complete outcome is the ability to derive a method’s update, check its domain and curvature assumptions, and distinguish a proved convergence statement from a finite numerical trace or useful heuristic.

Lab1 · Exact quadratic modes and a Newton solve

Download lab1_quadratic_modes.py

"""Eigenmodes determine the full constant-step interval of a quadratic."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)
A = np.array([[3.0,1.0], [1.0,3.0]])
b = np.array([2.0,-1.0])
optimum = np.linalg.solve(A, b)
eigenvalues = np.linalg.eigvalsh(A)
def objective(x):
    return 0.5*x@A@x-b@x
start = np.array([3.0,2.0])
print("Eigenvalues / unique optimum / optimal objective:", eigenvalues, optimum, objective(optimum))
print("eta      mode factors           error after 30      objective after 30")
for eta in [0.2, 1/3, 0.5, 0.55]:
    x = start.copy()
    history = [objective(x)]
    for _ in range(30):
        x -= eta*(A@x-b)
        history.append(objective(x))
    factors = 1-eta*eigenvalues
    error = np.linalg.norm(x-optimum)
    print(f"{eta:.6f}", factors, f"{error:.10e}", f"{objective(x):.10f}")
    if np.max(np.abs(factors)) < 1:
        assert error < 1e-5
        assert all(next_value <= value+1e-12 for value, next_value in zip(history, history[1:]))
    else:
        assert error > 1
print("Strict interval: 0 < eta < 2/lambda_max =", 2/eigenvalues[-1])
newton = start-np.linalg.solve(A, A@start-b)
print("Exact quadratic Newton result:", newton)
assert np.allclose(newton, optimum, atol=1e-12, rtol=0)

Eigenvalues / unique optimum / optimal objective: [2. 4.] [ 0.875 -0.625] -1.1875
eta      mode factors           error after 30      objective after 30
0.200000 [0.6 0.2] 7.8161433852e-08 -1.1875000000
0.333333 [ 0.333333 -0.333333] 1.6404273111e-14 -1.1875000000
0.500000 [ 0. -1.] 3.3587572106e+00 21.3750000000
0.550000 [-0.1 -1.2] 7.9728940561e+02 1271339.6050933360
Strict interval: 0 < eta < 2/lambda_max = 0.5
Exact quadratic Newton result: [ 0.875 -0.625]

Derive the optimum, eigenvalues and each multiplier before running. Explain the boundary’s persistent top mode, the oversized step’s growth and the exact quadratic Newton result. The finite trace illustrates the already derived all-start interval; it does not substitute for that proof.

Lab2 · Curvature conditioning and coordinates

Download lab2_scaling_conditioning.py

"""A coordinate change changes curvature and the effective gradient metric."""
import numpy as np
A = np.diag([1.0,100.0])
start = np.array([1.0,1.0])
print("Raw curvature eigenvalues / condition number:", np.diag(A), np.linalg.cond(A))
print("eta      steps      endpoint                norm")
for eta, steps in [(0.01,200), (2/101,200), (0.1,10)]:
    x = start.copy()
    for _ in range(steps):
        x -= eta*(A@x)
    print(eta, steps, x, np.linalg.norm(x))
    if eta == 0.1:
        assert np.linalg.norm(x) > 1e9
    else:
        assert np.linalg.norm(x) < np.linalg.norm(start)

# z=S*x, so x=S^-1*z; preserve the mathematical objective under this change.
S = np.diag([1.0,10.0])
inverse_S = np.diag([1.0,0.1])
transformed_A = inverse_S.T@A@inverse_S
z = S@start
assert np.allclose(transformed_A, np.eye(2))
z -= transformed_A@z  # eta_z=1 on identity curvature.
recovered = inverse_S@z
print("Transformed curvature / condition number:", transformed_A, np.linalg.cond(transformed_A))
print("One transformed-coordinate step, mapped back:", recovered)
assert np.allclose(recovered, 0, atol=1e-12)
preconditioned = start-inverse_S@inverse_S.T@(A@start)
assert np.allclose(preconditioned, recovered)
print("Same objective, different coordinate geometry; the equivalent raw update uses a matrix preconditioner.")

Raw curvature eigenvalues / condition number: [  1. 100.] 100.0
eta      steps      endpoint                norm
0.01 200 [0.13397967 0.        ] 0.13397967485796206
0.019801980198019802 200 [0.0183132 0.0183132] 0.0258987713130135
0.1 10 [3.4867844e-01 3.4867844e+09] 3486784401.0
Transformed curvature / condition number: [[1. 0.]
 [0. 1.]] 1.0
One transformed-coordinate step, mapped back: [0. 0.]
Same objective, different coordinate geometry; the equivalent raw update uses a matrix preconditioner.

Predict the slow factor for step.01, the balanced factors for2/101, and the unstable factor for.1. Verify the transformed objective’s identity Hessian and map the update back. Explain why one transformed step is a preconditioned update in the original coordinates.

Lab3 · Singular non-descent and stopping faults

Download lab3_newton_and_stopping_faults.py

"""Singular or indefinite curvature and small gradients need qualified handling."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)

H = np.diag([2.0,0.0])
b = np.array([2.0,0.0])
x = np.array([0.0,5.0])
gradient = H@x-b
try:
    np.linalg.solve(H, -gradient)
except np.linalg.LinAlgError:
    print("Singular Newton system: direct solve has no unique direction.")
direction, *_ = np.linalg.lstsq(H, -gradient, rcond=1e-12)
next_x = x+direction
print("Minimum-norm direction / resulting minimiser:", direction, next_x)
assert np.allclose(next_x, [1,5])  # Flat coordinate is preserved, not forced to zero.
print("Nonunique minima: first coordinate one, any second coordinate.")

def f(t):
    return t**4-3*t*t
t = 0.1
g, curvature = 4*t**3-6*t, 12*t*t-6
newton_direction = -g/curvature
print("Nonconvex Newton direction / gradient-dot-direction:", newton_direction, g*newton_direction)
print("Objective before / raw Newton step:", f(t), f(t+newton_direction))
assert g*newton_direction > 0 and f(t+newton_direction) > f(t)
# Replace a non-descent direction by -gradient; backtrack with explicit Armijo c.
descent, alpha, c = -g, 1.0, 1e-4
for _ in range(50):
    if f(t+alpha*descent) <= f(t)+c*alpha*g*descent:
        break
    alpha *= 0.5
else:
    raise RuntimeError("No accepted finite backtracking step")
print("Safeguarded step / objective:", alpha, f(t+alpha*descent))
assert f(t+alpha*descent) < f(t)

# Zero gradient is not sufficient for a nonconvex minimum.
print("Saddle x^2-y^2 at zero: gradient zero, value along (0,0.1) =", -0.1**2)
assert -0.1**2 < 0

coefficient, location, target = 1e-12, 0.0, 100.0
small_gradient = 2*coefficient*(location-target)
mu = 2*coefficient
gradient_tolerance = 1e-6
print("Scaled objective gradient / tolerance:", small_gradient, gradient_tolerance)
print("Naive gradient test passes / solution error:", abs(small_gradient)<gradient_tolerance, abs(location-target))
print("Strong-convexity error certificate ||gradient||/mu:", abs(small_gradient)/mu)
assert abs(small_gradient) < gradient_tolerance and abs(location-target) == 100
print("For distance tolerance 0.01, sufficient gradient threshold:", mu*0.01)
print("State which quantity termination certifies; objective scaling changes gradient thresholds.")

Singular Newton system: direct solve has no unique direction.
Minimum-norm direction / resulting minimiser: [1. 0.] [1. 5.]
Nonunique minima: first coordinate one, any second coordinate.
Nonconvex Newton direction / gradient-dot-direction: -0.10136054421768709 0.06041088435374151
Objective before / raw Newton step: -0.029900000000000006 -5.553238278345991e-06
Safeguarded step / objective: 1.0 -1.218589138944
Saddle x^2-y^2 at zero: gradient zero, value along (0,0.1) = -0.010000000000000002
Scaled objective gradient / tolerance: -2e-10 1e-06
Naive gradient test passes / solution error: True 100.0
Strong-convexity error certificate ||gradient||/mu: 100.0
For distance tolerance 0.01, sufficient gradient threshold: 2e-14
State which quantity termination certifies; objective scaling changes gradient thresholds.

Distinguish a minimum-norm direction from the resulting flat-family minimiser. Check the nonconvex Newton directional sign, the safeguarded Armijo acceptance, and the scaled objective’s distance certificate. Explain which error criterion a small objective gap could satisfy even while parameters remain far from their target.

Exercises1–12 are required. Optional Exercises13–14 add35 minutes beyond the twelve-hour core schedule.

Use convex-function and unconstrained-minimisation selections in the authors’ Convex Optimization companion. The proofs above derive the particular supporting, descent and spectral bounds used by this lesson, and its labs make each numerical convention explicit.

Prove a convex example and a local-to-global certificate, derive the Lipschitz-gradient decrease bound, and analyse each quadratic eigenmode. Contrast gradient, cyclic coordinate and Newton updates with their costs and safeguards.

Exit task: For curvaturediag(1,100),state the universal interval0<η<.02,balanced step2/101 and its norm factor99/101. Explain whyη=.1 can appear successful from a first-mode-only start while failing generally, and why coordinate scaling changes the update metric.

Ready to move on: you can connect optimisation behaviour to stated objective, domain and curvature assumptions. Constrained optimisation next adds feasible directions, multipliers, KKT conditions and dual bounds. See the course overview.