Generate a random feasible solution?

[Baihong Jin]

Hi Johan,

I know that the feasibility of an optimization problem can be checked by using YALMIP by setting the objective function to be a constant. If the problem is feasible, the solver will return some feasible solution. Further than that, I've been looking for a way to generate a "random" (not necessarily be fully random, but I wanna get different results out of each run) feasible solution using YALMIP. Are you aware of any way to do that? Thanks!

Baihong

   

[Mark L. Stone]

How about using random objective functions, for instance, linear objective functions with random coefficients? If that doesn't get you enough different solutions, then add (bound or linear) constraints on subsequent solves to exclude previous solutions.  How well this works depends on the problem type and how you generate the random coefficients.  There are also "semi-random" things you can do, such as minimizing or maximizing one variable at a time, or sum of 2 at a time, etc..  Of course, if you don't impose constraints to exclude previous solutions, you may wind up getting some duplicate solutions,.

I have used such a technique to find different feasible starting points for use by a nonlinear optimizer on non-convex linearly constrained nonlinear optimization problems.  I solve Linear Programs having the same constraints as the nonlinear optimization problem, using randomly generated coefficients for the LP objective function. It was far better than using the optimizer's built-in way of generating random starting points

[Baihong Jin]

Hi Mark,

Thanks for your suggestion! Actually, I've been looking for random feasible points "within" the feasible region, but usually the optimal points are "on" the boundary of the feasible region, e.g. when we use a linear objective. One approach I can think of is to generate several feasible solutions on the boundary and take their convex combination. However, this only works when the feasible region is convex.

Baihong  

[Johan Löfberg]

Ray-shooting is the standard approach, which you then of course can use to generate interior random points as you say.  Another alternative is to generate random points xi, and then minimize (x-xi)'*(x-xi)

[Baihong Jin]

Thank you so much for the answer!