An approximate approach of global optimization for polynomial programming problems

Many methods for solving polynomial programming problems can only find locally optimal solutions. This paper proposes a method for finding the approximately globally optimal solutions of polynomial programs. Representing a bounded continuous variable x_i as the addition of a discrete variable d_i and a small variable ε_i, a polynomial term x_ix_j can be expanded as the sum of d_ix_j, d_jε_i and ε_iε_j. A procedure is then developed to fully linearize d_ix_j and d_jε_i, and to approximately linearize ε_iε_j with an error below a pre-specified tolerance. This linearization procedure can also be extended to higher order polynomial programs. Several polynomial programming examples in the literature are tested to demonstrate that the proposed method can systematically solve these examples to find the global optimum within a pre-specified error.