Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: fmincon complexity
Date: Fri, 16 May 2008 11:42:03 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 22
Message-ID: <g0jrua$7pv$1@fred.mathworks.com>
References: <g0jlni$idj$1@fred.mathworks.com> <g0jmr6$fme$1@fred.mathworks.com> <g0jnhl$6ge$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1210938123 7999 172.30.248.37 (16 May 2008 11:42:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 16 May 2008 11:42:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:468818


"Jun Li" <twofishleft@gmail.com> wrote in message 
<g0jnhl$6ge$1@fred.mathworks.com>...
> thank you so much, John.
> 
> m is quite large, around 10,000 or even more.
> but the algorithm starts at a feasible solution,
> 
> so i think the complexity just depends on n, right?

What worries me is, suppose n was 1. With n*m
inequalities and m = 10000, just the test for
the constraints will be a dominant factor.

The medium scale solver (required for this
class of problem) is an active set solver as I
recall. So once it knows which inequalities are
active, the problem gets much smaller, and
O(n^3). But since it may be forced to shuffle
the active constraints around a lot, things will
get nasty.

John