# 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

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

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