Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 0708.90049
Kojima, Masakazu; Mizuno, Shinji; Yoshise, Akiko
A primal-dual interior point algorithm for linear programming. (English)
[A] Progress in mathematical programming. Interior-point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 29-47 (1989).

Summary: [For the entire collection see Zbl 0669.00026.] \par This chapter presents an algorithm that works simultaneously on primal and dual linear programming problems and generates a sequence of pairs of their interior feasible solutions. Along the sequence generated, the duality gap converges to zero at least linearly with a global convergence ratio (1-$\eta$ /n); each iteration reduces the duality gap by at least $\eta$ /n. Here n denotes the size of the problems and $\eta$ a positive number depending on initial interior feasible solutions of the problems. The algorithm is based on an application of the classical logarithmic barrier function method to prime and dual linear programs, which has recently been proposed and studied by {\it N. Megiddo} [ibid., 131-158 (1989; Zbl 0687.90056)].

MSC 2000:: *90C05 Linear programming
65K05 Mathematical programming (numerical methods)
90-08 Computational methods (optimization)
49N15 Duality theory (optimization)

Keywords: interior feasible solutions; duality gap; logarithmic barrier function method

Citations: Zbl 0669.00026; Zbl 0687.90056

Cited in: Zbl 1243.90246 Zbl 0913.65051 Zbl 0738.90077 Zbl 0708.90050

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

	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]