Monthly Archives: February 2013

ORF523: Turing Machines

So far we have seen several algorithms to solve various optimization problems. For example for LPs we have seen that the ellipsoid method has a computational complexity of roughly $latex {O(n^4)}&fg=000000$, and we improved this bound with Interior Point Methods … Continue reading

Posted in Theoretical Computer Science | Comments Off on ORF523: Turing Machines

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

Guest post by Philippe Rigollet: Estimating structured graphs

Last wednesday, Sourav Chatterjee was speaking in the Mathematics Colloquium here at Princeton. While he is most famous for his contributions to probability, especially using Stein’s method, this talk was rather statistical. The problem was interesting and its solution simple enough that … Continue reading

Posted in Random graphs | Comments Off on Guest post by Philippe Rigollet: Estimating structured graphs

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: $latex \displaystyle \inf_{x \in {\mathbb R}^n : f_i(x) \leq 0, h_j(x) = 0, … Continue reading

Posted in Optimization | Comments Off on ORF523: Lagrangian duality

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 $latex {\mathcal{X}}&fg=000000$ (with non-empty interior) with a $latex {\nu}&fg=000000$-self-concordant barrier $latex {F}&fg=000000$ is of order $latex {O\left(M \sqrt{\nu} \log \frac{\nu}{\epsilon} \right)}&fg=000000$ … 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 $latex {\min_{x \in \mathcal{X}} f(x)}&fg=000000$ (with $latex {\mathcal{X}}&fg=000000$ a convex body in $latex {{\mathbb R}^n}&fg=000000$ and $latex {f}&fg=000000$ a convex function) in ‘time’ $latex {O( \max(M, n^2) n^2 )}&fg=000000$ … 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 $latex \displaystyle \mathcal{E} = \{x \in {\mathbb R}^n : (x – c)^{\top} H^{-1} (x-c) \leq 1 \} ,&fg=000000$ where $latex … Continue reading

Posted in Optimization | Comments Off on ORF523: the ellipsoid method

ORF523 (‘Advanced Optimization’): Introduction

In optimization we are ‘given’ a set $latex {\mathcal{X} \subset {\mathbb R}^n}&fg=000000$, and a real-valued function $latex {f}&fg=000000$ defined on this set. The objective is to find a point $latex {x^* \in \mathcal{X}}&fg=000000$ which minimizes $latex {f}&fg=000000$ on $latex {\mathcal{X}}&fg=000000$. … Continue reading

Posted in Optimization | 7 Comments