Linear-fractional programming: Difference between revisions

Revision as of 21:49, 12 February 2021

Revision as of 01:38, 7 April 2021

Line 12:

\end{align}

</math>

where <math>\mathbf{x} \in \mathbb{R}^n</math> represents the vector of variables to be determined, <math>\mathbf{c}, \mathbf{d} \in \mathbb{R}^n</math> and <math>\mathbf{b} \in \mathbb{R}^m</math> are vectors of (known) coefficients, <math>A \in \mathbb{R}^{m \times n}</math> is a (known) matrix of coefficients and <math>\alpha, \beta \in \mathbb{R}</math> are constants. The constraints have to restrict the [[feasible region]] to <math>\{\mathbf{x} | \mathbf{d}^T\mathbf{x} + \beta > 0\}</math>, i.e. the region on which the denominator is positive.<ref name="CC">{{cite journal |last1=Charnes |first1=A. |last2=Cooper |first2=W. W. |author2-link=William W. Cooper|title=Programming with Linear Fractional Functionals|journal=Naval Research Logistics Quarterly |volume=9 |issue=3–4 |year=1962 |pages=181–186|ref=harv|mr=152370|doi=10.1002/nav.3800090303}}</ref><ref name="BV">{{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|accessdateaccess-date=October 15, 2011|page=151}}</ref> Alternatively, the denominator of the objective function has to be strictly negative in the entire feasible region.

==Transformation to a linear program==

Line 35:

==Duality==

Let the [[duality (optimization)|dual variables]] associated with the constraints <math>A\mathbf{y} - \mathbf{b} t \leq \mathbf{0}</math> and <math>\mathbf{d}^T \mathbf{y} + \beta t - 1 = 0</math> be denoted by <math>\mathbf{u}</math> and <math>\lambda</math>, respectively. Then the dual of the LFP above is <ref>{{cite journal|last1=Schaible |first1=Siegfried |title=Parameter-free Convex Equivalent and Dual Programs|journal=Zeitschrift für Operations Research |volume=18 |year=1974 |issue=5 |pages=187–196|ref=harv|doi=10.1007/BF02026600|mr=351464|s2cid=28885670 }}</ref><ref>{{cite journal|title=Fractional programming&nbsp;I: Duality |last1=Schaible |first1=Siegfried | journal=Management Science |volume=22 |issue=8 |pages=858–867 |year=1976|jstor=2630017|mr=421679|ref=harv |doi=10.1287/mnsc.22.8.858}}</ref>

:<math>

\begin{align}

Line 48:

==Properties and algorithms==

The objective function in a linear-fractional problem is both quasiconcave and [[quasiconvex function|quasiconvex]] (hence quasilinear) with a [[monotonicity|monotone]] property, [[pseudoconvex function|pseudoconvexity]], which is a stronger property than [[quasiconvex function|quasiconvexity]]. A linear-fractional objective function is both pseudoconvex and pseudoconcave, hence [[pseudolinear function|pseudolinear]]. Since an LFP can be transformed to an LP, it can be solved using any LP solution method, such as the [[simplex algorithm]] (of [[George B. Dantzig]]),<ref>

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-5 |mr=949209|ref=harv}}</ref><ref>{{cite journal| last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming |journal=[[SIAM Review]]|volume=41 |year=1999 |issue=4 |pages=795–805 |mr=1723002|jstor=2653207|doi=10.1137/S0036144598335259|ref=harv|citeseerx=10.1.1.53.7355}}

</ref><ref>{{cite journal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |journal=[[SIAM Review]]|volume=37 |year=1995 |issue=2 |pages=230–234|mr=1343214|jstor=2132826|doi=10.1137/1037046|ref=harv}}

</ref><ref>{{harvtxt|Murty|1983|loc=Chapter&nbsp;3.20 (pp.&nbsp;160–164) and pp.&nbsp;168 and&nbsp;179}}</ref> the [[criss-cross algorithm]],<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|issue=1|

pages=198–214|year=1999 <!-- issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|ref=harv|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|citeseerx=10.1.1.36.7090}}</ref> or [[interior-point method]]s.

==Notes==

Line 59:

*{{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-5 |mr=949209}}

*{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|issue=1|

pages=198–214|year=1999 <!-- issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|ref=harv|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|citeseerx=10.1.1.36.7090}}

*{{cite journal|last1=Kruk|first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming|journal=[[SIAM Review]]|volume=41 |year=1999 |issue=4|pages=795–805|mr=1723002 | jstor = 2653207|doi=10.1137/S0036144598335259|doi-access=free}}

*{{cite journal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management|journal=[[SIAM Review]]|volume=37 |year=1995 | issue=2|pages=230–234|mr=1343214 | jstor = 2132826|doi=10.1137/1037046}}

*{{cite book|last=Murty|first=Katta&nbsp;G.|author-link=Katta G. Murty|chapter=3.10 Fractional programming (pp. 160–164)|title=Linear programming|publisher=John Wiley & Sons, Inc.|___location=New York|year=1983|pages=xix+482|isbn=978-0-471-09725-9|mr=720547|ref=harv}}

==Further reading==