How choose MultiStart x0

Hello,

I have a 3D function (e.g. f(x,y)). I find the global minumum with MultiStart. Given lb_x,lb_y,ub_x,ub_y and a linear equality constraint (const=x+y).

When MultiStart runs fmincon "i" times, default random generated x0 starting points satisfy bounds but linear equality constraint is unsatisfied (const not equal x+y). Why? What can I do for generated x0 satisfy equality constraint?

Thanks in advance!

[Matt J]

I have a 3D function (e.g. f(x,y))

If it's a function of only 2 variables, x & y, isn't it a 2D function?

[Zoltan]

3D function: z=f(x,y)

The results (values of x, y) satisfy exactly the linear equality constraint.

Answer 1

[Matt J]

With help from LCON2VERT from the File Exchange, you can generate a random point approximately satisfying the linear constraints.

First, find the vertices, V, of the feasible set using LCON2VERT. Then generate a random point as

 weights=rand(1, size(V,1));
  weights=weights/sum(weights);

 point=weights*V

[Zoltan]

OK thanks, but the results of multistart are ok, although starting points don't satisfy lin. eq. constraint. Perhaps it isn't necessary generate artifical sparting point. I don't understand the solvers method. :(

[Matt J]

It's not necessary, but choosing starting points more likely to be solutions can accelerate the search.

[Zoltan]

When I give a "bad" (ignore constraints, bounds) starting point for fmincon, fmincon generate a new one. How does is fmincon? What is the algorithm?

[Matt J]

It depends which fmincon algorithm you are using. SQP and Interior-Point can honor bound constraints at all iterations and so presumably those algs have some way of mapping the initial point to one that satisfies the bounds. All other constraints are satisfied only asymptotically.

Answer 2

[Matt J]

An equality constraint can never be satisfied exactly because of finite machine precision.

Solutions ultimately found by FMINCON also do not satisfy constraints exactly. They only satisfy them within the TolCon optimset parameter.

[Zoltan]

My problem is not the constraints tolerance (the default value is low).

The generated X0 (x and y) are absolutely bad for the lin. equality constraint.

For example: lin. constraint: 100=x+y generated x by MultiStart: 80 generated y: 93