Outer space branching search method for solving generalized affine fractional optimization problem

1.   Introduction

The considered generalized affine fractional optimization problem is as follows:

where $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^{m}$, $e_{i}, d_{i}\in \mathbb{R}^{n}$, and $g_{i}, f_{i}$ are arbitrary real numbers. $p\geq2$, $Y$ is a nonempty compact set, $\sum\limits_{j = 1}^{n}e_{ij}y_{j}+f_{i}$ and $\sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}$ are all bounded linearity functions defined on $Y$, and for any $y\in Y$, the denominator $\sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}\neq 0, i = 1, 2, \ldots, p$.

As a class of special fractional optimization problems, the GAFOP has attracted the attention of many researchers and practitioners for decades. It has a variety of applications in many fields, including finance and investment ^[1,2,3], transportation planning ^[4,5], optimal design ^[6], estimation of iterative parameters ^[7], signal processing ^[8], data envelopment analysis and others ^{[9,10,11,12,13,14,15,16,17]}. Furthermore, since the GAFOP may be not (quasi)convex, there may exist many local optimal solutions, many of which fail to be global solutions. Hence, it is still of great significance to propose an effective global algorithm to solve the GAFOP.

Some algorithms have been presented to globally solve the GAFOP over the past several decades: for instance, the cutting plane algorithm ^[18], branch-relaxation-bound methods ^[19,20], the interior-point algorithm ^[21], the partial linearization algorithm ^[22], the monotonic optimization method ^[23], the method of centers ^[24] and the prox-regularization method ^[25]. Recently, based on the Dinkelbach type algorithm, Ghazi and Roubi ^[26] presented a difference of convex functions (DC) method for globally solving the generalized convex fractional optimization problem. By utilizing the proximal bundle theory, Boualam and Roubi ^[27] proposed a dual method for the generalized convex fractional optimization problem. Jiao et al. ^[28] designed an image space branch-and-bound algorithm for solving minimax linear fractional programs. Haffari and Roubi ^[29] described a prox-dual regularization method for globally solving generalized fractional programs. By utilizing convex hull and concave hull approximation of a bilinear function, Jiao and Li ^[30] put forward a novel algorithm for globally addressing min-max linear fractional programs. However, the previous reviewed methods can only solve a particular form of the GAFOP, or they are difficult to use to solve large-scale practical problems. Therefore, there remains the necessity to propose a practical algorithm to solve the GAFOP.

In addition to the methods reviewed above, some theoretical progress on the generalized fractional optimization problem (GFOP) has also been made. For example, Ahmad and Husain ^[31] gave a duality theory for a non-differentiable GFOP with generalized convexity. Schmitendorf ^[32] presented some optimality conditions for the GFOP. By utilizing the optimality condition, Tanimoto ^[33] gave a dual problem for a class of non-differentiable GFOP and derived the duality theorems. Yadav and Mukherjee ^[34] gave a duality theory for GFOP. When the data in the system are uncertain, Jeyakumar et al. ^[35] put forward a strong duality theorem for the robust GFOP. Based on unconstrained conditions, Lai et al. ^[36] gave the duality theorem for the GFOP. For a detailed review of the methods and theories for the GFOP, readers can refer to Stancu-Minasian ^[37,38].

In this article, an outer space branching search method is designed for globally solving the GAFOP. We first convert the GAFOP into the EP. Next, by utilizing the structural characteristics of the EP, we construct a new linearizing method for establishing the LRP of the EP. Compared with the known existing algorithms, the branching search of the presented algorithm occurs in the outer space $\mathbb{R}^{p}$ rather than the variable dimension space $\mathbb{R}^{n}$, which provides the possibility of mitigating the required computational efforts of the algorithm. In addition, the numerical computational results are reported, indicating that the proposed algorithm has higher efficiency and notable superiority compared to the known existing algorithms ^[19,39,40].

The remainder of this article is organized as follows. We derive the EP of the GAFOP and establish the LRP of the EP in Section 2. In Section 3, we give an outer space branching search method for globally solving the GAFOP, and we also analyze the global convergence of the algorithm. Numerical results for some test examples from recent studies are presented in Section 4. Finally, Section 5 gives some conclusions.

