Global optimization algorithm for a class of linear ratios optimization problem

1.   Introduction

Consider the following sum of linear ratios optimization problem defined by

where $p\geq2$, $A$ is a $m\times n$ order real matrix, $b$ is a $m$ dimension column vector, $D$ is a nonempty bounded polyhedron set, $c_{ij}, f_{i}, d_{ij}$, and $g_{i}\in R, i = 1, 2, \ldots, p, j = 1, 2, \ldots, n,$ and for any $x\in D$, $\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\neq 0$.

The problem (FP) has attracted the attention of many researchers and practitioners for decades. One reason is that the problem (FP) and its special form have a wide range of applications in computer vision, portfolio optimization, information theory, and so on ^[1,2,3]. Another reason is that the problem (FP) is a global optimization problem, which generally has multiple locally optimal solutions that are not globally optimal. In the past several decades, many algorithms have been proposed for globally solving the problem (FP) and its special form. According to the characteristics of these algorithms, they can be classified into the following categories: Parametric simplex algorithm ^[4], image space analysis method ^[5], monotonic optimization algorithm ^[6], branch-and-bound algorithms ^{[7,8,9,10,11]}, polynomial-time approximation algorithm ^[12], etc. Jiao et al. ^[13,14] presented several branch-and-bound algorithms for solving the sum of linear or nonlinear ratios problems; Huang, Shen et al. ^[15,16] proposed two spatial branch and bound algorithms for solving the sum of linear ratios problems; Jiao et al. ^[17] designed an outer space methods for globally solving the min-max linear fractional programming problem; Jiao et al. ^{[18,19,20,21]} proposed several outer space methods for globally solving the generalized linear fractional programming problem and its special forms. In addition, several novel optimization algorithms ^[22,23,24] are also proposed for the fractional optimization problems. However, the above-reviewed methods are difficult to solve the problem (FP) with large-size variables. So it is still necessary to put forward a new algorithm for the problem (FP).

In this paper, based on the branch-and-bound framework, the new linearizing technique, and the image space region reduction technique, an image space branch-and-bound algorithm is proposed for globally solving the problem (FP). Compared with some methods, the algorithm has the following advantages. First, the branching search takes place in the image space $R^{p}$ of ratios, than in space $R^{n}$ of variable $x$, and $n$ usually far exceeds $p$, this will economize the required computations. Second, based on the characteristics of the problem (EP1) and the structure of the algorithm, an image space region reduction technique is proposed for improving the convergence speed of the algorithm. Third, the computational complexity of the algorithm is analyzed and the maximum iterations of the algorithm are estimated for the first time, which are not available in other articles. In addition, numerical results indicate the computational superiority of the algorithm. Finally, a practical application problem in education investment is solved to verify the usefulness of the proposed algorithm.

The structure of this paper is as follows. In Section 2, we give the equivalent problem (EP1) of problem (FP) and its linear relaxation problem (LRP). In Section 3, an image space branch-and-bound algorithm is presented, the convergence of the algorithm is proved, and its computational complexity is analysed. Numerical results are reported in Section 4. A practical application from education investment problem is solved to verify the usefulness of the algorithm in Section 5. Finally, some conclusions are given in Section 6.

2.   Equivalent problem and its linear relaxation

To find a global optimal solution of the problem (FP), we need to transform the problem (FP) into the equivalent problems (EP) and (EP1). Next, the fundamental assignment is to globally solve the problem (EP1). To this end, for each $i = 1, 2, \ldots, p,$ we need to compute the minimum value $\alpha_{i}^{0} = \min\limits_{x\in D}\frac{\sum_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x_{j}+g_{i}}$ and the maximum value $\beta_{i}^{0} = \max\limits_{x\in D}\frac{\sum_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x_{j}+g_{i}}$ of each linear ratio $\frac{\sum_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x_{j}+g_{i}}$. Next, we first consider the following linear fractional programs:

