This is supplemental course information, designed to give you a fuller picture of the course and an expanded look at the topics covered. This is an unofficial document. The USC Course Catalog is the binding description of all university courses. Information such as books, materials covered, and the order of topics is subject to change. Please consult instructor for this semseter to get more upto date course information.
Prerequisites:
EE441, or equivalent
Prof. Michael G. Safonov <msafonov@usc.edu>
D. Bertsekas, Nonlinear Programming, 2nd edition. Belmont, MA: Athena Scientific, 1999.
ISBN 1886529000. http://www.athenasc.com/nonlinbook.html
R. Fletcher, Practical Methods for Optimization. New York, NY: Wiley, 2001. ISBN
0471494631 http://www.wiley.com/cda/product/0,,0471494631,00.html
, MATLAB Optimization Toolbox User’s Guide. Natick, MA: MathWorks, 1999.
[Available in electronic PDF format: At the MATLAB ‘>>’ prompt, type doc; next, click on the link for ‘Online Manuals (in PDF)’ and, finally, select Optimization Toolbox User’s Guide.]
Access online course materials and grade information on TOTALe (BlackBoard) at http://learn.usc.edu
This is an introductory course on numerical methods for optimization. We will study methods for solving linear programming problems and nonlinear optimization problems, with and without constraints. We will examine the mechanism by which different algorithms find numerical solutions to these problems and the convergence properties of the algorithms. The theoretical work will be reinforced with practical examples computed using MATLAB. After completing the course, the student will be in a position to select and implement appropriate algorithms for solving a broad range of numerical optimization problems and understand the relative merits and drawbacks of the various methods at his or her disposal.
Use of the MATLAB software (available on USC’s student computing facility) will be required for some of the homework exercises. To use MATLAB type matlab at the Unix prompt, then type demo, help or doc for more information. Students are expected to know Unix computer basics such as how to login, create/edit files and so forth. To setup your university computer account, go to http://www.usc.edu/isd/firstlogin. Alternatively,
if you prefer to compute on your home computer rather than using USC’s unix
computers, you may optionally use the following:
, MATLAB Student Version. Natick, MA: MathWorks. ISBN 0-9672195-0-7
(Also need Optimization Toolbox.) MATLAB Student Version is available at the USC Bookstore and on the web at
http://www.mathworks.com/products/studentversion
Academic Integrity: University policies regarding academic integrity are described in SCampus. All violations will be reported to the Office of Student Conduct.
2
1. Introduction: Nonlinear Programming, Application Contexts, Characterization Issue, Computation Issue, Duality, Organization.
Ref.: Bertsekas, preface; Fletcher, preface & Ch. 1
2. Unconstrained Optimization; Local Minima; Necessary Conditions for Local Minima; Sufficient Conditions for Local Minima; The Role of Convexity
3. Quadratic Unconstrained Problems ; Existence of Optimal Solutions ; Iterative Computational Methods ; Gradient Methods - Motivation
Ref.: Bertsekas §1.1.1 & §1.2
4. Principal Gradient Methods ; Gradient Methods - Choices of Direction ; Gradient Methods Choice of Stepsize ; Gradient Methods - Convergence Issues
Ref.: Bertsekas §1.2
5. Approaches for Rate of Convergence Analysis ; The Local Analysis Method ; Quadratic Model Analysis ; The Role of the Condition Number ; Scaling ; Extension to Nonquadratic Problems ; Singular and Difficult Problems
Ref.: Bertsekas §1.3
6. Newtons Method ; Convergence Rate of the Pure Form ; Global Convergence ; Variants of Newtons Method ; Least Squares Problems ; The Gauss-Newton Method
Ref.: Bertsekas 1.4 & 1.5.1
7. Conjugate Direction Methods ; The Conjugate Gradient Method ; Quasi-Newton Methods of Davidon-Fletcher-Powell (DFP), and of Broyden-Fletcher-Goldfarb-Shanno (BFGS)methods
Ref.: Bertsekas §1.6 & 1.7
8. Non-Derivative Methods, simplex algorithm of Nelder-Meade; Practical Guidlines
Ref.: Bertsekas §1.8 & 1.10
9. Optimization over a Convex Constraint Set ; Optimality Conditions. Applications Problem:
minx2X f(x), where:(a) X12 < Ren is nonempty, convex, and closed.
(b) f is continuously differentiable over X.
Local and global minima. If f is convex local minima are also global.
Ref.: Bertsekas §2.1
10. Feasible Direction Methods ; Conditional Gradient Method ; Gradient Projection Methods
Ref.: Bertsekas §2.2 & §2.3
11. Manifold Suboptimization Methods; Affine Scaling; Simplex Method for Linear Programming Ref.: Bertsekas § 2.5 & § 2.6
12. Equality Constrained Problems ; Basic Lagrange Multiplier Theorem ; Proof 1: Penalty Approach ; Proof 2: Elimination Approach ; Examples
Ref.: Bertsekas
13. Equality Constrained Problems/Sufficiency Conditions ; Convexification Using Augmented Lagrangians ; Proof of the Sufficiency Conditions ; Sensitivity
Ref.: Bertsekas, § 3.1 and § 3.2.
14. Inequality Constrained Problems ; Karush-Kuhn-Tucker Optimality Conditions ; Fritz John Optimality Conditions ; Constraint Qualifications
Ref.: Bertsekas §3.3.1–3.3.5
15. Linear Programming revisited: Convex Cost/Linear Constraints ; Duality Theorem ; Linear Programming Duality ; Quadratic Programming Duality
Ref.: Bertsekas §3.4
16. Barrier and Interior Point Methods ; Linear Programs and the Logarithmic Barrier ; Path Following Using Newtons Method
Ref.: Bertsekas §4.1
17. Quadratic Penalty Methods ; Introduction to Multiplier Methods
Ref.: Bertsekas §4.2
18. EXAM #1 Thursday March 13, 2003, in class. Unless otherwise arranged, DEN students come to campus.
19. Multiplier Methods ; Geometric Interpretation of Multiplier Methods ; Geometric Framework for Duality
Ref.: Bertsekas §4.2
20. Multiplier Methods (continued)
Ref.: Bertsekas §4.2
21. Geometrical Definition of Lagrange Multipliers ; The Dual Problem ; Properties of the
Dual Function ; Dual Optimal Solutions and Lagrange Multipliers
Ref.: Bertsekas §5.1
22. Duality and L-multipliers (continued) ; Strong Duality Theorems
Ref.: Bertsekas §5.1
23. Strong Duality Theorems-Linear equality const. ;Fenchel Duality Framework
Ref.: Bertsekas §5.3
24. Branch-and-Bound Method ; Constraint vs Lagrangian Relaxation
Ref.: Bertsekas §5.5
25. Dual Methods ; Why dual? When dual?
Ref.: Bertsekas §6.1, also Prop. B.24 & Prop. B.25 Appendix B5
26. Dual Methods (Continued): Subgradients and Subdifferentials ; Optimality conditions; Differentiability properties of dual function
27. Dual Methods (continued): Di_erentiability Properties ; Subgradient Methods; Stepsize Choices; Convergence
Ref.: Bertsekas §6.3–6.3.2
28. Dual Methods (continued): Cutting Plane Methods ; Dantzig-Wolfe Decomposition
Ref: Bertsekas §6.3.3 & §6.4, 6.4.1
29. Review & Discussion
30. EXAM #2 Thursday May 01, 2003, in last class. Unless otherwise arranged, DEN students come to campus.
