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.