ORF523 -- Nonlinear Optimization
Professor Jonathan Eckstein (visiting professor from Rutgers
University)
Announcements
- The final exam is graded. You will
find the solutions and exam scores on BlackBoard (mean 89.3, median 92;
solutions under "assigments"). I have also uploaded course grades
to the PeopleSoft system.
- I will not hold any more
formal office hours, but I will be around most of the time, so just
e-mail me to make an appointment if you want to review your exam.
Day-by-day topics and documents
- February 4, 2008: Introduction, start real analysis crash
course
- Syllabus
- Basic notation for Rn,
Cauchy-Schwarz and triangle inequalities
- sup and inf
- Open sets and interiors
- Sequences, convergent sequences
- Closed sets, closed sets and open sets are complements,
closures, boundaries
- Accumulation points, lim sup, and lim inf
- February 6: complete real analysis crash course, start
convex analysis basics
- Finish real analysis basics
- Monotonic sequences
- Bounded sequences
- lim inf = lim sup equivalent to convergence
- Continuous functions
- Definitions of local and global minima and maxima
- Continuous functions obtain minima and maxima on
compact sets
- Start convex analysis: convex sets
- Some basic operations preserving convexity:
intersection, scaling, Minkowsi sum, interior, and closure
- Convex combinations and convex hulls
- The Carathéodory lemma
- Homework 1, due February
13 (minor correction posted on the afternoon of February 6)
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, February 11: More convex analysis -- projection and
separation
- Projection and separation
- The projection problem -- our first optimization problem
- Separating and supporting hyperplanes
- Wednesday, February 13: Convex functions
- Definition, domains, and epigraphs
- Convexity-preserving operations on functions
- Level sets
- Minima and maxima on convex sets
- Differential properties (partial)
- Homework 2, due February 20
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, February 18: Differential behavior of
convex functions, optimality conditions
- More differential properties of convex functions
- Subgradients
- Optimality conditions for unconstrained problems
- Wednesday, February 20: Second-order sufficient conditions,
start unconstrained algorithms
- Second-order sufficient conditions for a strict local
optimum
- Overview of unconstrained optimization algorithms
- Overview
of line search algorithms
- Boundedness of iterates
- Gradient-related search directions
- Homework 3, due February
27
- Solution is now posted in the "Assignments" area in Blackboard
-
Monday, February 25: Line search procedures, subsequential
convergence of gradient methods
- Line search
procedures
- Line minimization
- Bounded line
minimization
- Armijo backtracking
- Goldstein/two-slope
bisection
- Subsequential convergence of gradient-related
line-search methods
- Notes for
classes 6 and 7 (with minor corrections made after
class)
- Wednesday, February 27:
Convergence rate issues, first MATLAB code
- Kinds of
asymptotic convergence: linear, sublinear, superlinear,
quadratic
- Quadratic function models
- Analysis of
fixed-stepsize steepest descent methods
- Example same
phenomenon with exact line search
- Computational experiments
with Armijo steepest descent in MATLAB
- Brief
motivation for Newton methods
- Monday, March 3:
Newton methods
- Overview
- Convergence analysis
for regions where the Hessian is positive definite
- Wednesday, March 5: More
Newton methods
- More convergence analysis of Newton
methods
- Practical considerations in Newton implementations
- Computer demonstration
- Homework 4, due March 12 (corrections to problem 3(b) made March 11)
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, March 10: Background for conjugate gradient methods
- Motivation: drawbacks to Newton
- Ways of calculating derivatives
- Conjugate direction methods for quadratic problems
- Making conjugate directions out of gradients: a Gram-Schmidt procedure
- Wednesday, March 12: More conjugate gradients
- Conjugate gradients for quadratic problems
- Truncated Newton methods (brief)
- Direct conjugate gradient application to nonquadratic problems
- MATLAB demonstration
- cg.m (simplified conjugate gradient code)
- bisectionsearch.m (crude exact line search)
- cgArmijo.m (combines CG with Armijo line search -- not supported by the theory we have covered)
- By popular demand: viewpath.m allows you to visualize the path of an algorithm on a function of two variables [x1,x2]. You should call it as follows: viewpath(function,[x1,x2],pointlist), where pointlist is normally generated by one of the algorithm methods like newton or steepestArmijo on the same choice of function.
---- (Spring break) ---
- Monday, March 24: Conic optimality conditions for constrained problems
- Basic intuition for constrained local optimality
- Feasible-direction and tangent cones
- Cone separation
- Polar cones
- Fundamental constrained optimality theorem -- statement and intuition
- The
take-home midterm was given out at the end of class and was due at 10AM
on Friday the 28th.
- Wednesday, March 26: Tangent cone theory
- Proof of conic constrained optimality theorem
- An asymptotic distance lemma
- A general constraint framework
- Monday, March 31: Tangent cones, metric regularity, and constraint qualification
- Tangent cone inclusion lemma
- Metric regularity
- Fundamental constraint qualification theorem
- Wednesday, April 2: Constraint qualification conditions
- Return midterm exam
- Robinson's condition
- Mangasarian-Fromowitz constraint qualification
- The convex case: the Slater constraint qualification
- Monday, April 7: From polar cones to Lagrange multipliers
- The "bipolar" theorem
- The polar of a linear/cone constraint
- Lagrange multipliers for equality constraints
- Lagrange multipliers for inequality constraints
- Wednesday, April 9: More Lagrange multipliers
- Finish theory of standard Lagrange multiplier optimality conditions
- Combining equalities and inequalities (sketch of analysis)
- Combining equalities, inequalities, and an abstract convex set X0 (sketch of analysis)
- Homework 5, due April 16 (updated April 14)
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, April 14: Finish Lagrange multipliers
- Polars of intersections of cones: puzzle resolved
- Example applications of Lagrange multipliers -- analytical solutions or simple algorithms
- Distributed typeset version of convex analysis notes: available on Blackboard
- Wednesday, April 16: Conjugate functions
- Definition
- Closed functions
- Simple example / fundamental illustration
- Fenchel's inequality
- Affine minorants
- The Fenchel-Moreau theorem
- Duality of arguments and subgradients
- Homework 6, due April 23
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, April 21: Duality for optimization problems
- Parameterized problem function setup
- Duals, conjugates, and Lagrangians (with examples)
- Weak duality
- The parametric value function
- Wednesday, April 23: Duality for optmization problems
- Strong duality
- Closedness of the parametric value function
- Sensitivity interpretation of optimal multipliers and other observations
- Linear programming example
- Course evaluation forms
- Homework 7, due April 30
- Solution is now posted in the "Assignments" area in Blackboard
- Monday, April 28: Overview tour of constrained optimization algorithms
- Wednesday, April 30: Primal-dual Newton barrier methods