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:
optimization

Subject: optimization

From: Hobst Friedli

Date: 3 Jul, 2010 16:15:08

Message: 1 of 6

Hello

I am a lerner in Stata and have some major problems replicating results from a paper.

The Lagrangian was differentated and reformulatet, gives:

(ni. - nii)/(1-pi) +(n.i - nii)/(pi) +lamda = 0 für alle i = 1,...,20

and Sum (pi) =1

n.i = sum row
ni. = sum column
nii = diagonal entries
Pii = cell-percentage of row-sum

I now want to solve this for the Pi's, probably with fmincon. But i just dont get how to specifie the commands.

For every kind of help i would be very grateful... I need to do this estimation for my bachelor thesis and i cant find help anywhere... Thank you very much in advance

Here i add the part of the paper i want to replicate :

http://img340.imageshack.us/img340/9861/paperu.png

Subject: optimization

From: us

Date: 3 Jul, 2010 17:28:05

Message: 2 of 6

"Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0nnmc$cp2$1@fred.mathworks.com>...
> Hello
>
> I am a lerner in Stata and have some major problems replicating results from a paper.
>
> The Lagrangian was differentated and reformulatet, gives:
>
> (ni. - nii)/(1-pi) +(n.i - nii)/(pi) +lamda = 0 für alle i = 1,...,20
>
> and Sum (pi) =1
>
> n.i = sum row
> ni. = sum column
> nii = diagonal entries
> Pii = cell-percentage of row-sum
>
> I now want to solve this for the Pi's, probably with fmincon. But i just dont get how to specifie the commands.
>
> For every kind of help i would be very grateful... I need to do this estimation for my bachelor thesis and i cant find help anywhere... Thank you very much in advance
>
> Here i add the part of the paper i want to replicate :
>
> http://img340.imageshack.us/img340/9861/paperu.png

what have YOU done so far to solve YOUR particular problem...
(after all, it is YOUR thesis...)

us

Subject: optimization

From: Hobst Friedli

Date: 4 Jul, 2010 15:17:05

Message: 3 of 6

"us " <us@neurol.unizh.ch> wrote in message <i0nrv5$fe3$1@fred.mathworks.com>...
> "Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0nnmc$cp2$1@fred.mathworks.com>...
> > Hello
> >
> > I am a lerner in Stata and have some major problems replicating results from a paper.
> >
> > The Lagrangian was differentated and reformulatet, gives:
> >
> > (ni. - nii)/(1-pi) +(n.i - nii)/(pi) +lamda = 0 für alle i = 1,...,20
> >
> > and Sum (pi) =1
> >
> > n.i = sum row
> > ni. = sum column
> > nii = diagonal entries
> > Pii = cell-percentage of row-sum
> >
> > I now want to solve this for the Pi's, probably with fmincon. But i just dont get how to specifie the commands.
> >
> > For every kind of help i would be very grateful... I need to do this estimation for my bachelor thesis and i cant find help anywhere... Thank you very much in advance
> >
> > Here i add the part of the paper i want to replicate :
> >
> > http://img340.imageshack.us/img340/9861/paperu.png
>
> what have YOU done so far to solve YOUR particular problem...
> (after all, it is YOUR thesis...)
>
> us


Sorry, you are right of course, i didn't write what i have so far:


clear all
A = [.....]
B = [.....]
C = [.....]
x0 = [0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1]

for ind =1:15
     nii=A(ind)
     n_i=B(ind)
     ni_=C(ind)
    fun = @(x) [(nii-ni_)/(1-x) + (nii-n_i)/x - L, sum(x)-1]

x(ind,: ) = fsolve(fun,x0)
 
I dont know if any of this code is useable. And there are obviously some parts missing.

Now my problem is still, how can i specifie the L to be a constant for every i ? and it seems that the fsolve does only solve for one variable. But i have 2 Variables x and L.

Any tipps would be appreciated. Thank you

Subject: optimization

From: Roger Stafford

Date: 5 Jul, 2010 00:33:05

Message: 4 of 6

"Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0q8lh$5v8$1@fred.mathworks.com>...
> > "Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0nnmc$cp2$1@fred.mathworks.com>...
> > > .......
> > > (ni. - nii)/(1-pi) +(n.i - nii)/(pi) +lamda = 0 für alle i = 1,...,20
> > >
> > > and Sum (pi) =1
> > >
> > > n.i = sum row
> > > ni. = sum column
> > > nii = diagonal entries
> > > Pii = cell-percentage of row-sum
> > >
> > > I now want to solve this for the Pi's, probably with fmincon. But i just dont get how to specifie the commands.
> > >
> > > For every kind of help i would be very grateful... I need to do this estimation for my bachelor thesis and i cant find help anywhere... Thank you very much in advance
> > >
> > > Here i add the part of the paper i want to replicate :
> > >
> > > http://img340.imageshack.us/img340/9861/paperu.png
> .......
> clear all
> A = [.....]
> B = [.....]
> C = [.....]
> x0 = [0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1]
>
> for ind =1:15
> nii=A(ind)
> n_i=B(ind)
> ni_=C(ind)
> fun = @(x) [(nii-ni_)/(1-x) + (nii-n_i)/x - L, sum(x)-1]
>
> x(ind,: ) = fsolve(fun,x0)
>
> I dont know if any of this code is useable. And there are obviously some parts missing.
>
> Now my problem is still, how can i specifie the L to be a constant for every i ? and it seems that the fsolve does only solve for one variable. But i have 2 Variables x and L.
>
> Any tipps would be appreciated. Thank you
- - - - - - - - -
  There are at least three things wrong with your anonymous function fun. First the expression in brackets must be a vector expression, not something that is done-one-at-a-time in a for-loop. Second, the division operators need a dot so as to avoid matrix division. Finally, you need to include the unknown L (which I presume is your -lambda) as one of the elements of vector x to be evaluated, say the last one. That means if k is the k of the paper you referenced, then x should have a length of k+1.

  Let A and B be row vectors of length k and defined for each i as

 A(i) = ni. - nii
 B(i) = n.i - nii

in your earlier notation. Then do:

 fun = @(x) [A./(1-x(1:k))+B./x(1:k)-x(k+1),sum(x(1:k))-1]

 x = fsolve(fun,x0);

Also be sure to include an initial estimate for L in the k+1 element of x0.


  However, I would predict that fsolve might have difficulty successfully solving the equations in this particular problem. My reasoning goes something like this. For each particular value of L, the i-th equation

 A(i)/(1-x(i))+B(i)/x(i) = L

is equivalent to a quadratic equation in x(i) (where I am assuming A(i) and B(i) are always positive quantities since they derive from "n-counts".) There are two real roots, one root, or none, to this quadratic depending on whether

 sqrt(A(i))+sqrt(B(i))

is less than, equal to, or greater than L, respectively. If L is greater than the maximum of this sum of two square roots for all i, then all k equations would have two roots, so there would be 2^k = 32,768 possible cases which fsolve would have to "investigate" for such L values to make sure it didn't overlook a possible solution to sum(x(1:k))-1=0. It looks like a very ugly problem when looked at from that point of view, and I can conceive of fsolve getting hopelessly stuck in these numerous blind alleys.

  I can envision a process by which a single solution can certainly be found, but I see no guarantee that it would be the only possible one. It can easily be seen that as L approaches infinity, one of the roots of each of the above quadratics must approach zero while the other root must approach one. Start with a very high value of L and choose in each case the smaller of the two possible roots for x(i). If L is sufficiently large the sum of these x(i) would be less than 1. Now imagine L decreasing continuously unless reaching the greatest

 sqrt(A(i))+sqrt(B(i))

at an i=i0, which would be the lowest value that L can be allowed to have. The corresponding sum(x(1:k)) would continuously increase as the roots increase. If it passes through one somewhere along the line, there is your solution. If not, then let L commence increasing again from this minimum value but choosing the greater of the two possible roots for the i0 case while the other roots remain at their lesser values. This would be a continuous process for sum(x(1:k)) with no discontinuous jumps, since you would have passed through the one-root point at i0 when making the switch in roots. Since x(i0) would now approach one as L again approaches infinity, there surely must come a point where sum(x(1:k)) crosses one, and there would be your solution.

  In other words, there must always exist a solution in which either all the x(i) roots are chosen as the lesser of a pair, or else there is a solution in which just one of the x(i) is the greater of a pair and all the other roots are still at their lesser values.

  However, making the transition for any other of the root pairs from the lower to the upper one would in general involve a discontinuous jump in sum(x(1:k)), so we are not sure any other solutions can be found in the L-varying process. If they do exist I foresee fsolve having a difficult time finding them.

  As for the single "sure-fire" solution above, it should be possible to translate that process to something fzero, rather than fsolve, could solve in terms of the single unknown L. It can be determined in advance whether sum(x(1:k)) is above or below one for L chosen at sqrt(A(i0))+sqrt(B(i0)), and this would allow you to determine which of the above two alternatives to select for the x(i0) root in starting fzero with a pair of surrounding estimates for L.

  My apologies for not going into greater detail in the previous paragraph with respect to fzero. I could not be sure you would be interested in such an approach.

