登入選單

返回Google圖書搜尋

Box Method for Linear Programming: Part I-basic Theory

Stanford University. Systems Optimization LaboratoryKarel ZikanRichard W. Cottle

出版	Stanford University, Department of Operations Research, Systems Optimization Laboratory, 1987
URL	http://books.google.com.hk/books?id=6dwEAAAAIAAJ&hl=&source=gbs_api

註釋

This paper presents a new interior-point algorithm for linear programming where the constraints are all expressed as inequalities. Along with the concept of minimum-weight basis, the algorithm features a novel mechanism for finding search directions. Unlike other interior-point methods which implicity or explicitly involve optimization over ellipsoids for their direction-finding schemes, the one reported here uses boxes. The corresponding subproblems are simple linear programs having closed form solutions. It is shown that the iterates generated by the algorithm converge to an extreme point of the feasible region. When this point is nondegenerate, it is optimal and reached within finitely any steps. The methodology introduced here also gives rise to a polyhedral subdivision of the problem's feasible region and in fact to the entire space of decision variables.