Solving a class of generalized fractional programming problems using the feasibility of linear programs
Abstract This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent op...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2017-06-01
|
| Series: | Journal of Inequalities and Applications |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13660-017-1420-1 |
| _version_ | 1819066465257521152 |
|---|---|
| author | Peiping Shen Tongli Zhang Chunfeng Wang |
| author_facet | Peiping Shen Tongli Zhang Chunfeng Wang |
| author_sort | Peiping Shen |
| collection | DOAJ |
| description | Abstract This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an exploration of a suitably defined nonuniform grid. The main work of the algorithm involves checking the feasibility of linear programs associated with the interesting grid points. It is proved that the proposed algorithm is a fully polynomial time approximation scheme as the ratio terms are fixed in the objective function to problem (P), based on the computational complexity result. In contrast to existing results in literature, the algorithm does not require the assumptions on quasi-concavity or low-rank of the objective function to problem (P). Numerical results are given to illustrate the feasibility and effectiveness of the proposed algorithm. |
| first_indexed | 2024-12-21T16:02:47Z |
| format | Article |
| id | doaj.art-bba78971fca042649d2a740e6a01fe14 |
| institution | Directory Open Access Journal |
| issn | 1029-242X |
| language | English |
| last_indexed | 2024-12-21T16:02:47Z |
| publishDate | 2017-06-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Journal of Inequalities and Applications |
| spelling | doaj.art-bba78971fca042649d2a740e6a01fe142022-12-21T18:57:58ZengSpringerOpenJournal of Inequalities and Applications1029-242X2017-06-012017111610.1186/s13660-017-1420-1Solving a class of generalized fractional programming problems using the feasibility of linear programsPeiping Shen0Tongli Zhang1Chunfeng Wang2College of Mathematics and Information Science, Henan Normal UniversityCollege of Mathematics and Information Science, Henan Normal UniversityCollege of Mathematics and Information Science, Henan Normal UniversityAbstract This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an exploration of a suitably defined nonuniform grid. The main work of the algorithm involves checking the feasibility of linear programs associated with the interesting grid points. It is proved that the proposed algorithm is a fully polynomial time approximation scheme as the ratio terms are fixed in the objective function to problem (P), based on the computational complexity result. In contrast to existing results in literature, the algorithm does not require the assumptions on quasi-concavity or low-rank of the objective function to problem (P). Numerical results are given to illustrate the feasibility and effectiveness of the proposed algorithm.http://link.springer.com/article/10.1186/s13660-017-1420-1generalized fractional programmingglobal optimizationapproximation algorithmcomputational complexity |
| spellingShingle | Peiping Shen Tongli Zhang Chunfeng Wang Solving a class of generalized fractional programming problems using the feasibility of linear programs Journal of Inequalities and Applications generalized fractional programming global optimization approximation algorithm computational complexity |
| title | Solving a class of generalized fractional programming problems using the feasibility of linear programs |
| title_full | Solving a class of generalized fractional programming problems using the feasibility of linear programs |
| title_fullStr | Solving a class of generalized fractional programming problems using the feasibility of linear programs |
| title_full_unstemmed | Solving a class of generalized fractional programming problems using the feasibility of linear programs |
| title_short | Solving a class of generalized fractional programming problems using the feasibility of linear programs |
| title_sort | solving a class of generalized fractional programming problems using the feasibility of linear programs |
| topic | generalized fractional programming global optimization approximation algorithm computational complexity |
| url | http://link.springer.com/article/10.1186/s13660-017-1420-1 |
| work_keys_str_mv | AT peipingshen solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms AT tonglizhang solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms AT chunfengwang solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms |