TITLE

On degeneracy in linear programming and related problems

AUTHOR(S)
George, Karen; Osborae, M. R.
PUB. DATE
December 1993
SOURCE
Annals of Operations Research;1993, Vol. 46/47 Issue 1-4, p343
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are reported. These are obtained using a careful implementation of the projected gradient algorithm [11]. These are compared with results obtained using a steepest descent approach which can be implemented by means of a closely related projected gradient method, and which is not affected by degeneracy in principle. However, the problem of correctly identifying degenerate active sets occurs with both algorithms. The numerical results favour the more standard projected gradient procedure which resolves the degeneracy explicitly. Extension of both methods to general polyhedral convex function minimization problems is sketched.
ACCESSION #
18643382

 

Related Articles

  • On the E-Epigraph of an E-Convex Function. DUCA, D. I.; LUPŞA, L. // Journal of Optimization Theory & Applications;May2006, Vol. 129 Issue 2, p341 

    In Ref 1, Yang shows that some of the results obtained in Ref. 2 on E-convex programming are incorrect, but does not prove that the results which make the connection between an E-convex function and its E-epigraph are incorrect. In this note, we show that the results obtained in Ref. 2...

  • Disjunctive programming and relaxations of polyhedra. Conforti, Michele; Del Pia, Alberto // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p307 

    Given a polyhedron $$L$$ with $$h$$ facets, whose interior contains no integral points, and a polyhedron $$P$$, recent work in integer programming has focused on characterizing the convex hull of $$P$$ minus the interior of $$L$$. We show that to obtain such a characterization it suffices to...

  • ON NONLINEAR FRACTIONAL PROGRAMMING. Dinkelbach, Werner // Management Science;Mar67, Vol. 13 Issue 7, p492 

    The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric...

  • A SUPERLINEARLY CONVERGENT ALGORITHM FOR ONE-DIMENSIONAL CONSTRAINED MINIMIZATION PROBLEMS WITH CONVEX FUNCTIONS. Mifflin, Robert // Mathematics of Operations Research;May83, Vol. 8 Issue 2, p185 

    This paper presents a globally and superlinearly convergent algorithm for solving one-dimensional constrained minimization problems involving (not necessarily smooth) convex functions. The constraint is handled by what can be interpreted as a new type of penalty method. The algorithm does not...

  • A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem. Le Thi, Hoai; Moeini, Mahdi; Pham Dinh, Tao; Judice, Joaquim // Computational Optimization & Applications;Apr2012, Vol. 51 Issue 3, p1097 

    In this paper, we investigate a DC (Difference of Convex functions) programming technique for solving large scale Eigenvalue Complementarity Problems (EiCP) with real symmetric matrices. Three equivalent formulations of EiCP are considered. We first reformulate them as DC programs and then use...

  • A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527 

    In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

  • DCA based algorithms for multiple sequence alignment (MSA). Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay // Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501 

    In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the...

  • A regularized simplex method. Fábián, Csaba; Eretnek, Krisztián; Papp, Olga // Central European Journal of Operations Research;Dec2015, Vol. 23 Issue 4, p877 

    In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a polyhedral convex objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized...

  • GENERALIZED LINEAR MULTIPLICATIVE AND FRACTIONAL PROGRAMMING. Konno, Hiroshi; Kuno, Takahito // Annals of Operations Research;1990, Vol. 25 Issue 1-4, p147 

    This paper addresses itself to the algorithm for minimizing the sum of a convex function and a product of two linear functions over a polytope. It is shown that this nonconvex minimization problem can be solved by solving a sequence of convex programming problems. The basic idea of this...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics