The Numerical Method For Complementary Eigenvalue Problem Based On Manifold

The complementary problem is an important research direction in the intersection of operational research and applied mathematics.Since it was proposed in 1963,it has received extensive attention from scholars in the fields of mathematics and operational research.It has a wide range of applications in engineering,economics and other fields,such as supply chain networks,friction problems,free boundary problems,etc.Combining the classical eigenvalue problem with the complementary condition,the complementary eigenvalue problem is obtained.Therefore,the complementary eigenvalue problem is a special complementary problem,which originated from the study of the static equilibrium point of the unilateral friction mechanics system,and has a wide range of applications in the engineering and physics.However,many general conclusions cannot be generalized to the complementary eigenvalue problem,which brings great difficulty to the numerical solution of the complementary eigenvalue problem.At present,the most common idea to solve them from the perspective of cone constraint optimization,so the complementary eigenvalue problem is also called the eigenvalue problem under the cone constraint.Since the number of complementary eigenvalues increases exponentially with the expansion of the problem size,solving all complementary eigenvalues of a large matrix is an NP-hard problem,and the resulting numerical computational complexity challenges cannot be underestimated.This master’s thesis focuses on the eigenvalue complementary problem of symmetric matrices based on manifold structures,and uses the Rayleigh quotient function to write a non-negative orthogonal constraint optimization problem:(?) Let S_+~n={x∈R~n|x~Tx=1,x≥0},S_+~n can be seen a special Riemannian manifold——Stiefel manifold,then the problem can be turned into an unconstrained optimization problem based on the Riemannian manifold:(?) Clearly,each stable point of the optimization problem is the solution of the eigenvalue complementary problem of the symmetric matrix.Based on the above considerations,this paper deeply studies the basic properties of the eigenvalue complementary problem of the symmetric matrix,designs three descent algo-rithms and penalty function method with different penalty terms for solving the equivalent Riemannian manifold optimization problem,and discusses its convergence.The first descent algorithm takes the steepest descent method on the Riemannian manifold as a framework,corrects the search direction,and increases the step size constraint to construct an iterative sequence.The second descent algorithm uses the NCP function to correct the search direction,and the Armijo criterion determines the step size to construct an iterative sequence.The third descent algorithm uses the projection operator on the Riemannian manifold to ensure the non-negativity of the iterative sequence,uses the NCP function to correct the search direction,and the Armijo criterion determines the step size to construct the iterative sequence.The fourth exact penalty function method is based on the traditional penalty function method,using the manifold structure to design the iterative sequence.Numerical experimental results show that the latter three algorithms can effectively ensure the non-negativity of the iterative sequence,and the use of the projection operator can greatly improve the computational efficiency.