The Generalized Slack Variable Linear Program

The dilemma of when to cease analysis of a subproblem and go on to the next subproblem in convex programming is an especially difficult one. This paper views convex programming as an extension of linear programming and focuses attention on the analysis of a given subproblem. Specifically, if K = {x∣Ax ≤ b} is bounded with a nonempty interior and represents a residual unsearched region in some convex programming algorithm, what is (are) the “best” trial point(s) which can be selected? The generalized slack variable linear program (GSVLP) provides a mechanism for implementing trial point selection based on many strategies. Several implications of the L₂ norm are revealed which are especially important in constraint deletion and rate of reduction of the hypervolume of the residual search region K.