Global Optimality Conditions And Optimization Methods For Polynomial Programming Problems

The polynomial programming problem which has a polynomial objective function, either with no constraints or with polynomial constraints have a wide range of applications, such as engineering design, investment science, control theory, network distribution, signal processing and location-allocation contexts. Moreover, the polynomial programming problem is known to be Nondeterministic Polynomial-time hard(NP-hard). In recent decades, the polynomial programming problem has attracted a lot of attention, including quadratic, cubic, homogenous or normal quartic programming problems and so on. The algebraic method and some convex relaxation methods are major methods for solving polynomial programming problems. Among these methods, semidefinite programming(SDP) and sum of squares(SOS) relaxations method are commonly used to solve the general polynomial programming problems.It is well-known that traditional local optimization methods are designed based on necessary local optimality conditions, i.e., Karush-Kuhn-Tucker(KKT) conditions. According to this, some researchers proposed a necessary global optimality condition for a quadratic programming problem and designed a new local optimization method. In this thesis,this idea is applied to cubic and quatic programming problems, and further to general constrained polynomial programming problems. For these polynomial programming problems, necessary global optimality conditions are investigated and new local optimization methods are designed according to these conditions. These necessary global optimality conditions are generally stronger than KKT condition. Hence, these new local minimizers which is obtained by using the new local optimization methods may be better than the KKT points. The ultimate purpose is to design global optimization methods for these polynomial programming problems. For the filled function method is one of the famous and practical auxiliary function methods which are used to achieve a global minimizer, we design the global optimization methods by combining the new local optimization methods with some auxiliary functions. Some numerical examples illustrate the efficiency and stability of these optimization methods.In this paper, we focus on both global optimality conditions and global optimization method for some kinds of polynomial programming problems. We now proceed the contends of this paper as follows:In chapter 1, a literature review is given. We briefly introduced local optimality conditions, global optimality conditions, local optimization methods and global optimization methods for nonlinear programming problems and polynomial programming problems.In chapter 2, a special non-convex cubic optimization problem with binary constraints is considered, and a global optimal necessary sufficient condition of this special non-convex cubic optimization problem is proposed. The results extend and improve the corresponding results of global optimality conditions in some references. At the same time, numerical examples show that the global optimal necessary and sufficient condition can effectively determine the optimal solution for the non-convex cubic optimization problem.In chapter 3, we consider the multivariate quartic polynomial optimization problems with linear constraints which are denoted by(QPOPL). A necessary global optimality conditions for the problem(QPOPL) is established and a new(strongly or ε-strongly) local optimization methods are proposed by exploiting the necessary global optimality conditions. Then, a global optimization method for the problem(QPOPL) is put forward by combining the new(strongly or ε-strongly) local optimization method together with some auxiliary functions. The results in this chapter also extend some corresponding results on global optimality conditions in some references. The numerical results demonstrate the efficiency of this global optimization method.In chapter 4, we concentrate on general polynomial programming problems with linear constraints which are denoted by(GPL), after we have built up the knowledge for cubic and quartic programming problems. A necessary global optimality condition for the problem(GPL) is provided by using some properties of univariate polynomial functions. A new local optimization method is designed for the problem(GPL) according to the necessary global optimality condition, which could improve some KKT points. Finally, some numerical examples are given to illustrate that the new local optimization methods are efficient.In Chapter 5, we focus on general constrained polynomial programming problems which are denoted by(GPP). Necessary global optimality conditions for the problem(GPP) are established. Then, a new local optimization method for this problem is proposed with these necessary global optimality conditions. A global optimization method is suggested for this problem by combining this local optimization method with an auxiliary function. We also investigate the efficiency and stability of our optimization methods.In chapter 6, we summarize the research in this article and make a prospect for the fourther research studying.