Optimization Algorithms With Active Set Prediction And Probability For Solving Linear Inequalities System And Its Application

The linear inequalities system can be generalized from various fields of engineering,such as machine learning,signal process,medical science and radiation therapy,its theory and numerical algorithms have important scientific significance and application value.In this doctoral dissertation,hybrid algorithms with active set prediction and the randomized coordinate descent methods are proposed and applied for three kinds of engineering problems: the calculation of a hyperplane to separate the data in machine learning,the radiation therapy in medicine,and signal reconstruction.The linear inequalities system is divided into two groups: consistent system and inconsistent system,however,it is a partial order relation such that those theories and algorithms of the linear equations can not be directly applied to linear inequalities,as the traditional linear program merely solves the small-medium consistent system of linear inequalities.Thus,numerous scholars are main concerns with the large inconsistent systems of linear inequalities.By introducing the correction vector,the Euclidean least deviation problem,which is to find the smallest correction by the least squares methods,can be recovered from the inconsistency.Due to the second order Non-differentiability of the Euclidean least deviation problem,it is necessary to develop and design the high performance of numerical algorithms for solving the problem.At present,the numerical algorithms for solving the problems raised above consist of Newton type methods and simple iterations.Newton type methods have a finite termination,but the need for the inversion of the Hessian costs too much computational effort.Simple iterations are suitable under no exact solution because the computational effort per iteration is rather small,but ones have an unacceptably slow rate of convergence when close to the solution.Consequently,some scholars tackle it with a hybrid algorithm which is a way to improve the efficiency of numerical algorithms for the Euclidean least deviation problem.Nevertheless,the key to hybrid algorithms is the strategy that chooses the optimal algorithm.This doctoral dissertation proposes a framework of hybrid algorithms and proves the convergence of this framework.Three kinds of active set predictions in terms of the identification property further are presented.With the help of active set prediction,hybrid algorithms decrease the number of Newton type iterations and take both advantages for making efficiency improvements.Simple iterations are suitable for the large scale or the need for an inexact solution.For this reason,this doctoral dissertation deeply researches the coordinate descent which is less effort at every iteration.The coordinate descent method is essentially equivalent to the Gauss-Seidel algorithm in solving the linear equations.Fortunately,this method can also solve inconsistent systems.To this end,this dissertation presents the randomized or the cyclic coordinate descent for solving the Euclidean least deviation problem.Not only that,the dissertation further analyzes their related theories and two probabilities for choosing the coordinate axis: the uniform distribution and the probabilities proportion to the column norm.Finally,the rate of convergence of the approximation errors is derived.Motivated by the linear inequalities,this doctoral dissertation establishes the Euclidean least deviation model for calculating a hyperplane to separate the data in machine learning,radiation therapy in medicine,and signal reconstruction in engineering.In contrast to the classical model in relation to numerical methods,numerical experiments show the Euclidean least deviation problem with our algorithms has some advantages in the speed or the accuracy and is suitable for solving the related application.