Linear decomposition approach for a class of nonconvex programming problems
Abstract 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 l...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2017-04-01
|
| Series: | Journal of Inequalities and Applications |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13660-017-1342-y |
| _version_ | 1829107367922368512 |
|---|---|
| author | Peiping Shen Chunfeng Wang |
| author_facet | Peiping Shen Chunfeng Wang |
| author_sort | Peiping Shen |
| collection | DOAJ |
| description | Abstract 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. |
| first_indexed | 2024-12-12T06:37:35Z |
| format | Article |
| id | doaj.art-62ee76cba97c4efca68faeaedfed0443 |
| institution | Directory Open Access Journal |
| issn | 1029-242X |
| language | English |
| last_indexed | 2024-12-12T06:37:35Z |
| publishDate | 2017-04-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Journal of Inequalities and Applications |
| spelling | doaj.art-62ee76cba97c4efca68faeaedfed04432022-12-22T00:34:26ZengSpringerOpenJournal of Inequalities and Applications1029-242X2017-04-012017111110.1186/s13660-017-1342-yLinear decomposition approach for a class of nonconvex programming problemsPeiping Shen0Chunfeng Wang1College of Mathematics and Information Science, Henan Normal UniversityCollege of Mathematics and Information Science, Henan Normal UniversityAbstract 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.http://link.springer.com/article/10.1186/s13660-017-1342-ynonconvex programmingglobal optimizationlinear decomposition approachapproximation algorithmcomputational complexity |
| spellingShingle | Peiping Shen Chunfeng Wang Linear decomposition approach for a class of nonconvex programming problems Journal of Inequalities and Applications nonconvex programming global optimization linear decomposition approach approximation algorithm computational complexity |
| title | Linear decomposition approach for a class of nonconvex programming problems |
| title_full | Linear decomposition approach for a class of nonconvex programming problems |
| title_fullStr | Linear decomposition approach for a class of nonconvex programming problems |
| title_full_unstemmed | Linear decomposition approach for a class of nonconvex programming problems |
| title_short | Linear decomposition approach for a class of nonconvex programming problems |
| title_sort | linear decomposition approach for a class of nonconvex programming problems |
| topic | nonconvex programming global optimization linear decomposition approach approximation algorithm computational complexity |
| url | http://link.springer.com/article/10.1186/s13660-017-1342-y |
| work_keys_str_mv | AT peipingshen lineardecompositionapproachforaclassofnonconvexprogrammingproblems AT chunfengwang lineardecompositionapproachforaclassofnonconvexprogrammingproblems |