The time has come to publish a post, yet unfinished, with an optimization trick back from the last spring. Suppose we have the following family of convex optimization problems:
parametrized by for fixed Denote the value of the problem corresponding to (obviously is a non-increasing function of ). Given some unknown in advance we are asked to find
Obviously is non-increasing. The question makes sense, for example, in the context of approximation. Specifically, consider the following family of fitting problems:
for fixed and Here, is the overall “budget”, and the columns of provide the approximation vectors used to approximate First we are given the initial resource which provide the error Then we are asked how much of the initial budget we can actually spare without losing the quality of the approximation.
Suppose that each particular problem (for a fixed ) of may be efficiently solved (this is the case e.g. for fitting problems above). Then, we can adopt the following approach: we first evaluate at any point solving the problem instance corresponding to this Since can be evaluated fast for any we can use binary search to find (i.e. each iteration gives us one digit since we restricted ourself in advance with only ). It is evident (why?) that binary search method will yield the correct result.
Discussion. Can we do better (quadratic convergence) for fitting problems? Note that we can almost surely obtain where is the optimal Lagrange multiplier, solving the dual problem (see perturbation and sensitivity analysis in Stephen Boyd’s lectures). Besides, is convex. So what comes to mind is using Newton’s method or some other root-finding method (some of them have superlinear convergence). But to employ each of them, some regularity conditions need to be verified.