Since any linear ratio is quasi-convex, the problem (1) can attain the minimum value at some vertex of $D$. Since $\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\neq 0$, without losing generality, we can suppose that $\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i} > 0$. Thus, for solving the problem (1), for any $i\in \{1, 2, \ldots, p\}$, let $t_{i} = \frac{1}{\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}}$ and $z_{j} = t_{i}x_{j}$, then the problem (1) can be converted into the following linear programming problems:

Obviously, if $x^{*}$ is a global optimal solution of the problem (1), then if and only if $(z^{*}, t_{i}^{*})$ is a global optimal solution of the problem (2) with $z^{*} = t_{i}^{*}x^{*}$, and the problems (1) and (2) have the same optimal value. Therefore, $\alpha^{0}_{i}$ can be obtained by solving a linear programming problem (2). Similarly, we can compute the maximum value $\beta_{i}^{0}$ of each linear ratio over $D$.

Let $\Omega^{0} = \{\omega\in R^{p}\mid \alpha_{i}^{0}\leq \omega_i\leq \beta_{i}^{0}, \ i = 1, 2, \ldots, p\}$ be the initial image space rectangle, so we can get the equivalent problem (EP) of the problem (FP) as follows:

Obviously, let $\omega_i^* = \frac{\sum\limits_{j = 1}^{n}c_{ij}x^{*}_{j}+f_{i}}{\sum\limits_{j = 1}^{n}d_{ij}x^{*}_{j}+g_{i}}, \ i = 1, 2, \ldots, p$, if $x^*$ is a global optimal solution to the problem (FP), then $(x^*, \omega^*)$ is a global optimal solution to the problem (EP); conversely, if $(x^*, \omega^*)$ is a global optimal solution to the problem (EP), then $x^*$ is a global optimal solution to the problem (FP). Furthermore, from $\sum\limits_{j = 1}^{n}d_{ij}x_{j}+g_{i}\neq 0$, the problem (EP) can be reformulated as the following equivalent problem (EP1).

In the following, for globally solving the problem (EP1), we need to construct its linear relaxation problem, which can offer a reliable lower bound in the branch-and-bound searching process. The detailed deriving process of the linear relaxation problem is given as follows.

For any $x\in D$ and $\omega\in\Omega = \{\omega\in R^{p}\mid \alpha_{i}\leq \omega_i\leq \beta_{i}, \ i = 1, 2, \ldots, p\}\subseteq\Omega^{0}$, we have

and

Consequently, we can construct the linear relaxation problem $({\rm{LP}}_{\Omega})$ of the problem (EP1) over $\Omega$ as follows, which is a linear programming problem.

For any $\Omega = \{\omega\in R^{p}\mid \alpha_{i}\leq \omega_i\leq \beta_{i}, i = 1, 2, \ldots, p\}\subseteq\Omega^{0}$, by the constructing method of the problem $({\rm{LP}}_{\Omega})$, all feasible points of the problem (EP1) over $\Omega$ are always feasible to the problem $({\rm{LP}}_{\Omega})$, and the optimal value of the problem $({\rm{LP}}_{\Omega})$ is less than or equal to that of the problem (EP1) over $\Omega$. Thus, the optimal value of the problem $({\rm{LP}}_{\Omega})$ can provide a valid lower bound for that of the problem (EP1) over $\Omega$.

Without losing generality, for any $\Omega = \{\omega\in R^{p}\mid \alpha_{i}\leq \omega_i\leq \beta_{i}, \ i = 1, 2, \ldots, p\}\subseteq\Omega^{0}$, define

then we have the following Theorem 1.

Theorem 1. For any $i\in\{1, 2, \ldots, p\},$ let $\psi_{i}(x, \omega_{i}), \underline{\psi}_{i}(x, \omega_{i})$ and $\overline{\psi}_{i}(x, \omega_{i})$ be defined in the former, and let $\Delta \omega_{i} = \beta_{i}-\alpha_{i}$. Then, we have:

