EE236A: Linear Programming

• Lecture notes
• Homework
• Course information
• Software

1. Introduction and overview (4/page)
2. Linear inequalities (4/page)
3. Geometry of linear programming (4/page)
4. The linear programming problem (4/page)
5. Structural optimization (4/page)
6. FIR filter design (4/page)
7. Applications in control (4/page)
8. Network optimization (4/page)
9. Duality (part 1) (4/page)
10. Duality (part 2) (4/page)
11. The simplex method (4/page)
12. The barrier method (4/page)
13. Convergence analysis of the barrier method (4/page)
14. Primal-dual interior-point methods (4/page)
15. Self-dual formulations (4/page)
16. Large-scale linear programming (4/page)
17. Integer linear programming (4/page)

Instructor: Prof. Lieven Vandenberghe
Office: 68-119 Engineering IV
Tel: (310) 206-1259
Email: vandenbe@ee.ucla.edu
Office hours: Wednesday 2-4PM.

Course material. The lecture notes are available from this website. The following books may be useful as optional reference texts:

• D. Bertsimas and J. N. Tsitsiklis, Introduction to linear optimization (Athena Scientific).
• S. J. Wright, Primal-dual interior-point methods (SIAM).
• C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization. Algorithms and complexity (Dover).

Course requirements

• Weekly homework. Most assignments will involve Matlab programming.
• Open book final exam on Tuesday, December 11, 8-11AM.

Grading. Approximate weights: homework 30%, final exam 70%.

Prerequisites. Basic linear algebra (vectors, matrices, linear equations). The essential topics will be reviewed in the first lectures.

Approximate syllabus

1. Introduction
2. Basic definitions and geometry of linear programming
3. Engineering applications
4. Duality
5. The simplex method
6. Interior-point methods
7. Large-scale linear programming
8. Introduction to network optimization and integer linear programming

Students who don't have the optimization toolbox can request a free semester license of the MOSEK optimization tools for Matlab (Click on "Trial license" in the left column of the MOSEK home page). MOSEK includes an LP solver linprog with the same calling sequence as Matlab's linprog.

You can also use the routine lp236a.m, a pure Matlab implementation of a primal-dual method. This code is less efficient and reliable than the MOSEK solver, but should be adequate for the purposes of this course.

The following Matlab packages allow you to specify and solve LPs using a very simple and intuitive description format: CVX (which includes the necessary solver) and YALMIP.

Octave

Python