Parametric simplex algorithms for solving a special class of nonconvex minimization problems |
| |
Authors: | Hiroshi Konno Yasutoshi Yajima Tomomi Matsui |
| |
Affiliation: | (1) Institute of Human and Social Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguru-ku, 152 Tokyo, Japan;(2) Department of Industrial Engineering and Management, Tokyo Institute of Technology, Tokyo, Japan;(3) Department of System Sciences, Tokyo Institute of Technology, Tokyo, Japan |
| |
Abstract: | It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems. |
| |
Keywords: | Parametric simplex algorithm minimization of products linear multiplicative programming |
本文献已被 SpringerLink 等数据库收录! |
|