Quadratic constraints problem feasibility

This is the first time, I plan to use Matlab for optimization. Please give me some hints on solving the following problem:

I have up to 4 dimensions and a set of quadratic constraints. I would like to know if there exists any feasible region for the given problem. I.e., is there any solution that satisfies all the constraints?

The constraints have the general form: lower_bound <= x M x^T + N x^T <= upper_bound

where M is a 4x4 matrix, N is a 4 dimensional vector and the constraint may be unbounded at one side.

In geometric interpretation, there is a set of regions defined by quadratic functions and I wish to know if there exists an intersection point.

What is the best way to solve the problem? I have thought of nonlinear optimization (yet with no idea how to implement it), but may be there is some better way. Thank you for any help :)

[Matt J]

Are the M positive definite?

[Martin]

Thank you, I think I have to edit the question :) The constraints are different.

[Martin]

No it does not have to be positive definite. It can be a general quadric. Would it make the solution simpler?

[Matt J]

Not sure.

[Matt J]

I would like to know if there exists any feasible region for the given problem

So you realize that the feasible set will often consist of disconnected regions or "islands" in R^4? And you're only interested in finding one piece, not all of them? It would be hard to minimize globally over this feasible set without finding all of them, and finding all of them would be really hard.

[Martin]

Yes, I just want to compute whether at least one exists.

Answer 1

[Alan Weiss]

You can solve this problem using fmincon. Give an objective function of zero:

 fun = @(x)0

Express your nonlinear constraints in the correct syntax for nonlinear constraints. Choose a variety of starting points for fmincon if you get a "no feasible solution" result, because fmincon looks for solutions based on the starting point.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Matt J]

This approach has the potential to give misleading results. For example, a special case of this problem in R^1 is (with all M=0, and N=1) the simple interval constraints

 0<=x<=1

 1+2*TolCon <= x <=2

This feasible set is empty. However, if you initialize FMINCON at x0=1+TolCon, it will stop right away claiming that x0 is already a solution.

Obviously, the key is to make options.TolCon smaller, but that requires foreknowledge of the distances between the regions specified by the different inequalities.