IAI Colloquia Series: Andre Tits, "Constraint Reduction for Linear and Convex Optimization"
Wednesday, May 4, 2016
1146 AV Williams Building
Intelligent Automation, Inc. Colloquia Series
Constraint Reduction for Linear and Convex Optimization, with Applications
Professor André Tits
Electrical and Computer Engineering Department
Institute for Systems Research
In the context of interior-point methods for numerical optimization, constraint reduction is a technique targeted at problems in which only a small portion of the given set of inequality constraints are active at the solution. (This include includes “unbalanced” linear optimization problems which, in standard dual form, have many more inequality constraints than variables.) When constraint reduction is used for the solution of such problems, the search direction computation involves only a wisely chosen small subset (updated at each iteration) of the set of inequality constraints, leading to major computational savings. The talk focuses on “unbalanced” linear, and convex quadratic, optimization problems. We provide some background, outline schemes, discuss convergence properties, and report numerical results, both on randomly generated problems and on problems arising in specific applications, including digital filter design for GPS applications and approximate solution of linear kinetic transport equations.