Category Archives: Optimization

ORF523: Oracle complexity of smooth convex functions

In this lecture we consider the unconstrained minimization of a function that satisfy the following requirements:  (i) admits a minimizer on . (ii) is continuously differentiable and convex on . (iii) is smooth in the sense that the gradient mapping … Continue reading

Posted in Optimization | Leave a comment

ORF523: Oracle complexity of Lipschitz convex functions

In this lecture we consider the unconstrained minimization of a function that satisfy the following requirements: (i) admits a minimizer on such that . (ii) is convex on . Recall that in particular this implies for any . (iii) is … Continue reading

Posted in Optimization | 5 Comments

ORF523: Oracle complexity, large-scale optimization

Our study of the computational complexity of mathematical optimization led us to realize that we are still far from a complete understanding of what exactly can be optimized with a computer. On the positive side we proved that some problems can be … Continue reading

Posted in Optimization | 2 Comments

ORF523: Classification, SVM, Kernel Learning

In this post I will go over some simple examples of applications for the optimization techniques that we have seen in the previous lectures. The general theme of these examples is the canonical Machine Learning problem of classification. Since the … Continue reading

Posted in Optimization | 2 Comments

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 | 7 Comments