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

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

[2]   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.

[3]   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.

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

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

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

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

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

[9]   R. Saigal. Linear Programming. Kluwer Academic Publishers, Boston, 1995.

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