A KKT Simplex Method for Efficiently Solving Linear Programs for Grasp Analysis Based on the Identification of Nonbinding Constraints

Abstract

A one-phase efficient method to solve linear programming (LP) problems for grasp analysis of robotic hands is proposed. Our method, named as KKT Simplex method, processes free variables directly while choosing the entering and leaving variables, which makes it a one-phase method able to start at any point of the set of feasible solutions. Besides, the proposed method lowers the number of simplex steps by an angular pricing strategy to choose the entering variable. Moreover, the method reduces the size of an LP problem by the identification of nonbinding constraints that preserves the Karush-Kuhn-Tucker (KKT) cone. We developed the KKT Simplex method by incorporating to the well-known revised simplex method the following components: a method to process free variables, a pricing strategy, and an identification method. We solve LP problems of grasp analysis to test the efficiency and the one-phase nature of the proposed method.