Lectures notes

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)

Homework

• Homework 1 (due 10/11): Exercises 2, 6, 8 (a,c,d,e,g), 9, 11.

• Homework 2 (due 10/18): Exercises 12, 14 (b), 15, 20, 36.

• Homework 3 (due 10/25): Exercises 22, 23, 26, 30, 31 (a).

• Homework 4 (due 11/1): Exercises 28, 29, 33, 40, 41.

• Homework 5 (due 11/8): Exercises 42, 44, 50, 53, 55.

• Homework 6 (due 11/15): Exercises 45, 54, 58, 63, 66.

• Homework 7 (due 11/29): Exercises 46, 47, 69, 71, 72, 74.

• Homework 8 (due 12/7): Exercises 75, 76, 86. Submit your code for problem 86 by email to vandenbe@ee.ucla.edu.

The homework assignments are from the EE236A Exercises. Some of the problems require Matlab files: ex9data.m, ex15data.m, ex17data.m, ex18data.m, ex20data.m, ex35data.m.

Software

• Matlab The Matlab LP solver is called linprog and is included in the optimization toolbox. 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 Octave users can download the Octave version of lp236a.m.

• Python Python users can download the CVXOPT package, which includes an LP solver and modeling support.

Course information

Lectures: Boelter Hall 5273. Tue & Thu 10:00-11:50A.

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.