Non-convex optimization problems with multiple variables: practical applications and learning approaches
Creators: name: Xia, Jingyuan
Publisher: name: Imperial College London
Year: 2020

description: Optimization is pivotal for a wide range of technologies in scientific and industrial areas. In recent years, there has been an increasing interest in non-convex optimization in modern domains such as machine learning, signal processing and computer science. This thesis provides a deep insight into non-convex multi-variable optimization problems in the aspects of practical applications and solution approaches. We firstly present two applications which use non-convex optimization techniques on practical problems, where a bi-linear inverse model is proposed to solve an origin-destination (OD) flow estimation problem and a non-linear model is improved for solving multiple kernel clustering (MKC). In the light of optimizing the variables in the non-convex optimization problem on a global scope, a meta-learning based global scope optimization (GSO) approach is introduced for solving non-convex multi-variable problems. It performs significant improvements on accuracy than alternating minimization(AM)-based methods and shows . First, we study the OD flow estimation problem to present that a significant dimension reduction is achieved by reformulating the previous NP-hard OD flow estimation problem as a bi-linear inverse problem. Specifically, a new forward model is developed which does not involve OD flows directly but is built upon the flows characterized only by their origins, henceforth referred as O-flows. The new O-flow model preserves all the OD information and more importantly reduces the dimension of the inverse problem substantially. An AM-based Gauss-Seidel method is deployed to solve the inverse problem, and the necessary condition for the uniqueness of the solution is derived. Simulations demonstrate that blind estimation, where no prior information is available, is possible. Some challenging network settings are identified and discussed, where a remedy based on temporal patterns of the O-flows is developed and numerically shown effective. We then study a non-linear non-convex multi-variable problem that is MKC problem. In this work, we improve the existing non-convex optimization model by incorporating an extra regularization term to provide finer structural constraints, therefore rising the accuracy and efficiency on clustering performance. Specifically, we propose a Localized Incomplete Multiple Kernel k-means with Matrix-induced Regularization (LI-MKKM-MR) model to solve MKC problem with taking the correlation among incomplete base kernels into account. The proposed model effectively reduces the redundancy and increases the diversity of the obtained kernel matrices. This improves the imputation of incomplete kernel matrices, and thus offers better clustering performance. A three-step optimization algorithm is proposed for solving LI-MKKM-MR, and the convergence is proved. We also carry out the theoretical analysis on the generalization error bound of the proposed LI-MKKM-MR. Extensive experiments on multiple benchmark data sets for MKC have been proposed to evaluate LI-MKKM-MR. At last, we propose a new meta-learning approach, GSO approach, for solving non-convex optimization problems. Typically, the AM-based approaches are widely applied to optimize non-convex optimization problem with multiple variables. It splits the overall problem into several sub-problems corresponding to each variable, then it finds the optimum by iterating between the sub-problems. However, due to the intrinsic non-convexity, the stationary solutions of overall problem are not universally guaranteed, even when each sub-problem can be globally optimized at each iteration. Instead of exhaustively minimizing each sub-problem as what the AM strategy does, our meta-learning model explores a less greedy but more global scope strategy that intends to optimize variables based on its corresponding sub-problem and overall problem integrally. This is achieved via replacing the variable updating functions by neural networks, whose parameters are updated with respect to minimizing the accumulated global losses through backpropagation. Specifically, the proposed meta-learning model exploits Long Short-Term Memory (LSTM) networks as meta-learners, which are updated in two levels of meta-learning. We evaluate the proposed model based on extensive simulations. The results verify that our proposed approach outperforms the exiting AM-based methods in standard cases, and is able to find the optimum of the overall problem while the AM strategy typically fails in some challenging cases.