The Higher Order Optimality Condition Of Non-Constrain Optimization Problem And The Research Of Binary Quadratic Programming

Optimality condition is undoubtedly the essencial theory for optimization problem. There are mounting numbers algorithms designed and application based on optimality condition. The most of bibliography only talk about one or two order optimality condition which used in lots of fields, but there are large numbers of situations which hard to judge only depend on low order optimality condition. So we are necessary to study the optimality condition of non-constrain optimization in detailed in order to get the higher order optimality condition.Combinatorial quadratic optimization problem is an optimization problem which the objective function is a quadratic function and the decision variable only can take a finite or a countable integer (e.g. can take-1 or 1). This kind of problem plays a significant role in theory of modern mathematical optimization. With the progress of the modern society and the development of science and technology, combinatorial quadratic optimization problem are used in many fields such as graph theory, signal processing, communication system, relevant clustering and so on. So the research on discrete quadratic optimization problem is a meaningful work.The main contents of this dissertation are list as follows: (1) In this paper, we express the Taylor expansion of function f(x) by tensor method and show the general optimality condition:n-order optimality condition. This paper complete the optimality condition of non-costrain optimization problem. There is always have x* is a local minimum point of non-costrain minimize problem (?) all of the feasible directions around the x* are not the drop direction of f(x) i.e. (?)d∈Rn are not the drop direction of f(x) in x*. We prove the (?)d∈Rn are rise direction of f(x) in x'and get the higher order sufficient condition of non-costrain minimize problem. We get the higher order necessary condition of non-costrain minimize problem by the counter-evidence method. With the computer software technology development, there are more and more mathematical researchers use the high order optimality condition(greater than second order) to design algorithm.(2) This paper considers the combinatorial quadratic optimization pro-blem which the objective function is a quadratic function and the decision variable only can take-1 or 1(for convenience, in this paper the problem is called BQP problem). We establish the improvement approximation algoiithm-AZX algorithm for this problem based on the Charikar and Wirth's algorithm and use the semidefinite relaxation programming and convexity of quadratic function return a solution whose ratio to the optimum is the same as theirs. We can also guarantee that our AZX algorithm returns a solution to the MAX-CUT problem in the requirement of the sum of all weights of edges are nonnegative which relax the requirement of all weights of edges are nonnegative in Goemans and Williamson's algorithm. In the Computational test, the performance of our AZX algorithm is significantly stronger than Charikar and Wirth's algorithm and analogous to the Goemans and Williamson's algorithm.