Warning

 

Close

Confirm Action

Are you sure you wish to do this?

Confirm Cancel
BCM
User Panel

Posted: 12/22/2013 9:37:39 AM EDT
I need to replace some Matlab code based around quadprog from the Optimization toolbox with C/C++, minimizing a quadratic function in an N-dimensional convex region.  I cannot pass Matlab code to the programming droids, lest their heads explode, so I need to convert it to something that they understand.  A recommendation for a reference book on quadratic programming is appreciated.
Link Posted: 12/22/2013 12:12:42 PM EDT
[#1]
This is only a guess, but there used to be a book (probably out of print now) called "Numerical Recipes in C" which might have covered that territory.

http://en.wikipedia.org/wiki/Numerical_Recipes

ETA: Maybe there's something here:

http://www.nr.com/

And see the discussion at:

http://www.nr.com/forum/showthread.php?t=1379




Link Posted: 12/22/2013 1:25:15 PM EDT
[#2]
Discussion ForumsJump to Quoted PostQuote History
Quoted:
This is only a guess, but there used to be a book (probably out of print now) called "Numerical Recipes in C" which might have covered that territory.

http://en.wikipedia.org/wiki/Numerical_Recipes


View Quote



I have that particular book, but unfortunately, solutions for Quadratic Programming are excluded.


Link Posted: 1/16/2014 6:04:12 PM EDT
[#3]
I figured it out, between searches on the web, and a few insights from Barazaa's book:

Nonlinear Programming

I'm using a Cutting Plane algorithm to train a Linear Support Vector Machine which requires the solution of a sequence of quadratic programs.  The sub-problems are convex and apparently the state-of-the-art solution for these are Internal Point Methods.  The biggest difficulty I found, and in the end there is a very simple solution for, is how to keep the variables all non-negative.  If you attempt to put barriers on all of the variables the equations become very ill-conditioned, but just putting them on the slack variables apparently does the trick.  Another surprising thing that I found is that as the feasible region is convex you do not need a full blown line search, a simple ratio test that keeps the variables feasible along the Newton direction is sufficient.

Close Join Our Mail List to Stay Up To Date! Win a FREE Membership!

Sign up for the ARFCOM weekly newsletter and be entered to win a free ARFCOM membership. One new winner* is announced every week!

You will receive an email every Friday morning featuring the latest chatter from the hottest topics, breaking news surrounding legislation, as well as exclusive deals only available to ARFCOM email subscribers.


By signing up you agree to our User Agreement. *Must have a registered ARFCOM account to win.
Top Top