Final Scientific/Technical Report

[摘要] 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.

[发布日期] 2013-08-30

[学科分类] 数学（综合）

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