Roger Stafford

Subject: optimization

From: Hobst Friedli

Date: 5 Jul, 2010 09:27:03

Message: 5 of 6

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i0r981$5nd$1@fred.mathworks.com>...
> "Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0q8lh$5v8$1@fred.mathworks.com>...
> > > "Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0nnmc$cp2$1@fred.mathworks.com>...
> > > > .......
> > > > (ni. - nii)/(1-pi) +(n.i - nii)/(pi) +lamda = 0 für alle i = 1,...,20
> > > >
> > > > and Sum (pi) =1
> > > >
> > > > n.i = sum row
> > > > ni. = sum column
> > > > nii = diagonal entries
> > > > Pii = cell-percentage of row-sum
> > > >
> > > > I now want to solve this for the Pi's, probably with fmincon. But i just dont get how to specifie the commands.
> > > >
> > > > For every kind of help i would be very grateful... I need to do this estimation for my bachelor thesis and i cant find help anywhere... Thank you very much in advance
> > > >
> > > > Here i add the part of the paper i want to replicate :
> > > >
> > > > http://img340.imageshack.us/img340/9861/paperu.png
> > .......
> > clear all
> > A = [.....]
> > B = [.....]
> > C = [.....]
> > x0 = [0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1]
> >
> > for ind =1:15
> > nii=A(ind)
> > n_i=B(ind)
> > ni_=C(ind)
> > fun = @(x) [(nii-ni_)/(1-x) + (nii-n_i)/x - L, sum(x)-1]
> >
> > x(ind,: ) = fsolve(fun,x0)
> >
> > I dont know if any of this code is useable. And there are obviously some parts missing.
> >
> > Now my problem is still, how can i specifie the L to be a constant for every i ? and it seems that the fsolve does only solve for one variable. But i have 2 Variables x and L.
> >
> > Any tipps would be appreciated. Thank you
> - - - - - - - - -
> There are at least three things wrong with your anonymous function fun. First the expression in brackets must be a vector expression, not something that is done-one-at-a-time in a for-loop. Second, the division operators need a dot so as to avoid matrix division. Finally, you need to include the unknown L (which I presume is your -lambda) as one of the elements of vector x to be evaluated, say the last one. That means if k is the k of the paper you referenced, then x should have a length of k+1.
>
> Let A and B be row vectors of length k and defined for each i as
>
> A(i) = ni. - nii
> B(i) = n.i - nii
>
> in your earlier notation. Then do:
>
> fun = @(x) [A./(1-x(1:k))+B./x(1:k)-x(k+1),sum(x(1:k))-1]
>
> x = fsolve(fun,x0);
>
> Also be sure to include an initial estimate for L in the k+1 element of x0.
>
>
> However, I would predict that fsolve might have difficulty successfully solving the equations in this particular problem. My reasoning goes something like this. For each particular value of L, the i-th equation
>
> A(i)/(1-x(i))+B(i)/x(i) = L
>
> is equivalent to a quadratic equation in x(i) (where I am assuming A(i) and B(i) are always positive quantities since they derive from "n-counts".) There are two real roots, one root, or none, to this quadratic depending on whether
>
> sqrt(A(i))+sqrt(B(i))
>
> is less than, equal to, or greater than L, respectively. If L is greater than the maximum of this sum of two square roots for all i, then all k equations would have two roots, so there would be 2^k = 32,768 possible cases which fsolve would have to "investigate" for such L values to make sure it didn't overlook a possible solution to sum(x(1:k))-1=0. It looks like a very ugly problem when looked at from that point of view, and I can conceive of fsolve getting hopelessly stuck in these numerous blind alleys.
>
> I can envision a process by which a single solution can certainly be found, but I see no guarantee that it would be the only possible one. It can easily be seen that as L approaches infinity, one of the roots of each of the above quadratics must approach zero while the other root must approach one. Start with a very high value of L and choose in each case the smaller of the two possible roots for x(i). If L is sufficiently large the sum of these x(i) would be less than 1. Now imagine L decreasing continuously unless reaching the greatest
>
> sqrt(A(i))+sqrt(B(i))
>
> at an i=i0, which would be the lowest value that L can be allowed to have. The corresponding sum(x(1:k)) would continuously increase as the roots increase. If it passes through one somewhere along the line, there is your solution. If not, then let L commence increasing again from this minimum value but choosing the greater of the two possible roots for the i0 case while the other roots remain at their lesser values. This would be a continuous process for sum(x(1:k)) with no discontinuous jumps, since you would have passed through the one-root point at i0 when making the switch in roots. Since x(i0) would now approach one as L again approaches infinity, there surely must come a point where sum(x(1:k)) crosses one, and there would be your solution.
>
> In other words, there must always exist a solution in which either all the x(i) roots are chosen as the lesser of a pair, or else there is a solution in which just one of the x(i) is the greater of a pair and all the other roots are still at their lesser values.
>
> However, making the transition for any other of the root pairs from the lower to the upper one would in general involve a discontinuous jump in sum(x(1:k)), so we are not sure any other solutions can be found in the L-varying process. If they do exist I foresee fsolve having a difficult time finding them.
>
> As for the single "sure-fire" solution above, it should be possible to translate that process to something fzero, rather than fsolve, could solve in terms of the single unknown L. It can be determined in advance whether sum(x(1:k)) is above or below one for L chosen at sqrt(A(i0))+sqrt(B(i0)), and this would allow you to determine which of the above two alternatives to select for the x(i0) root in starting fzero with a pair of surrounding estimates for L.
>
> My apologies for not going into greater detail in the previous paragraph with respect to fzero. I could not be sure you would be interested in such an approach.
>
> Roger Stafford



