Integrability of vector and multivector fields associated with interior point methods for linear programming |
| |
Authors: | Masao Iri |
| |
Institution: | (1) Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, 113 Tokyo, Japan |
| |
Abstract: | In the feasible region of a linear programming problem, a number of desirably good directions have been defined in connexion with various interior point methods. Each of them determines a contravariant vector field in the region whose only stable critical point is the optimum point. Some interior point methods incorporate a two- or higher-dimensional search, which naturally leads us to the introduction of the corresponding contravariant multivector field. We investigate the integrability of those multivector fields, i.e., whether a contravariantp-vector field isX
p
-forming, is enveloped by a family ofX
q
's (q > p) or envelops a family ofX
q
's (q < p) (in J.A. Schouten's terminology), whereX
q
is aq-dimensional manifold.Immediate consequences of known facts are: (1) The directions hitherto proposed areX
1-forming with the optimum point of the linear programming problem as the stable accumulation point, and (2) there is anX
2-forming contravariant bivector field for which the center path is the critical submanifold. Most of the meaningfulp-vector fields withp 3 are notX
p
-forming in general, though they envelop that bivector field. This observation will add another circumstantial evidence that the bivector field has a kind of invariant significance in the geometry of interior point methods for linear programming.For a kind of appendix, it is noted that, if we have several objectives, i.e., in the case of multiobjective linear programs, extension to higher dimensions is easily obtained. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|