3
$\begingroup$

I need to solve an optimization problem, which is defined in a Mathematica notebook.

Using Mathematica's FindMinimum is not an option, because it is too slow. So, the idea is to use an external solver for quadratically constraint quadratic problems and use MathLink to get the constraints of the problem from Mathematica, calculate the solution, and return the solution to Mathematica.

And here is my problem: The constraints (quadratic and linear) are given to me as a list of expressions, e.g.

{ -1+(-0.363263+x)^2+(-0.329466+y)^2<=0,
-1+(-0.248721+x)^2+(0.451803 +y)^2<=0, 
-1+(0.33444 +x)^2+(-0.41341+y)^2<=0, 
-1+(0.414249 +x)^2+(0.384528 +y)^2<=0, 
-1+(-0.65488+x)^2+(0.242478 +y)^2<=0, 
-1+(-0.176244+x)^2+(0.30843 +y)^2<=0, 
-1.4+x<=t, -0.5+y<=t, 0.4 -x<=t, -0.5-y<=t }

How do I deal with such a list in my C++ function? Do I need to change its template signature so that it takes a SymbolList instead of a RealList (as in my current version)?

Or is there a way to extract all the numbers in my constraint list and put them in a list in Mathematica?

|improve this question
$\endgroup$
  • 4
    $\begingroup$ Welcome to Mathematica.SE! Are you sure that you don't want to investigate speeding up your optimization problem in Mathematica first? What function of x and y do you want to optimize? What's the value of t? I tried a few rather complex functions and they all finish below 1/10 s. $\endgroup$ – Sjoerd C. de Vries Sep 2 '12 at 21:17
  • 5
    $\begingroup$ Downvoted because the assertion FindMinimum is not an option, because it is too slow is not justified. I'll remove the vote if you share some insight about the problem that justifies it $\endgroup$ – Dr. belisarius Sep 2 '12 at 22:06
  • 1
    $\begingroup$ Lets replace prove by illustrate in my above comment. $\endgroup$ – halirutan♦ Sep 3 '12 at 3:29
  • 1
    $\begingroup$ The others have a point. By compiling your objective function you can easily get a factor of 10. Also take a look at this: mathematica.stackexchange.com/questions/4700/…. Mathematica is quite fast for numerics nowadays. $\endgroup$ – Ajasja Sep 3 '12 at 7:37
  • 5
    $\begingroup$ You mention that your objective is simple, you could give the Jacobian to FindMinimum, or chose a better algorithm. It were good if you would actually show to issue at hand. Even if FindMinimum is the actual bottleneck most likely MathLink is not the way to go. $\endgroup$ – user21 Sep 3 '12 at 9:18
8
$\begingroup$

I don't know if this answer helps you but what I wanted to convey would be too lengthy for a comment. First of all quoting from your comment

"...the objective function (it is t, so fairly trivial)"

this problem actually renders to be so simple that any mechanism involving Compile or binding with external optimization routine (e.g CPLEX) involving Mathlink becomes completely unnecessary. Given that you agree with my conclusion of your comment you can see that MMA built-in optimization functions FindMinimum and NMinimize are already pretty efficient.

linearcons=
-1.4 + x <= t &&
-0.5 + y <= t &&
 0.4 - x <= t &&
-0.5 - y <= t;
quadraticcons=
-1+(-0.363263+x)^2+(-0.329466+y)^2<=0&&
-1+(-0.248721+x)^2+(0.451803+y)^2<=0&&
-1+(0.33444+x)^2+(-0.41341+y)^2<=0&&
-1+(0.414249+x)^2+(0.384528+y)^2<=0&&
-1+(-0.65488+x)^2+(0.242478+y)^2<=0&&
-1+(-0.176244+x)^2+(0.30843+y)^2<=0

Now call the optimization functions and see the Timing

res=NMinimize[{t,quadraticcons && linearcons},{x,y,t}]; // AbsoluteTiming
res1 = FindMinimum[{t,quadraticcons && linearcons},{x,y,t}]; // AbsoluteTiming

{0.2100003, Null}

{0.0300001, Null}

Is not it practically fast enough for your "fairly trivial" objective function? Added advantage is that MMA finds the unique global minimum here. You can visualize the minimum as in case of this too simple objective the intersection of the parameter space spanned by the quadratic and the linear constraint is a unique point. Lets see the two parameter spaces seperately using RegionPlot3D and RegionPlot. enter image description here

Now using the visualization code from a past question we can see that the linear and the quadratic constrain agrees at a single point and MMA finds it really fast as we have seen above. enter image description here The sought after point {x,y,t} is

FindArgMin[{t, quadraticcons && linearcons}, {x, y, t}]

{0.537203, -0.076731, -0.137203}

However I am using a high end desktop with core i7 extreme processor so on average machine the timing may turn out to be a bit worse..

BR

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ +1 I was going to post the same. Just for reference in a Core2Duo @2GHz your timing for FindMinimum[] gets a x3 factor. And what the OP is looking for is the min t (ie the square's size) where these two figures intersect i.stack.imgur.com/EnhO6.png. Perhaps the only justification for trying to optimize this is having to solve thousands of these problems per second. $\endgroup$ – Dr. belisarius Sep 3 '12 at 13:46
  • 1
    $\begingroup$ This is a nice answer, but given that he is being told to do this with CPLEX I suspect that he does need to solve thousands of such problems per second in some line-of-business application. FindMinimum uses the nonlinear interior point method for this problem, which unfortunately is implemented as top-level code. A modest speedup can be had by setting Method -> {"InteriorPoint", "Theta" -> 1/3}, but I think that's the best that can be done, unless somebody (somebody else this time!) wants to reimplement this method in compiled code. $\endgroup$ – Oleksandr R. Sep 3 '12 at 14:09
  • $\begingroup$ @OleksandrR. The method option you specified is it documented? However I did not see any speed improvement contrarily it was a bit slower. Is it a correct observation? $\endgroup$ – PlatoManiac Sep 3 '12 at 14:24
  • 4
    $\begingroup$ @PlatoManiac I averaged over 100 runs of FindMinimum. The run-to-run variability is quite large; I got anywhere between your stated value of about 30ms and a much greater figure of 265ms. The option is not documented but you can see what options exist with Options[FindMinimum`InteriorPoint]. Theta was the only one I found to make a significant difference. $\endgroup$ – Oleksandr R. Sep 3 '12 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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