Infeasible interior-point methods for linear optimization based on large neighborhood

Journal article (2015)

Authors

Asadi Asadi Algorithmics - EEMCS
Roos Roos Discrete Mathematics and Optimization - EEMCS
Research Group
Algorithmics (EEMCS) (TU Delft)
Linear optimization Oolynomial algorithms Primal-dual infeasble interior-point methods
More Info
expand_more

Published Date

2015

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Algorithmics

Abstract

In this paper, we design a class of infeasible interior-point methods for linear optimization based on large neighborhood. The algorithm is inspired by a full-Newton step infeasible algorithm with a linear convergence rate in problem dimension that was recently proposed by the second author. Unfortunately, despite its good numerical behavior, the theoretical convergence rate of our algorithm is worse up to square root of problem dimension.