Cargando…
Solving a class of generalized fractional programming problems using the feasibility of linear programs
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 optimizatio...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer International Publishing
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5487952/ https://www.ncbi.nlm.nih.gov/pubmed/28680250 http://dx.doi.org/10.1186/s13660-017-1420-1 |
_version_ | 1783246556565078016 |
---|---|
author | Shen, Peiping Zhang, Tongli Wang, Chunfeng |
author_facet | Shen, Peiping Zhang, Tongli Wang, Chunfeng |
author_sort | Shen, Peiping |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-5487952 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Springer International Publishing |
record_format | MEDLINE/PubMed |
spelling | pubmed-54879522017-07-03 Solving a class of generalized fractional programming problems using the feasibility of linear programs Shen, Peiping Zhang, Tongli Wang, Chunfeng J Inequal Appl Research 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. Springer International Publishing 2017-06-24 2017 /pmc/articles/PMC5487952/ /pubmed/28680250 http://dx.doi.org/10.1186/s13660-017-1420-1 Text en © The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Research Shen, Peiping Zhang, Tongli Wang, Chunfeng Solving a class of generalized fractional programming problems using the feasibility of linear programs |
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 | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5487952/ https://www.ncbi.nlm.nih.gov/pubmed/28680250 http://dx.doi.org/10.1186/s13660-017-1420-1 |
work_keys_str_mv | AT shenpeiping solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms AT zhangtongli solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms AT wangchunfeng solvingaclassofgeneralizedfractionalprogrammingproblemsusingthefeasibilityoflinearprograms |