$Proof.$ By the definitions of the $\overline{\psi}_{i}(x, \omega_{i})$, $\underline{\psi}_{i}(x, \omega_{i})$ and $\psi_{i}(x, \omega_{i})$, we can get that

which implies that

Similarly, we also have

which implies that

The proof is completed.◇

From Theorem 1, the functions $\underline{\psi}_{i}(x, \omega_{i})$ and $\overline{\psi}_{i}(x, \omega_{i})$ will infinitely approximate the function $\psi_{i}(x, \omega_{i})$ as $\|\beta-\alpha\|\rightarrow 0$, which ensures that the problem (LP$_{\Omega}$) will infinitely approximate the problem (EP1) over $\Omega$ as $\|\beta-\alpha\|\rightarrow 0$.

3.   Algorithm and its computational complexity

In this section, based on the branch-and-bound framework, the linear relaxation problem, and the image space region reduction technique, we propose an image space branch-and-bound algorithm for globally solving the problem (FP).

3.1.   Image space region reduction technique

To improve the convergence speed of the algorithm, for any investigated image space rectangle $\Omega^{k}$, without losing the global optimal solution of the problem (EP1), the region reduction technique aims at replacing $\Omega^{k}$ by a smaller rectangle $\bar{\Omega}^{k}$ or judging that the rectangle $\Omega^{k}$ does not contain the global optimal solution of problem (EP1). For this purpose, let $\hat{\Phi}^{k} = \sum\limits_{i = 1}^{p}\alpha_{i}^{k},$ then the smaller rectangle $\bar{\Omega}^{k}$ can be derived by the following theorem.

Theorem 2. Let $UB_{k}$ be the best currently known upper bound at the $k_{th}$ iteration, for any rectangle $\Omega^{k} = [\alpha^{k}, \beta^{k}]\subseteq \Omega^{0}$, we have the following conclusions:

(ⅰ) If $\hat{\Phi}^{k} > UB_{k}$, then there exists no global optimal solution to the problem (EP1) over $\Omega^{k}$.

(ⅱ) If $\hat{\Phi}^{k}\leq UB_{k}$ and $\alpha_{\rho}^{k}\leq \tau_{\rho}^{k}\leq \beta_{\rho}^{k}$ for any $\rho \in \{1, 2, \ldots, p\}$, then there is no global optimal solution to the problem (EP1) over $\hat{\Omega}^{k}$ where

with

$Proof.$ For any $\Omega^{k} = [\alpha^{k}, \beta^{k}]\subseteq \Omega^{0}$, we consider the following two cases:

(ⅰ) If $\hat{\Phi}^{k} > UB_{k}$, then for any feasible solution $(\check{x}, \check{\omega})$ to the problem (EP1) over $\Omega^{k}$, the corresponding target function value $\Psi(\check{x}, \check{\omega})$ to the problem (EP1) over $\Omega^{k}$ satisfies that

Thus, there is no global optimal solution to the problem (EP1) over $\Omega^{k}$.

(ⅱ) If $\hat{\Phi}^{k}\leq UB_{k}$ and $\alpha_{\rho}^{k}\leq \tau_{\rho}^{k}\leq \beta_{\rho}^{k}$ for any $\rho \in \{1, 2, \ldots, p\}$, then for any feasible solution $(\check{x}, \check{\omega})$ of the problem (EP1) over $\hat{\Omega}^{k}$, we have

Thus, there exists no global optimal solution to the problem (EP1) over $\hat{\Omega}^{k}$.◇

From Theorem 2, the investigated image space rectangle $\Omega^{k}$ can be replaced by a smaller rectangle $\bar{\Omega}^{k} = \Omega^{k}\setminus\hat{\Omega}^{k}$ or judged that the rectangle $\Omega^{k}$ does not contain the global optimal solution of the problem (EP1).

3.2.   Image space branch-and-bound algorithm (Algorithm ISBBA)

