[Coin-ipopt] Dense problem

[Carl Damon Laird]

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
>
>