why mincx is slow for high number of variables?

Hi I've tried to solve an optimization problem which has 7 variables and the constraints are on the LMI system form and mincx function worked like charm it solved in 0.5 (s). when i tried another problem with 35 variables it takes like 30 (S) the problem is that i am going to run this function inside a loop of 9000 element so it will take forever to finish. my question, is this time normal for mincx or i am doing something wrong? also is there any faster alternative for mincx if it is really slow

Note: when i run Profiler it shows that most of the time is in function called Pds (Mex).

i really need help since my senior project will come to an end if this problem is not solved

Answer 1

[John D'Errico]

One thing you should have learned in class at some point is that larger problems do not always take the same amount of time to solve as small problems.

For example, how much time does it take to multiply two vectors, in an element-wise fashion?

N = 10000;
x = rand(1,N);
y = rand(1,N);

z = x.*y;

We would expect this to be roughly linear in the length of those vectors. Thus, double N, and it will take twice as much time to process. In the most basic sense, your computer does one thing at a time, so double the amount of work, and double the amount of time.

However, many operations are NOT linear in the size of the problem. For example, the matrix multiply X*Y below will require time that will be roughly proportional to the cube of N to complete.

N = 1000;
x = rand(N,N);
y = rand(N,N);

z = x*y;

So, double N, and it will take roughly 8 times as much work to do. You can show this to be effectively true by listing all the computations in a matrix*matrix multiply. (The use of multi-threaded processing, the BLAS for linear algebra, etc., changes some of that, but even so, think O(N^3) here for the number of computations in a matrix multiply.)

Now you are wanting to use mincx. It does an optimization. Bigger problems in an optimization are the same as what I showed above. They take more time, and the increase in time is NOT linear. In fact, at the very least, since it will use linear algebra to do those computations, I would expect the work needed will potentially increase with the cube of the number of variables. This is because as the problem size gets larger, the computations will probably be dominated by operations that takes O(N^3) time.

So if a 7 variable problem takes roughly 0.5 seconds, then for a problem with 5 times as many variables, at least SOME of the internal computations inside mincx will take 5^3=125 as much computational effort. So even without thinking about the computations inside mincx, I might predict a rough estimate of the time required for a 35 variable problem might be:

.5*5^3
ans =
     62.5

So something on the order of a minute to complete. That mincx took only 30 seconds or so, is due to the fact that some of the internal computations do not scale as O(N^3).

Is there a faster alternative to mincx? Um, well, gosh. Maybe the author of mincx intentionally chose a slow way to code the algorithm. Yeah, right.

So while it is possible to solve your problem faster, that might require a faster computer. Or solve smaller problems. Or learn to use the parallel processing toolbox well, and get a good enough computer to handle it in stride. (You might need to buy that toolbox too, since it is not free.) Start your computer running overnight, and get a good nights rest while it works.

And, hey, it could be worse. Some problems grow exponentially with problem size in terms of the time required to solve them. That is true of many combinatorial problems. So O(N^3) is small potatoes.

Just wanting a big problem to run more quickly than it does is not sufficient. Big problems often take big time to solve. That your project might hinge on solving this is just a fact of life. People very often create far to large of a problem for them to solve. It happens all the time. Sometimes it just means you need to retrench, back up and solve a smaller problem that is mathematically tractable.

As far as your current problem goes, it does not seem at all impossible to solve. 9000 sub-problems, each of which takes 30 seconds to solve. So a couple of hours. Sorry, but I don't see the problem here. Start it running, and go read a book. I want to suggest one about numerical analysis, but "War and Peace" might be sufficient. :-) I've worked on problems that took weeks of computational time to solve.

[Walter Roberson]

Nonlinear optimization problems, or linear or quadratic optimization that is coded with the wrong tools, often take time proportional to 2^N

[mohamed abbas]

what do u mean by coded with wrong tools ?

[John D'Errico]

Of course you CAN write code in a terrible way. Using the wrong algorithm can turn a linear problem into one using exponential time or worse. But we should try not to confuse people.

[Walter Roberson]

Linear optimization can be automatically broken up into a number of sub-tasks, each involving a convex polygon. For each of those convex polygons, the optimal solution can be calculated fairly directly for the inside, and the local optimum solution for that polygon is always either that inside solution or the value at one of the vertices (or edges? I'm not sure at the moment.) This makes the work for each subtask linear to find a local solution that is certain to be optimum within that area. You can run the calculations over each of the areas and pick the best out of all of the solutions to get an overall minimum for the entire problem. The only question left to resolve then how the number of regions to be checked increases with the number of linear constraints.

The algorithms for handling linear programming are well known and guarantee a global solution.

But suppose that you take the linear problem and feed it to fmincon instead of to the dedicated linear optimizer. Then fmincon looks around a bit for some point that works, and then mostly proceeds along a gradient, gets projected into some region that the constraints forbid, and backs up, staying within whatever region it happened to be in, finds the local minima there and gives up. No global solution. Even if it does not get blocked by a constraint, it is still using gradient (sometimes Hessian too) information, and that tends to get stuck in local minima.

Now suppose you take the linear problem and feed it to patternsearch instead of to the dedicated linear optimizer or to fmincon. patternsearch does not use gradients (and so can work for functions that have singularities), but on the other hand at any given position, the only way to check to be sure it is at a local minima is to alter one parameter at a time, testing a higher value and testing a lower value. Then repeat with pairs of parameters, ++, +-, -+, --, Then test with triples of parameters.. and so. This would be a 2^N process in order to be certain that you are at a minima.

This is not to say that patternsearch is useless: patternsearch can be pretty effective at getting out of local minima that are not too steep. patternsearch can pull you across large swaths of multiple minima and maxima to get you to near a major minima. But you might want to call fmincon after patternsearch to find the best location within that basin of attraction. But the theory of patternsearch says that it can be as bad as 2^N.

Thus, choosing the right tool can be important.