How to use quadprog with a group of points

Hi, I am trying to use the function quadprog from a group of points to obtain the middle point and make the smallest circle that encloses all the points. I don't know how to obtain the H, I suposse is the Hessian, Aeq and Beq. Someone could help me with this problem?

[X,FVAL,EXITFLAG] = quadprog(H,f,A,b,Aeq,beq)

The points are P =[3 0;0 -3;-2 1;1 4]

The matrix A is

1 0 -1 0 0 0 0 0 0 0;

1 0 0 0 -1 0 0 0 0 0;

1 0 0 0 0 0 -1 0 0 0;

1 0 0 0 0 0 0 0 -1 0;

-1 0 -1 0 0 0 0 0 0 0;

-1 0 0 0 -1 0 0 0 0 0;

-1 0 0 0 0 0 -1 0 0 0;

-1 0 0 0 0 0 0 0 -1 0;

0 1 0 -1 0 0 0 0 0 0;

0 1 0 0 0 -1 0 0 0 0;

0 1 0 0 0 0 0 -1 0 0;

0 1 0 0 0 0 0 0 0 -1;

0 -1 0 -1 0 0 0 0 0 0;

0 -1 0 0 0 -1 0 0 0 0;

0 -1 0 0 0 0 0 -1 0 0;

0 -1 0 0 0 0 0 0 0 -1;

The f is

0 0 1 1 1 1 1 1 1 1;

The b is

3 -3 0 0;

0 0 -3 3;

-2 2 1 -1;

1 -1 4 -4;

Thank you for your help, and sorry for the long post.

Answer 1

[Alan Weiss]

I am not sure what you are really trying to do. You seem to already have f, A, and b. Do you need to figure out an appropriate H?

I suggest that you start with a verbal description of your problem and then try to write equations that represent the problem. What are your control variables (the things that you can change to try to reach a minimum)? What is your objective function? What kinds of constraints are there in the problem? Once you have figured out all that, you can see what kind of solver is appropriate.

Alan Weiss

MATLAB mathematical toolbox documentation

[Marc Arbones]

Hello, I will try to explain better, sorry if my english is difficult to understand.

I have a group of points P =[3 0;0 -3;-2 1;1 4], and I have to find the smallest circle that encircles all the points. For that I have to found the point that minimize the distance to all the points and after this find the radius.

I already find this point using lineprog, where I used the f,A,b thats the reason I have them, but for this exercise I need to use the function quadprog to obtain this point. And I don't know how to find the parametres that I need.

Thank you for your time.

[Alan Weiss]

It sounds like you have three control variables: the x- and y- locations of the circle center, and the radius of the circle. Let's call these variables x(1), x(2), and x(3) respectively.

Your objective is to minimize x(3) or x(3)^2, subject to the constraints that the points in P are in your circle.

You need to devise a formula to represent the constraints that each point in P is inside your circle. Something like

 (x(1) - P(1))^2 + (x(2) - P(2))^2 <= x(3)^2

for each point (P(1),P(2)).

Did I understand your problem correctly? If so, then perhaps you can take it from here and find an appropriate solver and the inputs to that solver.

Alan Weiss

MATLAB mathematical toolbox documentation

[John D'Errico]

Except this constraint is a quadratic constraint in the unknowns. quadprog does not handle constraints of that form.

Answer 2

[Torsten]

Since you try to minimize the maximum distance between the center (xc,yc) of the circle and the points (x(i),y(i)) given, try fminimax with the F_i given by

F_i(xc,yc) = sqrt((x(i)-xc)^2 + (y(i)-yc)^2)

http://de.mathworks.com/help/optim/ug/fminimax.html

Best wishes

Torsten.