The Optimization Algorithm Of Complementarity Problem And Its Application

Optimization theory and algorithm is a widely used discipline, it is mainly to discuss the best method of the decision-making problem, to seek the optimum calculation method, theoretical properties of these calculation methods and practical calculation performance. Mathematical programming is an important branch of optimization theory, compared with other branches of mathematics, it is a very young and very active branch of applied mathematics. The complementarity problem is a kind of mathematical model of considerable. In fact, the mathematical model for many practical problems is a special complementarity problem, linear programming problems and nonlinear classic problem can be transformed into complementary problem to solve calculation.Since1947, Danzig proposed the concept of linear programming and the famous simplex algorithm, the algorithm has a good performance in the actual process of calculation, but in theory of complexity,it is not ideal. Affected by the computational complexity theory, scholars have had a lot of time to hope that simplex method has a polynomial time algorithm. However, in1972,Klee and Minty used the example, proved the simplex algorithm method, it is not a polynomial algorithm, this is a very significant issue:whether the linear programming problems have polynomial algorithm? In1978, Khachiyan gave the linear programming problem a new method,the ellipsoid algorithm, this algorithm is a linear programming algorithm, but on theoretical, advantages are not in the actual computational performance beyond simple simplex method, which had caused many scholars try to find the linear programming with polynomial algorithm better practical performance calculation another. Until1984, the "Karmarkar" made the projective scaling algorithm for linear programming and had a true breakthrough, this new algorithm not only in theory was superior to the simplex algorithm, but also showed great potential in solving large-scale problems. The Karmarkar algorithm was again really different from simplex algorithm (a vertex of feasible region from iteration to another vertex), its approximation from inside the feasible region one of the optimal solution, it is known as the "interior point algorithm".According to in-depth study of the Karmarkar algorithm by a lot of scholars, had been the development of the most representative of three categories:projection transformation method decreased potential function (Karmarkar algorithm), trajectory method for balancing transform and affine tracking center. But the existing feasible interior point algorithm is also not be the pink of perfection, the most prominent problem is polynomial time bounds, complexity analysis obtained but not as the only measure of an algorithm by calculation.First, small step (narrow neighborhood) primal-dual interior point algorithm for polynomial complexity is O(Vn log((?)nlog(n/ε)), far below the size (wide neighborhood) complexity of primal-dual interior point algorithm-O(n log(n/ε)), But in the calculation of actual effects, the former is than the latter with a lot of calculation results. In view of this inconsistent phenomenon, in the90’s, Ye and Huang proposed a higher order (r order) predictor-corrector primal-dual size (wide neighborhood) interior point algorithm, the iteration complexity is reduced to O(nr+1/2r log(n/ε)),(where r∈[1,n]),among them. We can find that, iterative approximation to the time complexity of the algorithm, And the other based on high order interior point algorithm to reduce the size (wide neighborhood) primal-dual interior point algorithm work had another. For example, Peng et al. By defining the self-regular proximity measure (Self-Regular), the large step with this new analytical tool (wide-neighborhood interior-point algorithm) polynomial time complexity was reduced to O(nq+1/2q log(n/ε)),(where q>1), among them. In2006, Pan et al found by analysis, Newton direction of the self-regular proximity measure method used in the proof of the above conclusions, was through the "central equation" with an equivalent was idempotent transformation. Although the power function transformation from algebraic sense equivalent, but the speed to the optimal solution was not the same. Therefore, algebraic transformation based on proper, also can be reduced the computational complexity of primal-dual interior point algorithm.Second, it is the feasible interior point algorithm in the initial iteration point selection is too demanding, not only to meet the strict equality constraints and nonnegative condition, and selecting the initial points in practical problems are hard to get, but infeasible interior point algorithm for relaxing the conditions, as long as it meets the nonnegative condition in the iteration begins, without the need to satisfy the equality constraints. This greatly reduces the difficulty in selecting the initial feasible point. Therefore, infeasible interior point algorithm in dealing with practical problems are widely used.This paper is divided into two parts, theory and application. The first part, solve some theory problems of optimization algorithms mainly use the theory part; the second part, the application part is mainly used to solve some practical problems of optimization algorithm.In the theory part, we firstly discussed the different neighborhood (based on large step size and small step size) for solving non-monotone linear complementary problem of higher order interior point algorithm. Secondly, ideas and framework of algebraically equivalent transformation based on KMM algorithm for linear complementarity problems, put forward a new primal-dual infeasible interior point algorithm, the global convergence of the algorithm. And the effectiveness of the algorithm is tested by numerical experiments. Finally, discussed based on kernel function to solve the infeasible interior point algorithm and prove its computational complexity and similar kernel function for solving nonlinear complementarity problem based on kernel function.The second part is the application part, because that the complementarity problem is an important optimization problem, which is widely used in economic analysis, traffic equilibrium strategies of social economic model. So it is the very vital significance to research the study of complementarity problems. Therefore, the department based on economics theory as a foundation, discusses the application of linear complementary double matrix game problem in economics, and a collection of two typical double matrix game example (prisoner’s dilemma game and inspect the game), potential function usd by linear complementarity problem and the descent method and path tracking algorithm the effective solution to test the above example.Second is the use of cooperative mechanism of evolutionary game theory and optimization algorithm for rural cooperative organization, established heterogeneous groups of farmers (with organization and management ability and influence of the class and ordinary peasant class) in the evolution game model of operation of rural cooperative organization, in the previous round of cooperation according to the results, whether the cooperation game under the adjustment a round, gradually seek evolutionary stable equilibrium solution. In order to find the evolution stable equilibrium solution presents a new evolutionary algorithm. The basic idea of the algorithm is the combination of strategies space search space optimization problem is mapped to game theory in the objective function, the utility function is mapped to the game theory, the irrational game subject to local stable equilibrium state, according to local equilibrium Kobo subject to adjust their own strategy, the next round of the game, to search for better reach equilibrium, evolutionarily stable equilibrium solution, thus solving the evolutionary stable state of the actual problem.