2.   Linear relaxation programming problem

In the following, to solve the GAFOP, we first transform the GAFOP into the EP. Then, we present a novel linearization technique and construct the LRP of the EP. For this purpose, for each $i = 1, \ldots, p,$ we introduce the additional variables $z_{i} = \sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}$. By computing the minimum value $\underline{z}_{i}^{0} = \min\limits_{y\in Y}\sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}$ and the maximum value $\overline{z}_{i}^{0} = \max\limits_{y\in Y}\sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}$ of the linear function $\sum\limits_{j = 1}^{n}c_{ij}y_{j}+h_{i}$ over $Y$, an initial outer space rectangle $Z^{0} = \{z\in \mathbb{R}^{p}\mid \underline{z}_{i}^{0}\leq z_i\leq \overline{z}_{i}^{0}, \ i = 1, \ldots, p\},$ can be constructed. By introducing the new variable $r = \max \bigg\{\frac{\sum\limits_{j = 1}^{n}e_{1j}y_{j}+f_{1}}{z_{1}}, \frac{\sum\limits_{j = 1}^{n}e_{2j}y_{j}+f_{2}}{z_{2}}, \ldots, \frac{\sum\limits_{j = 1}^{n}e_{pj}y_{j}+f_{p}}{z_{p}}\bigg\}$, we can simplify the objective function of the original problem GAFOP to $r$, so that we can get the EP of the GAFOP as below:

Theorem 1. $y^{*}$ is a global optimum solution of the GAFOP if and only if $(y^{*}, z^{*}, r^{*})$ is a global optimum solution of the EP, with

and

Additionally, the global optimal values of the GAFOP and EP are equal.

Proof. By the above discussion, the conclusions are obvious, and thus we omit the proof.

By Theorem 1, to globally solve the GAFOP, we can instead solve the EP. In the following, we only consider solving the EP.

For globally solving the EP, we need to establish its LRP for providing the lower bound in the branch-and-bound process. The detailed derivation process of the LRP is as follows.

For any $Z = \{z\in \mathbb{R}^{p}\mid \underline{z}_{i}\leq z_i\leq \overline{z}_{i}, \ i = 1, \ldots, p\}\subseteq Z^{0}$, we define

Obviously, for each $i = 1, \ldots, p$, we can see that

Based on (1), for any $Z \subseteq Z^{0}$, we can construct the LRP of the EP as below.

From the above discussion, it is known that all feasible points of the EP over the sub-rectangle $Z$ are also feasible for the LRP. Let $v$(EP) and $v$(LRP) be the global optimal values of the LRP and EP, respectively, and we have $v$(LRP) $\leq$ $v$(EP) over $Z^{k}$. Thus, the optimal value of the LRP will provide a valid lower bound for that of the EP over $Z$.

Next, we will prove that the optimal solution of the LRP will infinitely approximate the optimal solution of the EP over $Z$ as $\|\overline{z}-\underline{z}\|\rightarrow 0$, as detailed in Theorem 2.

Theorem 2. For each $i = 1, 2, \ldots, p$, consider the functions $\Phi_{i}(y, z_{i})$ and $\underline{\Phi}_{i}(y, \underline{z}_{i}, \overline{z}_{i})$. We have the following:

Proof. By the definitions of the functions $\Phi_{i}(y, z_{i})$ and $\underline{\Phi}_{i}(y, \underline{z}_{i}, \overline{z}_{i})$, for any $y\in Y$, $z_{i}\in [\underline{z}_{i}, \overline{z}_{i}]$, we have

Since $\sum\limits_{j = 1}^{n}|e_{ij}|y_{j}+|f_{i}|$ is a bounded linear function, we have

and complete the proof of the Theorem.

The above Theorem ensures that the function $\Phi_{i}(y, z_{i})$ will be infinitely approximated by the function $\underline{\Phi}_{i}(y, \underline{z}_{i}, \overline{z}_{i})$ as $\|\overline{z}-\underline{z}\|\rightarrow 0$, so the global optimal solution of the LRP will infinitely approximate the global optimal solution of the EP over $Z$ as $\|\overline{z}-\underline{z}\|\rightarrow 0$.

