OPIM 914

OPIM (Wharton)

OPIM-914: Nonlinear Programming

Tuesdays and Thursdays 3:00-4:30PM

Spring 2007
Professor Monique Guignard-Spielberg

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

================================================
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

================================================
Exam period: (starting 26 April 2007)

The final exam is available.
The no-cheating form must be returned with the exam.
The project report must be returned at the latest on May 4.

back to the top
New this week: (9 April 2007)

Homemork 5 is available.

back to the top
New this week: (2 April 2007)

Makeup classes on 4/04, 3-4:30, in room JMHH F38.
Recommended reading:
Kuhn in the OR Hall of Fame.
Tucker in the OR Hall of Fame.
Kantorovich in the OR Hall of Fame.
list of individuals in the OR Hall of Fame.

back to the top
================================================
New this week: (26 March 2007)

Makeup classes on 3/28 and 4/04, 3-4:30, in room JMHH F38.

back to the top
================================================
New this week: (19 March 2007)

No class on Tuesday.
Look at for "painless" conjugate gradient....

back to the top
================================================
New this week: (26 February 2007)

There are a couple more papers in the project folder. Homework 3 is available.
================================================
New this week: (19 February 2007)

There will be a makeup class Wed. Feb. 21, 3-4:30, in room F85.
Homework 3 is available.
================================================
New this week: (12 February 2007)

Look at the project section for an initial selection of papers that could serve as starting points for a project

================================================
New this week: (5 February 2007)

Look at the following for more information on symmetric and on positive definite matrices.
symmetric matrices
matrix algebra
matrix operations look in particular at 31.6.
special matrix types
matrix algebra (for economics)
orthogonality and eigenvectors
determinant tests.

You may also want to refer to these short articles on orthogonal and unitary matrices to refresh your memory.

Homework 2 is available.
================================================

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@wharton.upenn.edu
URL: http://opim.wharton.upenn.edu/~guignard
Office Hours: Tuesday 1:30-3 and by appointment.

back to the top

Textbooks

"Nonlinear Programming: 2nd Edition", by Dimitri P. Bertsekas
Athena Scientific Press,
ISBN: 1-886529-00-0
Publication: 1999, 780 pages, hardcover
Price: $89.00

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

http://www.athenasc.com/nonlinbook.html

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