Category Archives: Optimization

ORF523: Lagrangian duality

In this post I review very basic facts on Lagrangian duality. The presentation is extracted from Chapter 5 of Boyd and Vandenberghe. We consider the following problem: Let be the non-empty domain of definition for this problem (that is the … Continue reading

Posted in Optimization | Leave a comment

ORF523: IPMs for LPs and SDPs

We have seen that, roughly, the complexity of Interior Point Methods to optimize linear functions on a convex set (with non-empty interior) with a -self-concordant barrier is of order where is the complexity of computing the Newton direction (which can … Continue reading

Posted in Optimization | 2 Comments

ORF523: Interior Point Methods

Khachiyan’s ellipsoid method was such a breakthrough that it made it to The New York Times in 1979. The next time that optimization theory was featured in The New York Times was only a few years later, in 1984, and … Continue reading

Posted in Optimization | 2 Comments

ORF523: LP, SDP, and Conic Programming

Recall from the previous lecture that we can ‘solve’ the problem (with a convex body in and a convex function) in ‘time’ where is the computational complexity of finding a separating hyperplane from at , and computing the and order … Continue reading

Posted in Optimization | 3 Comments

ORF523: the ellipsoid method

In this lecture we describe the wonderful ellipsoid method. Recall that an ellipsoid is a convex set of the form where , and is a symmetric positive definite matrix. Geometrically is the center of the ellipsoid, and the semi-axes of … Continue reading

Posted in Optimization | Leave a comment

ORF523 (‘Advanced Optimization’): Introduction

In optimization we are ‘given’ a set , and a real-valued function defined on this set. The objective is to find a point which minimizes on . This goal is ambitious. It encompasses an enormous variety of problems, from engineering … Continue reading

Posted in Optimization | 6 Comments

Announcement: lecture notes on optimization

This semester at Princeton I am going to teach a graduate course on ‘advanced optimization’. As you can see from the title, I’m allowing myself a lot of flexibility, and I will discuss various topics. The syllabus for the course … Continue reading

Posted in Optimization | Leave a comment