Chapter 14
Optimization and Nonlinear Systems
Rendered from the uploaded full LaTeX source with KaTeX. No PDF, no PDF.js, no image extraction, and no raw LaTeX displayed.
After completing this chapter, the reader should be able to:
solve nonlinear systems using Newton, damped Newton, inexact Newton, and quasi-Newton methods;
derive Newton’s method for unconstrained optimization and distinguish it from Newton’s method for nonlinear systems;
apply line-search and trust-region globalization strategies;
implement gradient descent, nonlinear conjugate gradients, BFGS, DFP, and L-BFGS;
formulate and solve nonlinear least-squares problems using Gauss–Newton and Levenberg–Marquardt methods;
understand derivative-free optimization, including Nelder–Mead, coordinate search, pattern search, and Powell-type methods;
formulate constrained optimization problems and derive the KKT conditions;
understand SQP, penalty, barrier, interior-point, augmented Lagrangian, and ADMM ideas;
minimize parameter-dependent integrals using accurate quadrature rules;
differentiate quadrature-based objectives with respect to parameters;
connect residual minimization, Galerkin methods, inverse problems, and PDE-constrained optimization;
solve basic, advanced, and research-level exercises on nonlinear systems and optimization.
Nonlinear Systems
A nonlinear system has the form F(x)=0, \qquad F:\mathbb R^n\to\mathbb R^n. Newton’s method linearizes F at x_k: F(x_k+s) \approx F(x_k)+J_F(x_k)s, where J_F(x)= \left[ \frac{\partial F_i}{\partial x_j}(x) \right]_{i,j=1}^n. The Newton correction solves J_F(x_k)s_k=-F(x_k), and the update is x_{k+1}=x_k+s_k.
Caption.
Newton method for nonlinear systems
nonlinear map F, Jacobian J_F, initial guess x_0
For k=0,1,2,\ldots:
Solve J_F(x_k)s_k=-F(x_k)
x_{k+1}\gets x_k+s_k
If \|F(x_{k+1})\| and \|s_k\| are small:
Return x_{k+1}
Let F\in C^2 near a solution x_\ast, assume F(x_\ast)=0, \qquad J_F(x_\ast) \text{ is nonsingular}. Then, for x_0 sufficiently close to x_\ast, Newton’s method is well defined and converges quadratically: \|x_{k+1}-x_\ast\| \le C\|x_k-x_\ast\|^2.
Write the Taylor expansion F(x_k)=F(x_\ast)+J_F(x_k)(x_k-x_\ast)+r_k, where \|r_k\|\le C_1\|x_k-x_\ast\|^2. Since F(x_\ast)=0 and Newton solves J_F(x_k)(x_{k+1}-x_k)=-F(x_k), we obtain J_F(x_k)(x_{k+1}-x_\ast)=-r_k. For x_k close to x_\ast, J_F(x_k)^{-1} is uniformly bounded. Therefore \|x_{k+1}-x_\ast\| \le \|J_F(x_k)^{-1}\|\|r_k\| \le C\|x_k-x_\ast\|^2.
□
Damped and Globalized Newton Methods
Pure Newton steps can fail far from the solution. Damped Newton uses x_{k+1}=x_k+\alpha_k s_k, \qquad 0<\alpha_k\le1. The step length \alpha_k is chosen to reduce a merit function, often \Phi(x)=\frac12\|F(x)\|_2^2.
The Armijo condition requires \Phi(x_k+\alpha s_k) \le \Phi(x_k)+c\alpha\nabla\Phi(x_k)^Ts_k, \qquad 0<c<1.
Caption.
Damped Newton method with backtracking
F, J_F, initial guess x_0, constants 0<c<1, 0<\rho<1
For k=0,1,2,\ldots:
Solve J_F(x_k)s_k=-F(x_k)
\alpha\gets1
While \Phi(x_k+\alpha s_k)>\Phi(x_k)+c\alpha\nabla\Phi(x_k)^Ts_k:
\alpha\gets\rho\alpha
x_{k+1}\gets x_k+\alpha s_k
Inexact Newton and Newton–Krylov Methods
For large nonlinear systems, the Newton linear system may be solved approximately: J_F(x_k)s_k\approx -F(x_k). An inexact Newton condition is \|J_F(x_k)s_k+F(x_k)\| \le \eta_k\|F(x_k)\|, \qquad 0\le\eta_k<1. Newton–Krylov methods solve the Newton system using Krylov methods such as GMRES, often requiring only Jacobian-vector products: J_F(x)v\approx \frac{F(x+\varepsilon v)-F(x)}{\varepsilon}.
For discretized nonlinear PDEs, n can be huge. Forming the Jacobian explicitly may be expensive or impossible. Newton–Krylov methods use residual evaluations, preconditioning, and matrix-free Jacobian-vector products.
Broyden and Quasi-Newton Methods for Systems
Broyden’s method approximates the Jacobian by a matrix B_k. The step solves B_ks_k=-F(x_k), then updates x_{k+1}=x_k+s_k. Let y_k=F(x_{k+1})-F(x_k). The secant condition is B_{k+1}s_k=y_k. The good Broyden update is B_{k+1} = B_k+ \frac{(y_k-B_ks_k)s_k^T}{s_k^Ts_k}.
The update B_{k+1} = B_k+ \frac{(y_k-B_ks_k)s_k^T}{s_k^Ts_k} satisfies B_{k+1}s_k=y_k.
Multiply by s_k: B_{k+1}s_k = B_ks_k+ \frac{(y_k-B_ks_k)s_k^Ts_k}{s_k^Ts_k} = B_ks_k+y_k-B_ks_k = y_k.
□
Unconstrained Optimization
The unconstrained optimization problem is \min_{x\in\mathbb R^n} f(x). A necessary first-order condition is \nabla f(x_\ast)=0. If f\in C^2, a second-order sufficient condition is \nabla f(x_\ast)=0, \qquad \nabla^2 f(x_\ast)\succ0.
If f is differentiable and x_\ast is a local minimizer in the interior of the domain, then \nabla f(x_\ast)=0.
For any direction d, define \phi(t)=f(x_\ast+td). Since x_\ast is a local minimizer, t=0 is a local minimizer of \phi. Therefore \phi'(0)=0. But \phi'(0)=\nabla f(x_\ast)^Td. Since this holds for every direction d, we must have \nabla f(x_\ast)=0.
□
Gradient Descent
Gradient descent uses the direction of steepest decrease: x_{k+1}=x_k-\alpha_k\nabla f(x_k). For a fixed step size, convergence requires conditions on \alpha_k. If \nabla f is Lipschitz with constant L, then 0<\alpha<\frac{2}{L} is a natural stability range for strongly convex quadratic problems.
Suppose \nabla f is Lipschitz continuous with constant L. Then f(x+s) \le f(x)+\nabla f(x)^Ts+\frac{L}{2}\|s\|^2. In particular, for s=-\alpha\nabla f(x), f(x-\alpha\nabla f(x)) \le f(x)-\alpha\left(1-\frac{\alpha L}{2}\right)\|\nabla f(x)\|^2.
Use the integral identity f(x+s)-f(x) = \int_0^1 \nabla f(x+ts)^Ts\,\dd t. Add and subtract \nabla f(x): f(x+s)-f(x) = \nabla f(x)^Ts+ \int_0^1 \left[\nabla f(x+ts)-\nabla f(x)\right]^Ts\,\dd t. By Lipschitz continuity, \|\nabla f(x+ts)-\nabla f(x)\|\le Lt\|s\|. Thus f(x+s)-f(x) \le \nabla f(x)^Ts+ \int_0^1 Lt\|s\|^2\,\dd t = \nabla f(x)^Ts+\frac{L}{2}\|s\|^2. Substitute s=-\alpha\nabla f(x).
□
Line Search Methods
A line-search method chooses a search direction p_k and a step length \alpha_k>0. The update is x_{k+1}=x_k+\alpha_k p_k. A descent direction satisfies \nabla f(x_k)^Tp_k<0. The Armijo condition is f(x_k+\alpha p_k) \le f(x_k)+c_1\alpha\nabla f(x_k)^Tp_k, \qquad 0<c_1<1. The Wolfe curvature condition is \nabla f(x_k+\alpha p_k)^Tp_k \ge c_2\nabla f(x_k)^Tp_k, \qquad c_1<c_2<1.
Newton’s Method for Optimization
Newton’s method for optimization applies Newton’s method to \nabla f(x)=0. The Newton step solves \nabla^2 f(x_k)s_k=-\nabla f(x_k), and x_{k+1}=x_k+s_k. If H_k=\nabla^2 f(x_k) is positive definite, then s_k is a descent direction: \nabla f(x_k)^Ts_k = -s_k^TH_ks_k<0.
If \nabla^2f(x_k) is symmetric positive definite, then the Newton direction s_k=-\nabla^2f(x_k)^{-1}\nabla f(x_k) is a descent direction unless \nabla f(x_k)=0.
Let H_k=\nabla^2f(x_k) and g_k=\nabla f(x_k). Since H_ks_k=-g_k, we have g_k^Ts_k=-s_k^TH_ks_k. If g_k\ne0, then s_k\ne0. Since H_k\succ0, s_k^TH_ks_k>0. Therefore g_k^Ts_k<0.
□
Trust-Region Methods
Trust-region methods minimize a local quadratic model m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks inside a ball: \|s\|\le\Delta_k. The trust-region subproblem is \min_{\|s\|\le\Delta_k}m_k(s). The quality of a step is measured by \rho_k= \frac{f(x_k)-f(x_k+s_k)} {m_k(0)-m_k(s_k)}. If \rho_k is large, the model is reliable and the radius can be increased. If \rho_k is small or negative, the radius is decreased.
Caption.
Trust-region framework
initial point x_0, radius \Delta_0
For k=0,1,2,\ldots:
Build model m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks
Approximately solve \min_{\|s\|\le\Delta_k}m_k(s)
Compute \rho_k=\dfrac{f(x_k)-f(x_k+s_k)}{m_k(0)-m_k(s_k)}
If \rho_k is sufficiently positive:
x_{k+1}\gets x_k+s_k
Else:
x_{k+1}\gets x_k
Update \Delta_k according to the value of \rho_k
Conjugate Gradient Methods for Optimization
For a quadratic function f(x)=\frac12x^TAx-b^Tx, \qquad A=A^T\succ0, minimization is equivalent to solving Ax=b. Conjugate gradient constructs A-conjugate directions: p_i^TAp_j=0, \qquad i\ne j. For nonlinear optimization, nonlinear conjugate gradient uses p_{k+1}=-g_{k+1}+\beta_kp_k, where g_k=\nabla f(x_k). Common formulas are: \beta_k^{FR}= \frac{g_{k+1}^Tg_{k+1}}{g_k^Tg_k}, and \beta_k^{PR}= \frac{g_{k+1}^T(g_{k+1}-g_k)}{g_k^Tg_k}.
Quasi-Newton Methods: DFP, BFGS, and L-BFGS
Quasi-Newton methods approximate the Hessian or inverse Hessian using gradient differences. Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant equation is B_{k+1}s_k=y_k. The BFGS update for a Hessian approximation is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. The inverse BFGS update is H_{k+1} = \left(I-\rho_ks_ky_k^T\right) H_k \left(I-\rho_ky_ks_k^T\right) + \rho_ks_ks_k^T, \qquad \rho_k=\frac1{y_k^Ts_k}. The DFP inverse update is H_{k+1} = H_k+ \frac{s_ks_k^T}{s_k^Ty_k} - \frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}.
If B_k\succ0 and y_k^Ts_k>0, then the BFGS update satisfies B_{k+1}\succ0.
For any nonzero z, z^TB_{k+1}z = z^TB_kz - \frac{(z^TB_ks_k)^2}{s_k^TB_ks_k} + \frac{(z^Ty_k)^2}{y_k^Ts_k}. The first two terms are nonnegative by the Cauchy–Schwarz inequality in the B_k-inner product, and the last term is nonnegative. If the expression were zero, both terms must vanish in a way forcing z to be simultaneously proportional to s_k and orthogonal to y_k, contradicting y_k^Ts_k>0. Hence z^TB_{k+1}z>0.
□
L-BFGS stores only a small number of pairs (s_k,y_k), making it practical for large-scale optimization.
Nonlinear Least Squares
A nonlinear least-squares problem has the form \min_x \frac12\|r(x)\|_2^2, \qquad r:\mathbb R^n\to\mathbb R^m. The gradient is \nabla f(x)=J(x)^Tr(x), where J(x)=Dr(x). The Hessian is \nabla^2f(x)=J(x)^TJ(x)+\sum_{i=1}^{m}r_i(x)\nabla^2r_i(x). Gauss–Newton neglects the second term: J(x_k)^TJ(x_k)s_k=-J(x_k)^Tr(x_k). Levenberg–Marquardt solves \left(J^TJ+\lambda I\right)s=-J^Tr.
Caption.
Levenberg–Marquardt method
residual r(x), Jacobian J(x), initial x_0, damping \lambda_0>0
For k=0,1,2,\ldots:
Solve (J_k^TJ_k+\lambda_kI)s_k=-J_k^Tr_k
If \|r(x_k+s_k)\|<\|r(x_k)\|:
Accept x_{k+1}\gets x_k+s_k, decrease \lambda_k
Else:
Reject step, increase \lambda_k
Optimization of Parameter-Dependent Integrals
Many scientific problems require minimizing an objective of the form \mathcal J(\theta) = \int_a^b \Phi(x,\theta)\,\dd x, \qquad \theta\in\mathbb R^p. Examples include residual minimization, \mathcal J(\theta) = \int_a^b |R(x,\theta)|^2\,\dd x, data fitting, \mathcal J(\theta) = \int_a^b |u(x;\theta)-u_{\mathrm{data}}(x)|^2w(x)\,\dd x, and regularized inverse problems, \mathcal J(\theta) = \int_a^b |u(x;\theta)-d(x)|^2\,\dd x + \lambda\|\theta\|^2.
A quadrature rule gives \mathcal J(\theta) \approx \mathcal J_Q(\theta) = \sum_{j=1}^{q} w_j\Phi(x_j,\theta). Thus the continuous optimization problem is replaced by a finite-dimensional optimization problem: \min_{\theta}\mathcal J_Q(\theta).
If the quadrature error is larger than the optimizer tolerance, the algorithm may minimize the wrong objective. Increase the quadrature order until changes in \mathcal J_Q, \nabla\mathcal J_Q, and the minimizer are negligible.
Quadrature Rules for Integral Objectives
For smooth integrands on [a,b], Gauss–Legendre quadrature is often efficient: \int_a^b \Phi(x,\theta)\,\dd x \approx \frac{b-a}{2} \sum_{j=1}^{q} \omega_j \Phi\left( \frac{b-a}{2}\xi_j+\frac{a+b}{2}, \theta \right), where \xi_j,\omega_j are Gauss–Legendre nodes and weights on [-1,1].
Composite high-order quadrature uses elements a=x_0<x_1<\cdots<x_M=b and applies Gauss quadrature on each element: \mathcal J_Q(\theta) = \sum_{e=0}^{M-1} \frac{h_e}{2} \sum_{\ell=1}^{q} \omega_\ell \Phi\left( x_{e,c}+\frac{h_e}{2}\xi_\ell,\theta \right).
For two-dimensional parameter-dependent integrals, \mathcal J(\theta) = \int_\Omega \Phi(x,y,\theta)\,\dd x\,\dd y, tensor-product quadrature on rectangles is \sum_{r=1}^{q}\sum_{s=1}^{q} w_rw_s \Phi(x_r,y_s,\theta).
Caption.
Quadrature-based minimization of an integral objective
integrand \Phi(x,\theta), interval [a,b], quadrature nodes and weights, optimizer
Build
\item \mathcal J_Q(\theta) \item = \item \sum_{j=1}^{q}w_j\Phi(x_j,\theta) \item
If available, build
\item \nabla_\theta\mathcal J_Q(\theta) \item = \item \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta) \item
Minimize \mathcal J_Q(\theta) using BFGS, trust-region, Gauss–Newton, or derivative-free methods
Increase quadrature order q and repeat to verify quadrature convergence
Return optimized parameters \theta_\ast
Differentiating Integral Objectives
If \Phi is sufficiently smooth and differentiation under the integral sign is valid, then \nabla_\theta \mathcal J(\theta) = \int_a^b \nabla_\theta\Phi(x,\theta)\,\dd x. The quadrature gradient is \nabla_\theta \mathcal J_Q(\theta) = \sum_{j=1}^{q} w_j\nabla_\theta\Phi(x_j,\theta). Similarly, the Hessian is \nabla_\theta^2 \mathcal J_Q(\theta) = \sum_{j=1}^{q} w_j\nabla_\theta^2\Phi(x_j,\theta).
For residual least squares, \mathcal J(\theta)= \frac12\int_a^b R(x,\theta)^2\,\dd x, the gradient is \nabla_\theta\mathcal J(\theta) = \int_a^b R(x,\theta)\nabla_\theta R(x,\theta)\,\dd x. The Gauss–Newton Hessian approximation is H_{GN}(\theta) = \int_a^b \nabla_\theta R(x,\theta) \nabla_\theta R(x,\theta)^T\,\dd x. By quadrature, H_{GN,Q}(\theta) = \sum_{j=1}^{q} w_j \nabla_\theta R(x_j,\theta) \nabla_\theta R(x_j,\theta)^T.
Let \mathcal J_Q(\theta) = \frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2. Then \nabla_\theta\mathcal J_Q(\theta) = \sum_{j=1}^{q} w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Differentiate term by term: \nabla_\theta \left[ \frac12 w_jR(x_j,\theta)^2 \right] = w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta). Summing over j gives the formula.
□
Residual Minimization for Differential Equations
Let u(x;\theta) be a trial function depending on parameters \theta, and let \mathcal L u=f be a differential equation. Define the residual R(x,\theta)=\mathcal L u(x;\theta)-f(x). A least-squares residual objective is \mathcal J(\theta) = \int_\Omega |R(x,\theta)|^2\,\dd x + \lambda P(\theta), where P is a penalty or regularizer.
A quadrature version is \mathcal J_Q(\theta) = \sum_{j=1}^{q} w_j|R(x_j,\theta)|^2+\lambda P(\theta). This formulation appears in: \text{least-squares finite elements}, \qquad \text{spectral residual methods}, \text{physics-informed neural networks}, \qquad \text{parameterized trial methods}.
Nelder–Mead Simplex Method
Nelder–Mead is a derivative-free method for \min_{x\in\mathbb R^n} f(x). It maintains a simplex of n+1 vertices: x_1,\ldots,x_{n+1}. Assume they are ordered so that f(x_1)\le f(x_2)\le\cdots\le f(x_{n+1}). The best point is x_1, and the worst point is x_{n+1}. Define the centroid of all points except the worst: \bar x=\frac1n\sum_{i=1}^{n}x_i.
The reflection point is x_r=\bar x+\alpha(\bar x-x_{n+1}), \qquad \alpha>0. The expansion point is x_e=\bar x+\gamma(x_r-\bar x), \qquad \gamma>1. The outside contraction point is x_c^{out}=\bar x+\rho(x_r-\bar x), \qquad 0<\rho<1. The inside contraction point is x_c^{in}=\bar x-\rho(\bar x-x_{n+1}). If contraction fails, shrink all points toward the best: x_i\leftarrow x_1+\sigma(x_i-x_1), \qquad i=2,\ldots,n+1, \qquad 0<\sigma<1. Common coefficients are \alpha=1, \qquad \gamma=2, \qquad \rho=\frac12, \qquad \sigma=\frac12.
Caption.
Nelder–Mead simplex method
initial simplex x_1,\ldots,x_{n+1}
For k=0,1,2,\ldots:
Order vertices so that f(x_1)\le\cdots\le f(x_{n+1})
Compute centroid \bar x=(1/n)\sum_{i=1}^{n}x_i
Reflect x_r=\bar x+\alpha(\bar x-x_{n+1})
If f(x_1)\le f(x_r)<f(x_n):
Replace x_{n+1}\gets x_r
Compute expansion x_e=\bar x+\gamma(x_r-\bar x)
Replace worst by x_e if f(x_e)<f(x_r), otherwise by x_r
Else:
Compute inside or outside contraction
If contraction improves the simplex:
Replace the worst point by the contraction point
Else:
Shrink x_i\gets x_1+\sigma(x_i-x_1), i=2,\ldots,n+1
If simplex diameter and function spread are small:
Return best point x_1
Nelder–Mead is popular because it is simple and derivative-free, but it has weak general convergence guarantees in high dimensions. It is best used for small to moderate dimension, noisy objectives, expensive black-box functions, or as a preliminary optimizer.
Other Derivative-Free Methods
Derivative-free optimization is useful when gradients are unavailable, unreliable, or too expensive.
- Coordinate search.
-
Optimize along coordinate directions: x_{k+1}=x_k+\alpha_k e_i if this decreases the objective.
- Pattern search.
-
Search over a set of directions d\in\mathcal D_k, accepting a point if f(x_k+\alpha_k d)<f(x_k).
- Powell-type methods.
-
Use conjugate direction ideas without derivatives.
- Simulated annealing.
-
Accepts occasional uphill moves with probability depending on a temperature parameter: P(\text{accept})\approx e^{-\Delta f/T}.
- Genetic algorithms.
-
Use populations, selection, crossover, and mutation.
- Particle swarm optimization.
-
Moves particles according to personal and global best locations.
Use derivative-free methods when the objective is nonsmooth, noisy, black-box, or available only through simulations. If reliable gradients are available, gradient, quasi-Newton, or Newton-type methods are usually more efficient.
Constrained Optimization and KKT Conditions
Consider \min_x f(x) subject to equality constraints c(x)=0 and inequality constraints g(x)\le0. The Lagrangian is \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are: \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0, g(x)\le0, \mu\ge0, \mu_i g_i(x)=0 \qquad \text{for all }i.
Under a suitable constraint qualification, if x_\ast is a local minimizer of the constrained problem, then there exist multipliers \lambda_\ast and \mu_\ast\ge0 satisfying the KKT conditions.
The proof is based on separating feasible first-order directions from descent directions. At a constrained local minimum, no feasible first-order direction can produce strict decrease of f. Under a constraint qualification, this geometric separation yields multipliers \lambda_\ast and \mu_\ast\ge0 such that the gradient of the Lagrangian vanishes in x. Feasibility and complementarity follow from the primal constraints and the fact that inactive inequalities have zero multipliers.
□
Sequential Quadratic Programming
Sequential quadratic programming solves a constrained nonlinear problem by successive quadratic approximations: \min_s \frac12s^TB_ks+\nabla f(x_k)^Ts subject to linearized constraints: c(x_k)+J_c(x_k)s=0, g(x_k)+J_g(x_k)s\le0. The matrix B_k approximates the Hessian of the Lagrangian: \nabla_{xx}^2\mathcal L(x_k,\lambda_k,\mu_k).
Penalty, Barrier, and Interior-Point Methods
A quadratic penalty method for equality constraints minimizes f(x)+\frac{\rho}{2}\|c(x)\|^2. As \rho\to\infty, constraint violations are penalized more strongly, but the problem may become ill-conditioned.
For inequality constraints g_i(x)<0, a logarithmic barrier method minimizes f(x)-\mu\sum_i\log(-g_i(x)), \qquad \mu>0. Interior-point methods decrease \mu while approximately minimizing the barrier problem.
Augmented Lagrangian and ADMM
The augmented Lagrangian for equality constraints is \mathcal L_\rho(x,\lambda) = f(x)+\lambda^Tc(x)+\frac{\rho}{2}\|c(x)\|^2. It combines multiplier information with penalty stabilization.
ADMM is useful for separable problems: \min_{x,z} f(x)+g(z) \qquad \text{subject to} \qquad Ax+Bz=c. The iterations alternate minimization in x and z, followed by multiplier updates.
Optimization with Noisy or Expensive Objectives
When f(x) is noisy or expensive, classical derivative-based methods may be unreliable. Useful strategies include: \text{sample averaging}, \qquad \text{surrogate models}, \qquad \text{Bayesian optimization}, \text{trust-region derivative-free models}, \qquad \text{stochastic approximation}. For integral objectives computed by quadrature, noise can come from insufficient quadrature, stochastic sampling, discretization error, or simulation tolerance.
Adjoint Methods for Parameter Optimization
Suppose a state u(\theta) is defined by A(\theta)u(\theta)=b(\theta), and the objective is J(\theta)=\Psi(u(\theta),\theta). Direct differentiation can be expensive when \theta has many components. The adjoint method introduces \lambda satisfying A(\theta)^T\lambda=\Psi_u(u,\theta). Then gradients with respect to \theta can be computed without solving one sensitivity equation per parameter. This is central in inverse problems, PDE-constrained optimization, optimal control, and data assimilation.
Practical Comparison of Methods
- Newton for systems.
-
Fast local convergence when the Jacobian is accurate and nonsingular.
- Damped Newton.
-
More robust global behavior than pure Newton.
- Newton–Krylov.
-
Essential for very large nonlinear systems, especially discretized PDEs.
- Gradient descent.
-
Simple but often slow and sensitive to scaling.
- Newton optimization.
-
Fast near a minimizer when the Hessian is positive definite.
- BFGS/L-BFGS.
-
Strong general-purpose methods when gradients are available.
- Trust region.
-
Robust when curvature is indefinite or line search is unreliable.
- Gauss–Newton/Levenberg–Marquardt.
-
Natural for nonlinear least squares and residual minimization.
- Nelder–Mead.
-
Derivative-free and simple. Useful for small black-box problems but not ideal for large-scale smooth optimization.
- SQP/interior point.
-
Standard choices for constrained smooth nonlinear optimization.
- Quadrature-based optimization.
-
Use when objectives are integrals depending on parameters. Quadrature accuracy must be tied to optimization tolerance.
Exercises
The following exercise bank is intentionally large. Basic problems test definitions, computations, and essential formulas. Starred exercises require proofs, derivations, algorithm design, or advanced optimization analysis. Problems marked \star, \star\star, and \star\star\star are progressively harder.
Basic problems
Derive Newton’s method for solving F(x)=0.
Define the Jacobian matrix of F:\mathbb R^n\to\mathbb R^n.
Write the damped Newton update.
For a nonlinear system, define the merit function \Phi(x)=\frac12\|F(x)\|^2.
State the good Broyden update.
State the first-order necessary condition for unconstrained minimization.
Write the gradient descent iteration.
Derive Newton’s method for minimizing f(x).
Define a descent direction.
State the Armijo condition.
State the Wolfe curvature condition.
Write the trust-region subproblem.
State the BFGS Hessian update.
Explain why L-BFGS is useful for large-scale problems.
Derive the Gauss–Newton equations for nonlinear least squares.
Write the Levenberg–Marquardt linear system.
Give an example of an optimization objective defined by an integral with parameters.
Approximate \mathcal J(\theta)=\int_a^b \Phi(x,\theta)\,\dd x using a quadrature rule.
Write the quadrature approximation to \nabla_\theta \mathcal J(\theta).
Write a least-squares residual objective \int |R(x,\theta)|^2\,\dd x.
How many vertices does a Nelder–Mead simplex have in \mathbb R^n?
Write the Nelder–Mead reflection formula.
Write the Nelder–Mead shrink formula.
State the KKT conditions for equality and inequality constrained optimization.
Write a logarithmic barrier for constraints g_i(x)<0.
Write the augmented Lagrangian for equality constraints c(x)=0.
Explain the purpose of an adjoint method in parameter optimization.
Intermediate problems \star
Prove the referenced result.
Show that the Newton direction for F(x)=0 is a descent direction for \Phi(x)=\frac12\|F(x)\|^2 under suitable nonsingularity assumptions.
Prove the referenced result.
Prove the referenced result.
Prove that if \nabla f(x_\ast)=0 and \nabla^2f(x_\ast)\succ0, then x_\ast is a strict local minimizer.
Prove the referenced result.
Prove the referenced result.
Derive the exact line-search step length for minimizing a quadratic along a direction.
Explain why steepest descent may zigzag on ill-conditioned quadratic functions.
Derive the trust-region ratio \rho_k= \frac{f(x_k)-f(x_k+s_k)}{m_k(0)-m_k(s_k)}.
Derive the Cauchy point for a trust-region method.
Derive the Fletcher–Reeves and Polak–Ribiere formulas.
Show that the BFGS update satisfies the secant equation.
Prove the referenced result.
Verify that the DFP inverse update satisfies the inverse secant condition.
Derive the exact Hessian of a nonlinear least-squares objective and identify the Gauss–Newton approximation.
Explain Levenberg–Marquardt as a regularized Gauss–Newton method.
Prove the referenced result.
Derive the Gauss–Newton system for minimizing \frac12\int_a^b R(x,\theta)^2\,\dd x.
Design a quadrature refinement test for an integral optimization objective.
Derive the centroid used in the Nelder–Mead method.
Explain reflection, expansion, contraction, and shrink in Nelder–Mead.
Derive coordinate descent for a separable quadratic objective.
Derive the KKT conditions for one equality and one inequality constraint.
Derive the SQP quadratic subproblem from a second-order Lagrangian approximation.
Compute the gradient and Hessian of a logarithmic barrier objective.
Derive multiplier updates for the augmented Lagrangian method.
Advanced problems \star\star
State and prove a Newton–Kantorovich theorem for nonlinear systems.
Analyze how the forcing term \eta_k affects inexact Newton convergence.
Design a matrix-free Newton–Krylov method for a nonlinear residual arising from a PDE discretization.
Explain how preconditioning changes the efficiency of Newton–Krylov methods.
Prove a global convergence result for descent methods with Wolfe line search under standard assumptions.
Prove that a trust-region method has accumulation points satisfying first-order optimality under standard assumptions.
Derive the dogleg method for trust-region least squares.
Derive the symmetric rank-one quasi-Newton update and compare it with BFGS.
Derive the L-BFGS two-loop recursion.
Analyze how variable scaling affects gradient descent, Newton, and BFGS.
Replace the squared residual by a Huber loss and derive the corresponding Gauss–Newton-type method.
Study variable projection for separable nonlinear least-squares problems.
Relate quadrature error to stopping criteria in optimization of integral objectives.
Design an adaptive quadrature strategy inside a BFGS method.
Compare analytic differentiation, automatic differentiation, and finite differences for quadrature-based objectives.
Formulate a parameterized residual minimization method for an ODE and derive the quadrature-based objective and gradient.
Formulate a residual minimization method for a PDE using volume and boundary quadrature.
Study an example where Nelder–Mead stagnates or converges to a nonstationary point.
State convergence conditions for a pattern-search method.
Explain Bayesian optimization with a Gaussian-process surrogate and an acquisition function.
Derive the KKT linear system for an equality-constrained SQP subproblem.
Derive primal-dual Newton equations for inequality-constrained optimization with slack variables.
Derive ADMM for \min_{x,z} f(x)+g(z) \quad \text{subject to} \quad Ax+Bz=c.
Derive an adjoint gradient for A(\theta)u=b(\theta), \qquad J(\theta)=\Psi(u,\theta).
Formulate the KKT system for a PDE-constrained optimization problem.
Explain Pareto optimality and scalarization for multiobjective optimization.
Research-level problems \star\star\star
Develop a complete convergence theory for damped Newton with an Armijo line search.
Compare exact, dogleg, truncated CG, and Lanczos methods for the trust-region subproblem.
Study saddle points, negative curvature, and escape mechanisms in nonconvex optimization.
Analyze stochastic gradient descent, variance reduction, and adaptive methods such as Adam.
Develop a derivative-free trust-region method based on interpolation models.
Design a surrogate-assisted optimizer for an expensive simulation-based objective.
Develop certified bounds for minimizers of quadrature-based integral objectives.
Design an adaptive quadrature method that refines where a parameterized residual is large.
Compare quadrature-based residual minimization using neural trial functions with Galerkin finite elements.
Formulate optimization of residual integrals for a fractional PDE with nonlocal memory terms.
Develop adjoint-based optimization for a large-scale time-dependent PDE.
Compare full-space and reduced-space SQP methods for equality-constrained optimization.
Study the linear algebra and preconditioning of primal-dual interior-point KKT systems.
Study subgradient, proximal gradient, and bundle methods for nonsmooth objectives.
Derive a proximal Newton method for composite optimization.
Derive first-order optimality conditions for an ODE-constrained optimal control problem.
Introduce shape derivatives and formulate a shape optimization problem for an elliptic PDE.
Study bilevel optimization and derive implicit differentiation through the lower level problem.
Formulate stochastic programming and robust optimization versions of an integral objective.
Design reproducible benchmarks comparing Newton, BFGS, L-BFGS, trust region, Levenberg–Marquardt, Nelder–Mead, SQP, interior point, and quadrature-based residual minimization.
Exercise solutions
The solutions below are converted from the uploaded LaTeX solution file. Open an accordion to view the full solution.
This chapter gives detailed worked solutions for the exercises in Chapter 14. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 14.1
Problem formulation.
Derive Newton’s method for solving F(x)=0.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.2
Problem formulation.
Define the Jacobian matrix of F:\mathbb R^n\to\mathbb R^n.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.3
Problem formulation.
Write the damped Newton update.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.4
Problem formulation.
For a nonlinear system, define the merit function \Phi(x)=\frac12\|F(x)\|^2.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.5
Problem formulation.
State the good Broyden update.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.6
Problem formulation.
State the first-order necessary condition for unconstrained minimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.7
Problem formulation.
Write the gradient descent iteration.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.8
Problem formulation.
Derive Newton’s method for minimizing f(x).
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.9
Problem formulation.
Define a descent direction.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.10
Problem formulation.
State the Armijo condition.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.11
Problem formulation.
State the Wolfe curvature condition.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.12
Problem formulation.
Write the trust-region subproblem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.13
Problem formulation.
State the BFGS Hessian update.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.14
Problem formulation.
Explain why L-BFGS is useful for large-scale problems.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.15
Problem formulation.
Derive the Gauss–Newton equations for nonlinear least squares.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.16
Problem formulation.
Write the Levenberg–Marquardt linear system.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.17
Problem formulation.
Give an example of an optimization objective defined by an integral with parameters.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.18
Problem formulation.
Approximate \mathcal J(\theta)=\int_a^b \Phi(x,\theta)\,\dd x using a quadrature rule.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.19
Problem formulation.
Write the quadrature approximation to \nabla_\theta \mathcal J(\theta).
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.20
Problem formulation.
Write a least-squares residual objective \int |R(x,\theta)|^2\,\dd x.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.21
Problem formulation.
How many vertices does a Nelder–Mead simplex have in \mathbb R^n?
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.22
Problem formulation.
Write the Nelder–Mead reflection formula.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.23
Problem formulation.
Write the Nelder–Mead shrink formula.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.24
Problem formulation.
State the KKT conditions for equality and inequality constrained optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For \min f(x) subject to c(x)=0,\qquad g(x)\le0, define \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0,\qquad g(x)\le0, \mu\ge0, \mu_i g_i(x)=0. These are necessary under a constraint qualification and sufficient for convex problems with convex inequalities and affine equalities.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.25
Problem formulation.
Write a logarithmic barrier for constraints g_i(x)<0.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.26
Problem formulation.
Write the augmented Lagrangian for equality constraints c(x)=0.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.27
Problem formulation.
Explain the purpose of an adjoint method in parameter optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.28
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.29
Problem formulation.
Show that the Newton direction for F(x)=0 is a descent direction for \Phi(x)=\frac12\|F(x)\|^2 under suitable nonsingularity assumptions.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.30
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.31
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.32
Problem formulation.
Prove that if \nabla f(x_\ast)=0 and \nabla^2f(x_\ast)\succ0, then x_\ast is a strict local minimizer.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.33
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.34
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.35
Problem formulation.
Derive the exact line-search step length for minimizing a quadratic along a direction.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.36
Problem formulation.
Explain why steepest descent may zigzag on ill-conditioned quadratic functions.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.37
Problem formulation.
Derive the trust-region ratio \rho_k= \frac{f(x_k)-f(x_k+s_k)}{m_k(0)-m_k(s_k)}.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.38
Problem formulation.
Derive the Cauchy point for a trust-region method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.39
Problem formulation.
Derive the Fletcher–Reeves and Polak–Ribiere formulas.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.40
Problem formulation.
Show that the BFGS update satisfies the secant equation.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.41
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.42
Problem formulation.
Verify that the DFP inverse update satisfies the inverse secant condition.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.43
Problem formulation.
Derive the exact Hessian of a nonlinear least-squares objective and identify the Gauss–Newton approximation.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.44
Problem formulation.
Explain Levenberg–Marquardt as a regularized Gauss–Newton method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.45
Problem formulation.
Prove the referenced result.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.46
Problem formulation.
Derive the Gauss–Newton system for minimizing \frac12\int_a^b R(x,\theta)^2\,\dd x.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.47
Problem formulation.
Design a quadrature refinement test for an integral optimization objective.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.48
Problem formulation.
Derive the centroid used in the Nelder–Mead method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.49
Problem formulation.
Explain reflection, expansion, contraction, and shrink in Nelder–Mead.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.50
Problem formulation.
Derive coordinate descent for a separable quadratic objective.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.51
Problem formulation.
Derive the KKT conditions for one equality and one inequality constraint.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For \min f(x) subject to c(x)=0,\qquad g(x)\le0, define \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0,\qquad g(x)\le0, \mu\ge0, \mu_i g_i(x)=0. These are necessary under a constraint qualification and sufficient for convex problems with convex inequalities and affine equalities.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.52
Problem formulation.
Derive the SQP quadratic subproblem from a second-order Lagrangian approximation.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.53
Problem formulation.
Compute the gradient and Hessian of a logarithmic barrier objective.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.54
Problem formulation.
Derive multiplier updates for the augmented Lagrangian method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.55
Problem formulation.
State and prove a Newton–Kantorovich theorem for nonlinear systems.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.56
Problem formulation.
Analyze how the forcing term \eta_k affects inexact Newton convergence.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.57
Problem formulation.
Design a matrix-free Newton–Krylov method for a nonlinear residual arising from a PDE discretization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.58
Problem formulation.
Explain how preconditioning changes the efficiency of Newton–Krylov methods.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.59
Problem formulation.
Prove a global convergence result for descent methods with Wolfe line search under standard assumptions.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.60
Problem formulation.
Prove that a trust-region method has accumulation points satisfying first-order optimality under standard assumptions.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.61
Problem formulation.
Derive the dogleg method for trust-region least squares.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.62
Problem formulation.
Derive the symmetric rank-one quasi-Newton update and compare it with BFGS.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.63
Problem formulation.
Derive the L-BFGS two-loop recursion.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.64
Problem formulation.
Analyze how variable scaling affects gradient descent, Newton, and BFGS.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.65
Problem formulation.
Replace the squared residual by a Huber loss and derive the corresponding Gauss–Newton-type method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.66
Problem formulation.
Study variable projection for separable nonlinear least-squares problems.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.67
Problem formulation.
Relate quadrature error to stopping criteria in optimization of integral objectives.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.68
Problem formulation.
Design an adaptive quadrature strategy inside a BFGS method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Let s_k=x_{k+1}-x_k, \qquad y_k=\nabla f(x_{k+1})-\nabla f(x_k). The secant condition is B_{k+1}s_k=y_k. The BFGS update is B_{k+1} = B_k - \frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k} + \frac{y_ky_k^T}{y_k^Ts_k}. If B_k\succ0 and y_k^Ts_k>0, then B_{k+1}\succ0. This preserves positive definiteness under a Wolfe line search.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.69
Problem formulation.
Compare analytic differentiation, automatic differentiation, and finite differences for quadrature-based objectives.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.70
Problem formulation.
Formulate a parameterized residual minimization method for an ODE and derive the quadrature-based objective and gradient.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.71
Problem formulation.
Formulate a residual minimization method for a PDE using volume and boundary quadrature.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.72
Problem formulation.
Study an example where Nelder–Mead stagnates or converges to a nonstationary point.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
In \mathbb R^n, Nelder–Mead maintains n+1 simplex vertices. After ordering f(x_1)\le\cdots\le f(x_{n+1}), compute the centroid excluding the worst point: \bar x=\frac1n\sum_{i=1}^{n}x_i. Reflection is x_r=\bar x+\alpha(\bar x-x_{n+1}). Expansion is x_e=\bar x+\gamma(x_r-\bar x). Contraction and shrink steps reduce the simplex if reflection fails: x_i\leftarrow x_1+\sigma(x_i-x_1). The method is derivative-free but has limited convergence guarantees in high dimension.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.73
Problem formulation.
State convergence conditions for a pattern-search method.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.74
Problem formulation.
Explain Bayesian optimization with a Gaussian-process surrogate and an acquisition function.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.75
Problem formulation.
Derive the KKT linear system for an equality-constrained SQP subproblem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For \min f(x) subject to c(x)=0,\qquad g(x)\le0, define \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0,\qquad g(x)\le0, \mu\ge0, \mu_i g_i(x)=0. These are necessary under a constraint qualification and sufficient for convex problems with convex inequalities and affine equalities.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.76
Problem formulation.
Derive primal-dual Newton equations for inequality-constrained optimization with slack variables.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.77
Problem formulation.
Derive ADMM for \min_{x,z} f(x)+g(z) \quad \text{subject to} \quad Ax+Bz=c.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.78
Problem formulation.
Derive an adjoint gradient for A(\theta)u=b(\theta), \qquad J(\theta)=\Psi(u,\theta).
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.79
Problem formulation.
Formulate the KKT system for a PDE-constrained optimization problem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For \min f(x) subject to c(x)=0,\qquad g(x)\le0, define \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0,\qquad g(x)\le0, \mu\ge0, \mu_i g_i(x)=0. These are necessary under a constraint qualification and sufficient for convex problems with convex inequalities and affine equalities.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.80
Problem formulation.
Explain Pareto optimality and scalarization for multiobjective optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.81
Problem formulation.
Develop a complete convergence theory for damped Newton with an Armijo line search.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.82
Problem formulation.
Compare exact, dogleg, truncated CG, and Lanczos methods for the trust-region subproblem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.83
Problem formulation.
Study saddle points, negative curvature, and escape mechanisms in nonconvex optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.84
Problem formulation.
Analyze stochastic gradient descent, variance reduction, and adaptive methods such as Adam.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.85
Problem formulation.
Develop a derivative-free trust-region method based on interpolation models.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.86
Problem formulation.
Design a surrogate-assisted optimizer for an expensive simulation-based objective.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.87
Problem formulation.
Develop certified bounds for minimizers of quadrature-based integral objectives.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.88
Problem formulation.
Design an adaptive quadrature method that refines where a parameterized residual is large.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.89
Problem formulation.
Compare quadrature-based residual minimization using neural trial functions with Galerkin finite elements.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.90
Problem formulation.
Formulate optimization of residual integrals for a fractional PDE with nonlocal memory terms.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Check both the singular kernel evaluation and the long-history summation; fractional errors often come from the memory term rather than the algebraic solver.
Exercise 14.91
Problem formulation.
Develop adjoint-based optimization for a large-scale time-dependent PDE.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.92
Problem formulation.
Compare full-space and reduced-space SQP methods for equality-constrained optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.93
Problem formulation.
Study the linear algebra and preconditioning of primal-dual interior-point KKT systems.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For \min f(x) subject to c(x)=0,\qquad g(x)\le0, define \mathcal L(x,\lambda,\mu) = f(x)+\lambda^Tc(x)+\mu^Tg(x). The KKT conditions are \nabla_x\mathcal L(x,\lambda,\mu)=0, c(x)=0,\qquad g(x)\le0, \mu\ge0, \mu_i g_i(x)=0. These are necessary under a constraint qualification and sufficient for convex problems with convex inequalities and affine equalities.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 14.94
Problem formulation.
Study subgradient, proximal gradient, and bundle methods for nonsmooth objectives.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.95
Problem formulation.
Derive a proximal Newton method for composite optimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.96
Problem formulation.
Derive first-order optimality conditions for an ODE-constrained optimal control problem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 14.97
Problem formulation.
Introduce shape derivatives and formulate a shape optimization problem for an elliptic PDE.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.98
Problem formulation.
Study bilevel optimization and derive implicit differentiation through the lower level problem.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
Use first-order and second-order expansions: f(x_k+s)=f(x_k)+\nabla f(x_k)^Ts+\frac12s^T\nabla^2f(x_k)s+O(\|s\|^3). Gradient methods choose descent directions satisfying \nabla f(x_k)^Tp_k<0. Newton and quasi-Newton methods solve local quadratic models, while constrained methods solve KKT systems. Trust-region methods minimize m_k(s)=f(x_k)+g_k^Ts+\frac12s^TB_ks subject to \|s\|\le\Delta_k.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.99
Problem formulation.
Formulate stochastic programming and robust optimization versions of an integral objective.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For an integral objective J(\theta)=\int_a^b\Phi(x,\theta)\,\dd x, choose quadrature nodes x_j and weights w_j: J_Q(\theta)=\sum_{j=1}^{q}w_j\Phi(x_j,\theta). If differentiation under the integral sign is valid, then \nabla_\theta J_Q(\theta) = \sum_{j=1}^{q}w_j\nabla_\theta\Phi(x_j,\theta). For least-squares residuals, J_Q(\theta)=\frac12\sum_{j=1}^{q}w_jR(x_j,\theta)^2, and \nabla J_Q(\theta)= \sum_{j=1}^{q}w_jR(x_j,\theta)\nabla_\theta R(x_j,\theta).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 14.100
Problem formulation.
Design reproducible benchmarks comparing Newton, BFGS, L-BFGS, trust region, Levenberg–Marquardt, Nelder–Mead, SQP, interior point, and quadrature-based residual minimization.
Method.
Use Newton linearization, first- and second-order optimality conditions, quasi-Newton secant equations, trust-region models, KKT systems, and quadrature-based objectives.
Detailed solution and justification.
For a nonlinear system F(x)=0, Taylor expansion gives F(x_k+s)=F(x_k)+J_F(x_k)s+O(\|s\|^2). Newton’s method sets the linear model equal to zero: J_F(x_k)s_k=-F(x_k), then updates x_{k+1}=x_k+s_k. For optimization, apply Newton’s method to \nabla f(x)=0. The step satisfies \nabla^2f(x_k)s_k=-\nabla f(x_k).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.