+1
Under review

multiple precision for fmincon

Iuliia 6 year бұрын updated by Pavel Holoborodko 2 апта бұрын 9

Hello,


I would like to ask if you consider including fmincon in the Toolbox in near future. I have a part of Matlab code with optimization of nonlinear constrained function, and it would be very useful for me.


Best regards,

Iuliia

Under review

Dear Iuliia,


Thank you for the question. 

Yes, indeed, fmincon is in our todo list and actually we have beta version of fmincon (not included in toolbox yet). 

What optimization algorithm do you use in fmincon? So far our code supports "trust-region-reflective" and "active-set".


I will send you the code by email in a minute.

Are you actually modifying FMINCON source code, or are you independently creating code to emulate the FMINCON functionality (at least for those FMINCON algorithm options which you support?


If the former, have you encountered algorithm assumptions predicated on all computations being done in DP, such that if they were not identified and addressed, would prevent the MP version of FMINCON from achieving arbitrarily high accuracy, presuming that user-settable algorithm tolerances (e.g., for feasibility and optimality) are set appropriately?  This seems like it might be a non-trivial effort to implement.


Edit: I now see https://mct.userecho.com/forums/1-general/topics/125-mp-linprog-support/ . So, apparently you have to create your own implementation of FMINCON funtionality.  Nonlinear optimization solvers are very complicated, and there are many subtleties and refinements which are usually not documented in papers and books, but can be very significant to performance and robustness. A highly non-trivial undertaking to do well!!

You are absolutely right - this is non-trivial task to do.


However, please let me know what parts of toolbox you find trivial to implement :)?

Full re-implementation of MATLAB's core for matrix computations in arbitrary precision? Or n-dim arrays, sparse matrices, special functions or FFT?  With all optimizations and parallelism in native language....


The main issue is not the implementation difficulty itself, but restrictions and overhead imposed by MATLAB for third-party plugins. For example, MATLAB simply crashes when we call M-function (with nested calls to other M-language functions) from within MEX. This basically prevents direct and efficient implementation of optimization methods in native language (we use C++). Special workarounds are needed - like in ARPACK, or similar.

Is an MCT compatible version of Matlab's fmincon() nonlinear optimization available for SQP algorithm?

Not to my knowledge (toolbox doesn't provide it). There is a chance that the built-in code can be ported to use the "mp" type. Or at least the needed part of the code can be enabled with the "mp"

Currently, supported optimization functions:

fminsearchFind minimum of unconstrained multivariable function (Nelder-Mead)
fzeroFind root of continuous function of one variable
fsolveSolve system of nonlinear equations
lsqnonnegSolve nonnegative linear least-squares problem
optimsetCreate or edit optimization options structure
optimgetOptimization options values

6 years ago you mentioned possible implementation of "fmincon". What is the actual state of the art of optimization methods supported by MCT.

Michal,

Matlab's fmincon() provides choice of algorithm: interior point, SQP, trust region.

Interior point algorithms were never designed for accuracy, providing only a few decimal digits precision on easier problems.

SQP is more accurate, disclosed in an excellent textbook by Nocedal & Wright:

https://www.convexoptimization.com/TOOLS/nocedal.pdf

Still, Matlab's SQP implementation would benefit greatly from quadruple precision because it is sensitive to quantization noise of double precision floating point; even on low-dimensional problems.

It is best not to begin with Optimization source code developed at Mathworks.

I speculate that the authors of fmincon() are not specialists in mathematical Optimization. 

It would be better to port original source code developed by mathematicians themselves: Philip Gill, Walter Murray, Michael Saunders, Margaret Wright, Gene Golub, Stephen Wright, Stephen Boyd, Lieven Vandenberghe, Nick Higham, Yinyu Ye, Jan de Leeuw, Henry Wolkowicz, Mar Hershenson, Michael Grant, Jos Sturm, David Donoho, Emmanuel Candes, Monique Laurent, Joakim Jalden, Benjamin Recht, Pablo A. Parrilo, Angelia Nedić.

I know that two of these authors certainly want to see their code translated into Matlab source.

Jon Dattorro

@dattorro Thanks for answer and additional insight info. But my primary question was oriented on MCT developers. Pavel 6 years ago announced here, that "fmincon" is already implemented as part of MCT beta-version (see Pavel's answer: "fmincon is in our todo list and actually we have beta version of fmincon (not included in toolbox yet)"). So, I am just asking Pavel if this function will be available in the near future or not, because in MCT documentation is still not mentioned.

We still have the same beta version of fmincon (can send it by email for tests).

The fmincon is the part of the optimization toolbox, and its M-code depends heavily on the Mathworks compiled dll/so libraries (hardcoded to double precision). This makes it difficult to port to "mp" and include all the special cases and plethora of  functionality it provides.

What many of our users do - is they implement exactly the algorithm they need for particular problem.
This is what original topic starter did (we helped her along the way).