MATLAB Central Newsreader - Computational complexity of fmincon algorithm

Computational complexity of fmincon algorithm

Lior Vernia — Sat, 07 Nov 2009 17:35:04 -0500

Hello,

I've wondered what the computational complexity of the fmincon algorithm is (the medium scale one, I think it's a line search). I'd especially like to know how it depends on the number of variables; is it exponential? I thought it'd be easier to ask here than to look at the m-file and try to figure out the exact algorithm myself.

Thanks, Lior.

Re: Computational complexity of fmincon algorithm

Matt — Sat, 07 Nov 2009 19:20:03 -0500

"Lior Vernia" <liorvern@post.tau.ac.il> wrote in message <hd4b47$mq$1@fred.mathworks.com>...
> Hello,
>
> I've wondered what the computational complexity of the fmincon algorithm is (the medium scale one, I think it's a line search). I'd especially like to know how it depends on the number of variables; is it exponential? I thought it'd be easier to ask here than to look at the m-file and try to figure out the exact algorithm myself.
======

That would really depend on your objective function. For example

f(x)=norm(x)^2

is obviously linear in the number of variables, while for a dense square matrix A

f(x)=norm(A*x)^2

is obviously quadratic in the the number of variables, because computing A*x is O(N^2)

Re: Computational complexity of fmincon algorithm

Lior Vernia — Sat, 07 Nov 2009 20:06:02 -0500

Hi Matt,

Thanks for the speedy reply. You are correct, of course. However, let's assume that since the objective function is written by me, its complexity is known to us. We can call it T(n), n being the number of variables. Let's also say that f(x) is analytical and that I'm supplying the gradients and the Hessian matrix, and thus we know their complexity as well. What should the complexity of the entire call to fmincon be? 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?

Thanks, Lior.

Re: Computational complexity of fmincon algorithm

Matt — Sun, 08 Nov 2009 16:05:19 -0500

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

The number of iterations though is influenced in part by you, since you choose the stopping/convergence criteria through optional arguments passed to fmincon. It obviously also depends on the shape of the graph of f(), e.g. the condition number of the Hessian at the solution. Some functions just take more iterations to minimize than others.

Re: Computational complexity of fmincon algorithm

Matt — Sun, 08 Nov 2009 17:02:02 -0500

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

Re: Computational complexity of fmincon algorithm

Lior Vernia — Sun, 08 Nov 2009 19:16:02 -0500

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

Re: Computational complexity of fmincon algorithm

Matt — Sun, 08 Nov 2009 20:23:01 -0500

"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?