Definition 1. Denote $x^{k}$ as a known feasible solution for problem (FP), and denote $v^{*}$ as the global optimal value for problem (FP), if $G(x^{k})-v^{*}\leq\varepsilon$, then $x^{k}$ is called as a global $\varepsilon-$optimum solution for problem (FP).

The basic steps of the proposed image space branch-and-bound algorithm are given as follows.

Step 0. Given the termination error $\varepsilon > 0$ and the initial rectangle $\Omega^{0}.$ Solve the problem $\left(\operatorname{LP}\left(\Omega^{0}\right)\right)$ to obtain its optimal solution $(x^{0}, \hat{\omega}^{0})$ and optimal value $\Psi\left(x^{0}, \hat{\omega}^{0}\right).$ Set $LB_{0} = \Psi\left(x^{0}, \hat{\omega}^{0}\right),$ let $\omega^{0}_{i} = \frac{\sum_{j = 1}^{n}c_{ij}x^{0}_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x^{0}_{j}+g_{i}}, i = 1, 2, \ldots, p, UB_{0} = \Psi\left(x^{0}, \omega^{0}\right).$ If $UB_{0}-LB_{0} \leq \varepsilon$, then stops, and $x^{0}$ is a global $\varepsilon$ -optimal solution to the problem (FP). Otherwise, let $F = \left\{\left(x^{0}, \omega^{0}\right)\right\}$ be the set of feasible points, and let $k = 0,$ $T_{0} = \left\{\Omega^{0}\right\}$ is the set of all active nodes.

Step 1. Using the maximum edge binding method of rectangles to subdivide $\Omega^{k}$ into two new sub-rectangles $\Omega^{k 1}$ and $\Omega^{k 2}$, and let $H = \left\{\Omega^{k 1}, \Omega^{k 2}\right\}$.

Step 2. For each rectangle $\Omega^{k\sigma}(\sigma = 1, 2),$ use the image space region reduction technique proposed in Section 3.1 to compress its range, and still denote the remaining region of $\Omega^{k\sigma}$ as $\Omega^{k\sigma}$, if $\Omega^{k\sigma}\neq\emptyset$, then solve the problem $\left(\operatorname{LP}\left(\Omega^{k\sigma}\right)\right)$ to obtain its optimal solution $(x^{\Omega^{k\sigma}}, \hat{\omega}^{\Omega^{k\sigma}})$ and optimal value $\Psi\left(x^{\Omega^{k\sigma}}, \hat{\omega}^{\Omega^{k\sigma}}\right).$ Let $LB\left(\Omega^{k\sigma}\right) = \Psi\left(x^{\Omega^{k\sigma}}, \hat{\omega}^{\Omega^{k\sigma}}\right),$ $\omega_{i}^{\Omega^{k\sigma}} = \frac{\sum_{j = 1}^{n}c_{ij}x^{\Omega^{k\sigma}}_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x^{\Omega^{k\sigma}}_{j}+g_{i}}, i = 1, 2, \ldots, p$, and $F = F\bigcup\left\{\left(x^{\Omega^{k\sigma}}, \omega^{\Omega^{k\sigma}}\right)\right\}.$ If $UB_{k} < LB\left(\Omega^{k\sigma}\right),$ then let $H = H \backslash \Omega^{k \sigma}, F = F \backslash\{(x^{\Omega^{k \sigma}}, \omega^{\Omega^{k \sigma}})\}$ and $T_k = T_k \backslash\left\{\Omega^{k \sigma}\right\}$. Update the upper bound by $UB_{k} = \min_{(x, \omega) \in F} \Psi(x, \omega)$ and denote by $\left(x^{k}, \omega^{k}\right) = \arg\min_{(x, \omega) \in F} \Psi(x, \omega).$ Let $T_{k} = \left(T_{k}\backslash \Omega^{k}\right)\cup H$ and $LB_{k} = \min\left\{LB(\Omega) \mid \Omega \in T_{k}\right\}$.

Step 3. Set $T_{k+1} = \left\{\Omega\mid UB_{k}-LB(\Omega) > \varepsilon, \Omega\in T_{k}\right\}.$ If $T_{k+1} = \emptyset,$ then the algorithm stops with that $x^{k}$ is a global $\varepsilon$ -optimal solution to the problem (FP). Otherwise, select the rectangle $\Omega^{k+1}$ satisfying that $\Omega^{k+1} = \arg\min_{\Omega\in T_{k+1}} LB(\Omega),$ set $k = k+1,$ and return to Step 1.

3.3.   Global convergence analysis

In the following, we will discuss the global convergence of the algorithm.

Theorem 3. Let $v^{*}$ be the global optimal value of the problem (FP), Algorithm ISBBA either ends at the global optimal solution of the problem (FP) or generates an infinite sequence of feasible solutions so that its any accumulation point is the global optimal solution of the problem (FP).

$Proof.$ If Algorithm ISBBA is terminated finitely after $k$ iterations, then when Algorithm ISBBA is terminated, we obtain a better feasible solution $x^{k}$ of the problem (FP) and a better feasible solution $(x^{k}, \omega^{k})$ of the problem (EP) with $\omega^{k}_{i} = \frac{\sum_{j = 1}^{n}c_{ij}x^{k}_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x^{k}_{j}+g_{i}}, i = 1, 2, \ldots, p,$ respectively. By the termination conditions, the updating method of the upper bound, and the steps of Algorithm ISBBA, we can get the following inequalities:

By combining the above equalities and inequalities, we can get

Therefore, we can get that $x^{k}$ is an $\epsilon-$global optimal solution of the problem (FP).

If Algorithm ISBBA produces an infinite sequence of feasible solutions $\{x^{k}\}$ for the problem (FP) and an infinite sequence of feasible solutions $\{(x^{k}, \omega^{k})\}$ for the problem (EP) with $\omega^{k}_{i} = \frac{\sum_{j = 1}^{n}c_{ij}x^{k}_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x^{k}_{j}+g_{i}}, i = 1, 2, \ldots, p,$ respectively. Without losing generality, let $x^{*}$ be an accumulation point of $\{x^{k}\}$, we can get that $\lim\limits_{k\rightarrow \infty} x^{k} = x^{*}.$

By the continuity of the $\frac{\sum_{j = 1}^{n}c_{ij}x_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x_{j}+g_{i}}$, $\frac{\sum_{j = 1}^{n}c_{ij}x^{k}_{j}+f_{i}}{\sum_{j = 1}^{n}d_{ij}x^{k}_{j}+g_{i}} = \omega_{i}^{k}\in [\alpha_{i}^{k}, \beta_{i}^{k}], i = 1, 2, \ldots, p,$ and the exhaustiveness of the partitioning method, we can get that

Thus, $(x^{*}, \omega^{*})$ is a feasible solution for the problem (EP). Also since $\{LB_{k}\}$ is an increasing lower bound sequence satisfying that $LB_{k}\leq v^{*},$ we can follow that

Hence, by the method of updating upper bound and the continuity of $G(x)$, we can get that

From (3) and (4), we can get that

Therefore, any accumulation point $x^{*}$ of the infinite sequence $\{x^{k}\}$ of feasible solutions is a global optimal solution for the problem (FP), and the proof of the theorem is completed.◇

3.4.   Computational complexity of the algorithm

In this subsection, by analysing the computational complexity of Algorithm ISBBA, we estimate the maximum iteration times of Algorithm ISBBA. For convenience, we first define the size of a rectangle

as

Theorem 4. For any given termination error $\varepsilon > 0$, if there exists a rectangle $\Omega^{k}$, which is formed by Algorithm ISBBA at the $k_{th}$ iteration, and which is satisfied with $\delta(\Omega^{k})\leq \frac{\varepsilon}{p}$, then we have that

where $LB(\Omega^{k})$ represents the optimal value for the problem (LP($\Omega^{k}$)), and $UB_{k}$ represents the currently known best upper bound of the global optimal value of the problem (EP).

