Font Size: a A A

The Theory And Algorithms For A Class Of Constrained Matrix Least Squares Problems

Posted on:2019-12-19Degree:MasterType:Thesis
Country:ChinaCandidate:L ChangFull Text:PDF
GTID:2370330545473899Subject:Computational Mathematics
Abstract/Summary:PDF Full Text Request
Least squares problem is one of the classical research topics in the field of numerical algebra.The theory and algorithm for solving the least squares problem are widely used in the fields of structural design,parameter identification,vibration theory,and linear optimal control.This Master's thesis focuses on a matrix least-squares problem with non-negative constraints.This problem is mainly used to deal with theoretical and practical problems arising from medical image reconstruction,inverse problems in radiation therapy,and computational separation of hyperplanes.Incompatible linear inequalities.The solution of such non-negative constrained least squares problem is the best approximation solution of the corresponding linear inequality group in the sense of least squares.Especially when the objective function value of the least squares problem is zero,it indicates that the corresponding linear inequality group is compatible.Although the objective function of this class of non-negative constrained least squares problem is a convex function,and the corresponding gradient is global Lipschitz continuous,but this class of non-negative constrained least squares problem is different from the classical non-negative constrained least squares problem(NNLS)and the solution may not be unique.Moreover,the second-order Jacobi matrix of its objective function does not exist.Therefore,it is not possible to solve the non-negative constrained least squares problem by using the second-order method for solving convex optimization problems directly.Since the objective function of such non-negative constrained least-squares problem is semi-smooth,we can try to solve this kind of non-negative constrained leastsquares problem by using the semi-smooth Newton's method.This Master's thesis is based on the penalty function method and transforms this non-negatively constrained least squares problem into a class of unconstrained convex optimization problems.Based on this,it uses the modified Newton method based on generalized Jacobi to solve the problem and gives the corresponding proof of the convergence of the algorithm.In order to guarantee the nonnegativity of the solution and the positive definiteness of the generalized Jacobi matrix,this method needs to introduce a larger penalty parameter and a smaller correction factor,which may lead to the instability of the numerical algorithm.Therefore,this Master's thesis will study the characteristics of the solutions to this class of non-negative constrained least squares problems,and use the classical best approximation theorem and polar decomposition theorem in Hilbert space to give the necessary and sufficient conditions for the solution of this class of nonnegative constrained least squares problems.Based on the existing research,this paper will also propose an exact fixed matrix iterative method for solving this problem.Since each step of the exact fixed-matrix iteration method requires an exact solution of the classical non-negative constrained least squares subproblem(NNLS),this method has a large amount of calculation and is not suitable for solving large-scale problems.Thus,in this paper,based on the Armijo search conditions,the corresponding inaccurate iterative method is proposed,and the convergence of the exact and inexact matrix iteration methods are given respectively.When the iterative approximation solution is close to the true solution of such a nonnegatively constrained least squares problem,the exact and inexact fixed matrix iterative method proposed in this paper cannot guarantee that the objective function value of the corresponding iterative solution has enough descent.Therefore,this paper will also discuss the active set strategy for the exact and inexact fixed matrix iterative method.By constantly updating the active set corresponding to the iterative solution,the original problem is transformed into an unconstrained least squares problem,and the solution of the unconstrained least squares problem is taken as the downward direction of the next iteration to ensure that each iteration has enough decrease.Thus,the computational efficiency of the exact and inexact fixed matrix iteration method is further improved.Finally,we will verify the correctness of the theoretical results and the validity of the numerical methods through multiple numerical examples,and compare the computational efficiency of several algorithms proposed in this paper.
Keywords/Search Tags:Least squares problem, the system of linear inequality, Non-negative solutions, Fixed matrix iterative method, Active set method
PDF Full Text Request
Related items