Why can not we use Lagrange multiplier in mathematical (in particular linear) programming?

Question

I am studying linear programming right now. And I can not explain to myself why I can not solve any linear programming task using the Lagrange multiplier method.

Could you help me understand that, please?

Answer 1

The basic method of Lagrange multipliers only works for maximizing over a set given by a system of equations. Any interesting linear program, on the other hand, will contain some inequalities, even if it's only the domain constraints of the form $x \ge 0$.

In a multivariable calculus class, you might learn to use Lagrange polynomials to deal with inequalities by doing casework: to deal with an inequality $ax \le b$, you can either set $ax=b$, or ignore the inequality and later check if it's satisfied. This corresponds to the "brute force" approach to linear programming, where we check all possible intersections of the inequalities and find which vertex is optimal.

You may have also seen the Karush-Kuhn-Tucker method, which generalizes the method of Lagrange multipliers to deal with inequalities. It can indeed be used to solve linear programs: it corresponds to using the dual linear program and complementary slackness to find a solution.

The special case of linear programming, however, is much nicer than the general case of the KKT method for solving nonlinear programs. It is better to first learn linear programming, and then see what features of the method do and do not extend to nonlinear programming.

Answer 2

I cannot give a complete answer, but I believe the accepted answer is not accurate.

Inequalities are not the issue - linear programs with inequalities are converted to equalities using slack and surplus variables.

I believe the issue is because we cannot enforce decision variables to be positive, using Lagrange. The principle advancement made by the Simplex method was to ensure positive values for decision variables, which is imperative for the algorithm to produce meaningful results.

Without enforcing positivity, one variable can shoot way positive and another variable can shoot way negative. As an example, given this:

x + y = 1;

we want something like 0.3 and 0.7, but with a smooth system we could get (-139393 + 139394), or literally any combination.

You might think, well we could solve this with slack variables:

x >= 0; y >= 0;

which translates to:

x - s1 = 0;
y - s2 = 0;

but then we are back to square one, because we need to enforce s1 and s2 to be positive.

*note that in reality, by positive, we really mean non-negative, since variables can take on value of 0 in Simplex algorithms.