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

Tue Aug 11 06:14:40 EDT 2015

Hi,

I do not have a meaningful comparison, but for large problems, I could 
imagine that switching to PARDISO can give a substantial improvement.

Stefan

On 08/10/2015 11:52 PM, Michael Mwangi wrote:
> 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
>>
>

-- 
http://www.gams.com/~stefan