On the Complexity of a Column Generation Algorithm for Convex or Quasiconvex Feasibility Problems

Jean-Louis Goffin, Zhi-Quan Luo and Yinyu Ye
Additional contact information
Jean-Louis Goffin: McGill University, Faculty of Management
Zhi-Quan Luo: McMaster University, Department of Electrical and Computer Engineering
Yinyu Ye: The University of Iowa, Department of Management Sciences

A chapter in Large Scale Optimization, 1994, pp 182-191 from Springer

Abstract: Abstract We analyze the convergence and the complexity of a potential reduction column generation algorithm for solving general convex or quasiconvex feasibility problems defined by a separation oracle. The oracle is called at the analytic center of the set given by the intersection of the linear inequalities which are the previous answers of the oracle. We show that the algorithm converges in finite time and is in fact a fully polynomial approximation algorithm, provided that the feasible region has an nonempty interior. This result is based on the works of Ye [22] and Nesterov [16].

Keywords: Convex feasibility problem; potential reduction; column generation; cutting planes (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3632-7_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461336327

DOI: 10.1007/978-1-4613-3632-7_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().