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.
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$