Convex simplex method

From Glossary

Jump to: navigation, search

This extends the general strategy of the simplex method in linear programming to maximize a concave objective over linear constraints of the form LaTeX: Ax=b and LaTeX: x \ge 0. (A form of local convergence applies when the objective is not concave, but is smooth.) A tableau is maintained, but nonbasic variables need not be at zero level. The partition is used to compute a generalized reduced cost of the form LaTeX: d(x) = \nabla f(x) - y^T A. The LaTeX: y vector is determined by the basic portion: LaTeX: 0 = \nabla_B f(x) - y^TB (so LaTeX: y = (\nabla_B f(x))B^{-1}).

As in the simplex method, pricing is used to determine whether there is an improving nonbasic vector. If not, the algorithm terminates (satisfying the Kuhn-Tucker conditions); otherwise, a line search is used to determine the new point, changing only the basic variables to compensate for the change in the one nonbasic level. If this causes a basic variable to reach zero, the basis is changed with the pivot operation.

Personal tools