derivative-free optimization

user30490

13:08

Hi there @Paul

Paul

hi @user30490

user30490

Thanks for setting this up

Paul

no problem! optimization is an old interest of mine. most of my PhD research was on optimization

user30490

So I guess I just wanted to give a better description of the problem I am working on to you

NIce!

Are you familiar with black box optimization?

Or the idea of a black box simulator?

Paul

yeah, your values of f(x) and c(x) come from a simulator and you don't know what it's doing, but it's probably complicated

most likely you are an engineer or working closely with them

user30490

13:11

That is correct

So I can evaluate the computer simulator

Paul

how complex is that simulation? like order of magnitude lines of code? and how long does it take to evaluate f(x) and c(x)

user30490

Well right now I am just running it on toy examples

so I actually do know f(x) and c(x)

Paul

sure, makes sense

user30490

and so evaluating them is trivial

So what I do is

Paul

i mean in the target application, after you're satisfied with the toy examples. how complex

user30490

13:15

I start with an initial set of points x and get back f(x) and c(x)

from these "inputs" (x) and "outputs" (f(x),c(x))

I build a surrogate model for f(x) and c(x) using a Gaussian Process

Paul

something similar to this? scikit-learn.org/stable/modules/gaussian_process.html

user30490

so now I have an approximation for f(x) and c(x) because in the black box world the assumption is that evaluating the true f(x) and c(x) is computationally costly

100%

similar

Gaussian Processes (GP's) are also a special case of a radial basis function if your more familiar with that

but in any event

I build teh surrogates because they are cheaper to evaluate and work with

and they give me prediction at new x values

Paul

yeah, that makes sense. you're just trying to make the absolute best use of the info you have, since querying new points is costly

user30490

yup

Paul

but you also want some theoretical guarantees on convergence

user30490

13:20

yes

and as of now I have empirical convergence

just not theoretical

but so after I build my GP surrogate models

the next thing we do is say

ok, I need more actual evaluations from the black box simulator, let's pick the next point that we think is best. And best is judged by will this value of x return a c(x) that meets the constraint and is smaller than my previous f(x)

so I am trying to pick new points, iteratively, that I think do better at minimizing f(x) while also satisfying c(x)

and so i do this, iterating until convergence

which really means I run the code as long as I can until I run out of computational budget

and so I am not too concerned about discovering the rate of convergence but just that it has convergent properties

be it locally or globally

Paul

yeah, all this makes sense. this is a textbook application of DFO in an engineering context.

user30490

yup

and I have seen many papers out there on convergence proofs

just none that exactly fit my problem

and so what I was hoping to get out of my posting of the question

was kind of a checklist of criteria to need to ensure teh method convereges

and that's why I have also been vague about what f and c are

because as of now I am not really assuming anything about them

but am willing to if it helps makes a convergence argument

Paul

sure. the first thing i would say is, this problem is at the absolute frontier of theoretical analysis, possibly beyond. definitely manage expectations on what is provable.

user30490

ok

I have kind of gotten that impression given that I haven't been able to find much

Paul

i believe that Michael Powell's UOBYQA algorithm has some theoretical convergence results, but that is for unconstrained optimization. He also did this COBYLA algorithm for nonlinear constrained optimization, but was not able to prove anything about it.

and he's the best, so you will probably not get much farther than he got, unless you take advantage of special knowledge about f and c.

user30490

13:31

ok

Paul

now i'm not an expert on DFO but i can tell you how it probably works

we know how to prove convergence of gradient descent to a local optimum

user30490

ok

Paul

and if we don't have derivatives, we can at least hope to construct a surrogate that has similar shape to the true function

especially when we're close to a local optimum, where f(x) has a locally quadratic shape.

here's how i would approach it

i would try to prove successively more general convergence results

start with unconstrained quadratic optimization

once you have that, you will be close to a proof of local convergence. that is, if you're close to the optimal point, you will get there, because in the neighborhood of the optimum the function is basically quadratic

user30490

ok

Paul

then you can try adding in a simple constraint, such as a bound constraint (x>=0)

try to build up from very simple, not-ambitious results and see how far you can get. this stuff is hard and any proofs at all represent progress

especially since you are proposing a new algorithm (well there may be precedent but i'm not familiar with it)

user30490

13:41

ok

also I expect that my constraints will be highly nonlinear, which sounds like that will be a problem?

Paul

yes. like i said, people have attempted theoretical results on DFO with general nonlinear constraints, and failed

user30490

ok

Paul

however, you can again simply things using local arguments

user30490

well thanks for the discussion

I actually have to run

Paul

if c(x) is smooth it is locally linear

user30490

13:44

but this was very helpful

Paul

so you try to minimize f(x) under linear constraint, and if your algorithm can do that, a local convergence result is not far off

very glad to be of service! best of luck. you can get theoretical results. any results, even special case type results, will be a significant advance

just think: f(x) is locally quadratic, and c(x) is locally linear.

that's how you get off the ground.

good luck

Paul

13:59

in UOBYQA, i think the main idea is, you can reconstruct a multidimensional quadratic function via interpolation, and once you've done that, you can find the minimum in one step

so if a function is roughly quadratic you can approximate it via interpolation and find a rough minimum

i think most DFO theory must be based on a similar concept

Transcript for

derivative-free optimization