Symmetric indefinite systems for interior point methods

作     者：Vanderbei, Robert J. Carpenter, Tamra J. 

作者机构：Program in Statistics and Operations Research Princeton University Princeton 08544 NJ United States 

出 版 物：《Mathematical Programming》 (Math. Program.)

年 卷 期：1993年第58卷第1-3期

页      面：1-32页

学科分类：07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Interior point method linear programming quadratic programming 

摘      要：We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is {Mathematical expression} instead of reducing to obtain the usual AD2AT system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product AD2AT when A has dense columns;and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that D be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense. © 1993 The Mathematical Programming Society, Inc.