[Coin-ipopt] Dense problem

[Andreas Waechter]

Hi Fijoy,

Just a few additional comments regarding your dense problem:

As Carl pointed out, storing and factorizing the linearized KKT system
(the linear system that needs to be solve in order to compute the Newton
steps in Ipopt) for your problem is a little challanging, due to the
large number of nonzeros in the constraint Jacobian (1e7).

However, things might not be quite as bad as Carl's initial estimate,
since the KKT system for your problem is actually very structured, and if
MA27 does a good job recognizing this structure (I'm not sure if it
necessarily, but it should), the fill-in should actually be rather small
(probably not even a factor of 2).  In that case, storing the factor would
only require about 200MB, and with the other stuff that Ipopt needs to
store, things might work on the 1GB machine you have.

The Ipopt option that would need to adjust are

liw_init_factor  2
la_init_factor   2

Since MA27 doesn't have internal memory allocation, it needs to be given
sufficient space from the beginning, and for safety, Ipopt overestimates
the amount of memory needed by the number given by the above options.  The
default is 5, but you might be able to get away with even less than 2
(like 1.5)...

At some point, alternative linear solvers will be available in Ipopt,
which might be an interesting alternative for you if you consider to use
Ipopt for your problem.  Also, it would also be possible to write Ipopt
code for solving the linear system efficiently exploiting your specific
structure, but that of course would require some work.

Out of curiosity: How large was the problem that you were able to solve
with fmincon?

Regards,

Andreas


On Fri, 11 Nov 2005, Carl Damon Laird wrote:

> While IPOPT has been used successfully for small dense problems, I think
> it will have difficulty with this one. To give a quick
> back-of-the-envelope calculation (so quick that I hope I have it right):
>
> Ignoring the contribution to the hessian (small number of vars) and the
> addition of slacks (diagonal contribution because of the barrier term) we
> are left estimating the number of nonzero entries in the KKT system as:
>
> nz in KKT ~= 1e5 constraints * 1e2 variables ~= 1e7 nonzero elements.
>
> with a fill-in factor for the factorization of 5-10 (maybe higher for
> dense systems). Giving us 1e8 nonzeros in the factorized KKT system which,
> for doubles, translates to ~1e9 bytes = 1e3 MB = 1GB.
>
> So, just for storing the factorized KKT system, I guess somewhere around a
> Gig. This is likely a lower bound estimate since the sparse matrix
> structure is actually 3 times the number of elements, the fill-in factor
> may be low and there is other memory usage to consider.
>
> On the whole, I think IPOPT will have trouble with this class and size of
> problem. You may want to consider an interior point method that inserts
> the inequalities directly into the barrier term instead of using slacks.
> This would give you an unconstrained problem with a small dense hessian.
>
> Does anyone know which solvers do this? Anyone have additional comments?
>
>
> Hope this helps (and don't forget to check my math :),
>
> Carl.
>
>
>
> On Fri, 11 Nov 2005 fvadakku at purdue.edu wrote:
>
> > Hi all,
> >
> > I was planning to use IPOPT C++ version to solve a dense constrained
> > optimization problem. I expect the final version of the problem to have the
> > following dimensions:
> >
> > # variables: a few hundred (200 - 400)
> > # constraints: approximately 100,000
> >
> > The objective function and all constraints are nonlinear. All constraints are
> > inequality constraints. Every constraint depends on every variable.
> >
> > However, after reading some posts in the archives, I suspect that I may run
> > into problems such as insufficient memory since IPOPT is designed to solve
> > sparse problems.
> >
> > Could someone tell me what kind of difficulties I should expect? Will the
> > sparse solver MA27 give me trouble?
> >
> > Approximately, how much memory would I need? The machine I use has 1GB RAM.
> >
> > So far I have been using the MATLAB routine fmincon() in  medium-scale mode
> > which is based on SQP. Does anyone know how the memory requirements of IPOPT
> > comapres with those of fmincon()?
> >
> > Thank you
> > Fijoy
> >
> >
> > _______________________________________________
> > Coin-ipopt mailing list
> > Coin-ipopt at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/coin-ipopt
> >
> >
> _______________________________________________
> Coin-ipopt mailing list
> Coin-ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-ipopt
>