CUHK electronic theses & dissertations collection

Although cardinality constraints naturally arise in many applications, e.g., in portfolio selection problems of choosing small number of assets from a large pool of stocks or dynamic portfolio selection problems with limited trading dates within a given time horizon and in subset selection of the regression analysis, the state-of-the-art in cardinality constrained optimization has been stagnant up to this stage, largely due to the inherent combinatorial nature of such hard problems. We focus in this research on developing efficient and implementable solution algorithms for cardinality constrained optimization by investigating prominent structures and hidden properties of such problems. More specifically, we develop solution algorithms for four specific cardinality constrained optimization problems, including (i) the cardinality constrained linear-quadratic control problem, (ii) the optimal control problem of linear switched system with limited number of switching, (iii) the time cardinality constrained dynamic mean- variance portfolio selection problem, and (iv) cardinality constrained quadratic optimization problem. Taking advantages of a linear-quadratic structure of cardinality constrained optimization problems, we strive for analytical solutions when possible. More specifically, we derive an analytical solution for problem (iii) and obtain for both problems (i) and (ii) semi-analytical expressions of the solution governed by a family of Ricatti-like equations, which still suffer an exponentially growing complexity. To achieve high-performance of the solution algorithm, we devise algorithms of a branch and bound (BnB) type with various tight and computationally-cheap lower bounds achieved by identifying suitable SDP formulations and by exploiting geometric properties of the problem. We demonstrate efficiency of our proposed solution schemes evidenced from numerical experiments and present a firm step-forward in tackling this long-standing challenge of cardinality constrained optimization.Gao, Jianjun.Adviser: Duan Li.Source: Dissertation Abstracts International, Volume: 72-11, Section: B, page: .Thesis (Ph.D.)--Chinese University of Hong Kong, 2009.Includes bibliographical references (leaves 134-142).Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Abstract also in Chinese