optimization
in [Matlab]
|
Prev: Thanks Re: pre-allocation question
Next: optimization
From: Hobst Friedli on 5 Jul 2010 05:27 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <i0r981$5nd$1(a)fred.mathworks.com>... > "Hobst Friedli" <tobias.friedli(a)access.uzh.ch> wrote in message <i0q8lh$5v8$1(a)fred.mathworks.com>... > > > "Hobst Friedli" <tobias.friedli(a)access.uzh.ch> wrote in message <i0nnmc$cp2$1(a)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.
From: Roger Stafford on 5 Jul 2010 11:12
"Hobst Friedli" <tobias.friedli(a)access.uzh.ch> wrote in message <i0s8h7$8c7$1(a)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 |