First-order affine scaling continuous method for convex quadratic programming

  • Hongwei Yue

Student thesis: Doctoral Thesis

Abstract

We develop several continuous method models for convex quadratic programming (CQP) problems with di.erent types of constraints. The essence of the continuous method is to construct one ordinary di.erential equation (ODE) system such that its limiting equilibrium point corresponds to an optimal solution of the underlying optimization problem. All our continuous method models share the main feature of the interior point methods, i.e., starting from any interior point, all the solution trajectories remain in the interior of the feasible regions. First, we present an a.ne scaling continuous method model for nonnegativity constrained CQP. Under the boundedness assumption of the optimal set, a thorough study on the properties of the ordinary di.erential equation is provided, strong conĀ­vergence of the continuous trajectory of the ODE system is proved. Following the features of this ODE system, a new ODE system for solving box constrained CQP is also presented. Without projection, the whole trajectory will stay inside the box region, and it will converge to an optimal solution. Preliminary simulation results illustrate that our continuous method models are very encouraging in obtaining the optimal solutions of the underlying optimization problems. For CQP in the standard form, the convergence of the iterative .rst-order a.ne scaling algorithm is still open. Under boundedness assumption of the optimal set and nondegeneracy assumption of the constrained region, we discuss the properties of the ODE system induced by the .rst-order a.ne scaling direction. The strong convergence of the continuous trajectory of the ODE system is also proved. Finally, a simple iterative scheme induced from our ODE is presented for findĀ­ing an optimal solution of nonnegativity constrained CQP. The numerical results illustrate the good performance of our continuous method model with this iterative scheme. Keywords: ODE; Continuous method; Quadratic programming; Interior point method; A.ne scaling.
Date of Award24 Jan 2014
Original languageEnglish
SupervisorLizhi LIAO (Supervisor)

User-Defined Keywords

  • Interior-point methods
  • Programming (Mathematics)
  • Quadratic programming

Cite this

'