Spring 2005 / ETC 7.146
NONLINEAR PROGRAMMING
PROFESSOR: / J. F. Bard
OFFICE: / ETC 5.126, 471-3076
OFFICE HOURS: / 2:00 – 4:00 TTH, or by appointment
EMAIL: /
WEB PAGE: / http://www.me.utexas.edu/~bard/ (See textbook corrections)
PREREQUISITES: / OR Methods or equivalent; elementary computer programming ability.
TEXTS Required: / Nonlinear Programming, Second Edition, by D.P. Bertsekas, Athena Scientific, Belmont, MA (1999). (see errata sheet on course web site)
References: / Linear and Nonlinear Programming,
by D.G. Luenberger, Second Edition, Addison-Wesley Publishers (1984).
“Nonlinear Programming,” Chapter 4, in Practical Bilevel Optimization, by J.F. Bard, Kluwer, Boston, MA (1998).
OBJECTIVE: / The purpose of this course is to develop an appreciation of the theoretical underpinnings of the techniques used to solve nonlinear, continuous optimization problems. In the first half of the course, we will concentrate on basic principles and concepts, including topological properties of functions, general convexity, and optimality conditions. In the second half, we will study line search methods, unconstrained techniques, and algorithms for constrained formulations. We will end with a discussion of Lagrangian duality theory and bundle methods for nondifferentiable optimization.
GENERAL COURSE POLICIES
HOMEWORK: / Homework and computer assignments can be done in teams of 2 or 3 students. Dates will be posted to indicate when these assignments are due.
SOLUTIONS: / All solutions to the homework assignments and exams will be posted on the web.
EXAMS: / All exams are open book and open notes. All students must take the exams when scheduled, including the final –– no exceptions. There will be NO make-up exams and there will be NO incompletes in the course; every student will get a grade. If you would like to review your final exam, please do so no later than one week after the next semester begins (fall, spring, or summer). After that time, all exams and other uncollected class material will be discarded.
GRADING: / Homework / 15%
First Exam / February 24 (Thursday) / 25%
Second Exam / April 7 (Thursday) / 25%
Final Exam / May 13 (Fri. 2:00 - 5:00 pm) / 35%
Arithmetic errors on exams and homework are usually penalized a few points. Conceptual errors or errors in logic are more severely penalized. On exams, always show the computations or logic that led to your solution, label the solution, and cross out any work that you do not want graded. If your exam contains erroneous information or computations, even if you have the correct solution, you will still be penalized.
Necessary (but not sufficient) conditions for receiving a grade of A in the course are either an A on the first two examines or an A on the final and at least a high B on the first two exams. An A on the two midterms and a C on the final will likely result in a B in the course. Analogous requirements exist for receiving a grade of B and so on. Grades on the homeworks are used to evaluate borderline students. All students must take the final on the scheduled date
RE-GRADING: / If you feel that you weren't graded fairly on an exam question, first look at the solution, then write a note to me explaining how your answer compares to the posted solution and why you think that you deserve more credit. Hand in your note and exam to me no later than 2 weeks after the exam is returned.
EXTRA CREDIT: / There will be NO extra assignments for those wishing to try to improve their overall grade.
DISHONESTY: / All University of Texas procedures regarding academic dishonesty will be followed exactly as prescribed. Cheating on exams or homework can lead to a failure in the course.
DISABILITIES: / The University of Texas provides upon request academic adjustments for students with documented disabilities. For more information, contact the Office of the Dean of Students at 471-6259, 471-4241.
COMPUTER ASSIGNMENTS
During the semester, you will be asked to write a number of computer programs implementing some of the methods discussed in class. These programs can be written in any language and run on any machine you choose, circumstances permitting. The code should be well-documented with comments so someone reviewing it can understand the logic even if he or she is not familiar with the language. In addition, input and output should be well thought out. Interactive codes are fine if the user is not overburdened with input requests. Output should be tabularized and easy to read. Often you will be asked to provide the solution to a sample problem.
Computer accounts for the Mechanical Engineering graduate PC laboratory in ETC 3.140 can be obtained by accessing the website:
http://hpc.me.utexas.edu/
See Sue Ponder in ETC 3.138 if you have any trouble with the ME account.
Accounts on University computers can be obtained from the Computation Center.
In general, the assignment that you turn in should include:
· Name, date, class, title of assignment.
· Well-documented code.
· Input files if not an interactive problem; if interactive, provide a printout of the session.
· Statement of model. If solving an LP, for example, provide the model in algebraic form along with the data.
· Results in tabularized or other easy to read format.
REFERENCES
Journal Articles
[1] J.E. Dennis, Jr. and J.J. Moré, “Quasi-Newton Methods, Motivation and Theory,” SIAM Review, Vol. 19, No. 1 (January 1977).
[2] M.J.D. Powell, “Algorithms for Nonlinear Constraints that use Lagrangian Functions,” Mathematical Programming, Vol. 14 (1978), pp. 224-248.
[3] J. Zhang, N.-E. Kim and L. Lasdon, “An Improved Successive Linear Programming Algorithm," Management Science, Vol. 31, No. 10, pp. 1312-1331 (1985).
[4] B.A. Murtagh and M.A. Saunders, “A Projected Lagrangian Algorithm and its Implementation for Sparse Nonlinear Constraints,” Mathematical Programming Study, Vol. 14, pp. 84-117 (1982).
[5] L.S. Lasdon, A.D. Warren, A. Jain and M. Ratner, “Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming,” ACM Transactions on Mathematical Software, Vol. 4, No. 1, pp. 34-50 (March 1978).
[6] Y. Fan, S. Sarkar and L.S. Lasdon, “Experiments with Successive Quadratic Programming Algorithms," Journal of Optimization Theory and Applications, Vol. 56, No. 3 (March 1988), pp. 359-383.
[7] A.V. Fiacco, “Sensitivity Analysis for Nonlinear Programming Using Penalty Methods,” Mathematical Programming, Vol. 10, No. 3, pp. 287-311 (June 1976).
Books
[8] M. S. Bazaraa, H. D. Sherali, and C.M. Shetty, Nonlinear Programming, Theory and Algorithms, second edition, John Wiley & Sons, New York (1993).
[9] A. Brooke, D. Kendrick and A. Meeraus, GAMS: A User's Guide, (see web site
http://www.gams.com/).
[10] A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, New York (1968).
[11] R. Fletcher, Practical Methods of Optimization, Second Edition, John Wiley & Sons, New York (1995).
[12] P.E. Gill, W. Murray and M. Wright , Practical Optimization, Academic Press, New York (1983).
[13] J. Liebman, L.S. Lasdon, L. Schrage and A. Warren, Modeling and Optimization with GINO, boyd & fraser, Danvers, MA, 1988.
[14] O.L. Mangasarian, Nonlinear Programming, McGraw-Hill, New York (1969).
[15] G.P. McCormick, Nonlinear Programming: Theory, Algorithms, and Applications, John Wiley & Sons, New York (1983).
[16] S.G. Nash and A. Sofer, Linear and Nonlinear Programming, McGraw Hill, New York (1996).
Book Chapters
[17] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, “Constrained Nonlinear Programming,” in G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (eds.), Handbooks in Operations Research and Management Science, Vol. 1, Optimization, pp. 171-210, Elsevier, Amsterdam, 1989.
[18] C. Lemaréchal, “Nondifferentiable Optimization,” in G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (eds.), Handbooks in Operations Research and Management Science, Vol. 1, Optimization, pp. 529-572, Elsevier, Amsterdam, 1989.
- 2 -