Thank you very much for your detailed answer, i really appreciate it and it helps me a lot. I will implement the suggested changes today and see if it gives me useful results. As i have the original data and results from a similar estimation, i can easily verify the results. I see the problem your mentioning.

an other idea was to not use the lamda and the sum(x)=1 at all. My thoungt is, that as long as i do not have a unknown lamda in the equation i dont need the sum=1 equation, the xi are determines by the k equations. If i set lamda =0 or zero (or whatever) the relatiive values for xi should stay the same. Then i can normalize the xi in a second step, by deviding the result vertor by sum(x).

Anyways i will try these approaches, and report back later. And again, thank you for your help.

Subject: optimization

From: Roger Stafford

Date: 5 Jul, 2010 15:12:07

Message: 6 of 6

"Hobst Friedli" <tobias.friedli@access.uzh.ch> wrote in message <i0s8h7$8c7$1@fred.mathworks.com>...
> .......
> an other idea was to not use the lamda and the sum(x)=1 at all. My thoungt is, that as long as i do not have a unknown lamda in the equation i dont need the sum=1 equation, the xi are determines by the k equations. If i set lamda =0 or zero (or whatever) the relatiive values for xi should stay the same. Then i can normalize the xi in a second step, by deviding the result vertor by sum(x).
> .......
- - - - - - - - - -
  I don't think that would give a valid solution. Multiplying all the xi by a normalizing factor could give you a sum xi of one, but in general it would also cause the quantities

 (ni_-nii)/(1-xi) +(n_i-nii)/xi

to no longer be equal to one another for the various values of i. Consequently your probability values would then fail to represent a maximum likelihood. Having a common value of L along with a sum xi of one would appear to be a crucial ingredient in finding a valid solution.

  After giving your problem more thought it seems likely to me that a solution using all lower quadratic roots is the only one possible. In this case, using fzero with L as the only unknown would surely be the best way of solving your equations. The use of fsolve with many unknowns may end up searching a great many blind alleys.

  For the equation A/(1-x) + B/x = L, the lower root is given by

 x = (L+B-A-sqrt((L-A-B)^2-4*A*B))/(2*L)

so adjusting the single variable L so that the sum of these lower roots is one, is the task that you could set fzero to solving. It should perform very well if given an appropriate initial x0 interval.

  By the way, in my previous article I misstated the value of L which gives just one root in the quadratic. It should have been

 (sqrt(A(i))+sqrt(B(i)))^2

instead of just

 sqrt(A(i))+sqrt(B(i))

Roger Stafford

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