Bib Salilahi, On the Central Path of Redundant Klee-Minty Problems

VSSD: Science and Technology

b

On the Central Path of Redundant Klee-Minty Problems

Bib Salilahi

2011 / xviii + 106 pp. / paperback / thesis / ISBN 978-90-6562-273-0

The central path is a smooth curve in the interior of the domain of a Linear Optimization (LO) problem. It leads to the set of optimal solutions of the problem. Ideally the curve goes more or less straightforward to the optimal set, but in practice the curve may posses sharp turns. We may consider the number of sharp turns in the central path as a lower bound for the number of iterations of any path-following Interior Point Method (IPM). Deza et al. showed that when adding many suitably chosen redundant constraints to the Klee-Minty (KM) problem then one may force the central path to visit small neighborhoods of all the vertices of the KM cube, just as the simplex method visits all the vertices of the KM cube in the famous example of Klee and Minty. Deza et al. proved that this gives rise to a lower bound for the maximal number of iterations of any IPM. In this way they found ½( n/ln n) as such a lower bound, where n is the number of inequalities in the LO problem; currently this is the best lower bound for the maximal number of iterations of an IPM.

The contribution of this thesis is twofold. First, we present a computational model to minimize the number of redundant constraints for getting a central path that visits small neighborhoods of a given set of vertices of the KM cube. Second, we consider a new set of redundant constraints and show that by using this type of redundant constraints, the central path may visit at least half of the vertices of the KM cube. Although in our case the central path does not visit all the vertices of the KM cube, it gives rise to the same lower bound as mentioned above.

PDF files:

repository TU Delft

a00

English language textbooks

Homepage

Updated: 23 May 2011, hlf@vssd.nl

VSSD: Science and Technology	b
On the Central Path of Redundant Klee-Minty Problems Bib Salilahi 2011 / xviii + 106 pp. / paperback / thesis / ISBN 978-90-6562-273-0
The central path is a smooth curve in the interior of the domain of a Linear Optimization (LO) problem. It leads to the set of optimal solutions of the problem. Ideally the curve goes more or less straightforward to the optimal set, but in practice the curve may posses sharp turns. We may consider the number of sharp turns in the central path as a lower bound for the number of iterations of any path-following Interior Point Method (IPM). Deza et al. showed that when adding many suitably chosen redundant constraints to the Klee-Minty (KM) problem then one may force the central path to visit small neighborhoods of all the vertices of the KM cube, just as the simplex method visits all the vertices of the KM cube in the famous example of Klee and Minty. Deza et al. proved that this gives rise to a lower bound for the maximal number of iterations of any IPM. In this way they found ½( n/ln n) as such a lower bound, where n is the number of inequalities in the LO problem; currently this is the best lower bound for the maximal number of iterations of an IPM. The contribution of this thesis is twofold. First, we present a computational model to minimize the number of redundant constraints for getting a central path that visits small neighborhoods of a given set of vertices of the KM cube. Second, we consider a new set of redundant constraints and show that by using this type of redundant constraints, the central path may visit at least half of the vertices of the KM cube. Although in our case the central path does not visit all the vertices of the KM cube, it gives rise to the same lower bound as mentioned above.	PDF files: repository TU Delft
a00
English language textbooks Homepage	Updated: 23 May 2011, hlf@vssd.nl