B.5 Fractional programming methods
Consider the concave-convex fractional program (FP) (refer to Section A.5 for details) \[\begin{equation} \begin{array}{ll} \underset{\bm{x}}{\textm{maximize}} & \dfrac{f(\bm{x})}{g(\bm{x})}\\ \textm{subject to} & \bm{x}\in\mathcal{X}, \end{array} \tag{B.4} \end{equation}\] where \(f(\bm{x})\) is a concave function, \(g(\bm{x})>0\) is a convex function, and \(\mathcal{X}\) denotes the convex feasible set.
Recall that FPs are nonconvex problems, so in principle they are difficult to solve (Stancu-Minasian, 1992). Fortunately, the concave-convex FP in (B.4), albeit still being nonconvex, is a quasiconvex optimization problem and can be conveniently solved. In the following, we briefly overview three practical methods to solve the FP in (B.4), namely, the iterative bisection method, the Dinkelbach method, which is still an iterative method, and the Schaible transform, which allows a direct convex reformulation.
B.5.1 Bisection method
Problem (B.4) is a quasiconvex problem and can be conveniently solved by solving a sequence of convex feasibility problems (see Section A.4.4 in Appendix A for details) of the form: \[\begin{equation} \begin{array}{ll} \underset{\bm{x}}{\textm{find}} & \begin{array}{c} \bm{x} \end{array}\\ \textm{subject to} & \begin{array}[t]{l} t g(\bm{x}) \leq f(\bm{x})\\ \bm{x}\in\mathcal{X}, \end{array} \tag{B.5} \end{array} \end{equation}\] where \(t>0\) is not an optimization variable but a fixed parameter.
The goal is to find the right value of \(t\) to be equal to the optimal value of problem (B.4). This can be done iteratively based on the following simple observation: if the feasibility problem (B.5) is infeasible, then \(t\) is too large and has to be decreased, otherwise \(t\) is probably too small and can be further increased.
The bisection method, also known as the sandwich technique, performs a series of attempts for the parameter \(t\) in a very efficient way by halving an interval known to contain the optimal value of \(t\) at each iteration. More specifically, suppose that the original problem (B.4) is feasible and that we start with an interval \([l,u]\) known to contain the optimal value denoted by \(t^\star\), we can then solve the convex feasibility problem at the interval midpoint \(t=(l+u)/2\), to determine whether the optimal value is in the lower or upper half of this interval, and update the interval accordingly. This produces a new interval, which also contains the optimal value, but has half the width of the initial interval; so the length of the interval after \(k\) iterations required is \(2^{-k}(u - l)\), where \((u - l)\) is the length of the initial interval. Therefore, if a tolerance of \(\epsilon\) is desired in the computation of \(t^\star\), the number of iterations is \(\lceil\textm{log}_2\left((u-l)/\epsilon\right)\rceil\), where \(\lceil\cdot\rceil\) denotes the ceiling rounding operation. This procedure is summarized in Algorithm B.4 (which is a particular case of the more general Algorithm A.1 in Section A.4).
Algorithm B.4: Bisection method to solve the concave-convex FP in (B.4).
Choose interval \([l,u]\) containing optimal value of problem (B.4) and tolerance \(\epsilon>0\);
repeat
- \(t \leftarrow (l+u)/2\);
- Solve the convex feasibility problem (B.5);
- if feasible, then \(l \leftarrow t\) and keep solution \(\bm{x}\); else \(u \leftarrow t\);
until convergence (i.e., \(u-l \leq \epsilon\));
B.5.2 Dinkelback method
The Dinkelbach transform, proposed in (Dinkelbach, 1967), reformulates the original concave-convex FP in (B.4) into a sequence of simpler convex problems of the form
\[\begin{equation} \begin{array}{ll} \underset{\bm{x}}{\textm{maximize}} & f(\bm{x}) - y^k g(\bm{x})\\ \textm{subject to} & \bm{x}\in\mathcal{X}, \end{array} \tag{B.6} \end{equation}\]
where the parameter \(y^k\) is sequentially updated as \(y^{k} = f(\bm{x}^{k})/g(\bm{x}^{k})\) with \(k\) the iteration index. This is summarized in Algorithm B.5.
Algorithm B.5: Dinkelbach method to solve the concave-convex FP in (B.4).
Choose initial point \(\bm{x}^0\);
Set \(k \gets 0\);
repeat
- Set \(y^{k} = f(\bm{x}^{k})/g(\bm{x}^{k})\);
- Solve the convex problem (B.6) and keep current solution as \(\bm{x}^{k+1}\);
- \(k \gets k+1\);
until convergence;
The Dinkelbach method can be shown to converge to the global optimum of the original concave-convex FP in (B.4) by carefully analyzing the increasingness of \(\{y^{k}\}\) and the function \(F(y) = \textm{arg max}_{\bm{x}} f(\bm{x}) - y g(\bm{x})\).
B.5.3 Charnes-Cooper-Schaible transform
We first consider the linear FP case and then move to the more general concave-convex FP.
Charnes-Cooper transform
One particular case of FP is when both \(f\) and \(g\) are linear as well as the constraint set, termed linear FP (LFP): \[\begin{equation} \begin{array}{ll} \underset{\bm{x}}{\textm{minimize}} & \begin{array}{c} \dfrac{\bm{c}^\T \bm{x} + d}{\bm{e}^\T \bm{x}+f}\end{array}\\ \textm{subject to} & \begin{array}[t]{l} \bm{G}\bm{x} \leq \bm{h},\\ \bm{A}\bm{x} = \bm{b}, \end{array} \end{array} \tag{B.7} \end{equation}\] with \(\textm{dom}\,f_{0}=\left\{ \bm{x} \mid \bm{e}^\T \bm{x} + f > 0\right\}.\)
Interestingly, the LFP in (B.7) can be transformed into the following LP via the Charnes-Cooper transform (Charnes and Cooper, 1962): \[\begin{equation} \begin{array}{ll} \underset{\bm{y},t}{\textm{minimize}} & \begin{array}{c} \bm{c}^\T\bm{y}+dt\end{array}\\ \textm{subject to} & \begin{array}[t]{l} \bm{G}\bm{y}\leq \bm{h}t\\ \bm{A}\bm{y}=\bm{b}t\\ \bm{e}^\T \bm{y} + ft = 1\\ t\geq0, \end{array} \end{array} \tag{B.8} \end{equation}\] from which the original variable \(\bm{x}\) can be easily recovered from \(\bm{y}\) and \(t\) as \(\bm{x} = \bm{y}/t\), see also (Bajalinov, 2003).
Proof. Define two new variables, \(\bm{y}\) and \(t\), related to the original variable \(\bm{x}\) in the LFP in (B.7) by \[ \bm{y} = \frac{\bm{x}}{\bm{e}^\T \bm{x}+f}\quad\textm{and} \quad t = \frac{1}{\bm{e}^\T \bm{x}+f}. \] Obviously, any feasible point \(\bm{x}\) in the original LFP in (B.7) leads to a feasible point \((\bm{y},t)\) in the LP in (B.8) with the same objective value. Conversely, any feasible point \((\bm{y},t)\) in the LP in (B.8) leads to a feasible point \(\bm{x}\) in the original LFP in (B.7) via \(\bm{x} = \bm{y}/t\), also with the same objective value: \[ \dfrac{\bm{c}^\T\bm{y}+dt}{1} = \dfrac{\bm{c}^\T\bm{y}+dt}{\bm{e}^\T \bm{y} + ft} = \dfrac{\bm{c}^\T\bm{y}/t+d}{\bm{e}^\T \bm{y}/t + f} = \dfrac{\bm{c}^\T\bm{x}+d}{\bm{e}^\T \bm{x} + f}. \]
Schaible transform
The Schaible transform, proposed in (Schaible, 1974), is a more general case of the Charnes-Cooper transform that rewrites the original concave-convex FP in (B.4) into the following convex problem: \[\begin{equation} \begin{array}{ll} \underset{\bm{y},t}{\textm{maximize}} & t f\left(\dfrac{\bm{y}}{t}\right)\\ \textm{subject to} & t g\left(\dfrac{\bm{y}}{t}\right) \le 1\\ & t \ge 0\\ & \bm{y}/t\in\mathcal{X}, \end{array} \tag{B.9} \end{equation}\] from which the original variable \(\bm{x}\) can be easily recovered from \(\bm{y}\) and \(t\) as \(\bm{x} = \bm{y}/t.\)
Proof. Define two new variables, \(\bm{y}\) and \(t\), related to the original variable \(\bm{x}\) in the FP in (B.4) by \[ \bm{y} = \frac{\bm{x}}{g(\bm{x})}\quad\textm{and} \quad t = \frac{1}{g(\bm{x})}. \] Any feasible point \(\bm{x}\) in the original FP in (B.4) leads to a feasible point \((\bm{y},t)\) in the convex problem (B.9) (in fact, satisfying \(t g\left(\bm{y}/t\right) = 1\)) with the same objective value. Conversely, any feasible point \((\bm{y},t)\) in (B.9) leads to a feasible point \(\bm{x}\) in the original FP in (B.4) via \(\bm{x} = \bm{y}/t\), also with the same objective value: \[ t f\left(\dfrac{\bm{y}}{t}\right) = \dfrac{f\left(\bm{x}\right)}{g\left(\bm{x}\right)}. \]
Observe that if instead of maximizing a concave-convex FP as in (B.4), we consider the minimization of a convex-concave FP, the Schaible transform similarly leads to the following convex problem: \[ \begin{array}{ll} \underset{\bm{y},t}{\textm{minimize}} & t f\left(\dfrac{\bm{y}}{t}\right)\\ \textm{subject to} & t g\left(\dfrac{\bm{y}}{t}\right) \ge 1\\ & t \ge 0\\ & \bm{y}/t\in\mathcal{X}. \end{array} \]