Shen Peiping, Wang Chunfeng
College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007 P.R. China.
Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, 453007 P.R. China.
J Inequal Appl. 2017;2017(1):74. doi: 10.1186/s13660-017-1342-y. Epub 2017 Apr 13.
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.
本文提出了一种针对一类非凸规划问题的线性分解方法，通过将输入空间划分为多项式数量的网格。结果表明，在某些假设下，原问题可以被转化并分解为多项式数量的等价线性规划子问题。基于求解与这些网格点对应的一系列线性规划子问题，我们可以得到原问题的近似最优解。与文献中的现有结果相比，所提出的算法不需要目标函数为准凹性和可微性的假设，并且在运行时间减少的情况下，通过给出一种有趣的方法来解决该问题，从而有显著不同。