3.   Global algorithm and its convergence

In this section, we first put forward an outer space rectangle bisection method. Next, by combining the previous LRP and the branch-and-bound framework, an outer space branching search method is designed to globally solve the GAFOP. In addition, we derive the global convergence of the outer space branching search method.

3.1.   Outer space rectangle bisection method

The outer space rectangle bisection method iteratively subdivides the currently investigated rectangle into two sub-rectangles. Consider any selected sub-rectangle $Z = \{z\in \mathbb{R}^{p}|\underline{z}_{i}\leq z_{i}\leq \overline{z}_{i}, i = 1, 2, \ldots, p\}\subseteq Z^{0}$. The outer space rectangle bisection method is given as follows:

(ⅰ) Let $q = \arg\max\{\overline{z}_{i}-\underline{z}_{i} | i = 1, 2, \ldots, p\};$

(ⅱ) Let

and

Through utilizing the proposed outer space rectangle bisection method, the selected sub-rectangle $Z$ can be subdivided into two sub-rectangles $Z^{1}$ and $Z^{2}$.

3.2.   Outer space branching search method

In this subsection, the basic steps of the proposed outer space branching search method are formulated as follows.

Step 0. Let the convergence error $\epsilon\geq 0$, and let the initial outer space rectangle

Denote $F = \emptyset$ as the set of the initial feasible points, let $k = 0$, and let the set of all active nodes $\Omega_{0} = \{Z^{0}\}$.

Step 1. Solve the LRP over $Z^{0}$, and define $(y^{0}, z^{0}, r^{0})$ and $LB_{0}$ as its optimal solution and optimal value. Let

If $UB_{0}-LB_{0}\leq\epsilon$, then the proposed algorithm stops. $y^{0}$ and $(y^{0}, z^{0}, \hat{r}^{0})$ are $\epsilon$-optimal solutions of the GAFOP and EP over $(Z^{0})$, respectively. Otherwise, proceed with Step 2.

Step 2. Use the proposed rectangle bisection method to subdivide $Z^{k-1}$ into two sub-rectangles $Z^{k, 1}$ and $Z^{k, 2}$. Let $Q = \{Z^{k, 1}, Z^{k, 2}\}$.

Step 3. For each $Z^{k, t}, t = 1, 2$, compute the lower bound $LB(Z^{k, t})$ and $(y(Z^{k, t}), z(Z^{k, t}), r(Z^{k, t}))$ by solving the LRP over $Z^{k, t}$, and let

If $LB(Z^{k, t}) > UB_{k}$, then set $Q = Q\backslash Z^{k, t}$; else, let

If $UB_{k} = UB(Z^{k, t})$, then let $y^{k} = y(Z^{k, t})$ and $(y^{k}, z^{k}, \hat{r}^{k}) = (y(Z^{k, t}), z(Z^{k, t}), r(Z^{k, t}))$.

Step 4. Set $\Omega_{k} = (\Omega_{k-1}\backslash Z^{k-1})\bigcup Q$.

Step 5. Set $LB_{k} = \min\{LB(Z)| Z\in \Omega_{k}\}$, and let $Z^{k}$ be the sub-rectangle which satisfies $LB_{k} = LB(Z^{k})$.

If $UB_{k}-LB_{k}\leq \epsilon$, then the proposed algorithm stops. $y^{k}$ and $(y^{k}, z^{k})$ are the $\epsilon$-global optimal solutions of the GAFOP and EP, respectively.

Otherwise, set $k = k+1$, and go back to Step 2.

3.3.   Global convergence analysis

In this part, first of all, we define

Let $v$ be the global optimal value of the EP over $\Theta^{0}$, and define $r(y^{k}, z^{k})$ as the objective functional value of the EP corresponding to the feasible solution $(y^{k}, z^{k})$. The global convergence analysis of the proposed algorithm can be given by the following theorem.

Theorem 3. Given any $\epsilon\geq 0$, if the proposed algorithm finitely terminates after $k$ iterations, then $y^{k}$ is a global $\epsilon$-optimal solution to the GAFOP in the sense that

