Applying a change of variables inside fmincon

I want to minimize a very well-behaved objective function over the convex hull of a finite set of points .

I am only interested in finding the point where f is maximized, and do not care about the weights that allow me to write .

Of course, I could simply write this as:

popt = fmincon(@(p) f(x'*p),[],[],ones(1,N),1,zeros(N,1),[]);
y = x'*popt;

However, if the points that span the convex hull are nearly multicollinear, then this compound function (as a function of p) is very flat around the optimum. I suspect that this is slowing down fmincon a lot, and would help it "solve the problem" in the space rather than over . What steps could I take to achieve this?

Answer 1

[Matt J]

If the dimension R^l is not too large, you could use vert2lcon

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-polyhedra-in-terms-of-vertices-or-in-equalities

to obtain the linear (in)equalities describing the convex hull of the x_i,

A*y<=b
Aeq*y=beq

Then you can do the optimization directly in the space of y.

[Michele Muller]

The problem is that N might be large, and since the number of facets can grow exponentially in the number of spanning points, I'd rather not do that... but thanks for the suggestion.

[Michele Muller]

I was hoping more for a way to supply a stopping criterion function that would evaluate convergence in y, not p.

[Matt J]

You can impose any stopping criterion you wish using an Output Function

https://www.mathworks.com/help/optim/ug/output-function.html

https://www.mathworks.com/help/optim/ug/output-function.html#f11675

However, it is not necessarily the case that y converges faster than p.

[Michele Muller]

Oh, thanks, that might be useful! Maybe if I combine that with a supplied gradient that points in the right direction? Will try and report back!

[Michele Muller]

Sorry, it took a while, but this seemed to help! I still don't exactly know what's going on "under the hood", but it definitely improved speed, with little if no precision decrease.

Answer 2

[Matt J]

You could add a regularizing penalty to better specify the solution p_i in the cases where it is ambiguous. Maybe an L1 penalty to enourage sparseness, or an L2 roughness penalty.

[Michele Muller]

Is there a way to do this in a "lexicographic" way that doesn't interfere with finding the correct y?

[Matt J]

You need to put a sufficiently small weight on the penalty that the solution is not greatly perturbed.