<div dir="ltr"><div class="gmail_quote"><div dir="ltr">Dear All:<div><br></div><div>I am hoping to use IPOPT to solve a very large and very nonlinear system of equations. I am hoping that you can advise me as to the best approach. Beneath my signature, I describe the problem, describe the four approaches that I have or am considering, and finally ask several questions. Any advice that you can provide me would be very much appreciated.</div><div><br></div><div>Thanks so much,</div><div>Michael Mwangi</div><div>Assistant Professor</div><div>Department of Biochemistry and Molecular Biology</div><div>Penn State University</div><div><br></div><div><br></div><div><b>THE PROBLEM</b></div><div><br></div><div>I would like to solve a system of equations:</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>g1(x1, x2, ..., xn) = 0</div><div>g2(x1, x2, ..., xn) = 0</div><div>.</div><div>.</div><div>.</div><div>gm(x1, x2, ..., xn) = 0</div><div><br></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px">l &lt;= xi &lt;= u for all i</blockquote><div><br></div><div>where:</div><div><ul><li>n ~ 1,000,000<br></li><li>m ~ 10,000<br></li><li>gi depends on only a subset of ~10,000 of the ~1,000,000 variables for all i so that the Jacobian of the gi has only ~m x 10^4 ~ 10^4 x 10^4 ~ 10^8 nonzero elements</li><li>gi is a highly nonlinear function of the ~10,000 variables so that the second-order partial derivatives of gi with respect to the ~10,000 variables are mostly nonzero for all i</li><li>gi and gj depend on disjoint subsets of variables when |j - i| &gt;~ 100 so that the Jacobian of the gi has a block-like form<br></li></ul><div><br></div></div><div><b>APPROACH 1: SOLVE A LEAST SQUARES FORMULATION USING L-BFGS-B</b></div><div><br></div><div>I tried to solve a least squares formulation of the problem</div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2</div><div><br></div><div>l &lt;= xi &lt;= u for all i<br></div><div><br></div></blockquote>using the L-BFGS-B solver <a href="http://www.chokkan.org/software/liblbfgs/" target="_blank">here</a> that only permits the simple constraints l &lt;= xi &lt;= u.</div><div><br></div><div>This approach fails because it always yields a local but not global minimum of f for which some of the (gi)^2 are unacceptably large.</div><div><br></div><div><br></div><div><b>APPROACH 2: SOLVE THE LEAST SQUARES FORMULATION IN APPROACH 1 USING IPOPT</b></div><div><br></div><div>I am thinking of using the IPOPT solver <a href="http://www.coin-or.org/Ipopt/documentation/node23.html">here</a> to solve the same exact problem as in approach 1.</div><div><br></div><div><br></div><div><b>APPROACH 3: SOLVE A MORE CONSTRAINED LEAST SQUARES FORMULATION USING IPOPT</b></div><div><br></div><div>I am thinking of using the IPOPT solver to solve a more constrained least squares formulation of the problem:</div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2<br></div><div><br></div><div>l &lt;= xi &lt;= u for all i<br></div><div><br></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>-e &lt;= gi &lt;= e for all i where e &gt;= 0 is some small error tolerance</div><div><br></div></blockquote>My hope is that the additional constraints -e &lt;= gi &lt;= e force the solver to find a better solution.</div><div><br></div><div><br></div><div><b>APPROACH 4: SOLVE THE ORIGINAL SYSTEM OF EQUATIONS USING IPOPT</b></div><div><br></div><div>I am thinking of using the IPOPT solver to solve the original system of equations:<br></div><div><br></div><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>minimize f = 0</div><div><br></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>l &lt;= xi &lt;= u for all i<br></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><br></div></blockquote></div></blockquote><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>0 &lt;= gi &lt;= 0 for all i</div></blockquote></div><div><br></div><div>Thus, the objective function f is trivially zero, and the problem is encapsulated in the constraint functions.</div><div><br></div><div><br></div><div><b>COMMENTS ABOUT APPROACHES 2 - 4</b></div><div><br></div><div>As already noted, the Jacobian of the gi has only ~10^8 nonzero elements and has a block-like form.</div><div><br></div><div>As already noted, the gi are highly nonlinear functions of different subsets of ~10,000 of the total of ~1,000,000 variables so that the second-order partial derivatives of a gi with respect to the ~10,000 variables are mostly nonzero. This means the Hessian in Eq. (9) <a href="http://www.coin-or.org/Ipopt/documentation/node22.html#eq:IpoptLAG" target="_blank">here</a> is very dense with ~10^6 x 10^6 ~ 10^12 nonzero elements. Therefore, the limited-memory quasi-Newton approximation will need to be used <a href="http://www.coin-or.org/Ipopt/documentation/node52.html#SECTION0001113010000000000000" target="_blank">by setting hessian_approximation = &quot;limited-memory&quot;</a>.</div><div><br></div><div>I will be doing the computations on a workstation with 120 GB of RAM, so memory should not be an issue.</div><div><br></div><div><br></div><div><b>MY QUESTIONS FOR YOU</b></div><div><br></div><div>I have the following questions for you:</div><div><ol><li>Will approach 2 be much slower than approach 1 even though the approaches are identical except that the IPOPT solver is being used in place of the L-BFGS-B solver? Since IPOPT will be using the same limited-memory quasi-Newton approximation as in L-BFGS-B, I imagine that the two running times will be similar. However, IPOPT is designed to solve more general problems than L-BFGS-B, so maybe there is substantial overhead due to extra code.</li><li>Do you expect approach 3 to yield a better solution than approach 2 [i.e. smaller (gi)^2], and do you expect approach 4 to yield a better solution than approaches 3 and 2? My hope is that the additional constraints will result in a better solution. </li><li>Do you expect approach 3 to be faster than approach 2, and do you expect approach 4 to be faster than approaches 3 and 2? I am hoping that the additional constraints reduce the search space and result in quicker convergence and hence a reduction in the running time.</li><li>Is IPOPT appropriate for the types of problems described?</li><li>Any other recommendations?</li></ol><div><br></div></div></div></div></div>