Otherwise, the proposed algorithm will generate an infinite sequence $\{y^{k}\}$, whose accumulation point will be a global optimum solution to the GAFOP.

Proof. If the presented algorithm finitely terminates after $k$ iterations, according to the termination of the algorithm, it follows that

By Step 3 of the presented algorithm, we can find a feasible solution $(y^{k}, z^{k})$ to the EP such that

Since $(y^{k}, z^{k})$ is feasible for the EP, we have

By using the above conclusions, we have

So, $(y^{k}, z^{k})$ is a global $\epsilon$-optimal solution of the EP, with

Thus, $y^{k}$ is a global $\epsilon$-optimum solution to the GAFOP.

If the presented algorithm does not finitely terminate, then it must produce an infinite feasible solution sequence $\{(y^{k}, z^{k})\}$, and the sequence $\{(y^{k}, z^{k})\}$ has a convergence subsequence. Therefore, we can let

So, we have

From the branch-and-bound structure of the algorithm, we also get

Since $y^{*}$ is a feasible solution of the GAFOP over $Z^{0}$, and due to Theorem 2, we can get

Combining the above inequalities, we have

Furthermore, by the equivalence of the GAFOP and EP, and the continuity of the function $\Lambda(y)$, we can conclude the following:

Based on the above inequalities (2) and (3), we have

Therefore, this implies that any accumulation point $y^{*}$ of the sequence $\{y^{k}\}$ is a globally optimum solution to the GAFOP. The proof is complete.

4.   Numerical comparisons

For verifying the computational superiority of the algorithm, the presented algorithm is implemented in the software MATLAB R2014a and solved on the same microcomputer with an Intel(R) Core(TM) i5-7200U CPU @2.50 GHz processor and 4 GB RAM.

We first tested some randomly generated Problem 1 with small-size variables, numerically compared them with the known existing algorithms ^[19,39,40] and listed these numerical comparison results in Table 1. Next, we tested some randomly generated Problem 1 with large-size variables to verify our algorithm further and listed the numerical results in Table 2. In Table 2, Avg.Iter represents the average iteration times and Avg.Time represents the average execution CPU time in seconds.

The maximum CPU time limit of all algorithms is set at $3600\; s$, and the approximation error is set as $\epsilon = 10^{-2}$. "$-$" denotes the situation in which the used algorithm failed to terminate in $3600\; s$. Since the known existing algorithms ^[19,39,40] failed to solve ten arbitrary randomly generated Problem 1 with large-size variables in $3600\; s$, we only list the numerical results obtained by our algorithm in Table 2.

We solved ten arbitrary randomly generated examples for all test problems. First of all, we tested the randomly generated Problem 1 with small-size variables. Table 1 shows the best results, worst results and average results among these ten test results, and we highlighted in bold the winners of these average results in their numerical comparison results in Table 1. Second, we solved the randomly generated Problem 1 with large-size variables, and numerical results are reported in Table 2.

From the computational results of Table 1, it can be seen that, when $p\geq 2, m\geq 10$, and $n\geq 6$, the algorithm of Feng et al. ^[19] failed to solve any one of ten randomly generated Problem 1 in $3600\; s$. When $p\geq 2, m\geq 10$, and $n\geq 10$, the algorithm of Wang et al. ^[39] failed to solve any one of ten randomly generated Problem 1 in $3600\; s$. When $p\geq 3, m\geq 10$, and $n\geq 20$, the algorithm of Jiao & Liu ^[40] failed to solve any one of ten randomly generated Problem 1 in $3600\; s$. However, in all cases, our algorithm can globally solve any one of ten randomly generated Problem 1. In addition, when $p\geq 2, m\geq 10$, and $n\geq 6$, compared with the known existing algorithms ^[19,39,40], our algorithm takes less running time and iterations. Thus, our algorithm has better computational superiority than the algorithms of Feng et al. ^[19], Wang et al. ^[39] and Jiao & Liu ^[40].

From the computational results of Table 2, it is obvious that the proposed algorithm can globally solve Problem 1 with large-size variables, and this demonstrates the strong robustness and the reliable stability of our algorithm.

