Digital Repository at the University of Maryland (DRUM)  >
Theses and Dissertations from UMD  >
UMD Theses and Dissertations 

Please use this identifier to cite or link to this item:

Title: Infeasible Constraint Reduction for Linear and Convex Quadratic Optimization
Authors: He, Meiyun
Advisors: Tits, Andre L
Department/Program: Electrical Engineering
Type: Dissertation
Sponsors: Digital Repository at the University of Maryland
University of Maryland (College Park, Md.)
Subjects: Electrical engineering
Keywords: Constraint Reduction
Convex Quadratic Optimization
Infeasible Initial Points
Interior Point Methods
Linear Optimization
Model Predictive Control
Issue Date: 2011
Abstract: Constraint-reduction schemes have been proposed in interior-point methods for linear and convex quadratic programs with many more inequality constraints than variables in standard dual form. Such schemes have been shown to be provably convergent and highly efficient in practice. A critical requirement of these schemes, however, is the availability of a dual-feasible initial point. The thesis first addresses this requirement for linear optimization. Building on a general framework (which encompasses several previously proposed approaches) for dual-feasible constraint-reduced interior-point optimization, for which we prove convergence to a single point of the sequence of dual iterates, we propose a framework for ``infeasible'' constraint-reduced interior-point. Central to this framework is an exact ($ell_1$ or $ell_infty$) penalty function scheme endowed with a scheme for iterative adjustment of the penalty parameter aiming to yield, after a finite number of updates, a value that guarantees feasibility (for the original problem) of the minimizers. Finiteness of the sequence of penalty parameter adjustments is proved under mild feasibility assumptions for all algorithms that fit within the framework, including ``infeasible'' extensions of a ``dual'' algorithm proposed in the early 1990s and of two recently recently proposed ``primal-dual'' algorithms. One of the latter two, a constraint-reduced variant of Mehrotra's Predictor Corrector algorithm is then more specifically considered. Further convergence results are proved for the corresponding infeasible method. Furthermore, this infeasible method is analyzed without feasibility assumptions. Next, the constraint-reduced scheme with arbitrary initial points is extended for the more general case of convex quadratic optimization. A stronger global convergence result is proven that generalizes the result in the linear case. Numerical results are reported that demonstrate that the infeasible constraint-reduced algorithms are of practical interest. In particular, in the application of model-predictive-control-based rotorcraft control, our algorithms yield a speed-up of over two times for both altitude control and trajectory following.
Appears in Collections:Electrical & Computer Engineering Theses and Dissertations
UMD Theses and Dissertations

Files in This Item:

File Description SizeFormatNo. of Downloads
He_umd_0117E_12896.pdf1.03 MBAdobe PDF180View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments