Fmincon requires way more memory than input variables

I'm using fmincon to solve a very large problem (up to 20000 variables). My problem is, that Matlab runs out of memory after a certain number of iterations. My objective function is sum((x - d).^2), where d is a constant. I use linear equality and inequality constraints as sparse matrices/vectors. My input variables x0, A, b, Aeq, beq require 0.5 MB up to 1 MB, although A for example is of the size 52560x17520. The maximum number of iterations is set to 525600. The error message is

                                              First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0   17521    0.000000e+00    2.188e+03    2.235e-07
    1   35043    5.897884e+00    2.027e+03    1.207e-01    2.429e+00
    2   52564    6.143605e+01    1.689e+03    3.174e-01    5.598e+00
Error using ldl
Requested 122641x122641 (18.3GB) array exceeds maximum array size preference. Creation of arrays greater than this limit may take a long time and
cause MATLAB to become unresponsive. See array size limit or preference panel for more information.

This brings me to a number of questions:

1. Why does fmincon need such huge arrays when the inputs are way smaller? And why do they require so much memory? Can't fmincon handle sparse matrices?
2. Why does this error occur after more than 50000 function calls and not at the beginning of the algorithm? Does this function add results to some intermediate variable, which grows with function calls? I also realized that every iteration step takes more time than the previous one, which suprises me.
3. Why does Matlab call my function 17521 times per iteration? I use exactly 17521 variables, but the cost function is made to handle vectors. Why doesn't Matlab compute the cost function with the complete x vector as a whole?

I was using lsqlin up to that point, which worked perfectly (no problems with the memory, extremely fast computation). Now I need nonlinear constraints, this is why I want to try to use fmincon.

Thank you very much for your help!

Answer 1

[Walter Roberson]

"Why does Matlab call my function 17521 times per iteration? I use exactly 17521 variables, but the cost function is made to handle vectors. Why doesn't Matlab compute the cost function with the complete x vector as a whole?"

https://www.mathworks.com/help/optim/ug/fmincon.html#inputarg_fun

"Function to minimize, specified as a function handle or function name. fun is a function that accepts a vector or array x and returns a real scalar f, the objective function evaluated at x."

Notice this does not say "returns a real f, the objective function evaluate at each row of x" or each column of x, or each hyperplane of x. Each call is passed an x the same size as your x0, and is responsible for returning a scalar. There is no option for providing multiple different x to each be evaluated separately in the call.

The reason that the number of function calls is the same as the number of iterations is that you have no provided it with a gradient function or hessian so it has to do estimation, which requires modifying each variable in turn.

Even if x0 were input as a sparse vector, gradient and hessian estimation is seldom going to return a sparse result.

But you can supply gradient and hessian functions; see https://www.mathworks.com/help/optim/ug/writing-scalar-objective-functions.html#bsj1e55 . The HessPattern option for one of the solvers allows you to specify the sparsity if you want it to estimate the hessian but have knowledge of which variables are connected.

At the moment I do not know quite why it needed such a large matrix, but I can tell from the error message that it was doing LDL, which is a step described at https://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-algorithms.html#brh9shq for the Interior Point algorithm.

[Thomas]

Thank you very much, Sir, this is exactly what I needed!

I ended up using my own gradient and hessian matrices and use them as sparse matrices!