$Proof.$ Without loss of generality, assume that $(x^{k}, \hat{\omega}^{k})$ is the optimal solution of the linear relaxation programming (LP($\Omega^{k}$)), and let $\omega_{i}^{k} = \frac{\sum\limits_{j = 1}^{n}c_{ij}x_{j}^{k}+f_{i}}{\sum\limits_{j = 1}^{n}d_{ij}x_{j}^{k}+g_{i}}, i = 1, 2, \ldots, p,$ then $(x^{k}, \omega^{k})$ must be a feasible solution to the problem (EP($\Omega^{k}$)).

By utilizing the definitions of $UB_{k}$ and $LB(\Omega^{k})$, we have that

Thus, by steps of Algorithm ISBBA, we can follow that

Furthermore, from the above formula and $\delta (\Omega^{k})\leq \frac{\varepsilon}{p}$, we can get that

and the proof of the theorem is completed.◇

According to Step 3 of Algorithm ISBBA, from Theorem 4, if $\delta(\Omega^{k})\leq \frac{\varepsilon}{p}$, then it can be seen easily that the rectangle $\Omega^{k}$ will be deleted. Thus, if the sizes of all sub-rectangles $\Omega$ generated by Algorithm ISBBA meet $\delta(\Omega)\leq \frac{\varepsilon}{p}$, then Algorithm ISBBA will stop. The maximum iteration times of Algorithm ISBBA can be estimated by using Theorem 4, see Theorem 5 for details.

Theorem 5. Given the termination error $\varepsilon > 0$, Algorithm ISBBA can find an $\varepsilon$-global optimal solution to the problem (FP) after at most

iterations, where $\Omega^{0} = \{\omega\in R^{p}|\alpha^{0}_{i}\leq \omega_{i}\leq \beta^{0}_{i}, i = 1, 2, \ldots, p\}$.

$Proof.$ Without losing generality, we assume that the $i-$th edge of the rectangle $\Omega^{0}$ is continuously selected for dividing $\gamma_{i}$ times, and suppose that after $\gamma_{i}$ iterations, there exists a sub-interval $\Omega_{i}^{\gamma_{i}} = [\alpha_{i}^{\gamma_{i}}, \beta_{i}^{\gamma_{i}}]$ of the interval $\Omega_{i}^{0} = [\alpha_{i}^{0}, \beta_{i}^{0}]$ such that

From the partitioning process of Algorithm ISBBA, we have that

From (5) and (6), we can get that

i.e.,

Next, we let

Let $\Lambda_{1} = \sum\limits_{i = 1}^{p}\bar{\gamma}_{i}$, then after $\Lambda_{1}$ iterations, Algorithm ISBBA will generate at most $\Lambda_{1}+1$ sub-rectangles, denoting these sub-rectangles as $\Omega^{1}, \Omega^{2}, \ldots, \Omega^{\Lambda_{1}+1}$, which must meet

where $\delta(\Omega^{\Lambda_{1}}) = \delta(\Omega^{\Lambda_{1}+1}) = \max\{\beta_{i}^{\bar{\gamma}_{i}}-\alpha_{i}^{\bar{\gamma}_{i}}, i = 1, 2, \ldots, p\}$ and

Furthermore, put these $\Lambda_{1}+1$ sub-rectangles into the set $T_{\Lambda_{1}+1}$, i.e.,

By (5), we have that

Thus, by (8), Theorem 4, and Step 3 of Algorithm ISBBA, the sub-rectangles $\Omega^{\Lambda_{1}}$ and $\Omega^{\Lambda_{1}+1}$ have been examined clearly, which should be discarded from the partitioning set $T_{\Lambda_{1}+1}$. Next, the remaining sub-rectangles are placed in the set $T_{\Lambda_{1}}$, where

and the remaining sub-rectangles $\Omega^{t}\ (t = 1, \ldots, \Lambda_{1}-1)$ will be examined further.

