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

- 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. - Quadratic Programming.

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.

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