Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0856.90088
Goffin, Jean-Louis; Luo, Zhi-Quan; Ye, Yinyu
Complexity analysis of an interior cutting plane method for convex feasibility problems. (English)
[J] SIAM J. Optim. 6, No.3, 638-652 (1996). ISSN 1052-6234; ISSN 1095-7189/e

Summary: We further analyze the convergence and the complexity of a dual column generation algorithm for solving general convex feasibility problems defined by a separation oracle. The oracle is called at an approximate 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 a nonempty interior.

MSC 2000:: *90C25 Convex programming
90C60 Abstract computational complexity for math. programming problems
90C26 Nonconvex programming

Keywords: potential reduction; cutting planes; convergence; complexity; dual column generation algorithm; convex feasibility problems; separation oracle; fully polynomial approximation algorithm

Cited in: Zbl 1198.90320 Zbl 0948.90149

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]