Next, consider the sub-rectangle $\Omega^{\Lambda_{1}-1}$, by using the branching rule, we can subdivide the sub-rectangle $\Omega^{\Lambda_{1}-1}$ into two sub-rectangles $\Omega^{\Lambda_{1}-1, 1}$ and $\Omega^{\Lambda_{1}-1, 2}$, which satisfies that

and

Therefore, after $\Lambda_{1}+(2^{1}-1)$ iterations, the sub-rectangle $\Omega^{\Lambda_{1}-1}$ has been examined clearly. By (8), Theorem 4, and Step 3 of Algorithm ISBBA, $\Omega^{\Lambda_{1}-1}$ should be discarded from the partitioning set $T_{\Lambda_{1}}$. Furthermore, the remaining sub-rectangles will be placed in the set $T_{\Lambda_{1}-1}$, where

Similarly, after Algorithm ISBBA executed $\Lambda_{1}+(2^{1}-1)+(2^{2}-1)$ iterations, the sub-rectangle $\Omega^{\Lambda_{1}-2}$ has been examined clearly, and which should be discarded from the partitioning set $T_{\Lambda_{1}-1}$. Furthermore, the remaining sub-rectangles will be put into the set $T_{\Lambda_{1}-2}$, where

Reduplicate the above procedures, until all sub-rectangles $\Omega^{t}(t = 1, 2, \ldots, \Lambda_{1}+1)$ are completely eliminated from $\Omega^{0}$. Thus, by (7), after at most

iterations, Algorithm ISBBA will stop, and the proof of the theorem is completed. ◇

Remark 1. By Theorem 5, from the above complexity analysis of Algorithm ISBBA, the running time of Algorithm ISBBA is bounded by $2\Lambda T(m+2p, n+p)$ for finding an $\varepsilon$-global optimal solution for the problem (FP), where $T(m+2p, n+p)$ represents the time taken to solve a linear programming problem with $(n+p)$ variables and $(m+2p)$ constraints.

4.   Numerical experiments

In this section, we numerically compare Algorithm ISBBA with the software "BARON" ^[25] and the branch-and-bound-algorithm presented in Jiao & Liu ^[10], denoted by Algorithm BBA-J. All used algorithms are coded in MATLAB R2014a, all test problems are solved on the same microcomputer with Intel(R) Core(TM) i5-7200U CPU @2.50GHz processor and 16 GB RAM. We set the maximum time limit for all algorithms to $4000$ seconds. These test problems and their numerical results are listed as follows.

Test Problem 1 is a problem with large-size variables, with the given termination error $\epsilon = 10^{-2}$, numerical comparisons among Algorithm ISBBA, BBA-J, and BARON are listed in Table 1, respectively. Test Problem 2 is a problem with the large-size number of ratios, with the given termination error $\epsilon = 10^{-3}$, numerical comparisons among Algorithm ISBBA and BARON are listed in Table 2, respectively. For test Problems 1 and 2, we solved arbitrary ten independently generated test examples and recorded their best, worst, and average results among these ten test examples, and we highlighted in bold the winners of average results in their numerical comparisons. What needs to be pointed out here is that "$\star$" represents that the used algorithm failed to terminate in $4000s$. From the numerical results for Problem 1 in Table 1, first, we see that the software BARON is more time-consuming than Algorithm ISBBA, though the number of iterations for BARON is smaller than Algorithm ISBBA. Second, in terms of computational performance, Algorithm ISBBA outperforms Algorithm BBA-J. Especially, when we fixed $m = 100$, let $p = 2$ and $n = 8000, 10000$ or $20000$, or let $p = 3$ and $n = 8000$, BARON failed to terminate in $4000s$ for all arbitrary ten independently generated test examples; when we fixed $m = 100$, let $p = 3$ and $n = 8000$, Algorithm BBA-J and BARON all failed to terminate in $4000s$ for all arbitrary ten independently generated test examples, but in all cases, Algorithm ISBBA can globally solve all arbitrary ten independently generated test examples.

