Unit 6 Constrained optimization and Lagrange multipliers
Recall from Definition 3.6.12 that an optimization problem has an objective function and a feasible region. In a constrained optimization problem, one or more equations or inequalities restrict the feasible region.
The section “Optimization problems and critical points” found interior critical points by solving
\begin{equation*}
\nabla f(\mathbf{x})=\mathbf{0}.
\end{equation*}
On a closed bounded region, absolute extrema may also occur on the boundary. Lagrange multipliers give equations for critical points on boundaries and feasible sets described by one or more equality constraints.
The same method connects constrained optimization to linear algebra. On the unit sphere, the extrema of a symmetric quadratic form occur in eigenvector directions. This leads to the section “Principal component analysis” for centered data and the section “Singular value decomposition” for general matrix maps.
Big questions. How do we find absolute extrema when the allowable inputs are restricted? Why do eigenvectors identify extremal directions of quadratic forms, data sets, and matrix maps?
Learning outcomes. By the end of this unit, students should be able to:
-
U6-LO1. Identify closed and bounded regions, and find absolute extrema on closed bounded regions by comparing interior and boundary candidates.
-
U6-LO2. Formulate and solve Lagrange-multiplier problems with one equality constraint, and explain the parallel-gradient and Lagrangian formulations.
-
U6-LO3. Formulate and solve Lagrange-multiplier problems with several equality constraints, and interpret the objective gradient as a linear combination of constraint gradients.
-
U6-LO4. Use Lagrange multipliers and eigenvalues to find extrema of symmetric quadratic forms on the unit sphere, and apply this result to maximum stretch and singular values.
-
U6-LO5. Center a small data set, form its covariance matrix, compute and interpret first and second principal directions, scores, reconstructions, and captured variation, and distinguish PCA from linear regression.
-
U6-LO6. Construct and interpret a small singular value decomposition\begin{equation*} A=U\Sigma V^T, \end{equation*}including its orthonormal input and output directions and singular-value stretch factors.
-
U6-LO7. Use an SVD to identify rank and orthonormal bases for the four fundamental subspaces, and connect the SVD of centered data with PCA directions, scores, and reconstructions.
Toolbox skills. Compare interior and boundary candidates; restrict a function to simple boundary pieces; form and solve one- and several-constraint Lagrange systems; write and differentiate Lagrangians; evaluate and diagonalize symmetric quadratic forms; center data and form covariance matrices; compute principal scores, projections, and reconstruction residuals; form \(A^TA\text{;}\) compute singular values and singular vectors; assemble and read small SVDs; and identify rank and bases for the four fundamental subspaces.
