Constraint Reduction for Linear and Convex Optimization

Constraint reduction is a technique by which, in the context of interior-point methods for the solution of optimization problems, at each iteration, the search direction computation involves only a small subset of the inequality constraints. For problems with many more constraints than variables, this can yield a dramatic speedup. 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.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.