Search

This paper presents a linear decomposition approach for a class of nonconvex programming problems by dividing the input space into polynomially many grids. It shows that under certain assumptions the original problem can be transformed and decomposed into a polynomial number of equivalent linear programming subproblems. Based on solving a series of liner programming subproblems corresponding to those grid points we can obtain the near-optimal solution of the original problem. Compared to existing results in the literature, the proposed algorithm does not require the assumptions of quasi-concavity and differentiability of the objective function, and it differs significantly giving an interesting approach to solving the problem with a reduced running time.

This paper presents a deterministic global optimization algorithm for solving generalized linear multiplicative programming (GLMP). In this algorithm, a new linearization method is proposed, which applies more information of the function of (GLMP) than some other methods. By using this new linearization technique, the initial nonconvex problem is reduced to a sequence of linear programming problems. A deleting rule is presented to improve the convergence speed of this algorithm. The convergence of this algorithm is established, and some experiments are reported to show the feasibility and efficiency of this algorithm.

We consider a branch-and-reduce approach for solving generalized linear multiplicative programming. First, a new lower approximate linearization method is proposed; then, by using this linearization method, the initial nonconvex problem is reduced to a sequence of linear programming problems. Some techniques at improving the overall performance of this algorithm are presented. The proposed algorithm is proved to be convergent, and some experiments are provided to show the feasibility and efficiency of this algorithm.

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.