  


Adaptive Constraint Reduction for Convex Quadratic Programming
Jin Jung (jjungcs.umd.edu) Abstract: We propose an adaptive, constraintreduced, primaldual interiorpoint algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational eort by assembling, instead of the exact normalequation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an anescaling variant. Numerical experiments on random problems, on a datatting problem, and on a problem in array pattern synthesis show the eectiveness of the constraint reduction in decreasing the time per iteration without signicantly aecting the number of iterations. We note that a similar constraintreduction approach can be applied to algorithms of Mehrotra's predictorcorrector type, although no convergence theory is supplied. Keywords: Convex Quadratic Programming, Constraint Reduction, Column Generation, PrimalDual InteriorPoint Method Category 1: Nonlinear Optimization (Quadratic Programming ) Citation: University of Maryland, January 2008 Download: [PDF] Entry Submitted: 01/22/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  