Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
fmincon minimisation

Subject: fmincon minimisation

From: free0iran

Date: 15 Mar, 2010 16:37:00

Message: 1 of 7

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?!

Subject: fmincon minimisation

From: Matt J

Date: 15 Mar, 2010 18:22:25

Message: 2 of 7

free0iran <free_iran@hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c9f2@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.

Subject: fmincon minimisation

From: Matt J

Date: 15 Mar, 2010 18:33:05

Message: 3 of 7

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hnltt1$q55$1@fred.mathworks.com>...
> free0iran <free_iran@hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c9f2@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.

Subject: fmincon minimisation

From: Marcelo Marazzi

Date: 15 Mar, 2010 22:41:42

Message: 4 of 7

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@THISieee.spam> wrote in message
> <hnltt1$q55$1@fred.mathworks.com>...
>> free0iran <free_iran@hotmail.co.uk> wrote in message
>> <c0e3ccdb-631d-4490-8436-90e5eec0c9f2@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.

Subject: fmincon minimisation

From: free0iran

Date: 18 Mar, 2010 21:28:25

Message: 5 of 7

On Mar 15, 6:33 pm, "Matt J " <mattjacREM...@THISieee.spam> wrote:
> "Matt J " <mattjacREM...@THISieee.spam> wrote in message <hnltt1$q5...@fred.mathworks.com>...
>
> > free0iran <free_i...@hotmail.co.uk> wrote in message <c0e3ccdb-631d-4490-8436-90e5eec0c...@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.

Subject: fmincon minimisation

From: Sadik

Date: 18 Mar, 2010 23:22:02

Message: 6 of 7

Hello,

I had a similar problem in the past, and it turned out that the problem IN DEED did not have a feasible solution!!!

Please try to check analytically if this is the case. For instance, you can easily check if your contraints are contradicting, of course if you have more than one [sorry, I did not look into your code in detail.]

Best.

Subject: fmincon minimisation

From: free0iran

Date: 26 Mar, 2010 10:56:42

Message: 7 of 7

On Mar 18, 11:22 pm, "Sadik " <sadik.h...@gmail.com> wrote:
> Hello,
>
> I had a similar problem in the past, and it turned out that the problem IN DEED did not have a feasible solution!!!
>
> Please try to check analytically if this is the case. For instance, you can easily check if your contraints are contradicting, of course if you have more than one [sorry, I did not look into your code in detail.]
>
> Best.

thank you all. the problem was just a simple change in the M-file. so
it works, though it has no improvement on the results.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us