Homogeneous Smoothing Algorithms With Applications

Smoothing algorithms have been proposed for solving various optimiza-tion problems successfully. In the analysis of their global convergence, variousassumptions have been presented in the literature, such as the existence ofstrictly feasible points or optimal solutions, which are called regularity as-sumptions. However, it is possible that it is very di?cult to check whetherthese assumptions hold or not. It is well known that the homogeneous andself-dual interior point methods have been proposed for solving some opti-mization problems and shown to be globally convergent without requiring anyregularity assumption. A natural question is whether a smoothing algorithmhas such a good property? This thesis gives some studies on this topic.Firstly, we present a smoothing algorithm for solving an augmented sys-tem constructed by the standard monotone linear complementarity problem(LCP). The algorithm is showed to be globally convergent without requiringany regularity assumption. In particular, if the LCP has a solution, then thealgorithm either generates a maximal complementary solution of the LCP ordetects correctly solvability of the LCP, and in the latter case, an existingsmoothing algorithm can be directly applied to solve the LCP without anyadditional assumption and it generates a maximal complementary solution ofthe LCP; and if the LCP is infeasible, then the algorithm detects correctlyinfeasibility of the LCP.Secondly, we propose a smoothing algorithm for solving the symmetriccone linear program (SCLP) by making use of an homogeneous and self-dualmodel constructed by the SCLP. This algorithm is proved to be globally con-vergent without requiring any regularity assumption. It only needs to solveone system of linear equations and to perform one line search at each itera-tion. In particular, if the SCLP has a solution, the algorithm will generate asolution of the SCLP; and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of the SCLP. We also reported some prelimi-nary numerical results of the algorithm. The numerical results show that ourtheoretical findings coincide with the practical results.Finally, based on the proposed homogeneous and self-dual model of theSCLP and the technique from inexact Newton methods, we present an inexactsmoothing algorithm for the SCLP, which has all the properties that the formersmoothing algorithm has. Since we solve the Newton equation approximatelyby using the conjugate gradient method at each iteration, the proposed inexactsmoothing algorithm can solve large-scale problems. We apply the algorithmto recovery problems in compressive sensing theory, which is one of the populartopics in signal processing field. As one of the compressive sensing recoveryalgorithms, this algorithm could recover sparse signals more exactly than theother state-of-the-art algorithms.