OPIM 914

OPIM (Wharton)

OPIM-914: Nonlinear Programming

Tuesdays and Thursdays 3:00-4:30PM, JMHH G94


Spring 2009
Professor Monique Guignard-Spielberg





================================================
Time/temperature in Philadelphia:

Click for Philadelphia, Pennsylvania Forecast
================================================
To go directly to one of the following topics, click on the corresponding link:

New this week
General Information
Textbooks
FAQ
Syllabus
Grading
Homework
Project
Exams
Slides
OR/MS Links

HOME

New this week: (20 April 2009)



There will be no extra class on Thursday.
Homework: in addition to the work given in class, do problems 4.2.1, 5.1.1 and 5.1.5.

Download the file Strong duality.

Download the file Discrete optimization.

Download the file Dual computational methods.

back to the top

New this week: (13 April 2009)



There will be no class on Tuesday.
Download the file Duality Theorems.

back to the top

New this week: (6 April 2009)



Download the file Penalty methods for Tuesday's class.

Download the file Augmented Lagrangean methods for Thursday 1:30 class.

Download the file Duality Theory for Thursday 3:00 class.

back to the top

New this week: (30 March 2009)



Download the file Introduction to duality.

Download the file Interior point methods.

back to the top

New this week: (23 March 2009)



Please download lectures 12 (sufficiency conditions) and 13 (inequality constraints).

========================================================================================================

Next assignmemt: read the pages distributed in class (if you did not get them, I will bring them again to class on Tuesday). They are taken from Rardin's book "Optimization in Operations Research", Prentice Hall, 1998. P. 787-805. They deal with examples of NLP problems of different kinds.

The next homework will consist of the following: (1) write the model of the quadratic portfolio model of p. 803/804 in gams.
Solve it using two different NLP solvers, MINOS and CONOPT.
Start from x1=x2=x3=1/3, and from x1=x2=0, x3=1.
Write a few lines analyzzing the results of the experiment (run time, binding vs nonbinding constraints, etc.).
Write the first order optimality conditions and check if they are satisfied.

(2) do the same thing for the Pfizer optimal lot-sizing problem of p. 796/797 (starting from x1=x2=x3=x4=10) and for the oxygen system engineering design of p. 792-794 (starting from a point of your choice).

Look for the complete assignment in the Homework section as HW2.



back to the top

New this week: (16 March 2009)



Download the file Constrained optimization; Lagrange multipliers.

back to the top

New this week: (2 March 2009)



Download the file on conjugate directions. This is part 3, to be covered on Tuesday 3/3/09.

Download the file on optimization over a convex constraint set.

Complement to the homework problems given last week: download this file . HW1 was due on February 26.

back to the top

New this week: (16 February 2009)



Download the file on conjugate directions. This is part 1, covered in part on Tuesday.

Download the file on conjugate directions. This is part 2, to be covered on Thursday.

Download the file on conjugate directions. This is part 3, to be covered next Tuesday.

Complement to the homework problems given last week: download this file . HW1 will be due on February 26.

back to the top

New this week: (7 February 2009)



Homework 1: 17(1.1.5), 1.1.4, 1.1.8. Other problems will be added later.

back to the top

New this week: (2 February 2009)



Try to translate the fortran code for Newton's method into your favorite programming language.
The code is available on Bertsekas' page, and also here.

Test your code with a few 1, 2 and 3 dimensional problems, convex and nonconvex, vary the starting point,
and email me the code and the results.

back to the top

New this week: (26 January 2009)



Do problems 1.1.1, 1.1.2(b), 1.1.3 and 1.1.6 p. 16-18. The answers are on Bertsekas's webpage.

back to the top

New this week: (19 January 2009)



Welcome to OPIM 914!

back to the top
================================================


General Information

Course Description

The course is concerned with the theory and use of nonlinear programming. Most optimization problems are nonlinear, and often nonconvex. The texbook by Bertsekas presents a comprehensive, unified treatment of the field. As stated in the preface, "the purpose … is to provide an up-to-date, comprehensive, and rigorous account of nonlinear programming at the beginning graduate student level. In addition to the classical topics, such as descent algorithms, Lagrange multiplier theory, and duality, we cover some of the important recent developments: interior point methods for linear and nonlinear programs, major aspects of large-scale optimization, and least squares problems and neural network training."

