AN IMPLEMENTATION OF AN INTERIOR POINT METHOD FOR EXTENDED LINEAR-QUADRATIC PROGRAMMING

Abstract

Extended linear-quadratic programming (ELQP for short), as a new model for decision under uncertainty and multistage optimization, is first brought up in a series of pioneer papers by Rockafellar and Wets [8, 9, 10, 11, 12, 13]. It can very well describe practical problems involving objectives generated by decisions in random scenarios, penalty representations of constraints, and large-scale optimal control systems. Certainly, the increasing importance of this model is calling for the development of highly efficient algorithms. Since the seminal paper of Karmarkar [1] in 1984, the last decade has witnessed a tremendous development in interior point methods for mathematical programs. Various interior point methods have been successfully implemented in many areas including linear programming, convex quadratic programming, linear complementarity problem and convex programming. Given such vast areas of application, it is only natural to ask whether the range can be extended to ELQP. In 1993, Sun and Zhu [14] developed a predictor-corrector method, one of the emerging interior point approaches for ELQP. The algorithm of Sun and Zhu has some nice theoretical properties such as polynomiality in computing time. However, as it is well known in optimization that an algorithm efficient in theory might not work "efficiently" in practice, doubts might be raised on the actual performance of the proposed algorithm in the above paper. In this thesis, we will explore the practicality and the sensitivity of the algorithm. Indeed, as shown in the thesis, some modifications have to be made in order for the algorithm to effectively solve ELQP problems. The thesis is organized as follows. In chapter 1, we introduce the problems of ELQP, showing how it is motivated. We also list some of the properties of ELQP. A review on the progress of ELQP so far, and the contribution of this thesis are also included in this chapter. In chapter 2, we present the algorithm of the predictor-corrector method together with the theory behind it, and discuss the complexity and some features of the algorithm. In chapter 3, we show the test results, describing their significance and modifying the algorithm accordingly. The final version of the algorithm is presented too. The last chapter is a summary of the thesis with some conclusions drawn. The future possible research area of the method is briefly discussed too.