Duality and Sensitivity Analysis for Fractional Programs (REVISED)
In this paper, we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relationship to certain approaches via...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5398 |
| _version_ | 1826199923762135040 |
|---|---|
| author | Bitran, Gabriel R. Magnanti, Thomas L. |
| author_facet | Bitran, Gabriel R. Magnanti, Thomas L. |
| author_sort | Bitran, Gabriel R. |
| collection | MIT |
| description | In this paper, we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relationship to certain approaches via variable transformations, and a variant of the procedure which has convenient convergence properties. The duality correspondences that are developed do not require either differentiability or the existence of optimal solution. The sensitivity analysis applies to linear fractional problems, even when they "solve" at an extreme ray, and includes a primal-dual algorithm for parametric right-hand-side analysis. |
| first_indexed | 2024-09-23T11:27:57Z |
| format | Working Paper |
| id | mit-1721.1/5398 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:27:57Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53982019-04-12T08:16:43Z Duality and Sensitivity Analysis for Fractional Programs (REVISED) Bitran, Gabriel R. Magnanti, Thomas L. In this paper, we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real valued functions. We discuss a procedure suggested by Dinkelbach for solving the problem, its relationship to certain approaches via variable transformations, and a variant of the procedure which has convenient convergence properties. The duality correspondences that are developed do not require either differentiability or the existence of optimal solution. The sensitivity analysis applies to linear fractional problems, even when they "solve" at an extreme ray, and includes a primal-dual algorithm for parametric right-hand-side analysis. Supported in part by the U.S. Army Research Office (Durham) under Contract No. DAHC04-73-C-0032 and Grant-In-Aid from Coca-Cola, U.S.A. administered at M.I.T. as OSP 27857 2004-05-28T19:37:38Z 2004-05-28T19:37:38Z 1975-04 Working Paper http://hdl.handle.net/1721.1/5398 en_US Operations Research Center Working Paper ; OR 042-75 1746 bytes 1987882 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Bitran, Gabriel R. Magnanti, Thomas L. Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title | Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title_full | Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title_fullStr | Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title_full_unstemmed | Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title_short | Duality and Sensitivity Analysis for Fractional Programs (REVISED) |
| title_sort | duality and sensitivity analysis for fractional programs revised |
| url | http://hdl.handle.net/1721.1/5398 |
| work_keys_str_mv | AT bitrangabrielr dualityandsensitivityanalysisforfractionalprogramsrevised AT magnantithomasl dualityandsensitivityanalysisforfractionalprogramsrevised |