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|
|Sponsors: ||Digital Repository at the University of Maryland|
University of Maryland (College Park, Md.)
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:||UMD Theses and Dissertations|
Electrical & Computer Engineering Theses and Dissertations
All items in DRUM are protected by copyright, with all rights reserved.