Problem 1.

where $d_{ij}, e_{ij}, b_{k}, a_{kj}, i = 1, 2, \ldots, p, k = 1, 2, \ldots, m, j = 1, 2, \ldots, n,$ are all randomly generated in the interval $[0, 10]$; $g_{i}$ and $h_{i}, i = 1, 2, \ldots, p,$ are all randomly generated in the unit interval $[0, 1]$. The numerators $g_{i}$ and denominators $h_{i}$ of the linear fraction function in test Problem 1 are small constants.

Problem 2. ^[20]

Before executing the algorithm, by calculating the upper and lower bounds of $z$, we can obtain the initial rectangle $Z^{1} = Z = \{z\in \mathbb{R}^{2}\mid 1.7315\leq z_{1}\leq 1.9292, 8.8500\leq z_{2}\leq 9.5500\}$.

We set the approximation error as $\epsilon = 10^{-2}$, and a brief summary of the algorithm's solution steps for this problem is as follows.

Initialization. Solving the problem $LRP$ over $Z^{1}$ yields $LB_{1} = 1.3076$ and its optimal solution

Let $F^{1} = \big\{(y^{1}, z^{1}, r^{1})\big\}$ and $\Omega_{1} = \{Z^{1}\}$.

According to

Following this, the upper bound of the currently known optimal value can be found: $UB_{1} = 1.3478.$ Since $UB_{1}-LB_{1} > \epsilon$, the algorithm continues with the following iterations.

Iteration 1. Subdivide $Z^{1}$ into two sub-rectangles, compress the range of each sub-rectangle, and denote the remaining two sub-rectangles as follows:

and

Solving the problem $LRP$ over $Z^{1, 1}$ yields $LB_{Z^{1, 1}} = 1.3076$ and its optimal solution

and $UB_{Z^{1, 1}} = 1.3478.$

Solving the problem $LRP$ over $Z^{1, 2}$ yields $LB_{Z^{1, 2}} = 1.3657$ and its optimal solution

and $UB_{Z^{1, 2}} = 1.3478.$

Let $\Omega_{2} = \big\{Z^{1, 1}, Z^{1, 2}\big\}$, $F^{2} = F^{1}\cup\{(y^{Z^{1, 1}}, z^{Z^{1, 1}}, r^{Z^{1, 1}}), (y^{Z^{1, 2}}, z^{Z^{1, 2}}, r^{Z^{1, 2}})\}$ and the upper bound $UB_{2} = \min\{1.3478, 1.3478, 1.3478\} = 1.3478$. The currently best feasible solution $(y^{2}, z^{2}, r^{2}) = (y^{Z^{1, 1}}, z^{Z^{1, 1}}, r^{Z^{1, 1}})$, and the lower bound $LB_{2} = \min \{LB(Z)| Z\in \Omega_{2}\} = \min\{LB_{Z^{1, 1}}, LB_{Z^{1, 2}}\} = \min\{1.3076, 1.3657\} = 1.3076$.

Since $LB_{2} = LB_{Z^{1, 1}}$, let $Z^{2} = Z^{1, 1}$. Since $UB_{2}-LB_{2} > \epsilon$, continue to iteration 2.

Iteration 2. Consistent with the above, subdivide $Z^{2}$ into two sub-rectangles, compress the range of each sub-rectangle, and denote the remaining two sub-rectangles as follows:

and

Solving the problem $LRP$ over $Z^{2, 1}$ yields $LB_{Z^{2, 1}} = 1.3076$ and its optimal solution

and $UB_{Z^{2, 1}} = 1.3478.$

Solving the problem $LRP$ over $Z^{2, 2}$ yields $LB_{Z^{1, 2}} = 1.3293$ and its optimal solution

and $UB_{Z^{2, 2}} = 1.3625.$