From the numerical results for Problem 2 in Table 2, we can see that when we fixed $p = 10$ and $n = 500$, or $p = 15$ and $n = 500$, or $p = 20$ and $n = 400$, the software BARON failed to terminate in $4000s$ for all arbitrary ten independently generated examples, but Algorithm ISBBA can successfully find the globally optimal solutions of all arbitrary ten independently generated tests. It should be noted that, when $p$ is larger for Problem 2, Algorithm BBA-J failed to solve all arbitrary ten tests in $4000s$. Therefore, we just report the computational comparisons among Algorithm ISBBA and BARON in Table 2, this indicates the robustness and stability of Algorithm ISBBA.

Problem 1.

where $c_{ij}, d_{ij}, f_{i}$, and $g_{i}\in R, i = 1, 2, \ldots, p$; $A\in R^{m\times n}$, $b\in R^{m}$; $c_{ij}$, $d_{ij}$, and all elements of $A$ are all randomly generated from $[0, 10]$; all elements of $b$ are equal to $10$; $f_{i}$ and $g_{i}, i = 1, 2, \ldots, p,$ are all randomly generated from $[0, 1]$.

Problem 2.

where $\gamma_{ij}, \xi_{i}, \delta_{ij}, \eta_{i}\in R$, $i = 1, 2, \ldots, p, j = 1, 2, \ldots, n;$ $A\in R^{m\times n}$, $b\in R^{m}$; all $\gamma_{ij}$ and $\delta_{ij}$ are randomly generated from $[-0.1, 0.1]$; all elements of $A$ are randomly generated from $[0.01, 1]$; all elements of $b$ are equal to $10$; all $\xi_{i}$ and $\eta_{i}$ satisfies that $\sum\limits_{j = 1}^{n}\gamma_{ij}x_{j}+\xi_{i} > 0$ and $\sum\limits_{j = 1}^{n}\delta_{ij}x_{j}+\eta_{i} > 0$.

5.   Application in education investment

Consider finding the optimal solution of the education investment problem, whose mathematical modelling can be given as below:

where $c_{ji}\ (j = 1, 2, \ldots, p, i = 1, 2, \ldots, n)$ is the $i-$th invested fund of the $j-$th education investment, $x_{i}\ (i = 1, 2, \ldots, n)$ is the investment percentage of the $i-$th education investment, $d_{ji}\ (j = 1, 2, \ldots, p, i = 1, 2, \ldots, n)$ is the $i-$th output fund of the $j-$th education investment.

The parameters of an education investment problem are given as below:

Using the presented algorithm in this article to solve the above problem, the global optimal solution can be obtained as below:

It is to say, the optimal investment percentage of these three kinds of education investment is $0.7286, 0.0000, 0.2714$, respectively.

6.   Conclusions

We study the problem (FP). Based on the image space search, the new linearizing technique, and the image space region reduction technique, we propose an image space branch-and-bound algorithm. In contrast to the existing algorithm, the proposed algorithm can find an $\epsilon$-approximate global optimal solution of the problem (FP) in at most $(2^{\sum\limits_{i = 1}^{p} \lceil \log_{2}\frac{p(\beta_{i}^{0}-\alpha_{i}^{0})}{\varepsilon}\rceil}-1)$ iterations. Numerical results show the computational superiority of the algorithm.

A potential field for future research lies in investigating the existence of analogous linear or convex relaxation problems with closed-form solutions in cases where both the numerators and denominators are nonlinear functions. Furthermore, there is also need to design an efficient algorithm for globally solving generalized nonlinear ratios optimization problems with non-convex feasible region, as well as for more general non-convex ratios optimization problems under uncertain variable environments.

Author contributions

All authors of this article have been contributed equally. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This paper is supported by the National Natural Science Foundation of China (12001167), the China Postdoctoral Science Foundation (2018M642753), the Key Scientific and Technological Research Projects in Henan Province (232102211085; 202102210147), the Research Project of Nanyang Normal University(2024ZX014).

Conflict of interest

The author declares no conflict of interest.