fractional programming

Let $f,\; g,\; h\_j,\; j=1,\; \backslash ldots,\; m$ be real-valued functions defined on a set $\backslash mathbf\{S\}\_0\; \backslash subset\; \backslash mathbb\{R\}^n$. Let $\backslash mathbf\{S\}\; =\; \backslash \{\backslash boldsymbol\{x\}\; \backslash in\; \backslash mathbf\{S\}\_0:\; h\_j(\backslash boldsymbol\{x\})\; \backslash leq\; 0,\; j=1,\; \backslash ldots,\; m\backslash \}$. The nonlinear program

:$$

\underset{\boldsymbol{x} \in \mathbf{S}}{\text{maximize}} \quad \frac{f(\boldsymbol{x})}{g(\boldsymbol{x})},

where $g(\backslash boldsymbol\{x\})\; >\; 0$ on $\backslash mathbf\{S\}$, is called a fractional program.

A fractional program in which f is nonnegative and concave, g is positive and convex, and S is a convex set is called a concave fractional program. If g is affine, f does not have to be restricted in sign. The linear fractional program is a special case of a concave fractional program where all functions $f,\; g,\; h\_j,\; j=1,\; \backslash ldots,\; m$ are affine.

The function $q(\backslash boldsymbol\{x\})\; =\; f(\backslash boldsymbol\{x\})\; /\; g(\backslash boldsymbol\{x\})$ is semistrictly quasiconcave on S. If f and g are differentiable, then q is pseudoconcave. In a linear fractional program, the objective function is pseudolinear.

By the transformation $\backslash boldsymbol\{y\}\; =\; \backslash frac\{\backslash boldsymbol\{x\}\}\{g(\backslash boldsymbol\{x\})\};\; t\; =\; \backslash frac\{1\}\{g(\backslash boldsymbol\{x\})\}$, any concave fractional program can be transformed to the equivalent parameter-free concave program{{cite journal|last1=Schaible |first1=Siegfried |title=Parameter-free Convex Equivalent and Dual Programs|journal=Zeitschrift für Operations Research |volume=18 |year=1974 |number=5 |pages=187–196|doi=10.1007/BF02026600|mr=351464|s2cid=28885670 }}

:$$

\begin{align}

\underset{\frac{\boldsymbol{y}}{t} \in \mathbf{S}_0}{\text{maximize}} \quad & t f\left(\frac{\boldsymbol{y}}{t}\right) \\

\text{subject to} \quad & t g\left(\frac{\boldsymbol{y}}{t}\right) \leq 1, \\

& t \geq 0.

\end{align}

If g is affine, the first constraint is changed to $t\; g(\backslash frac\{\backslash boldsymbol\{y\}\}\{t\})\; =\; 1$ and the assumption that g is positive may be dropped. Also, it simplifies to $g(\backslash boldsymbol\{y\})\; =\; 1$.

The Lagrangian dual of the equivalent concave program is

:$$

\begin{align}

\underset{\boldsymbol{u}}{\text{minimize}} \quad & \underset{\boldsymbol{x} \in \mathbf{S}_0}{\operatorname{sup}} \frac{f(\boldsymbol{x}) - \boldsymbol{u}^T \boldsymbol{h}(\boldsymbol{x})}{g(\boldsymbol{x})} \\

\text{subject to} \quad & u_i \geq 0, \quad i = 1,\dots,m.

\end{align}

• {{cite book |last1=Avriel |first1=Mordecai |last2=Diewert |first2=Walter E. |last3=Schaible |first3=Siegfried |last4=Zang |first4=Israel |title=Generalized Concavity |publisher=Plenum Press |year=1988}}
• {{cite journal |title=Fractional programming |last1=Schaible |first1=Siegfried |journal=Zeitschrift für Operations Research |volume=27 |year=1983 |pages=39–54 |doi=10.1007/bf01916898|s2cid=28766871 }}

{{Major subfields of optimization}}

Category:Optimization algorithms and methods