Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Computational complexity of fmincon algorithm
Date: Sun, 8 Nov 2009 20:23:01 +0000 (UTC)
Organization: Xoran Technologies
Lines: 17
Message-ID: <hd79b5$n0f$1@fred.mathworks.com>
References: <hd4b47$mq$1@fred.mathworks.com> <hd4h93$g15$1@fred.mathworks.com> <hd4jva$gd$1@fred.mathworks.com> <hd6q7v$2sk$1@fred.mathworks.com> <hd6tia$ph5$1@fred.mathworks.com> <hd75di$nm5$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1257711781 23567 172.30.248.38 (8 Nov 2009 20:23:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 8 Nov 2009 20:23:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:583403


"Lior Vernia" <liorvern@post.tau.ac.il> wrote in message <hd75di$nm5$1@fred.mathworks.com>...
> > It occurs to me there would also be an n-dependence on the complexity of fmincon solving, at each iteration
> > 
> > H*x=-g;   %H=Hessian, g=gradient
> > 
> > This would in general be O(n^3), but could be less depending on the sparsity structure of H.
> 
> Is this this the only dependence on n of each iteration? Because I'm running fmincon on increasingly larger inputs, and its runtime grows dramatically with each increase. I don't have enough data to say for sure that it grows exponentially, but that's how it seems.
=====

All I can say is  O(n^3) could be enough to give you a dramatic increase. If n increases by a factor of 10, the computations would increase by a factor of 1000.


> The function I'm minimizing is the same function, it's smooth and convex, and its complexity is O(n). Each gradient computation complexity is also O(n), so if all of them have to be computed during an iteration that adds O(n^2). 
=====

And what about the Hessian?