2
$\begingroup$

Consider the following:

Minimize[{(ξ - x)^2 + (η - y)^2, a ξ + b η == c}, {ξ, η}, Reals]

After asking Mathematica to do this yesterday afternoon and forgetting about it, I came back into work this morning to find it still grinding, with the Mathematica kernel using 42GB of memory.

(The simple question at this point is: What's going on?. More details follow.)

Why this should be an easy problem

I'm asking Mathematica to minimize a convex quadratic function of only two variables, subject to a linear constraint, over the whole real line. No discrete optimization; no weird-shaped constraint regions; no nonconvexity; really simple formulae. I can do it pretty quickly myself on paper, in at least two different ways. I actually can't think of any approach to symbolic optimization that wouldn't find this easy, and I confess I'm a little surprised Wolfram haven't special-cased quadratic programming in Minimize and made it trivial.

Some things that don't seem to help

A few things I tried that didn't lead to quick solutions (I didn't give it overnight, so I can't guarantee that they didn't help at all):

  • Using Assuming to tell Mathematica that all the parameters are real.
  • Likewise, but actually saying they're all positive just in case that helps with some case-splitting heuristic.
  • Trying again in a new notebook in case some leftover state from a previous calculation was confusing Mathematica.

Some things that do help

If I make the problem one notch easier by minimizing ξ^2 + η^2 (without the offsets by x,y) then Mathematica solves it in well under a second. If I make it one notch easier in a different direction by making the constraint a ξ + b η == 0 (without the parameter c) then it takes a few seconds and produces a solution with what looks like a startling number of special cases. (More precisely: a few special cases, defined by very lengthy Boolean expressions involving things like whether parameters are positive, negative or zero, how they compare with sqrt(3) times one another, and other largely-irrelevant-seeming conditions.)

So my best guess is that Mathematica is applying some heuristic where it splits the parameter space up according to the signs of, I dunno, all the parameters and every linear combination of them that it can think of, and then solving separately on each piece, and then trying to combine them, or something. But it's only a guess, and I have to say it doesn't seem terribly plausible.

More detailed questions

  • What could be making this difficult for Mathematica?
  • What's it actually doing that takes it so much time and memory?
  • Have I made some boneheaded error in how I've called Minimize, or something?
  • Is there some useful general technique for getting Mathematica to do symbolic optimizations in reasonable time when they fail like this?

Other info

I'm using Mathematica 9.0.1.0. In case it makes any difference: Windows 8.1 (64-bit), Core i7 processor, 16GB of RAM.

$\endgroup$
  • $\begingroup$ It does not return quickly in V10.0.2 either. No problem with the explicit Lagrange multiplier system, Solve[{D[(ξ - x)^2 + (η - y)^2, {{ξ, η}}] == λ D[a ξ + b η, {{ξ, η}}], a ξ + b η == c}, {ξ, η, λ}, Reals]. I would report it to Wolfram support. Maybe it gets confused with so many symbolic parameters (although it does not seem excessive to me)> $\endgroup$ – Michael E2 Feb 11 '15 at 11:42
1
$\begingroup$

It does give a result if you consider four different cases for the signs of a and b:

f[{g_, h_}, a_, b_] := g[a, 0] && h[b, 0]
Minimize[{(e - x)^2 + (n - y)^2, a e + b n == c && #}, {e, n}, Reals] & /@ 
                                                       (f[#, a, b] & /@ Tuples[{Greater, Less}, 2])

The result is too large to paste here, but the minimum value for the function is either

(-c + a x + b y)^2/(a^2 + b^2)

or it doesn't exist (Infinity)

$\endgroup$
  • $\begingroup$ How quickly does that run for you? One of the experiments I tried was giving it signs for all the parameters (I just told it a,b,c,x,y were all positive), and it still didn't return quickly. $\endgroup$ – Gareth McCaughan Feb 11 '15 at 14:28
  • $\begingroup$ (Yes, we are agreed about the minimum value -- as I said, this problem is easy enough that even a human can solve it. My problem is that Mathematica is being surprisingly ineffective, not that I need the answer and can't work it out :-).) $\endgroup$ – Gareth McCaughan Feb 11 '15 at 14:30
  • $\begingroup$ @GarethMcCaughan The code above takes less than one second to execute $\endgroup$ – Dr. belisarius Feb 11 '15 at 14:34
  • $\begingroup$ @GarethMcCaughan Without further feedback it won't be clear for other users how to focus their efforts on your problem $\endgroup$ – Dr. belisarius Feb 11 '15 at 15:10
  • $\begingroup$ Oh, now that's very interesting. If I feed it the information that a>0 (etc.) as you did, by adding it to the constraint, then Minimize returns quickly. But if I do it by wrapping the Minimize call in Assuming[a>0...], it doesn't. $\endgroup$ – Gareth McCaughan Feb 11 '15 at 18:03

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.