Course Outline: Optimization is concerned with optimal allocation of resources, and linear programming is the fundamental optimization problem. There has been a great deal of progress in linear programming and very large problems can now be solved routinely using two different types of approaches — the simplex method and interior point methods. This course discusses these two classes of approaches, the theory underlying them, and extensions of the approaches. Interior point methods can be regarded as methods for nonlinear programming applied to linear programming. They can also be used to solve nonlinear programming problems, particularly conic optimization problems.

1. Polyhedral theory: (1 week) The feasible region of a linear programming problem is a polyhedron, ie, the intersection of a finite collection of half spaces. The structure of polyhedra is discussed, including the Goldman Resolution theorem, and the Weyl and Minkowski theorems.
2. Duality: (1–2 weeks) Duality is fundamental to the study of linear programming, and to conic optimization and nonlinear programming more generally. We will return to duality throughout the course.
3. The simplex algorithm: (1–2 weeks) The simplex method is the traditional method for solving linear programming problems. I will discuss the simplex method in matrix terms, and indicate how it can be implemented efficiently.
4. Decomposition and column generation methods for large scale problems: (3–4 weeks) Some large linear programs can be broken into smaller ones and the polyhedral structure of linear programming can be exploited to develop an algorithm. For other problems, the number of variables is very large and an attractive approach is to generate columns of the constraint matrix only as needed.
5. The ellipsoid algorithm: (1 lecture) The ellipsoid algorithm was the first polynomial algorithm for linear programming. It was developed originally as an algorithm for nonlinear programming.
6. Interior point methods for linear programming: (3 weeks) Topics to be discussed include the relationship between these algorithms and traditional nonlinear programming methods, the polynomial complexity of many of these algorithms, the asymptotic rate of convergence of the algorithms, and the computational results achieved. Efficient linear algebra techniques will also be discussed.
7. Conic optimization: (3 weeks) Interior point methods for semidefinite programming and second order cone programming problems will be discussed. Various approaches for large-scale SDPs will also be discussed.

Grading policy: The grade will be determined by three elements: homework, a midterm exam, and a project. The three elements will be equally important. Grades will be posted on LMS.

I will give out a homework approximately every two weeks. The homeworks will probably contain some computational work using AMPL, a mathematical programming modeling language. You should learn a fair amount from the homeworks. Therefore, try working out the solutions on your own. If you have difficulties, you may talk to me or to other students about the homeworks, but you must write up your solutions on your own. You may be able to find the solutions to some of the homework questions on the web: do not use these solutions!

There will be an in-class midterm exam on about Friday, March 15. The exam must be all your own work.

The project will involve modeling and computational testing. Depending on the project, the testing may use AMPL or PYOMO or it may use a programming language such as MATLAB or PYTHON or C or FORTRAN. You will write up your solution and give a presentation in class. The presentation will take place either during the last week of classes or during the time scheduled for a final exam. Your project can be one of the following:

• a topic arising in your research that fits well with the topics covered in the course. You would work on your own on such a project.
• another project you suggest or I suggest. You can work in groups of up to three people on such a project. All group members should contribute equally to the project. Each individual should turn in a one-page description of their contribution to the project along with the group report.

Textbooks:

Required:

Online texts and resources:

Office Hours:

Piazza:

Find our class signup link at: https://piazza.com/rpi/spring2024/matp6640

Prerequisites: MATP4700/ISYE4770, or permission of instructor. Familiarity with linear programming and linear algebra will be assumed. Some elements of MATP6600/ISYE6780 and MATP4820/ISYE4780, such as the Karush-Kuhn-Tucker optimality conditions and Newton’s method, will be used, although it is not necessary to have seen this material before.

Attendance: Strongly encouraged. Active engagement in class will greatly help you in understanding the material.

The World Wide Web: This outline, the homeworks, and other information will be available via my homepage,

In addition, an RPI LMS page has been set up for this course. The software package AMPL will be available from there.

Academic Integrity: Student-teacher relationships are based on mutual trust. Acts which violate this trust undermine the educational process. The Rensselaer Handbook defines various forms of academic dishonesty and procedures for responding to them. The penalties for cheating can include failure in the course, as well as harsher punishments.

Appealing grades: As with any other administrative question regarding this course, see me in the first instance. If we are unable to reach agreement, you may appeal my decision to the Head of the Math Sciences department.

Cell phones: Please make sure that cell phone ringers are turned off during class.