Finding an initial feasible point x0 for fmincon

How to find an initial feasible solution x0 for solving a minimization problem with non linear constraints (fmincon)?

For small problems, I can figure out an x0, but for big problems with many constraints that are not linear, I don't see how.

Answer 1

[Matt J]

It is not required that the initial point you choose be feasible.

It is simply helpful to the optimization that your initial guess be as close as possible to the global minimum. Making the initial guess close to your global solution is an art and not a science, and is also problem specific. We would need to see a mathematical description of the problem to advise anything.

Answer 2

[John D'Errico]

Two simple rules apply.

1. If it was easy, then all solvers would do it for you, automatically. There would never be any issues. No complaints. No failures from this.
2. See rule 1.

Essentially, this reduces to finding SOME solution, ANY solution to a set of equality and inequality constraints. Sometimes that really is easy. For example, if you have only linear constraints and bounds, then finding a solution is relatively trivial, at least in terms of the linear algebra.

However, if the constraints are nonlinear, then things get nasty. At least, they can do so.

In fact of course, fmincon DOES try to find an initial feasible point. Does it always succeed? Of course not.

Now, take a look on Answers. Count the number of question that were asked where people have posed a problem for the solution of some system of equations, but a solver fails to find any solution. It is actually not that uncommon. Sometimes it means the person has posed an impossible problem with no solution, yet does not realize it. Sometimes a solution may exist, but the solver could not find one. And sometimes, it is the fault of the person writing the code. They made a mistake, and formlated their problem incorrectly.

Matt J said it very well, that we cannot give you more help beyond the generic without more information.

Answer 3

[Shashank Prasanna]

You can set your objective function to zero keeping constraints as it is and run the optimization to find a new feasible start point.

This is explained in this link:

http://www.mathworks.com/help/optim/ug/when-the-solver-fails.html#br44i73

[Del]

"You can set your objective function to zero keeping constraints as it is and run the optimization to find a new feasible start point."

Even by keeping the objective function zero, fmincon still requires an x0 too, right? Which x0 would I use there?

[Shashank Prasanna]

Did you get an opportunity to read the link? They explain a two step process to first a point that satisfies linear constraints and then use that to find a point that satisfies non linear constraints. I recommend you go through the whole page, which will also answer questions you may have in the future. As Matt J mentioned it is not absolutely necessary that you choose a feasible point but helps to do so.

[Daniela Würmseer]

@Shashank Prasanna

Iam at the same Problem and i was reading the link. Iam in step 2. "Check Nonlinear Constraints". But for "Run your optimization with all constraints and with the zero objective" i need to choose an initial point x0. For now i set

g = zeros(1,sizeX)
xnew = linprog(g,Aneq,bneq,Aeq,beq);
x0 = xnew;
f =@(x) 0;
nonlincon = @constr;
    function [cneq,cq] = constr(x)
        cq = [];
        cneq = zeros(size(c,1),1);
        for k=1:size(c,1)
            cneq(k) = c{k}(x);
        end
    end
opts = optimoptions(@fmincon,'Algorithm','sqp');
problem = createOptimProblem('fmincon','objective',f,'x0',x0,'Aineq',Aneq,'bineq',bneq,'Aeq',Aeq,'beq',beq,'nonlcon',nonlincon,'options',opts);
gs = MultiStart;
[~,~,~,output] = run(gs,problem,50);

But with this initial Point x0 i get in my Example (see down) the Error:

Error using sqpInterface
Nonlinear constraint function is undefined at initial point. Fmincon cannot continue.

(@Matt J you said it is not necessary that the initial Point is feasible but why is this then not working?)

This is my Example:

f1=@(x) x(1);
f2=@(x) x(2);
Aneq = [-1 0
         0  -1];
bneq = [0; -2];
Aeq = [];
beq = [];
c= cell(1,1);
c{1} = @(x) 1/x(1)-x(2);
sizeX = 2;

[Matt J]

(@Matt J you said it is not necessary that the initial Point is feasible but why is this then not working?)

Because you haven't tested your nonlinear constraint functions to see what it returns at x0. It is not necessary that x0 be feasible, but nonlincon must return a finite value.

[Daniela Würmseer]

Thank you. Is there a tool in Matlab existing with which i could find a "point which is fullfilling my constraint functions". (As my Algorithm should work for different problems)

[Matt J]

The above answer already suggests a way of doing that: Optimize an objective function which is zero everywhere.

[Daniela Würmseer]

But even by doing this i would need to define an initial Point x0 which is "fullfilling my constraint functions". And i want to generate this x0 in a matter that it would be appliable for different problems.

[Matt J]

But even by doing this i would need to define an initial Point x0 which is "fullfilling my constraint functions".

No, as I've already said a few times, that is false. Your x0 need not fulfill the constraints. Your constraint function(s) must, however, have a defined, real, finite value at x0.

[Torsten]

And i want to generate this x0 in a matter that it would be appliable for different problems.

Then you would have solved already half of the optimization in your head. That's why it usually is not possible.