Miscellaneous efficient optimization algorithms : theory and applications

Abstract

The design of optimization algorithms plays a fundamental role in various applications including signal processing, machine learning, and financial engineering. In this dissertation, we focus on efficient optimization algorithm design based on some of the existing general algorithmic frameworks, e.g., Majorization-Minimization or Minorization-Maximization (MM), Successive Convex Approximation (SCA), and Alternating Direction Method of Multipliers (ADMM). We first consider the low autocorrelation sequence design problem. Sequences with low autocorrelation sidelobes enjoy a wide range of applications in wireless communications and signal processing. We propose a unified framework to design low autocorrelation sequences, unifying various metrics and miscellaneous constraints. We apply the MM method to solve the optimization problem. In the majorization stage, we construct a total of three majorizing functions. Two of them apply to the unified metric, and the remaining one applies only to a specific metric. In the minimization stage, we provide efficient closed-form solutions to the minimization problems depending on the constraints. We also establish the connections between the MM and gradient projection method. Then we study the joint design of transmitting sequence(s) and receiving filters. This problem arises in active sensing, colocated radar systems, and multiuser communications. We employ the MM method and extend it so as to handle a piecewise smooth objective. The proposed algorithms successively solve a series of simple convex problems and we can claim convergence to a stationary solution of the original problem. The proposed algorithms can achieve slightly higher objective values empirically and are more efficient than the existing methods due to a low per-iteration computational complexity. Next we look into the robust low-rank matrix completion problem in the presence of outliers. This problem finds its application in recommendation systems. We provide two loss functions that promote robustness against two types of outliers, namely dense elliptical-distributed outliers and sparse spike-like outliers. We develop an efficient algorithm on the basis of SCA with provable convergence to a stationary solution, updating the variables in parallel instead of alternately. The proposed algorithm can get rid of parameter tuning issues. We ensure a monotonic decrease in the objective in every iteration with a well-chosen step size. We move on to the problem of graph Laplacian estimation. We study the estimation problem under a given connectivity topology. We apply the well-known ADMM and MM algorithmic frameworks and propose two algorithms, namely, GLE-ADMM and GLE-MM. Both algorithms can achieve an optimality gap as low as 10^-4, 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 less than 10^-4 as well. Finally, we look into a finance application. 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. We propose an efficient BSUM-M-based algorithm to solve the portfolio design problem. The proposed algorithm can perform as well as the off-the-shelf solvers but with a much shorter computational time.

Date of Award	2018
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology