Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I am currently trying to solve nonlinear constrained minimization problem as implemented in matlab "fmincon" function. My expectations are, minimize(fun1,x0,uB,lB,fun2) where x0 is initial state, fun1 is function that needs to be minimized, uB are upper bounds, lB are lower bounds and fun2 is function that provides vectors of nonlinear equalities/inequalities as described in http://www.mathworks.com/help/optim/ug/fmincon.html as nonlcon function. These vectors are changing through iterations as well (they are non-linearly dependent on x_n, n-th iteration of solution vector). In matlab implementation they are in a form c(x)<=0. This is the last piece of code that need to be ported from matlab to c++ and I ve been struggling a lot while trying to find appropriate c++ library containing this algorithm. This is why I am seeking help here and I would much appreciate if you could provide your expertise.

Good example of what I want to do is first one on this page http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b Only difference is that I need boundaries as well...

Thanks in advance.

Peter

share|improve this question
    
There is a possibility of using NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference but I would need to calculate finite differences using multiple calls to "minimized" function evaluation from objective function and I was kind of hoping that that would be taken care of by algorithm it self in order to improve performance. My minimized function is really expensive to calculate. Just to clarify, the minimized function is log-likelihood of estimated model with original data in time-series markov-switching model estimation. –  Peter Kottas Dec 30 '12 at 15:11
1  
Have you looked at the answers to this question? If your requirements are not sufficiently addressed there, you should edit your question to point them out in order to get helpful recommendations. –  Christian Clason Dec 30 '12 at 18:04
    
Thanks, there are some useful information there. Currently I am up to my elbows in NLOPT library since I discovered that it might suit my problem as well. I ll keep this topic posted and will provide solution when i come up with one. Any help that might make the process faster is still appreciated. Actual implementation for example, etc. –  Peter Kottas Dec 30 '12 at 21:11
1  
Several questions: 1. Is your problem convex? 2. Are the objective and constraints differentiable? If so, how many times? Once? Twice? 3. Can you calculate those derivatives easily, if they exist? Would finite difference approximations be easy to calculate if you don't have those derivatives readily available? 4. How many decision variables do you have? (i.e., over how many variables are you trying to minimize?) A rough estimate would suffice. 5. Are function evaluations expensive? It would be helpful to have all of this information in order to give you a better answer. –  Geoff Oxberry Dec 30 '12 at 23:26
    
Hi! First of all, thanks for reply. 1. Hard to tell but most likely no, because the minimized function is log-likelihood between markov switching model estimation of timeseries in finanancial application and from the nature of it I assume sort of noisy output. 2.no 3.only using finite differences 4.solution vector consists of n variables where n is dependent on desired models parameters, in general from 12 to lets say 30 5.log-likelihood between model and original data is expensive, additional nonlinear inequalities are cheep to calculate –  Peter Kottas Dec 31 '12 at 0:08

2 Answers 2

If your function is not differentiable, you should be careful about how you use finite differences. If you want to use derivative information, your best bet is probably some sort of semismooth Newton-type method. A set of notes describing such methods can be found here.

Twelve to thirty variables is probably on the upper end of what's doable with pattern search (also called direct search) methods. A recent review paper by Rios and Sahinidis in Journal of Global Optimization on derivative-free optimization methods (such as pattern search methods) can be found here, along with a companion web page. A less recent review paper on these methods by Kolda, Lewis, and Torczon in SIAM Review can be found here. These methods work fairly well with expensive function evaluations, and don't necessarily require differentiability or derivative information.

Many of these methods require some sort of convexity to guarantee convergence to the global optimum, so if you were to solve your problem rigorously, you might need to couple these methods above with a branch-and-bound strategy. However, if you don't care about rigor, an approach like MATLAB's fmincon might work well enough (there are no guarantees anymore). Finite differences will most likely give you a member of the subdifferential of your nondifferentiable function, which could suffice for your problem instance and particular input data to return a sufficiently accurate result for your purposes. In that case, you should probably look at the libraries mentioned in the answers to the question Christian linked in his comment.

share|improve this answer

If all you need is a C++ library to solve nonlinear optimization problems, you can use RobOptim. Even though RobOptim was initially developed with robotics optimization problems in mind, it is suitable for any nonlinear optimization problems. It provides a simple C++ interface with plugins for multiple nonlinear solvers (Ipopt, NAG, etc.). Using that kind of wrappers makes it easy to use another NLP solver. If you cannot provide gradients, finite-difference computation can be done automatically.

It's open source so you can check out the source code on GitHub: https://github.com/roboptim/

The analysis done by @Geoff Oxberry is essential for the choice of nonlinear solver that will be called by RobOptim. Note that when dealing with that kind of solvers, parameter tweaking can have a huge impact on performance, and you may still get stuck in local minimas (it really depends on the kind of problem you are dealing with).

Note: I am one of the developers of this project.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.