Interior point schemes for mixed-binary quadratic programs: Computational investigations and applications to unit commitment problems

Open Access
Wan, Wendian
Graduate Program:
Industrial Engineering
Master of Science
Document Type:
Master Thesis
Date of Defense:
Committee Members:
  • Vinayak V Shanbhag, Thesis Advisor
  • Interior point method
  • quadratic programming
  • mixed integer programming
We consider a class of mixed-binary quadratic programs, a subclass of mixed-integer quadratic programs. When the continuous relaxation of such problems is convex, then a host of algorithms exist for the resolution of such problems, including a range of branching schemes as well as outer-approximation techniques. We consider an alternate approach that relies on a smoothing-based interior-point approach and does not utilize any convexity properties of the relaxation. Our approach relies on the equivalence between the original discrete optimization and a continuous variant in which the binary restrictions are replaced by a suitably defined penalty function. Inspired by work by Murray and Ng [1], we develop an interior-point scheme that uses an augmented Lagrangian merit function for purposes of globalization. Furthermore, we present a distinct scheme for updating the penalty parameter associated with the integrality residual that relies on either a fixed penalty or an increasing penalty parameter. Preliminary numerical results on a class of mixed-binary quadratic programs from a class of unit commitment problems with quadratic costs appear to be promising. In particular, it is observed that the scheme obtains global or near-global solutions when the Hessians of the quadratic function are positive semidefinite.