Monthly Archives: February 2013

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 →

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 →

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 →

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 →

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 →

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 →

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 →