Next: O' notation and Rates Up: Fundamentals of Unconstrained Optimization Previous: Digression: Topology in

## Fundamental Theorems of Nonlinear Optimization

Theorem 2.2.1   Necessary order conditions:
If , open, has a local minimizer , then .

Caution: This is necessary, but not sufficient!

Proof. Suppose is a local minimizer. Then there is a neighborhood in which for all . Suppose that .
Then, set so

As . Consider the function

where . Then, is a continuous function of one variable and . Hence, we have that for all .
Fix ; if we take and apply the MVT,

for some . Notice , and .

Friday, 1-21-2005

Also,

Hence,

This contradicts the fact that is a local minimizer.

Theorem 2.2.2   order Necessary Conditions:
Let , open in with local minimizer at . Then, and matrix is positive semidefinite.

Remarks: This is a necessary condition, and not sufficient. For example, take . Then,

This make positive semidefinite at . However, we know to be a saddle point, and not a local minimizer.

Proof. Start of it - go by contradiction as before. Find as before. Use

To arrive at a contradiction, select such that is negative. Now, use Taylor's Theorem for multivariate functions just like we used the MVT in the last proof.

Theorem 2.2.3   Sufficient Condition for Local Minimizers:
Let , open in . Suppose that is a stationary point: . If is positive definite, then is a local minimizer.

Remark: In fact, the proof, using Taylors Theorem similar to the previous theorem, shows has a strict local minimizer at , i.e., for in some neighborhood of .

Theorem 2.2.4   Sufficient Condition for Local Minimizer: Let be convex, , open and convex
(a)
Any local minimizer is a global minimizer
(b)
If , then any stationary point is a global minimizer

Proof. Let have a local minimizer at . Suppose had a smaller value at . So, . Let , for . Then,

which contradicts the fact that is a local minimizer.

Monday, 1-24-2005
Assignment: 2.6, 2.9, 2.12, 2.13

Explained the 2nd derivative test from Calc III: Consider discriminant of :

If , have saddle at . If , have local max / min at . If , test fails.
Explanation: Let be a stationary point. Let . Then is symmetric real. So, is diagonalizable by orthogonal . In fact, , where are the eigenvectors of (correspond to real eigenvalues . Thus,

So,

If , both are either positive or negative. If positive, is symmetric positive definite. By considering or , we can use our sufficient conditions from above to see that there is a corresponding local min / max.

If , then has a positive and a negative eig (say ). Label the corresponding eigenvectors and . Now, recall Taylor's Theorem:

for small. Take . Then,

By continuity arguments, the term of Taylor's expansion is positive. Thus, resembles a local min at . Similarly, looks like a maximum. So, we have a saddle point.

Next: O' notation and Rates Up: Fundamentals of Unconstrained Optimization Previous: Digression: Topology in
Brian Bockelman 2005-06-09