Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems |
| |
Authors: | Arkadii Nemirovskii Katya Scheinberg |
| |
Institution: | (1) Faculty of Industrial Engineering and Management, The Israel Institute of Technology, 32000 Haifa, Israel;(2) Department of Industrial Engineering and Operations Research, Columbia University, 331 Mudd Building, 10027 New York, NY, USA |
| |
Abstract: | Convex quadratically constrained quadratic problems are considered. It is shown that such problems can be transformed to aconic form. The feasible set of the conic form is the intersection of a direct product of standard quadratic cones intersected with
a hyperplane (the analogue of a simplex), and a linear subspace. For a problem of such form, the analogue of Karmarkar's projective
transformation and logarithmic barrier function are built. This allows us to extend “word by word” the method of Karmarkar
for LP to QCQP and allows us to obtain a similar polynomial worst-case bound for the number of iterations. |
| |
Keywords: | Convex quadratically constrained quadratic problem Karmarkar's algorithm Potential function Projective transformation Conic form Interior point method |
本文献已被 SpringerLink 等数据库收录! |