Thesis Examination Committee
Prof Mordecai Jay GOLIN, CSE/HKUST (Chairperson)
Prof Daniel PALOMAR, ECE/HKUST (Thesis Supervisor)
Prof Chee Wei TAN, College of Science and Engineering, City University of Hong Kong (External Examiner)
Prof Wai Ho MOW, ECE/HKUST
Prof Roger CHENG, ECE/HKUST
Prof Jiheng ZHANG, IEDA/HKUST
The design of optimization algorithms plays a fundamental role in various applications. In this dissertation, we will put forward several efficient optimization algorithms based on two existing general algorithmic frameworks, namely, Majorization-Minimization (MM) and Alternating Direction Method of Multipliers (ADMM).
We first consider the problem of graph Laplacian estimation. We estimate the weights of a graphical model under a given connectivity topology. We apply the well-known ADMM and MM frameworks and propose two algorithms, namely, GLE-ADMM and GLE-MM. Both algorithms can achieve a small optimality gap, around three orders of magnitude more accurate than the benchmark. In addition, we find that GLE-ADMM is more computationally efficient in a dense topology while GLE-MM is more suitable for sparse graphs. Furthermore, we consider exploiting the leading eigenvectors of the sample covariance matrix as a nominal eigensubspace for the small-sample scenario and propose a third algorithm named GLENE, which is also based on ADMM. The optimality gap with respect to the CVX toolbox is small as well.
Next we study the problem of option portfolio design under the Markowitz mean-variance framework. The option returns are modeled statistically with first- and second-order moments, enriching the conventional delta-gamma approximation. The naive mean-variance formulation allows for the zero-risk fallacy, which can be circumvented with a more realistic robust formulation. Transaction cost is also considered in the robust formulation for a proper practical design. In order to efficiently solve the portfolio design problem, we borrow the framework of BSUM-M, which is a combination of ADMM and MM. The proposed algorithm can perform as well as the off-the-shelf solvers but with a much shorter computational time.