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 19:16:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 9
Message-ID: <hd75di$nm5$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>
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 1257707762 24261 172.30.248.38 (8 Nov 2009 19:16:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 8 Nov 2009 19:16:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 2081939
Xref: news.mathworks.com comp.soft-sys.matlab:583392


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

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). The number of iterations doesn't grow significantly with n. So really, I'm looking to blame whatever happens inside each iteration.