# Provable Convergence

Hopefully this question is on topic for the statistics community (rather than the pure math) since the optimization method I am using relies on a statistical model. Well I am building an algorithm for constrained optimization, so a problem like, $$\min_x f(x)$$ such that $$c(x)\leq0$$ where $f(x)$ is scalar valued. Why this is a statistics problem, is that I don't know the analytical forms of $f(\cdot)$ or $c(\cdot)$ but I do have some inputs $x$ and their corresponding outputs $f(x)$ and $c(x)$. So you could kind of think of this as a regression problem where I know some inputs and outputs and I want to fit a response surface for $f(\cdot)$ and $c(\cdot)$ and try to minimize that true function based on the predictive response surface I have built (hopefully I am not omitting too many details). So its an iterative procedure where I gather my data (the inputs and outputs) in time and so far empirically the procedure works. However, now I want to prove theoretically that my algorithm will converge to the (or possibly a local) solution. And there is where I am stuck. I don't really have too much intuition about how to prove this so any suggestions or citations would be very much appreciated.

• Obviously if needed I can give more details.
– user30490
Aug 25 '15 at 1:37
• This certainly cannot be generally true, you will need some assumptions about $f$ and $c$ (also it's not clear if $x$ is a scalar or a vector?). Hopefully for your problems, you can assume something like convexity of $f$. Even still, fairly advanced algorithms will be required (if $x$ is a vector) for the case of $c$ being a linear transformation. Aug 27 '15 at 17:31
• Hi @CliffAB, thanks for the response. $x\in\mathbb{R}^d$ so not always scalar.
– user30490
Aug 27 '15 at 17:36
• I haven't made any explicit assumptions about $f$ and $c$ other than that I am modeling them using a Guassian process so perhaps my assumptions about the form of $f$ and $c$ should be based on that?
– user30490
Aug 27 '15 at 17:37
• To prove convergence to the exact solution, you will need $f(x)$ to come from a specific parametric class of functions so that your global response surface is the true surface. If you can't assume that, you will never know if the response surface optimum is the true optimum (or even local), and the best you can hope for is to prove approximate convergence with high probability, or perhaps an asymptotic result - arbitrarily accurate convergence in the limit as number of samples goes to infinity. Which of these results are you interested in?
– Paul
Aug 27 '15 at 20:50

In one of your comments you state that you not only have values of $f(x)$ and $c(x)$ at various $x$, but can also evaluate $f(x)$ and $c(x)$ at new points. This means you are essentially doing ordinary numerical optimization. The lack of an analytical form for $f(x)$ and $c(x)$ is not an issue for most optimization algorithms, because they wouldn't use it even if they had it. They generally construct an easily optimized surrogate based on values and derivatives from the last few points, optimize the surrogate to get a new candidate optimum, and iterate. The only requirement for such a procedure is the ability to evaluate $f$ and $c$ and perhaps some derivatives.

All that is needed for convergence to a local optimum is some mild smoothness/regularity conditions on $f$ and $c$. Global convergence is hard to prove unless you're doing (quasi-)convex optimization.***

If you are able to compute gradients or Hessians of $f$ and $c$, there is an extensive classical literature on optimization algorithms that provably converge to local optima. Numerical Optimization by Nocedal and Wright is a good introduction. This literature is the foundation of all mathematical optimization theory, even if gradients and Hessians are not available in your problem.

If you cannot compute gradients or Hessians, you are doing derivative-free optimization (DFO). There are convergence results for unconstrained DFO, and for DFO with linear and bound constraints. For DFO with general nonlinear constraints I do not know of any proof results. There is the COBYLA algorithm by Michael Powell, one of the most productive researchers in DFO, but no proofs to my knowledge. This paper and this book are written by top DFO researchers and should help you get acquainted with the literature on what has been proven and how.

***It's always worth thinking for a moment about whether your problem has a quasiconvex flavor, because the benefits are potentially enormous. If you have two points $x_1,x_2$ and their costs $f(x_1), f(x_2)$, and you make a weighted average of the points $x = \alpha x_1 + (1-\alpha) x_2$ for $\alpha \in [0,1]$. Is the cost $f(x) \leq \max(f(x_1),f(x_2))$? Put another way, is a weighted average at least as good as the worst component that went into it?

• thanks for the good resources. I have actually read parts of the Conn book before (awhile ago) so maybe it's time for me to revisit that. And indeed I am doing DFO.
– user30490
Aug 29 '15 at 4:56
• I would love to pick your brain a bit offline (well off this site) as well if you don't mind.
– user30490
Aug 29 '15 at 4:57
• I set up an SE chatroom for us (chat.stackexchange.com/rooms/27549/derivative-free-optimization). I'll be around from now till 11:30 EDT. Feel free to drop by.
– Paul
Aug 29 '15 at 12:36

You are not going to get very far without some assumptions about $f$ and $c$. The standard assumption is Lipschitz continuity, which guarantees that the function cannot be too badly behaved between evaluation points. Without Lipschitz continuity you cannot say much, because even in the one-dimensional case over an interval you cannot rule out the possibility of an arbitrarily deep hole between any two points where the function has been evaluated.

Can you sample the function values iteratively? You do not say so explicitly, and it does make a difference. If you can sample, there are a number of derivative-free optimization algorithms, such as COBYLA.

If you cannot sample, the best you can hope for, even with Lipschitz continuity, is a confidence interval for the optimal objective value, with very limited information about the location of the optimum.

• I do sample the function values iteratively. Also, I don't need suggestions on methods, I already have a method that I am designing, I just want to know how to show that my method will converge.
– user30490
Aug 28 '15 at 2:07
• OK. Let me try again. You want to quantify the maximum error (this is where Lipschitz comes in), and you want to show that the error goes to 0 as your sample size increases. Without a clear description of your method I doubt anyone else can tell you more than that. Aug 28 '15 at 3:06

Possibly useful things to think about: 1: Can you prove your estimate of the parameters in f and c is consistent? Do they always converge to the true values (assuming the form is correct) as the sample size gets bigger? For example, maximum likelihood estimators are consistent. 2: Can you prove the control variable x converges to the the optimal value? Something like the Karush-Kuhn-Tucker conditions might be useful.

• Don't you need derivative information for the Karush-Kuhn-Tucker conditions? I don't have any derivative info.
– user30490
Aug 27 '15 at 21:24
• Like Paul's comment above, I'd assumed you were using a particular parametric form. The derivatives could then be calculated from the specific form. Are f and c smooth? Then it might be possible to assume they can approximated by quadratic functions near a local optimum. Aug 28 '15 at 9:11
• $f$ and $c$ are assumed to be smooth and/or nice behaving functions.
– user30490
Aug 28 '15 at 12:58
• If they are nice enough functions, they will have Taylor expansions about a local optimum (or any other point). Aug 28 '15 at 14:11

There is a paper reviewing your kind of problem: A Taxonomy of Global optimization Methods Based on Response Surfaces. I skimmed it once but don't remember exactly what they have and whether or not they consider constrained optimization, but it's an OK place to start. Basically, the method is to model the function using Gaussian Process Regression and then take an optimization step based on the interpolant. This may or may not fit your line of thought. Let me know if you don't have access to the paper and I'll send it to you.

More broadly, what you might be interested in is derivative-free optimization (or so it seems). For this there are many methods that I am not familiar with and even software packages (I'm pretty sure pyton's scipy has some flags in its "minimize" funciton that allow you to do derivative free optimization). You can google "derivative-free optimization" and see what you find. Also, one specific method that I like (though never used) is adaptive coordinate descent.

If you have a method that you like and you want to use it for constrained optimization, one of the first things I would try is to take optimization steps according to the method but after that, project to the subspace / manifold that satisfies the constraint.

• @Yasir, thanks for the citations and I have already actually seen that paper before. The paper is very close to what I am doing, i.e., obtain data from unknown functions, use Gaussian processes to build surrogates models for the functions, use a criteria to select new points that moves in the direction of the minimum, and iterate.
– user30490
Aug 27 '15 at 21:30
• So you are able to query for more values of $f$ and $c$ as you optimize?
– Paul
Aug 27 '15 at 22:04
• @Paul, Yes. I start with an initial set of values, fit my Gaussian Process model for both $f$ and $c$, then predict what $f$ and $c$ look like for values of $x$ I haven't sampled yet, then I choose the point $x$ that I think (based on my predictions) that meets the constraint $c$ and minimizes $f$, then I evaluate the point $x$ I chose, update my values that I have and iterate until "convergence".
– user30490
Aug 28 '15 at 12:57
• Then you are doing derivative-free optimization (DFO). There are convergence results for unconstrained DFO, and for DFO with linear and bound constraints. For DFO with general nonlinear constraints I do not know any results. Check the wikipedia article on derivative-free optimization and the links therein. This paper will help you get acquainted with the literature: damtp.cam.ac.uk/user/na/NA_papers/NA2007_03.pdf
– Paul
Aug 28 '15 at 21:59
• @Max can I pick your brain again?
– user30490
Oct 29 '15 at 1:00