A certain amount of mathematical sophistication will be expected of the students, and some topics/results may need to be reviewed during the semester. The appendices of the book may be sufficient refresher for the course. "Four appendixes are given. The first gives a summary of calculus, analysis, and linear algebra results used in the text. The second is a fairly extensive account of convexity theory, including proofs of the basic polyhedral convexity results on extreme points and Farkas' lemma, as well the basic facts about subgradients. The third appendix covers one-dimensional minimization methods. The last appendix discusses an implementation of rNewton's method for unconstrained optimization."

The goals of the course are the following: (1) to present students with a knowledge of the state-of-the art in the theory and practice of solving nonlinear programming problems, (2) to provide students with a framework for analyzing algorithms that unifies theoretical and empirical perspectives, (3) to help each student develop his or her own intuition about algorithm development and algorithm analysis.

Audience:

PhD students in OPIM and other Wharton programs, PhD and MS students in Engineering.

Background

This course assumes elementary background in optimization, and some calculus and matrix algebra.

Instructor

Prof. Monique Guignard-Spielberg
Office: 5th floor, OPIM Department, JMHH
Phone: 215-898-8235
Email: guignard at wharton.upenn.edu
URL: http://opim.wharton.upenn.edu/~guignard
Office Hours: by appointment.

back to the top

Textbooks

"Nonlinear Programming: 2nd Edition, 2nd printing", by Dimitri P. Bertsekas
Athena Scientific Press,
ISBN: 1-886529-00-0
Publication: 1999, 2nd printing 2004, hardcover

At various points during the semester, additional reading material, as well as lecture notes, will be made available as handouts.
Information on the book can be found at the website.
Read the preface.

back to the top

FAQ

The following website answers many of the questions you may have about nonlinear programming.
It was established by John W. Gregory ( ashbury@skypoint.com), and is currently being maintained
by Robert Fourer ( 4er@iems.nwu.edu) and the Optimization Technology Center.


back to the top

Course Syllabus

Lecture 1 Introduction
Lecture 2 Unconstrained Optimization - Optimality Conditions.
Lecture 2' Convex sets and functions (see Appendix B1).
Lecture 2" Differentiable and twice differentiable convex functions (see Appendix B1).
Lecture 3 Gradient Methods
Lecture 4 Convergence Analysis Of Gradient Methods
Lecture 5 Rate Of Convergence
Lecture 5' Symmetric and positive definite (pd) matrices. Cholesky factorization of a pd matrix.
Lecture 6 Newton And Gauss-Newton Methods
Lecture 7 Additional Methods
Lecture 8 Optimization Over A Convex Set; Optimality Conditions
Lecture 9 Feasible Direction Methods
Lecture 10 Alternatives To Gradient Projection
Lecture 11 Constrained Optimization; Lagrange Multipliers
Lecture 12 Relationship between the Lagrangean function and LP (and NLP) duality
Lecture 13 Example: min distance st linear constraints vs. projections
Lecture 13a Sufficiency Conditions
Lecture 14 Inequality constraints
Lecture 15 Introduction To Duality and Interior Point Methods
Lecture -- Affine scaling and affine scaling search.
Lecture 16 Penalty Methods
Lecture 17 Augmented Lagrangean Methods
Lecture 18 Duality Theory
Lecture 19 Duality Theorems
Lecture 20 (2 classes) Strong Duality


back to the top

Grading

1/3 for the homework.
1/3 for the project.
1/3 for the final exam.


back to the top

Homework

back to the top

Project

  • The project will concentrate on a paper, describing either a new algorithm, or some theoretical development, or both. Ideally the project should involve some algorithmic implementation and testing, and/or some conceptual development. It should, albeit on a small scale, be an introduction to research in nonlinear programming. It represents 1/3 of the final grade.

  • A few papers have been selected and are available here. They could serve as a starting point for a project. Keep checking as additional papers may be added in the coming weks.

    • back to the top

    Exams

      There will be a final take-home exam to be done over two days during the exam period. This will count for 1/3 of the final grade.

    back to the top

    Slides

    back to the top

    Interesting Links about Operations Research/Management Science