Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why would a nonlinear programming solver come p with a different solution than a linear programming solver if all the constraints are linear? Isn't a linear programming solver basically a "subset" of a nonlinear programming solver?

share|improve this question
1  
Well, if the function to be optimized is also linear. But, at the end, these are computer programs. Computers hate us. See "I Have No Mouth and I Must Scream" by Harlan Ellison. –  Will Jagy May 23 '12 at 19:47
    
What nonlinear solver and what linear solver are you using? What optimality criteria are used by either? –  copper.hat May 24 '12 at 3:03
    
Why would anyone use a knife to cut an apple when you can use a chainsaw which can cut anything? –  Inquest Feb 8 '13 at 21:25
add comment

2 Answers

I cannot agree with the answer of Nunoxic nor the strong words of the comment of Will Jagy, so I decided to write my own answer (the comment is too short).

I see three major possible reasons why those results differ:

  • the inputs are different,
  • there are multiple solutions,
  • because of rounding/approximation errors.

Ad 1. Those differences might be unnoticeable, i.e. maybe you use rational numbers in one input and floats in the other? Or you use some approximations like $1.333$ instead of $4/3$? Moreover, different algorithms, when arriving at their internal representations, may arrive at slightly different problems (for the same reasons). Finally, you might have made a mistake (e.g. the minimization function not being linear, etc.) ;-)

Ad 2. I think this is clear, if there are multiple solutions and you use two different algorithms. In fact this may even happen for the same algorithm, if it is randomized.

Ad 3. This is a huge problem and there is no cheap workaround. Best, if you can, use rational numbers in your linear programming, however, in general, you are doomed. All gradient descent methods and other numerical ways are more like heuristics, not exact solutions (imagine how easy it is for a program to miss a zero of a function if there is nothing around this place that points to it). It is hard to tell anything without symbolic manipulation, and this is often too difficult for computers. So it may happen that the algorithm, being just oblivious, decided that the solution it got to is good enough and that it won't help much by approximating it further. On the other hand, the linear programing optimizer, being not that oblivious as the previous algorithm, knows that it can approximate the exact solution if it runs long enough.

Hope that explains something ;-)

share|improve this answer
    
I agree with your analysis of the problem but I fail to see how this applies to Linearity/Nonlinearity of the problem. I mean, Point 2 is acceptable but I assumed there is only one. Point 1 and Point 3 happen to every numerical method. Isn't every numerical algorithm susceptible to rounding errors? Again, I don't disagree with your points, I merely wish to know where the "linear, nonlinear" discussion pictures in? –  Inquest May 23 '12 at 20:46
    
@Nunoxic Nowhere. I have no knowledge of the algorithms in use, so I can just state the obvious, that means things that apply, as you pointed out, to every numerical algorithm. Where I (barely) scratched the surface, it is the point 3, where I suspect that the solution of LP should be better, but again, I have no evidence, the problem may be too complex for "traditional" LP. Also, it should be possible for the non-linear solver to input the starting points obtained from LP and thus arrive at similar solution. I conjecture, that the point 3 is the real reason, but this is just a wild guess. –  dtldarek May 23 '12 at 21:07
add comment

Because things like these play hide and seek. You know it's linear but the computer doesn't know that until you code it explicitly to behave differently when you have different constraints and creating such a (I'll call it) decision tree will ruin the coder's life. Usually, the rule is that the programmer's time is more important than the system run time and thus, you'd probably expect that linear systems tend to take same time as nonlinear systems because the underlying mechanism for solving might be same. Same goes with answers, you'd expect different answers because although you know that the constraints are linear, unless you communicate it to the computer in some form, it is bound to assume otherwise and apply a generic algorithm.

The tradeoff between the complexity of your code and its performance is something all coders look at. A very good example of this would be MATLAB's A\b function (Basically another form of solving for x in $Ax=b$ which essentially goes about doing tens of checks to find out attributes about the matrix such as sparsity, bandedness, positive definiteness, symmetry etc. and then depending upon these results, will apply the right algorithm. The last resort is the generic Gaussian Elimination with Partial Pivoting). Here the coder(s) have stressed heavily upon performance and hence, although you'd get the same answer any which way, your question is subtly answered : Are you willing to spend those extra 1000 hours coding for "special cases" and give them shorter escape routes to the solution?

On a tangential topic (but something I thought worth mentioning) is a similar question Mathematicians have with respect to high performance computing (Super computing included). The common complaint is "Processes X and Y happen independent of each other, why can't the computer (compiler) realize this and automatically make it run on multiple cores". The answer here is the same: The coder and the compiler play hide and seek with such optimizations. Unless the coder sits and explicitly codes the math at a very low level (maybe even ASM), it's unlikely that you'll extract the largest punch from the supercomputer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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