[Coin-ipopt] Dense problem

[Fijoy George]

Hi Andreas, Carl,

Thanks for the replies.

MATLAB medium-scale fmincon() has so far given me better results than I
had expected. For example, I have been able solve an instance of my
problem with 200 variables and 26300+ constraints on a P4 3.39GHz 1GB
machine within 5 - 20 minutes depending on the initial solution. I have
also observed comparable timings for another instance with 100 variables
and 76000+ constraints. As long as fmincon() does not run out of memory,
it does find a solution.

Given these results, I do think that my problem is well conditioned with
smooth objective and constraints. What exactly do you mean by
structured? Some sort of relationship between gradients of constraints?

Would you think that for the problems IPOPT can handle, it would
converge significantly faster (say twice as fast) than fmincon()?  Is
there some published material which compares the timing results of IPOPT
(or an interior point method) with that of a method based on SQP?

-Fijoy



-----Original Message-----
From: Andreas Waechter [mailto:andreasw at watson.ibm.com] 
Sent: Monday, November 14, 2005 12:02 PM
To: fvadakku at purdue.edu
Cc: coin-ipopt mailing list
Subject: Re: [Coin-ipopt] Dense problem

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
>