Study guide for Exam 4
Exam 4 covers nonlinear equations and optimization (Heath Chapters 5 and 6, as covered in lecture), through the basics of active-set methods. These questions organize the main ideas and simple calculations to review. Use the practice exam to gauge the expected depth. Penalty and barrier methods are not included.
Nonlinear Equations
Residuals and convergence
- How is a scalar equation or system written as $f(x)=0$? How can the number of solutions differ from that of a nonsingular linear system? What is a simple scalar root?
- What is the difference between the residual $f(x)$ and the error $x-x^*$? Near a simple root, how does $f'(x^*)$ relate them? Why does a small residual not necessarily imply an accurate root?
- What information do residual size, the change between iterates, and bracket width give as stopping tests? Why can a small change between iterates be misleading?
- What are linear, superlinear, and quadratic convergence, in terms of the errors $e_k=x_k-x^*$? How can you recognize them from an error sequence? What does local convergence mean?
- For $x_{k+1}=g(x_k)$ with $g(x^*)=x^*$, how does $g'(x^*)$ predict local convergence? What do its magnitude and sign tell you about the errors? Under suitable smoothness assumptions, what is special about $g'(x^*)=0$?
Scalar methods
- What assumptions make $[a,b]$ a valid bisection bracket? Be able to update the bracket using function signs and obtain a midpoint error bound. Does a valid bracket imply a unique root?
- How does Newton's method use a linear approximation of $f$? Be able to compute one step. What assumptions give local quadratic convergence, and why is convergence from an arbitrary starting point not guaranteed?
- How does the secant method approximate a derivative using two previous iterates? What function values can be reused, and what is its usual local order of convergence near a simple root?
- Compare bisection, Newton, and secant in reliability, derivative requirements, and work per iteration. Why does a better asymptotic convergence rate not always mean less total computational work?
- How does inverse quadratic interpolation use data $(f(x_i),x_i)$ to estimate a root? Given an inverse interpolant $q$, where should it be evaluated? Why can repeated function values cause a problem?
Systems of equations
- What is the Jacobian of a vector-valued function? Write Newton's step as a linear system and update the iterate by adding the step. Be able to perform a small example.
- How can finite differences approximate Jacobian columns? For $f:\mathbb R^n\to\mathbb R^n$, how many additional evaluations does a forward-difference Jacobian require when $f(x)$ is known? Why can a smaller difference step reduce accuracy in floating-point arithmetic?
- What does Broyden's method approximate? What secant equation does its Jacobian approximation satisfy, and what is the role of its rank-one update? Does satisfying the secant equation recover the exact Jacobian?
- Compare Newton and Broyden in derivative evaluations, local convergence, and matrix work. How can updating an existing approximation and its factorization reduce work compared with forming and factoring a new Jacobian?
Optimization
Optimality and one-dimensional methods
- What distinguishes a local minimum, a global minimum, a stationary point, and a saddle point? Why does a zero gradient alone not establish that a point is a minimum?
- What is convexity? For a convex function on a convex feasible set, what does local minimality imply? Does convexity alone imply uniqueness of a minimizer?
- What are the gradient and Hessian? State the necessary conditions for an unconstrained local minimum and a sufficient condition for a strict local minimum. Why can a positive semidefinite Hessian at a stationary point be inconclusive?
- What does unimodality mean? How does golden section search use function values to retain an interval containing a minimizer? Be able to choose the retained interval and explain why one function value can be reused.
- How does successive parabolic interpolation select a new point? Does minimizing the interpolating parabola minimize the original function? Do golden section search and parabolic interpolation require derivatives?
Methods in several dimensions
- What is a descent direction? What does $\nabla f(x)^Tp<0$ imply for a sufficiently small positive step? Why is $-\nabla f(x)$ a descent direction when the gradient is nonzero?
- How does steepest descent choose a direction, and what is a line search? Does an exact line search minimize over all of $\mathbb R^n$? Why can an overly large step increase the objective?
- For $f(x)=\tfrac12x^TAx-b^Tx$ with $A$ symmetric positive definite, find the gradient and relate minimization to $Ax=b$. Why can poor conditioning make steepest descent slow, even with exact line searches?
- What does it mean for directions to be $A$-conjugate? How does conjugate gradient differ from steepest descent? What operations does each iteration require, especially when $A$ is sparse?
- Why does conjugate gradient solve an $n$-variable positive definite quadratic problem in at most $n$ iterations in exact arithmetic? Give a conceptual explanation using conjugate directions. Why may this bound fail in floating-point arithmetic?
- What quadratic model does Newton's method use for optimization, and what linear system gives its step? When does the step minimize this model? Does it necessarily minimize or decrease the original objective?
- When is Newton's method locally quadratically convergent to a minimum? How is it related to solving $\nabla f(x)=0$? Can it converge to a stationary point that is not a minimum?
- How do quasi-Newton methods such as BFGS approximate the Hessian using changes in iterates and gradients? What is the secant equation $Bs=y$? Can satisfying it conflict with keeping $B$ positive definite?
Nonlinear least squares
- How can nonlinear data fitting be written as minimizing $\phi(x)=\tfrac12\|r(x)\|_2^2$? If $J$ is the residual Jacobian, what are its dimensions and the gradient of $\phi$?
- Starting from $r(x+p)\approx r(x)+J(x)p$, write the linear least-squares problem and normal equations for the Gauss-Newton step. Use $x_{\mathrm{new}}=x+p$.
- Why can $J^TJ$ be a useful approximation to the least-squares Hessian near a small-residual solution? In what way is the zero-residual case special?
- How does Levenberg-Marquardt modify the Gauss-Newton equations? Why does a positive parameter help when $J$ is rank deficient? For full-column-rank $J$, what happens as the parameter tends to zero? What does a large parameter do?
Constrained optimization
For SQP and active-set methods, focus on the basic ideas below; detailed algorithms are not expected.
- What are the objective, feasible set, and equality and inequality constraints? At a constrained minimum, must the full objective gradient vanish? Be able to apply derivative conditions to variables that remain free.
- Using Heath's convention $g(x)=0$, $h(x)\le0$, $\mathcal L=f+\lambda_1^Tg+\lambda_2^Th$, and $\lambda_2\ge0$, state the KKT conditions under suitable constraint regularity. Do they alone establish a minimum?
- What makes an inequality active or inactive at a feasible point? What does complementary slackness say about its multiplier? Can an active constraint have a zero multiplier?
- What is the basic idea of sequential quadratic programming (SQP)? How are the objective and constraints modeled in each subproblem?
- How does an active-set method treat selected inequalities in its current subproblem? Why can the selected set change? Must the inequalities outside that set still be satisfied?