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 17:02:02 +0000 (UTC)
Organization: Xoran Technologies
Lines: 13
Message-ID: <hd6tia$ph5$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>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1257699722 26149 172.30.248.35 (8 Nov 2009 17:02:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 8 Nov 2009 17:02:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:583366


"Matt " <xys@whatever.com> wrote in message <hd6q7v$2sk$1@fred.mathworks.com>...
> "Lior Vernia" <liorvern@post.tau.ac.il> wrote in message <hd4jva$gd$1@fred.mathworks.com>...
> Obviously fmincon is the one who decides how many times to compute f(x), and its gradients and Hessian, so how does that depend on n?
> =====
> 
> Well, the number of times it computes f() and its derivatives depends on how many iterations it needs to reach some stopping/convergence criterion. So, the complexity I guess is O(N*T(n)) where N is the number of iterations it ends up running.
====

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.