Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied

Tibor Illes, Adrienn Nagy

Research output: Book/ReportOther report

Abstract

This paper considers the primal simplex method for linearly constrained convex quadratic programming problems. Finiteness of the algorithm is proven when s-monotone index selection rules are applied. The proof is rather general: it shows that any index selection rule that only relies on the sign structure of the reduced costs / transformed right hand side vector and for which the traditional primal simplex method is finite is necessarily finite as well for the primal simplex method for linearly constrained convex quadratic programming problems.
LanguageEnglish
Number of pages26
Volume2014
Publication statusPublished - 20 May 2014

Publication series

NameOperations Research Report
PublisherELTE
ISSN (Print)1215-5918

Fingerprint

Simplex method
Quadratic programming
Costs

Keywords

  • quadratic programming
  • finiteness of algorithms
  • algorithms
  • primal simplex method

Cite this

Illes, Tibor ; Nagy , Adrienn. / Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied. 2014. 26 p. (Operations Research Report).
@book{167e3c76582a47da9857c8dd1da41afc,
title = "Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied",
abstract = "This paper considers the primal simplex method for linearly constrained convex quadratic programming problems. Finiteness of the algorithm is proven when s-monotone index selection rules are applied. The proof is rather general: it shows that any index selection rule that only relies on the sign structure of the reduced costs / transformed right hand side vector and for which the traditional primal simplex method is finite is necessarily finite as well for the primal simplex method for linearly constrained convex quadratic programming problems.",
keywords = "quadratic programming, finiteness of algorithms, algorithms, primal simplex method",
author = "Tibor Illes and Adrienn Nagy",
year = "2014",
month = "5",
day = "20",
language = "English",
volume = "2014",
series = "Operations Research Report",
publisher = "ELTE",

}

Illes, T & Nagy , A 2014, Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied. Operations Research Report, vol. 2014.

Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied. / Illes, Tibor; Nagy , Adrienn.

2014. 26 p. (Operations Research Report).

Research output: Book/ReportOther report

TY - BOOK

T1 - Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied

AU - Illes, Tibor

AU - Nagy , Adrienn

PY - 2014/5/20

Y1 - 2014/5/20

N2 - This paper considers the primal simplex method for linearly constrained convex quadratic programming problems. Finiteness of the algorithm is proven when s-monotone index selection rules are applied. The proof is rather general: it shows that any index selection rule that only relies on the sign structure of the reduced costs / transformed right hand side vector and for which the traditional primal simplex method is finite is necessarily finite as well for the primal simplex method for linearly constrained convex quadratic programming problems.

AB - This paper considers the primal simplex method for linearly constrained convex quadratic programming problems. Finiteness of the algorithm is proven when s-monotone index selection rules are applied. The proof is rather general: it shows that any index selection rule that only relies on the sign structure of the reduced costs / transformed right hand side vector and for which the traditional primal simplex method is finite is necessarily finite as well for the primal simplex method for linearly constrained convex quadratic programming problems.

KW - quadratic programming

KW - finiteness of algorithms

KW - algorithms

KW - primal simplex method

UR - http://www.cs.elte.hu/opres/orr/

UR - http://www.cs.elte.hu/opres/orr/download/ORR14_01.pdf

M3 - Other report

VL - 2014

T3 - Operations Research Report

BT - Finiteness of the quadratic primal simplex method when s-monotone index selection rules are applied

ER -