Prev: How to detect an almost circular object in an image?
Next: Need help for anfis in a three link arm
From: free0iran on 15 Mar 2010 12:37
hello.
i am using fmincon for circle packing problem. specifically fitting n
unit circle into the smallest possible larger circle so that no two
circle overlap and that all the unit circle lie entirely within the
large circle. this is the M-file for the two nonlinear constraints:

function [c,ceq] = nonlconN(x)
n=(length(x)-1)/2;
cnt=1;
for i=1:(n-1)
for j=(i+1):n
c(cnt)=-(x(2*i-1)-x(2*j-1))^2-(x(2*i)-x(2*j))^2+4;
cnt=cnt+1;
end
c(cnt)=x(2*i-1)^2+x(2*i)^2-(x(2*n+1)-1)^2;
cnt=cnt+1;
end
c(cnt)=x(2*n-1)^2+x(2*n)^2-(x(2*n+1)-1)^2;
ceq=[];

the problem works if the derivative is approximated by the solver but
to see if i can get better results i want to manually supplly both the
objective and the nonlinear constraint gradient.
i have tried with the objective function gradient supplied and that
works fine too.
the problem is when i try to supply the nonlinear constraint
gradient.

this is what i wrote:

function [c,ceq,GC,GCeq] = nonlconNgrad(x)
n=(length(x)-1)/2;
cnt=1;cnt2=1
for i=1:(n-1)
for j=(i+1):n
c(cnt)=-(x(2*i-1)-x(2*j-1))^2-(x(2*i)-x(2*j))^2+4;
cnt=cnt+1;
if nargout > 2
for t=1:(2*n+1);
if t==(2*i-1);
GC(t,cnt2)=-2*x(2*i-1)+2*x(2*i);
else
if t==2*j-1
GC(t,cnt2)=2*x(2*i-1)-2*x(2*j-1);
else
if t==2*i
GC(t,cnt2)=-2*x(2*i-1)+2*x(2*j);
else
if t==2*j
GC(t,cnt2)=2*x(2*i)-2*x(2*j);
else
GC(t,cnt2)=0;
end
end
end
end
cnt2=cnt2+1
end

end
end


c(cnt)=x(2*i-1)^2+x(2*i)^2-(x(2*n+1)-1)^2;
cnt=cnt+1;
if nargout>2
for t=1:(2*n)
if t==(2*i-1)
GC(t,cnt2)=2*x(2*i-1);
else
if t==(2*i)
GC(t,cnt2)=2*x(2*i);
else
GC(t,cnt2)=0;
end
end
cnt2=cnt2+1;
end
end

end
c(cnt)=x(2*n-1)^2+x(2*n)^2-(x(2*n+1)-1)^2;
ceq=[];
if nargout>2
GC(2*n+1,cnt)=-2*x(2*n+1)+2;
GCeq=[];
end

the problem is that when i press start to run the solver once i get
messgae:

Optimization terminated: no feasible solution found. Magnitude of
search
direction less than 2*options.TolX but constraints are not satisfied.

i tried to change the x tolerance but that did no good.

can anybody please help me?!
From: Matt J on 15 Mar 2010 14:22
free0iran <free_iran(a)hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c9f2(a)z4g2000yqa.googlegroups.com>...

>
> Optimization terminated: no feasible solution found. Magnitude of
> search
> direction less than 2*options.TolX but constraints are not satisfied.
>
> i tried to change the x tolerance but that did no good.
====================

It's not clear why this is a problem? fmincon is just telling you that it's finished.
From: Matt J on 15 Mar 2010 14:33
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hnltt1$q55$1(a)fred.mathworks.com>...
> free0iran <free_iran(a)hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c9f2(a)z4g2000yqa.googlegroups.com>...
>
> >
> > Optimization terminated: no feasible solution found. Magnitude of
> > search
> > direction less than 2*options.TolX but constraints are not satisfied.
> >
> > i tried to change the x tolerance but that did no good.
> ====================
>
> It's not clear why this is a problem? fmincon is just telling you that it's finished.

Sorry, I overlooked the part about "no feasible solution found"

What you should do is comparethe output of your analytical constraint gradient function to a numerical approximation of the constraint gradient. Numerical approximation works, as you've mentioned, when MATLAB performs it. So the likelihood is that you have a mistake in the analytical gradient calculation.
From: Marcelo Marazzi on 15 Mar 2010 18:41
You can have your derivatives checked by setting the option DerivativeCheck as described in the documentation:
http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/f12471.html#br5vdvm

You mention you were trying to get better results. If you have MATLAB R2008a or later, you may want to also try
the interior-point algorithm to see if works better for you on this problem. Set fmincon'soption "Algorithm"
to 'interior-point'.

-Marcelo

On 3/15/2010 2:33 PM, Matt J wrote:
> "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message
> <hnltt1$q55$1(a)fred.mathworks.com>...
>> free0iran <free_iran(a)hotmail.co.uk> wrote in message
>> <c0e3ccdb-631d-4490-8436-90e5eec0c9f2(a)z4g2000yqa.googlegroups.com>...
>>
>> > > Optimization terminated: no feasible solution found. Magnitude of
>> > search
>> > direction less than 2*options.TolX but constraints are not satisfied.
>> > > i tried to change the x tolerance but that did no good.
>> ====================
>>
>> It's not clear why this is a problem? fmincon is just telling you that
>> it's finished.
>
> Sorry, I overlooked the part about "no feasible solution found"
>
> What you should do is comparethe output of your analytical constraint
> gradient function to a numerical approximation of the constraint
> gradient. Numerical approximation works, as you've mentioned, when
> MATLAB performs it. So the likelihood is that you have a mistake in the
> analytical gradient calculation.
From: free0iran on 18 Mar 2010 17:28
On Mar 15, 6:33 pm, "Matt J " <mattjacREM...(a)THISieee.spam> wrote:
> "Matt J " <mattjacREM...(a)THISieee.spam> wrote in message <hnltt1$q5...(a)fred.mathworks.com>...
>
> > free0iran <free_i...(a)hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c...(a)z4g2000yqa.googlegroups.com>...
>
> > > Optimization terminated: no feasible solution found. Magnitude of
> > > search
> > >  direction less than 2*options.TolX but constraints are not satisfied.
>
> > > i tried to change the x tolerance but that did no good.
> > ====================
>
> > It's not clear why  this is a problem? fmincon is  just telling you that it's finished.
>
> Sorry, I overlooked the part about "no feasible solution found"
>
> What you should do is comparethe output of your analytical constraint gradient function to a numerical approximation of the constraint gradient. Numerical approximation works, as you've mentioned, when MATLAB performs it. So the likelihood is that you have a mistake in the analytical gradient calculation.

HELLO AND MANY THANKS FOR THE REPLY.
I HAVE MATLAB R2006b. SO IN FMINCON I HAVE NO OPTION OF CHANGING THE
ALGORITHM. I JUST HAVE OPTION OF CHOOSING LARGE SCALE OR MEDIUM SCALE
AND SINCE IT CANNOT CONSIDER LARGE SCALE ALGORITHMS WITH INEQUALITY
CONSTRAINTS. COULD THE PROBLEM BE EXACTLY THAT SPECIFIC MEDIUM-SCALE
ALGORITHM (SQP ACTIVE-SET I THINK!!!!!) ?????????
ALSO USING THE CONSTRAINT FUNCTION WITH THE GRADIENT SUPPLIED IN
FMINCON BUT USING THE OPTION 'APPROXIMATE GRADIENT BY SOLVER' STILL
YIELDS THE SAME RESULTS AS WHEN USING THE CONSTRAINT FUNCTION WITHOUT
THE GRADIENT SUPPLIED!!!
SO DOES THIS NOT MEAN THAT IT IS CORRECT??
MANY THANKS IN ADVANCE.
PARVIZ.


 |  Next  |  Last
Pages: 1 2
Prev: How to detect an almost circular object in an image?
Next: Need help for anfis in a three link arm