Linear decomposition approach for a class of nonconvex programming problems

Journal of inequalities and applications

Peiping Shen¹ 

关键词: nonconvex programming;    global optimization;    linear decomposition approach;    approximation algorithm;    computational complexity;    90C30;    90C33;    90C15;   

DOI  :  10.1186/s13660-017-1342-y

学科分类：数学（综合）

来源: SpringerOpen

【 摘 要 】

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.

【 授权许可】

CC BY