# Convex simplex method

### From Glossary

This extends the general strategy of the simplex method
in linear programming to maximize a concave objective over linear constraints
of the form and . (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 . The
vector is determined by the basic portion: (so
).

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.