Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 0725.90063
Ye, Yinyu
An $O(n\sp 3L)$ potential reduction algorithm for linear programming. (English)
[A] Mathematical developments arising from linear programming, Proc. AMS-IMS- SIAM Jt. Summer Res. Conf., Brunswick/ME (USA) 1988, Contemp. Math. 114, 91-107 (1990).

Summary: [For the entire collection see Zbl 0722.00047.] \par We describe a primal-dual potential function for linear programming $$ \phi (x,s)=\rho \ln (x\sp Ts)-\sum\sp{n}\sb{j=1}\ln (x\sb js\sb j), $$ where $\rho\ge n$, x is the primal variable and s is the dual-slack variable in the standard linear programming form. As a result, we develop an interior algorithm seeking reductions in the potential function with $\rho =n+\sqrt{n}$. The algorithm neither traces the central path nor uses projective transformations. It converges to the optimal solution set in O($\sqrt{n}L)$ iterations and uses $O(n\sp 3L)$ arithmetic operations.

MSC 2000:: *90C05 Linear programming
90C60 Abstract computational complexity for math. programming problems
65K05 Mathematical programming (numerical methods)
90-08 Computational methods (optimization)

Keywords: primal-dual potential function; interior algorithm

Citations: Zbl 0722.00047

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]