520.430 Parallel Optimization

Department: Dept. of Electrical and Computer Engineering
Meeting Times: Monday, Wednesday 4-5:15, Barton 225
Instructor: Dr. Louis J. Podrazik, e-mail: podrazik@super.org
Office Hours: by appointment
Credits: 3

Synopsis: Optimization problems and their analysis including primal and dual formulations. Optimality conditions and their relationship to algorithm synthesis. Survey of both unconstrained and constrained optimization algorithms in the context of developing algorithms suitable for implementation on parallel computers. Unconstrained techniques include gradient descent, conjugate-gradient, Quasi-Newton and Newton's Method, their parallel implementations and algorithm variants. A survey of parallel algorithms for constrained optimization will be presented, including feasible set, projection and interior point methods. Various applications will be studied throughout the class to supplement the theory.

Prerequisite: A course in advanced calculus and a course in linear algebra (a previous course in optimization or parallel processing is not required).

Curriculum

Course Grading

Homework Assignments

Curriculum

Each lecture topic will consist of the necessary theoretical background followed by a discussion of selected parallel techniques and applications.

• Week 1. Introduction to parallel computation and optimization problems
• Week 2. Line search and trust region methods
• Week 3. Steepest descent and conjugate gradient algorithms
• Week 4. Practical Newton methods
• Week 5. Differentiation and applications
• Week 6. Quasi-Newton techniques and the solution of large-scale problems
• Week 7. Review & Mid Term Exam
• Week 8. Linear and nonlinear least squares problems
• Week 9. Constrained optimization and duality theory
• Week 10. Linear programming – simplex methods
• Week 11. Linear programming – interior point methods
• Week 12. Quadratic programming and gradient projection algorithms
Week 13. Selected barrier, penalty and sequential quadratic programming methods.

Course Grading

Evaluation: Students will be evaluated on the basis of the following three components:

• 25% One-week homeworks
• 25% Closed-book midterm
50% Open-book final exam

References

• Required text:

(1) J. Nocedal and S. J. Wright , Numerical Optimization, , Springer, 1999, ISBN 0-387-98793-2, QA 402.5.N62 .

• Optimization references:

(1) D. P. Bertsekas and John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, 1997, ISBN 1-886529-01-9.

(2) J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1996.

(3) R. Fletcher, Practical Methods of Optimization, 2nd Edition, John Wiley and Sons, 1987.

(4) P. Gill, W. Murray, and M. Wright, Practical Optimization, Academic Press, 1981.

(5) D. Butnariu, Y. Censor and S. Reich, Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, North-Holland, 2001, ISBN 0-444-50595-4, QA 76.58.B88.

(6) P.M. Pardalos, A.T. Phillips and J.B. Rosen, Topics in Parallel Computing in Mathematical Programming, Science Press, 1992, ISBN 1-880132-11-7.

(7) Y. Censor and S.A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997, ISBN 0-19-510062-X, QA 402.5.C426.

• Parallel computing references:

(8) Lakshmivarahan & Dhall (1990), Analysis and Design of Parallel Computers: Arithmetic and Matrix Problems, McGraw-Hill

(9) Leighton (1992), Introduction to Parallel Algorithms and Architectures: Arrays . Trees . Hypercubes, Morgan Kaufmann.

(10) Jagdish J. Modi, (1988), Parallel Algorithms and Matrix Computations

(11) Akl (1997), Parallel Computation: Models & Methods, Prentice Hall

(12) Geoffrey Fox, et al. (1988), Solving Problems on Concurrent Computers

• Some web sites of interest:

(1) http://www.mcs.anl.gov/otc/Guide/

• Journals: SIAM Journal on Optimization, SIAM Journal on Control and Optimization, IEEE Trans. on Computers, IEEE Trans. on Parallel & Distributed Systems, Journal of Parallel & Distributed Computing, and Parallel Computing.
• Conferences: Int'l Symp. Computer Architecture (ISCA, since 1973), Int'l Conf. Parallel Processing (ICPP, since 1972), Int'l Parallel Processing Symp. (IPPS, since 1987), IEEE Symp. Parallel and Distributed Processing (SPDP, since 1989), and ACM Symp. Parallel Algorithms and Architectures (SPAA, since 1988).