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.

Improve this question
$\endgroup$
1
  • $\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, 2015 at 11:42

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
6
  • $\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, 2015 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, 2015 at 14:30
  • $\begingroup$ @GarethMcCaughan The code above takes less than one second to execute $\endgroup$
    – Dr. belisarius
    Feb 11, 2015 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, 2015 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, 2015 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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