Econometrica: Jul 1967, Volume 35, Issue 3

Error Produced by Linearization in Mathematical Programming

https://doi.org/0012-9682(196707/10)35:3/4<447:EPBLIM>2.0.CO;2-N
p. 447-471

R. C. Bushnell, W. J. Baumol

This paper offers a qualitative theoretical analysis of the error that may arise when a linear programming calculation is used to solve a problem involving some degree of nonlinearity. Six propositions are developed: (1) a linear approximation to a nonlinear program will not necessarily yield the true maximum; (2) it need not provide an answer better than a randomly chosen initial solution; (3) it may not even provide the best possible corner solution; (4) a reduction in the curvature of the profit surface does not always guarantee improvement in the accuracy of a linear approximation; (5) proximity of the initial point to the maximum need not increase the accuracy of the linear approximation; and (6) only if the objective function is monotone throughout can we be assured that a linear approximation will yield results which represent an improvement over the initial point. The paper also describes sampling experiments in which the correct solution of a quadratic programming problem subject to linear constraints was compared with the solution of a linear programming problem obtained by replacing the quadratic maximand by its tangent hyperplane at the initial point and by other linear approximations. In general, the linear programming calculations did not yield results very close to the true maximum nor did the approximation improve substantially as the curvature of the objective function was reduced.

Log In To View Full Content

Back