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