Proving Convergence of a Derivative Free Method

Hopefully this question is on topic for the mathematics community (rather than the statistics) 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)\leq 0$$ where $f(x)$ is scalar valued. I don't have any gradient information about $f(\cdot)$ or $c(\cdot)$ (so the derivative free optimization case), and in fact, 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)$. These kind of problems arise in field of computer modeling and are what is known as a blak box optimization problem. 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).

Basically though, my procedure follows this paper: Filter Methods but like I said I am in the derivative free optimization setting and I assume I don't know the exact forms of $f$ and $c$. I could of course follow what the paper describes, but the problem is I am not using a trust region to solve the subproblem of picking new points, but rather, and using a statistical models that picks the "next best point" based on a predictive criteria.

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

Here are some of my assumptions so far:

The input space $\mathcal{X}\subset\mathbb{R}^d$ is a known, bounded, convex region such that $f:\mathcal{X}\rightarrow\mathbb{R}$ denotes a scalar-valued objective function and $c:\mathcal{X}\rightarrow\mathbb{R}^m$ denotes a vector of constraint functions.

Other than that I have no other assumptions, although I am willing to assume that $f$ are $c$ are lower bounded, continuous, and twice differentiable (so basically a nice smooth function).

• A sketch of how to approach this problem would be appreciated as well if a proof is not able. – user6291 Oct 29 '15 at 0:12
• I mean... if you don't have ANY form of expression for $f$ and $c$, this is just ill-defined. What are you minimizing? If you have data and some assumptions on the functions, then first estimate the functions and get an expression for $f$ and $c$, THEN maybe something can be done. In its current form, it's not even an optimization problem. – Benjamin Lindqvist Nov 4 '15 at 7:55
• @BenjaminLindqvist well I don't know the forms of $f$ and $c$ because they are functions that come from a black box computer model (en.wikipedia.org/wiki/Black_box). So $f$ and $c$ could be linear, nonlinear, convex, continuous, differentiable....but I don't get to know what they are. – user6291 Nov 4 '15 at 17:08
• You seem to think a black box is a legitimate mathematical model, which it is not. You can't minimize something if you don't know what you're minimizing. If you HAVE a machine that takes $x$ as input and outputs $f(x)$, then you have the means to estimate it. But until you do, your question is basically equivalent to "solve f(dog) = potato". – Benjamin Lindqvist Nov 4 '15 at 17:36
• Also, without assumptions on the functions, there is no way you can prove convergence. What if $f$ isn't convex? What if it's discontinuous? What if no local minima even exist? – Benjamin Lindqvist Nov 4 '15 at 17:44

The following is what I would do in such case.

If you know $f(x)$ for a certain set of $x\in{\bf X}$, then you can construct interpolation polynomial for which the error can be estimated. Similarly about $c(x)$.

Denote $P^f_n(x)$ a polynomial such that $\|P^f_n(x) - f(x)\|\to 0$. Similarly $P^c_n(x)$ a polynomial such that $\|P^c_n(x) - c(x)\|\to 0$.

Now approximate $$f^*=\min_{x:c(x)<0} f$$ using $$P_n^*=\min_{x:P^c_n(x)<0} P^f_n(x)$$

Analyze the error $\|f^*-P_n^*\|$ to hopefully find it is $\to0$ as $n\to\infty$.

In order to make such an analysis you have to make some certain assumptions on your functions $f(x)$ and $c(x)$, for example you have to assume some level of smoothness, belonging to some certain function space, existence of expansion in some basis etc, etc. If you success to prove something under such assumptions it doesn't say that this doesn't work without, but this is the only case you can prove so far. Later you can try to prove for another, hopefully expanded subspace of functions.

Another option is to work with finite differences instead of derivatives, which is in some sense similar, to the described above, but may be slightly less general.

• Hi Dr. Medvinsky, so using $P_n^*=\min_{x:P^c_n(x)<0} P^f_n(x)$ is exactly what I am doing. In my case, $P^f_n(x)$ and $P^c_n(x)$ are built from a Gaussian process (hence the statistical model part I mentioned). And this is true $\|f^*-P_n^*\|\rightarrow 0$ as $n\rightarrow\infty$ in my case. But I am still having trouble showing that proves convergence using the filter approach. – user6291 Nov 7 '15 at 16:14
• As long as $P_n^*$ is polynomial you know its derivatives. similarly if you can assume expansion of $f^*$ in some appropriate basis you can differentiate the basis functions. You say that experimentally you see it is converges which is good. To prove it analytically you will need to choose an appropriate representation of the functions and to choose a norm for which it is doable. To say more I will need to see more details. Particularly the l expression of $P_n^*$ in terms of given set of pairs $(x_i,f(x_i), 1\lei\le n$. And even after looking at this I can't promise immediate help. – Michael Medvinsky Nov 7 '15 at 17:40