The outline can also be downloaded as a postscript attachment caam664.ps.

When and Where: Monday and Friday between 3.30 - 4.55 PM in DH 1042. Kartik's office hours are Tuesday and Thursday between 11.00 - 12.00 PM, and by appointment. To set up an appointment, please send me an email.

Course webpage: The "official" webpage for this course is located at http://www4.ncsu.edu/~kksivara/caam664
Please check the webpage regularly for announcements regarding the course. I will also post most of the course material, including papers on the readings list here. I will try and keep this webpage up to date. Please inform me about missing links, and necessary updates by sending email to kksivara@ncsu.edu.

Course Outline: This course deals with "well structured" convex programming problems in a conic setting. Three important examples include linear programming (LP), second order cone programming (SOCP), and semidefinite programming (SDP). These problems arise in a variety of applications, and we can now solve them in time that is "polynomial in the problem size, and the accuracy desired" : how, why, and where? are the subject matters of this course. The primary emphasis is on semidefinite programming theory, algorithms, and applications.

Here is a list of topics that we will cover during the course. I will follow this outline more or less closely.

1.

Linear programming: A quick review of linear programming, including its geometry and duality theory.

2.

From linear to conic programming: The transition from linear programming to convex programming problems in a general conic setting. We will then discuss duality theory for conic programming. A few applications of conic programming are then presented.

3.

Semidefinite Programming: An overview of semidefinite programming, the primary example within the conic programming class. We will also discuss its geometry, duality theory, issues like nondegeneracy, complementarity etc.

4.

Applications of SDP: Approximation algorithms for combinatorial optimization, the Goemans Williamson algorithm, the Lovasz theta problem, applications in control, stability analysis, structural design, finance, chip design, and robust mathematical programming.

5.

Basic Interior-Point Theory: An overview of the basic theory of self concordant barrier functionals, their properties, Newton's method, and primal algorithms for conic programming. In particular we will discuss the generic barrier algorithm for conic programming, and also variants which include the long step barrier method, and the predictor corrector method. Although these interior point methods are not employed in practical implementations they serve to illustrate the worst case polynomial complexity of conic programming.

6.

Primal-Dual Interior Point Algorithms: We then discuss primal-dual interior point algorithms, the most successful implementations of interior point methods in practice. In particular we will cover notions like central paths, self scaled cones, and the generic primal dual path following algorithm. We will then examine primal-dual interior point methods for the SDP : in particular I shall discuss one algorithm within this class in detail with regard to the proof of its convergence, and polynomial complexity.

7.

Polynomial interior point cutting plane methods for SDP: The well structured convex programs mentioned above can also be solved in polynomial time using interior point cutting plane methods. I will present a brief introduction to the theory, and we shall apply this to the special case of the SDP.

8.

Second order cone programming: A brief overview of second order cone programming theory, algorithms, and applications.

I will give classroom lectures during the first part of the course, whereas the second half of the course, especially the last two weeks will be a series of student presentations. Each student is required to referee, and prepare and present a 75 minute talk [60 minutes for the presentation, and 15 minutes for questions and discussions] from a paper I post on the "readings list". The paper may discuss theory, algorithms or applications. You should describe the major contribution of the paper, and type out a short summary [3-5 pages long], which I will distribute in class before your presentation. This presentation will serve as an excellent opportunity to hone various skills you may need later in your research career.

Finally, everyone who is successful in completing these requirements gets an "A" for the course.

Textbooks:

For your convenience, the first book is available here, and the second book is available here.

I have also ordered these books from SIAM, and they should be available at the campus bookstore shortly.

These two books are also available on reserve in the library. I recommend that you purchase the first book, since it will serve as the primary reference material for the course.

Reference Material:

I will also draw some material from current papers. These papers can be downloaded from the Readings List.

Prerequisites: Knowledge of calculus, linear algebra, analysis, and the proverbial "mathematical maturity" are essential. Familarity with linear programming, and basic nonlinear programming is a plus, although I shall review most of the material. If you have any questions feel free to drop by, and talk to me about it.