how does fmincon interior-point algorithm deals wtih underdetermined system?

I am working on a tomography problem that may become underdetermined during iteration. To handle this, I may give NaN to fmincon to tell it to start from a new point.

The following text is from the documentation for the lsqnonlin function:

"For the trust-region-reflective algorithm, the nonlinear system of equations cannot be underdetermined; that is, the number of equations (the number of elements of F returned by fun) must be at least as many as the length of x." "In the underdetermined case, lsqnonlin uses the Levenberg-Marquardt algorithm."

I cannot find the documentation for the fmincon interior-point algorithm. Can you tell me how this algorithm deals with underdetermined systems?

Thank you for your help!

Answer 1

[Torsten]

All optimization problems are "underdetermined" in the sense of what you wrote above (i.e. less equality constraints than unknowns). Otherwise there would be no degree of freedom for optimization. So I cannot imagine this is true for any available algorithm for "fmincon". Maybe you read it in the description of "fsolve".

[Frank]

From lsqnonlin documentation: "In the underdetermined case, lsqnonlin uses the Levenberg-Marquardt algorithm." I wonder what fmincon do in the underdetermined case?

[Torsten]

I wonder what fmincon do in the underdetermined case?

Nothing because all optimization problems are underdetermined in the sense that the number of equality constraints is smaller than the number of unknows.

From the documentation of "fmincon":

The trust-region-reflective algorithm requires:

• A gradient to be supplied in the objective function
• SpecifyObjectiveGradient to be set to true
• Either bound constraints or linear equality constraints, but not both

If you select the 'trust-region-reflective' algorithm and these conditions are not all satisfied, fmincon throws an error.

These are the only restrictions for the application of "trust-region reflective".

The meaning of "underdetermined" for "fsolve" or "lsqnonlin" differs from the meaning for "fmincon".

For "fsolve" and "lsqnonlin" equality constraints do not exist, but you only try to determine a vector x that minimizes sum_i f_i(x)^2. If x has more elements than there are functions f_i, you can usually find a space of dimension numel(x) - numel(f_i) that makes the sum become 0. This is the "underdetermined" case.

For "fmincon", the number of unknows - the number of equality constraints also defines a kind of underdeterminedness, but this underdeterminedness is necessary to have degrees of freedom for optimization.

It would be interesting if you could explain what exactly you mean by "I am working on a tomography problem that may become underdetermined during iteration.".

[Frank]

https://ge0mlib.com/papers/Books/06_Geophysical_Data_Analysis_Discrete_Inverse.pdf

From the book:

"3.6.3 Overdetermined Problems". This overdetermined prolbem is also solved by optimization, which contradicts "All optimization problems are 'underdetermined' ".

https://ww2.mathworks.cn/en/academia/books/geophysical-data-analysis-menke.html

If you download the file from above, directly run the file gda12_13.m in MATLAB. You can see that there are 2430 rays with model parameters number 120. Obviously, 2430 > 120. This is an overdetermined problem solved by optimization. My original question is what fmincon does if there are few rays, such as only 100 or 50 rays? With 119 rays, I let the objective function returns NaN and fmincon starts from a new point; with 120 rays, keep running fmincon. Is this right? If not, what should I do?

Thank you very much for your answer!

[Torsten]

"3.6.3 Overdetermined Problems". This overdetermined prolbem is also solved by optimization, which contradicts "All optimization problems are 'underdetermined' ".

No. "lsqcurvefit", "lsqnonlin" or "fsolve" search for parameters such that a given function approximates some measurement data as close as possible. If the number of measurement data is greater than the number of parameters, the problem is called "overdetermined" since in general, we cannot find a parameter vector such that all the measurement data are reproduced without making errors. But seen from the optimization point of view, the problem is still underdetermined if the number of equality constraints on the parameters is smaller than the number of parameters. It is this kind of underdeterminedness that allows an optimization to make sense. If there were no degrees of freedom left in the choice of the parameters (e.g. if the number of equality constraints were equal or greater than the number of parameters), there would only be one or even no feasible parameter constellation as solution for the optimization.

As I said: you must differ between "underdeterminedness" in the sense that the number of measurement data is smaller than the number of parameters to be fitted and in the sense that the number of constraints on the parameters is smaller than the length of the parameter vector. The first influences the algorithm chosen (at least for "lsqcurvefit", "lsqnonlin" and "fsolve", not for "fmincon"), the second doesn't because it's typical for all optimizations.

You can see that there are 2430 rays with model parameters number 120. Obviously, 2430 > 120. This is an overdetermined problem solved by optimization. My original question is what fmincon does if there are few rays, such as only 100 or 50 rays? With 119 rays, I let the objective function returns NaN and fmincon starts from a new point; with 120 rays, keep running fmincon. Is this right? If not, what should I do?

I don't understand why the number of rays changes within one parameter fitting process. I interpreted them as some kind of measurements available for fitting the 120 parameters of your model. In principle, problems with less measurements than parameters can be formulated, but they don't make sense. Why ? Because the parameters you would get have no physical meaning and in general cannot be used for other applications. But for fmincon, it won't change the optimization algorithm. You'll get a parameter vector which leads to an optimal objective value of 0 with a solution manifold for your parameters of dimension (number of parameters - number of rays).

[Frank]

Thank you very much! I was confused.