Optimization Online


A regularized simplex method

Csaba I. Fabian (fabian.csaba***at***gamf.kefo.hu)
Krisztian Eretnek (eretnek.krisztian***at***gmail.com)
Olga Papp (papp.olga***at***gamf.kefo.hu)

Abstract: In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a certain convex polyhedral objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized simplex method. (Regularization is performed in the dual space and only affects the process through the pricing mechanism. Hence the resulting method moves among basic solutions.) We present favorable test results with this regularised simplex method. For general linear programming problems, we propose a Newton-type approach which requires the solution of a sequence of special problems.

Keywords: Linear programming, convex programming ; simplex method, cutting-plane methods, regularization

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 02/28/2012
Entry Accepted: 02/28/2012
Entry Last Modified: 02/25/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society