Let \(f: \R^n \to \R\) be a scalar-valued function, and consider a set \(U \subseteq \R^n\text{.}\) Then we can consider two optimization problems, in which we call \(f\) the objective function of the problem, and \(U\) the feasible region of the optimization problem:
The minimization problem of \(f\) on \(U\) is the problem of finding \(\mathbf{x}^* \in U\) such that the value \(f(\mathbf{x}^*)\) is smallest among all elements of \(U\) (so the function is minimized on \(U\) by \(\mathbf{x}^*\)).
The maximization problem of \(f\) on \(U\) is the problem of finding \(\mathbf{x}^* \in U\) such that the value \(f(\mathbf{x}^*)\) is largest among all elements of \(U\) (so the function is maximized on \(U\) by \(\mathbf{x}^*\)).
A common optimization problem that we have already encountered in Definition 4.2.4 involves taking a subspace \(U \subseteq \R^n\) and a given vector \(\mathbf{x}_0 \in \R^n\text{,}\) and finding the vector \(\mathbf{x}^* \in U\) that is closest to \(\mathbf{x}_0\text{,}\) i.e., finding the vector that minimizes the scalar-valued function \(g: \R^n \to \R\) on \(U\text{,}\) defined by setting \(g(\mathbf{x}) = \| \mathbf{x}_0 - \mathbf{x} \| \text{.}\) Then \(\mathbf{x}^*\) is the orthogonal projection of \(\mathbf{x}_0\) onto \(U\text{,}\) and we have seen in Theorem 4.2.6 that if \(U\) has an orthogonal basis \(\{ \mathbf{f}_1, \dots, \mathbf{f}_m \}\text{,}\) then
In Unit 4, projection was a closest-point problem. If \(W\) is a subspace and \(\mathbf{b}\) is a vector, the projection problem asks for the point \(\hat{\mathbf{b}}\in W\) that minimizes
over all \(\mathbf{w}\in W\text{.}\) Unit 4 solved this using orthogonality. Unit 5 studies the same kind of question with gradients: minimize a function by looking at how it changes.
Suppose \(f\) is a scalar-valued function. A point \(\mathbf{a}\) in the domain of \(f\) is a
local minimum if there is a ball centered at \(\mathbf{a}\) such that \(f(\mathbf{a}) \leq f(\mathbf{x})\) whenever \(\mathbf{x}\) is in that ball, and also in the domain of \(f\text{.}\) In this case, we say \(f(\mathbf{a})\) is a local minimum value for the function \(f\text{.}\)
local maximum if there is a ball centered at \(\mathbf{a}\) such that \(f(\mathbf{a}) \geq f(\mathbf{x})\) whenever \(\mathbf{x}\) is in that ball, and also in the domain of \(f\text{.}\) In this case, we say \(f(\mathbf{a})\) is a local maximum value for the function \(f\text{.}\)
global minimum if \(f(\mathbf{a}) \leq f(\mathbf{x})\) for all \(\mathbf{x}\) in the domain of \(f\text{.}\) In this case, \(f(\mathbf{a})\) is the global minimum value, or absolute minimum value, of the function \(f\text{.}\)
global maximum if \(f(\mathbf{a}) \geq f(\mathbf{x})\) for all \(\mathbf{x}\) in the domain of \(f\text{.}\) In this case, \(f(\mathbf{a})\) is the global maximum value, or absolute maximum value, of the function \(f\text{.}\)
The graph of the function \(-f\) is obtained by reflecting the graph of the function \(f\) in the output axis. This operation turns local and global maxima into local and global minima, and vice versa. So methods for finding minima for a general function often give methods for finding maxima, which makes the two problems often equivalent.
Suppose \(f\) is a scalar-valued function that is differentiable at a point \(\mathbf{a}\text{.}\) Then we say \(\mathbf{a}\) is a critical point if \(\nabla f(\mathbf{a}) = \mathbf{0}\text{.}\)
Just as the derivative of a scalar-valued function of a single variable helps identify local minima and maxima, partial derivatives provide information about possible local minima/maxima.
Suppose \(f\) is a scalar-valued function that is differentiable at a point \(\mathbf{a}\text{.}\) If \(\mathbf{a}\) is also local extremum of \(f\text{,}\) then \(\mathbf{a}\) is a critical point of \(f\text{.}\)
The critical points are the pairs \((x,y)\) that simultaneously solve the equations \(2x - 2 = 0\) and \(2y + 4 = 0\text{.}\) So the only critical point is \((1, -2)\text{.}\)
We compute that \(f_x(x,y) = 2x\) and \(f_y(x,y) = -2y\text{.}\) The only \((x,y)\) such that \(f_x(x,y) = 2x = 0\) and \(f_y(x,y) = -2y = 0\) is \((0,0)\text{.}\) This is the only critical point.
