Study On Algorithms For Absolute Value Equation

The absolute value equation is a NP-hard problem.It comes from the interval problem and has a wide range of practical applications in many practical problems,such as site selection problems,semi-supervised and unsupervised classification problems and knapsack feasibility problems,etc.Generally speaking the problems such as linear programming,bimatrix games,quadratic programming can be transformed into linear complementarity problems.Meanwhile the linear complementarity problems can be converted into absolute value equations.Therefore,the study of absolute value equations provides a new way to get solutions of many mathematical programming problems.So,the study on theory and algorithms of absolute value equation is important.This dissertation focuses on the numerical algorithm for the absolute value equation under the condition that the equation has a solution.Firstly,we construct a new smooth approximation function for the absolute value function and use it to convert the absolute value equation into a system of smooth equations.Then,we use the smoothing Newton algorithm to solve the equation,and prove the quadratic convergence property of our algorithm under suitable conditions.Secondly,we present a new merit function for the absolute value equation,and get the Lipschitz continuous property of the new function.We also prove that the level set is bounded.Based on this function,we apply the FR conjugate gradient algorithm to our problem and obtain global convergence property of our algorithm.The numerical results show that our algorithm is effective.