Thread: Math Minimization library and methods (in C++)?

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    2

    Math Minimization library and methods (in C++)?

    Greetings to all,
    I have an optimization problem I’m trying to solve. I have 3 variables (basically the position of sphere in X, Y, Z), and I have a cost function I want to minimize. I do not have a way of getting the derivative directly (although I could use something like forward-difference if I have to). So far, I’ve been using MINPACK and lmdif function, but it’s very sensitive to the starting position.
    Can anyone suggest a decent, efficient algorithm for this kind of problem, and moreover can anyone suggest any libraries that are known to work correctly and efficiently? I’m using C++ and Visual Studio. Method-wise, I’m considering Simplex, BFGS, or Simulated Annealing, but, again, I’m not sure what libraries to go with…
    Right now, I just want to get it to work well with the artificial, clean data, but the final problem will have to deal with somewhat noisy data AND an additional parameter (the radius of the sphere, which also has a size constraint). That said, anything that can also handle the latter conditions robustly as well would be excellent.
    If anyone could provide any assistance, it would be very greatly appreciated.
    Sincerely,
    Michael

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    In general, non-linear least squares optimisation problems are always characterised by sensitivity to numerical error. It doesn't matter what library you use, you will experience such sensitivity because, in general, there is no closed-form solution to a general non-linear least squares problem.

    Doing a google search for "nonlinear least squares optimization library" will turn up plenty of possible libraries.

    Rather than trying to find a better library, you would be better off spending some effort characterising your cost function mathematically (i.e. on paper) rather than numerically. Does it have mathematical properties that you can exploit? The more properties you can identify, the more chance you have of picking an algorithm that can exploit those properties to find a solution more efficiently and/or in a manner less sensitive to numerical error.

    Essentially, my message is to pick an algorithm that suits the mathematical characteristics of your problem, before worrying about picking a library that provides an implementation of such an algorithm. Picking the right algorithm by an analysis on paper needs to be about 90% of your investment.

    Incidentally, the simplex algorithm is for linear optimisation problems. To use it, you will need to find some linear approximation of your non-linear problem (eg a preprocessing phase). The process of finding such a linear approximation will be sensitive to your starting assumptions.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Jun 2010
    Posts
    2
    Thanks for the reply!

    Could you clarify what you mean by mathematical properties? Do you mean constraints on the parameters? Or breaking the single function up into individual cost functions? (Or something else entirely?) I've tried my darndest to turn this into a linear function, but no-go...

    (By the by, I was thinking of Nelder and Mead's Downhill Simplex method when I said Simplex before; I should have been more specific).

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Examples of mathematical properties: bounded, unbounded, continuous, one-to-one, transcendental, algebraic, differentiable, integrable, discontinuous, odd, even, convex, monotonic, periodic, unimodal, bimodal, multimodal, analytical, meromorphic, polynomial, trigonometric, .......
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. built-in methods
    By Aisthesis in forum C++ Programming
    Replies: 10
    Last Post: 12-22-2009, 11:07 PM
  2. Class methods in header or source file?
    By TriKri in forum C++ Programming
    Replies: 13
    Last Post: 09-17-2007, 05:23 AM
  3. an easy, portable, python accessible graphics math library
    By ichijoji in forum Game Programming
    Replies: 2
    Last Post: 12-07-2006, 12:10 AM
  4. Replies: 8
    Last Post: 07-27-2003, 01:52 PM
  5. exporting class methods to library results in .lib and .exp
    By Shadow12345 in forum C++ Programming
    Replies: 15
    Last Post: 01-05-2003, 08:01 PM