What is the difference between "no feasible solution found" and "the problem is infeasible" messages in LSQLIN?

I have an optimization problem solved through lsqlin and in some cases it gives "no feasible solution found" and still gives a solution, and in other cases it shows "the problem is infeasible" and the solution is empty (no solution).

What is the difference between the two messages and why is it still giving a solution with "no feasible solution found" message although it's supposed to be infeasible

[HN]

No feasible solution found (where x1 is the solution):

The problem is infeasible:

[Matt J]

The examples you have posted use a different solver in each case, lsqlin in the first and quadprog in the second.

[HN]

Thanks for your reply! although I used the same function "lsqlin" to solve the optimization problem. Does it use different solvers for the same function?

[Bruno Luong]

lsqlin with interiopoint algorithm and quadprog call the same engine ipqpdense/ipqpsparse

[HN]

Got it! thank you so much!

Answer 1

[Torsten]

"No feasible solution found" means: there might be a feasible solution for your problem, but I was not able to find it. But I give you the last iterate - it's not feasible, but you can see in which search region I spent some effort.

"The problem is infeasible" means: I could prove internally that no feasible solution exists for your problem and I return an empty structure in the solution field. So most probably, you did something wrong in your problem formulation.

[HN]

This made it clear. Thank you so much! I have another question: for the "No feasible solution found", since you mentioned that there might be a solution. What should I change in the options of the optmization problem to make the lsqlin optimizer search more for a solution? Currenlty, I have the default settings for the optimization.

[Torsten]

Nobody can answer this question without seeing the problem you want to solve.

[Bruno Luong]

The existing of feasible point can be answered in finite number of steps. http://www.columbia.edu/~cs2035/courses/ieor3608.F05/bigm1.pdf

So to me "No feasible solution found" is similar to "The problem is infeasible". It seems just a different message from lsqlin and quadprog as @Matt J has observed.

[Torsten]

Maybe you are right, but it's a poor wording then for an unexperienced user of the software (like me).

[Bruno Luong]

Finding the feasible point is quite a complex task by itself if inequality constraints are required

There are a quick check of preprocess of constraints

Solve X = Aeq\beq then verify the inequality constraint

If not solve an auxiliar linear programming problem to find the feasible point

https://www.mathworks.com/help/optim/ug/quadratic-programming-algorithms.html#bsqspm_ (Phase 1)

https://www.mathworks.com/help/optim/ug/linear-programming-algorithms.html#budwan6 (Phase 1)

May be different messages depend on which step the infeasability is detected.