Monthly Archives: March 2013

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 | 1 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 | 9 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

Announcement: Stochastic Analysis Seminar blog

The Stochastic Analysis Seminar is a weekly seminar that we run here at ORFE. Since 2011 Ramon van Handel has transformed it into an informal seminar course. The idea is that each semester we pick a contemporary topic in probability that … Continue reading

Posted in Uncategorized | Comments Off on Announcement: Stochastic Analysis Seminar blog

ORF523: Getting around NP-hardness

In this post I would like to argue that showing $latex {\mathbf{NP}}&fg=000000$-completeness of a problem is in fact only a weak certificate of difficulty. Dynamic Programming Consider the problem $latex {\mathrm{PARTITION}}&fg=000000$ of the previous lecture (which is $latex {\mathbf{NP}}&fg=000000$-complete): given … Continue reading

Posted in Theoretical Computer Science | Comments Off on ORF523: Getting around NP-hardness

ORF523: P vs. NP, NP-completeness

We are now going to restrict our attention to Boolean functions $latex {f : \{0,1\}^* \rightarrow \{0,1\}}&fg=000000$. Computing a Boolean function is called a decision problem, since we need to decide for $latex {x \in \{0,1\}^*}&fg=000000$ whether or not it is … Continue reading

Posted in Theoretical Computer Science | Comments Off on ORF523: P vs. NP, NP-completeness