Let $\Omega_{3} = \big\{Z^{1, 1}, Z^{2, 1}, Z^{2, 2}\big\}$, $F^{3} = F^{2}\cup\{(y^{Z^{2, 1}}, z^{Z^{2, 1}}, r^{Z^{2, 1}}), (y^{Z^{2, 2}}, z^{Z^{2, 2}}, r^{Z^{2, 2}})\}$ and the upper bound $UB_{3} = \min\{1.3478, 1.3478, 1.3625\} = 1.3478$. The currently best feasible solution $(y^{3}, z^{3}, r^{3}) = (y^{Z^{2, 1}}, z^{Z^{2, 1}}, r^{Z^{2, 1}})$, and the lower bound $LB_{3} = \min \{LB(Z)| Z\in \Omega_{3}\} = \min\{LB_{Z^{2, 1}}, LB_{Z^{2, 2}}\} = \min\{1.3076, 1.3293\} = 1.3076$.

Since $LB_{3} = LB_{Z^{2, 1}}$, let $Z^{3} = Z^{2, 1}$. Since $UB_{3}-LB_{3} > \epsilon$, continue to iteration 3.

Iteration 3. During this iteration, subdivide $Z^{3}$ into two sub-rectangles, compress the range of each sub-rectangle, and denote the remaining two sub-rectangles as follows:

and

Solving the problem $LRP$ over $Z^{3, 1}$ yields $LB_{Z^{3, 1}} = 1.4207$ and its optimal solution

and $UB_{Z^{3, 1}} = 1.3478.$

Solving the problem $LRP$ over $Z^{3, 2}$ yields $LB_{Z^{3, 2}} = 1.3242$ and its optimal solution

and $UB_{Z^{3, 2}} = 1.3478.$

Let $\Omega_{4} = \big\{Z^{3, 1}, Z^{3, 2}, Z^{2, 1}, \; \; Z^{2, 2}\big\}$, $F^{4} = F^{3}\cup\{(y^{Z^{3, 1}}, z^{Z^{3, 1}}, r^{Z^{3, 1}}), (y^{Z^{3, 2}}, z^{Z^{3, 2}}, r^{Z^{3, 2}})\}$, and the upper bound $UB_{3} = \min\{1.3625, 1.3478, 1.3478\} = 1.3478$. The currently best feasible solution $(y^{4}, z^{4}, r^{4}) = (y^{Z^{3, 2}}, z^{Z^{3, 2}}, r^{Z^{3, 2}})$, and the lower bound $LB_{4} = \min \{LB(Z)| Z\in \Omega_{4}\} = \min\{LB_{Z^{3, 1}}, LB_{Z^{3, 2}}\} = \min\{1.4207, 1.3242\} = 1.3242$.

Since $LB_{4} = LB_{Z^{3, 2}}$, let $Z^{4} = Z^{3, 2}$. Since $UB_{4}-LB_{4} > \epsilon$, continue to iteration 4.

Repeat the above iterative process, and the algorithm stops when $UB-LB\leq\epsilon$ is satisfied. The optimal solution $(y_{1}, y_{2}, y_{3}) = (1.0167, 0.5500, 1.4500)$ and optimal value $1.34783$ of the problem can be obtained after the algorithm executes 14 iterations.

5.   Conclusions

We study the GAFOP. By exploiting equivalent conversion and a new linearizing technique, the initial GAFOP is able to be converted into a series of LRPs. By integrating the outer space branching search method and the LRP, we put forward an efficient global algorithm for the GAFOP. In contrast to the known existing algorithms, our algorithm has the following computational superiority: (ⅰ) The branching search occurs in $\mathbb{R}^{p}$ outer space, which provides the possibility of mitigating the required computational efforts of the algorithm. (ⅱ) Numerical results demonstrate that our algorithm has superior efficiency compared to the known existing algorithms. Future work is to give a further improvement of our algorithm and extend our method to deal with the general nonlinear fractional optimization problem.

Acknowledgments

This paper is supported by the National Natural Science Foundation of China (11871196; 12071133; 12071112), the China Postdoctoral Science Foundation (2017M622340), the Key Scientific and Technological Research Projects in Henan Province (202102210147, 192102210114), the Science and Technology Climbing Program of the Henan Institute of Science and Technology (2018JY01), Henan Institute of Science and Technology Postdoctoral Science Foundation.

Conflict of interest

The authors declare that they have no conflicts of interest.