Princeton University
Department of Civil Engineering
and Operations Research
CIV 569
Interior-Point Methods for Nonlinear Programming
Course Information Fall 1997

Instructor:
Robert J. Vanderbei, ACE-42 E-Quad, 8-0876, rvdb@princeton.edu, http://www.princeton.edu/~rvdb/
Lectures:
MW 1:30–2:50 pm, E-415
Office Hours:
MW 4:30-6:00, ACE-42

### 1 Outline

• Motivating Examples.
Structural Optimization via Finite Element Models, Trajectory Optimization, Minimal Surfaces, Antennae Array Synthesis, Digital Filter Design, Hydrothermal Power Generation.
• Duality.
The Dual Problem, The Weak Duality Theorem, The Strong Duality Theorem, Complementary Slackness, Strict Complementarity, Lagrangian Duality.
• Path-Following Method.
The Barrier Problem, Lagrange Multipliers, Second-Order Information, Computing Step Directions, Newton’s Method, The Barrier Parameter, Step Lengths.
• Homogeneous Self-Dual Method.
From Standard Form to Self-Dual Form, Homogeneous Self-Dual Problems, Predictor-Corrector Algorithm, Convergence Analysis, Complexity of the Predictor-Corrector Algorithm, The KKT-System, Back to Standard Form.
The Markowitz Model, The Dual, Convexity and Complexity, Solution via Interior-Point Methods, Homogeneous Self-Dual Method.
• Convex Programming.
Convex and Concave Functions, Problem Formulation, Solution via Interior-Point Methods.
• Non-Convex Nonlinear Programming.
Merit Functions, Descent Directions, Local Optimality, Global Optimality.

Lecture material will be drawn from the following sources.

### References

   R.J. Vanderbei. Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1996.

   Y. Ye, M.J. Todd, and S. Mizuno. An $$O(\sqrt{n}l)$$-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research, 19:53–67, 1994.

   S. Mizuno, M.J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18:964–981, 1993.

   M.J. Todd. Potential-reduction methods in mathematical programming. Technical Report 1112, SORIE, Cornell University, Ithaca, NY, 1995.

   K.M. Anstreicher. Potential reduction algorithms. Technical report, Department of Management Sciences, University of Iowa, 1996.

   R.D.C. Monteiro and I. Adler. Interior path following primal-dual algorithms: Part i: Linear programming. Mathematical Programming, 44:27–41, 1989.

   R.D.C. Monteiro and I. Adler. Interior path following primal-dual algorithms. part ii: Convex quadratic programming. Mathematical Programming, 44:43–66, 1989.

   D. den Hertog. Interior Point Approach to Linear, Quadratic, and Convex Programming. Kluwer Academic Publishers, Dordrecht, 1994.

   R. Saigal. Linear Programming. Kluwer Academic Publishers, Boston, 1995.

   M. Minoux. Mathematical Programming: Theory and Algorithms. John Wiley and Sons, New York, 1983. Translated by Steven Vajda.