Final Scientific/Technical Report

O'Leary, Dianne P ; Tits, Andre

关键词: linear optimization;    quadratic optimization;    semi-definite programming;    second-order cone programming;    constraint reduction;    Euclidean distance matrix completion;   

DOI  :  10.2172/1091797
RP-ID  :  DOE/ER/25942-f
PID  :  OSTI ID: 1091797
Others  :  Other: ER25942

学科分类：数学（综合）

美国|英语

来源: SciTech Connect

【 摘 要 】

In this work, we have built upon our results from previous DOE funding (DEFG 0204ER25655), where we developed new and more efficient methods for solving certain optimization problems with many inequality constraints. This past work resulted in efficient algorithms (and analysis of their convergence) for linear programming, convex quadratic programming, and the training of support vector machines. The algorithms are based on using constraint reduction in interior point methods: at each iteration we consider only a smaller subset of the inequality constraints, focusing on the constraints that are close enough to be relevant. Surprisingly, we have been able to show theoretically that such algorithms are globally convergent and to demonstrate experimentally that they are much more efficient than standard interior point methods.