[Ipopt] Using IPOPT to solve a very large and very nonlinear system of equations

Mon Aug 10 17:52:45 EDT 2015

Thank you so much for your quick response.

For the linear solver, I am using MUMPS right now. I am thinking of
switching to PARDISO. Compared to MUMPS, how much faster is 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?

Thanks,
Mike

On Sun, Aug 9, 2015 at 10:08 AM, Stefan Vigerske <stefan at math.hu-berlin.de>
wrote:

> Hi,
>
> on 1). I don't expect that the overhead in Ipopt for handling 0
> constraints will make it much slower.
>
> on 2) and 3). I don't expect 3 to be better than 2, but I would expect 4
> to be better than 2.
>
> on 4). I think it's worth a try.
>
> on 5). Experiment with different linear solvers in Ipopt (linear_solver
> option), e.g., from the HSL library.
>
> Stefan
>
> On 08/04/2015 02:54 AM, Michael Mwangi wrote:
>
>> Dear All:
>>
>> 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.
>>
>> Thanks so much,
>> Michael Mwangi
>> Assistant Professor
>> Department of Biochemistry and Molecular Biology
>> Penn State University
>>
>>
>> *THE PROBLEM*
>>
>> I would like to solve a system of equations:
>>
>> g1(x1, x2, ..., xn) = 0
>> g2(x1, x2, ..., xn) = 0
>> .
>> .
>> .
>> gm(x1, x2, ..., xn) = 0
>>
>> l <= xi <= u for all i
>>
>>
>> where:
>>
>>     - n ~ 1,000,000
>>     - m ~ 10,000
>>     - 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
>>     - 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
>>     - gi and gj depend on disjoint subsets of variables when |j - i| >~
>> 100
>>     so that the Jacobian of the gi has a block-like form
>>
>>
>> *APPROACH 1: SOLVE A LEAST SQUARES FORMULATION USING L-BFGS-B*
>>
>> I tried to solve a least squares formulation of the problem
>>
>> minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2
>>
>> l <= xi <= u for all i
>>
>> using the L-BFGS-B solver here <http://www.chokkan.org/software/liblbfgs/
>> >
>> that only permits the simple constraints l <= xi <= u.
>>
>> 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.
>>
>>
>> *APPROACH 2: SOLVE THE LEAST SQUARES FORMULATION IN APPROACH 1 USING
>> IPOPT*
>>
>> I am thinking of using the IPOPT solver here
>> <http://www.coin-or.org/Ipopt/documentation/node23.html> to solve the
>> same
>> exact problem as in approach 1.
>>
>>
>> *APPROACH 3: SOLVE A MORE CONSTRAINED LEAST SQUARES FORMULATION USING
>> IPOPT*
>>
>> I am thinking of using the IPOPT solver to solve a more constrained least
>> squares formulation of the problem:
>>
>> minimize f = (g1)^2 + (g2)^2 + ... + (gm)^2
>>
>> l <= xi <= u for all i
>>
>> -e <= gi <= e for all i where e >= 0 is some small error tolerance
>>
>> My hope is that the additional constraints -e <= gi <= e force the solver
>> to find a better solution.
>>
>>
>> *APPROACH 4: SOLVE THE ORIGINAL SYSTEM OF EQUATIONS USING IPOPT*
>>
>> I am thinking of using the IPOPT solver to solve the original system of
>> equations:
>>
>> minimize f = 0
>>
>> l <= xi <= u for all i
>>
>>
>> 0 <= gi <= 0 for all i
>>
>>
>> Thus, the objective function f is trivially zero, and the problem is
>> encapsulated in the constraint functions.
>>
>>
>> *COMMENTS ABOUT APPROACHES 2 - 4*
>>
>> As already noted, the Jacobian of the gi has only ~10^8 nonzero elements
>> and has a block-like form.
>>
>> 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) here
>> <http://www.coin-or.org/Ipopt/documentation/node22.html#eq:IpoptLAG> 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 by
>> setting hessian_approximation = "limited-memory"
>> <
>> http://www.coin-or.org/Ipopt/documentation/node52.html#SECTION0001113010000000000000
>> >
>> .
>>
>> I will be doing the computations on a workstation with 120 GB of RAM, so
>> memory should not be an issue.
>>
>>
>> *MY QUESTIONS FOR YOU*
>>
>> I have the following questions for you:
>>
>>     1. 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.
>>     2. 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.
>>     3. 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.
>>     4. Is IPOPT appropriate for the types of problems described?
>>     5. Any other recommendations?
>>
>>
>>
>> _______________________________________________
>> Ipopt mailing list
>> Ipopt at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/ipopt
>>
>>
>
> --
> http://www.gams.com/~stefan
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/ipopt/attachments/20150810/3443e049/attachment.html>