Solving convex programming with simple convex constraints

  • Liangshao Hou

Student thesis: Doctoral Thesis


The problems we studied in this thesis are linearly constrained convex programming (LCCP) and nonnegative matrix factorization (NMF). The resolutions of these two problems are all closely related to convex programming with simple convex constraints. The work can mainly be described in the following three parts. Firstly, an interior point algorithm following a parameterized central path for linearly constrained convex programming is proposed. The convergence and polynomial-time complexity are proved under the assumption that the Hessian of the objective function is locally Lipschitz continuous. Also, an initialization strategy is proposed, and some numerical results are provided to show the efficiency of the proposed algorithm. Secondly, the path following algorithm is promoted for general barrier functions. A class of barrier functions is proposed, and their corresponding paths are proved to be continuous and converge to optimal solutions. Applying the path following algorithm to these paths provide more flexibility to interior point methods. With some adjustments, the initialization method is equipped to validate implementation and convergence. Thirdly, we study the convergence of hierarchical alternating least squares algorithm (HALS) and its fast form (Fast HALS) for nonnegative matrix factorization. The coordinate descend idea for these algorithms is restated. With a precise estimation of objective reduction, some limiting properties are illustrated. The accumulation points are proved to be stationary points, and some adjustments are proposed to improve the implementation and efficiency

Date of Award9 Jul 2020
Original languageEnglish
SupervisorLizhi LIAO (Supervisor)

User-Defined Keywords

  • Linear programming
  • Convex programming
  • Interior-point methods
  • Non-negative matrices

Cite this