Thread Subject: fmincon complexity

hi, all:

i am using the fmincon to solve problems.

like: f = log det(Q)
Q is n- square,
and it has n equality constraints,
n*m inequality constraints.

what is the complexity of the algorithm?

thanks

Jun

"Jun Li" <twofishleft@gmail.com> wrote in message
<g0jlni$idj$1@fred.mathworks.com>...
> hi, all:
>
> i am using the fmincon to solve problems.
>
> like: f = log det(Q)
> Q is n- square,
> and it has n equality constraints,
> n*m inequality constraints.
>
> what is the complexity of the algorithm?

Its probably roughly O(n^3)

I doubt that you can be much more
accurate than that. Unless m is quite
large, that should be the dominant
part.

If m is large, then I don't know there
will be a simple answer. It probably
depends on how many of your
constraints become active.

John

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?

thanks

Jun

"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