<div dir="ltr">Thank you so much for your quick response.<div><br></div><div>For the linear solver, I am using MUMPS right now. I am thinking of switching to <span style="color:rgb(84,84,84);line-height:14.5600032806396px">PARDISO. Compared to MUMPS, how much faster is </span><span style="color:rgb(84,84,84);line-height:14.5600032806396px">PARDISO? I suspect the answer is highly problem dependent. But is it common to see 2-fold or even 10-fold improvements in the run time for large problems?</span></div><div><span style="color:rgb(84,84,84);line-height:14.5600032806396px"><br></span></div><div><span style="color:rgb(84,84,84);line-height:14.5600032806396px">Thanks,</span></div><div><span style="color:rgb(84,84,84);line-height:14.5600032806396px">Mike</span></div><div><span style="color:rgb(84,84,84);line-height:14.5600032806396px"><br></span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Aug 9, 2015 at 10:08 AM, Stefan Vigerske <span dir="ltr"><<a href="mailto:stefan@math.hu-berlin.de" target="_blank">stefan@math.hu-berlin.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
on 1). I don't expect that the overhead in Ipopt for handling 0 constraints will make it much slower.<br>
<br>
on 2) and 3). I don't expect 3 to be better than 2, but I would expect 4 to be better than 2.<br>
<br>
on 4). I think it's worth a try.<br>
<br>
on 5). Experiment with different linear solvers in Ipopt (linear_solver option), e.g., from the HSL library.<br>
<br>
Stefan<span class=""><br>
<br>
On 08/04/2015 02:54 AM, Michael Mwangi wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
Dear All:<br>
<br>
I am hoping to use IPOPT to solve a very large and very nonlinear system of<br>
equations. I am hoping that you can advise me as to the best approach.<br>
Beneath my signature, I describe the problem, describe the four approaches<br>
that I have or am considering, and finally ask several questions. Any<br>
advice that you can provide me would be very much appreciated.<br>
<br>
Thanks so much,<br>
Michael Mwangi<br>
Assistant Professor<br>
Department of Biochemistry and Molecular Biology<br>
Penn State University<br>
<br>
<br></span>
*THE PROBLEM*<span class=""><br>
<br>
I would like to solve a system of equations:<br>
<br>
g1(x1, x2, ..., xn) = 0<br>
g2(x1, x2, ..., xn) = 0<br>
.<br>
.<br>
.<br>
gm(x1, x2, ..., xn) = 0<br>
<br>
l <= xi <= u for all i<br>
<br>
<br>
where:<br>
<br></span>
- n ~ 1,000,000<br>
- m ~ 10,000<br>
- gi depends on only a subset of ~10,000 of the ~1,000,000 variables for<span class=""><br>
all i so that the Jacobian of the gi has only ~m x 10^4 ~ 10^4 x 10^4 ~<br>
10^8 nonzero elements<br></span>
- gi is a highly nonlinear function of the ~10,000 variables so that the<span class=""><br>
second-order partial derivatives of gi with respect to the ~10,000<br>
variables are mostly nonzero for all i<br></span>
- gi and gj depend on disjoint subsets of variables when |j - i| >~ 100<span class=""><br>
so that the Jacobian of the gi has a block-like form<br>
<br>
<br></span>
*APPROACH 1: SOLVE A LEAST SQUARES FORMULATION USING L-BFGS-B*<span class=""><br>
<br>
I tried to solve a least squares formulation of the problem<br>
<br>
minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2<br>
<br>
l <= xi <= u for all i<br>
<br></span>
using the L-BFGS-B solver here <<a href="http://www.chokkan.org/software/liblbfgs/" rel="noreferrer" target="_blank">http://www.chokkan.org/software/liblbfgs/</a>><span class=""><br>
that only permits the simple constraints l <= xi <= u.<br>
<br>
This approach fails because it always yields a local but not global minimum<br>
of f for which some of the (gi)^2 are unacceptably large.<br>
<br>
<br></span>
*APPROACH 2: SOLVE THE LEAST SQUARES FORMULATION IN APPROACH 1 USING IPOPT*<span class=""><br>
<br>
I am thinking of using the IPOPT solver here<br></span>
<<a href="http://www.coin-or.org/Ipopt/documentation/node23.html" rel="noreferrer" target="_blank">http://www.coin-or.org/Ipopt/documentation/node23.html</a>> to solve the same<span class=""><br>
exact problem as in approach 1.<br>
<br>
<br></span>
*APPROACH 3: SOLVE A MORE CONSTRAINED LEAST SQUARES FORMULATION USING IPOPT*<span class=""><br>
<br>
I am thinking of using the IPOPT solver to solve a more constrained least<br>
squares formulation of the problem:<br>
<br>
minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2<br>
<br>
l <= xi <= u for all i<br>
<br>
-e <= gi <= e for all i where e >= 0 is some small error tolerance<br>
<br>
My hope is that the additional constraints -e <= gi <= e force the solver<br>
to find a better solution.<br>
<br>
<br></span>
*APPROACH 4: SOLVE THE ORIGINAL SYSTEM OF EQUATIONS USING IPOPT*<span class=""><br>
<br>
I am thinking of using the IPOPT solver to solve the original system of<br>
equations:<br>
<br>
minimize f = 0<br>
<br>
l <= xi <= u for all i<br>
<br>
<br>
0 <= gi <= 0 for all i<br>
<br>
<br>
Thus, the objective function f is trivially zero, and the problem is<br>
encapsulated in the constraint functions.<br>
<br>
<br></span>
*COMMENTS ABOUT APPROACHES 2 - 4*<span class=""><br>
<br>
As already noted, the Jacobian of the gi has only ~10^8 nonzero elements<br>
and has a block-like form.<br>
<br>
As already noted, the gi are highly nonlinear functions of different<br>
subsets of ~10,000 of the total of ~1,000,000 variables so that the<br>
second-order partial derivatives of a gi with respect to the ~10,000<br>
variables are mostly nonzero. This means the Hessian in Eq. (9) here<br></span>
<<a href="http://www.coin-or.org/Ipopt/documentation/node22.html#eq:IpoptLAG" rel="noreferrer" target="_blank">http://www.coin-or.org/Ipopt/documentation/node22.html#eq:IpoptLAG</a>> is<span class=""><br>
very dense with ~10^6 x 10^6 ~ 10^12 nonzero elements. Therefore, the<br>
limited-memory quasi-Newton approximation will need to be used by<br>
setting hessian_approximation = "limited-memory"<br></span>
<<a href="http://www.coin-or.org/Ipopt/documentation/node52.html#SECTION0001113010000000000000" rel="noreferrer" target="_blank">http://www.coin-or.org/Ipopt/documentation/node52.html#SECTION0001113010000000000000</a>><span class=""><br>
.<br>
<br>
I will be doing the computations on a workstation with 120 GB of RAM, so<br>
memory should not be an issue.<br>
<br>
<br></span>
*MY QUESTIONS FOR YOU*<span class=""><br>
<br>
I have the following questions for you:<br>
<br></span>
1. Will approach 2 be much slower than approach 1 even though the<span class=""><br>
approaches are identical except that the IPOPT solver is being used in<br>
place of the L-BFGS-B solver? Since IPOPT will be using the<br>
same limited-memory quasi-Newton approximation as in L-BFGS-B, I imagine<br>
that the two running times will be similar. However, IPOPT is designed to<br>
solve more general problems than L-BFGS-B, so maybe there is substantial<br>
overhead due to extra code.<br></span>
2. Do you expect approach 3 to yield a better solution than approach 2<span class=""><br>
[i.e. smaller (gi)^2], and do you expect approach 4 to yield a better<br>
solution than approaches 3 and 2? My hope is that the additional<br>
constraints will result in a better solution.<br></span>
3. Do you expect approach 3 to be faster than approach 2, and do you<span class=""><br>
expect approach 4 to be faster than approaches 3 and 2? I am hoping that<br>
the additional constraints reduce the search space and result in quicker<br>
convergence and hence a reduction in the running time.<br></span>
4. Is IPOPT appropriate for the types of problems described?<br>
5. Any other recommendations?<br>
<br>
<br>
<br>
_______________________________________________<br>
Ipopt mailing list<br>
<a href="mailto:Ipopt@list.coin-or.org" target="_blank">Ipopt@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/ipopt" rel="noreferrer" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
<br><span class="HOEnZb"><font color="#888888">
</font></span></blockquote><span class="HOEnZb"><font color="#888888">
<br>
<br>
-- <br>
<a href="http://www.gams.com/~stefan" rel="noreferrer" target="_blank">http://www.gams.com/~stefan</a><br>
</font></span></blockquote></div><br></div>