Linear-fractional programming: Difference between revisions

Revision as of 17:12, 20 February 2015

Revision as of 09:20, 25 May 2015

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 |year=1962 |pages=181–196181–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=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|format=pdf|accessdate=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 31:

==Duality==

Let the 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| url=http://www.springerlink.com/content/kv02870752256413/ |journal=Zeitschrift für Operations Research |volume=18 |year=1974 |issue=5 |pages=187–196187–186|ref=harv|doi=10.1007/BF02026600|mr=351464}}</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}