A nonlinear relaxation-strategy-based algorithm for solving sum-of-linear-ratios problems

1.   Introduction

Consider the following sum of linear ratios problem

where $p\geq2$, $c_i\in \mathbb{R}^n$, $d_i\in \mathbb{R}$, $e_i\in \mathbb{R}^n$, $f_i\in \mathbb{\mathbb{R}}$, $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^m$, ${\rm X}$ is a nonempty and bounded set. Besides, for any $x\in{\rm X}$, it is assumed that $e_i^{\top}x+f_i > 0$ ($i\in \{1, 2, \cdots, p\}$), which is without loss of generality (see ^[1,2]).

Over the years, many scholars have paid special attention to and studied algorithms for solving problem SLR. There are two main reasons for this. One is in the application, this problem has been widely appeared in the fields of economics ^[3], financial investment ^[4], portfolio ^[5,6] and system engineering ^[7], biodiversity conservation ^[8], network data envelopment analysis ^[9] and computer vision ^[10]. The other is in the theoretical research, except for some special cases ^[11], SLR is usually NP-hard ^[12], and its multiple local non-global solutions seriously interfere with the process of finding global optimal solutions. This property aggravates the difficulty of global optimization, so it is of great practical and theoretical significance to develop a new global optimization algorithm for SLR.

In general, there is a positive correlation between the difficulty of SLR and the magnitude of $p$. For a single linear fractional programming problem with $p = 1$ and the quasi-concavity (quasi-convexity) property of the objective function, Ozkok ^[13] proposes an iterative algorithm based on the $(\epsilon, \delta)$-definition of continuity; Charnes and Cooper adopts an ingenious method to transform the problem into a linear program ^[14]. When $p = 2$, Konno et al. ^[15] developed a parameter-based simplex method to solve the problem, while the branch-and-bound (B&B) algorithm based on wave-curve bounds proposed by Xia et al. ^[16] can also solve such problem cases. For decades, there have been many effective algorithms for the SLR problem with $p > 2$, such as the interior point method ^[17], heuristic method ^[18], concave minimization method ^[19], polynomial time approximation algorithm ^[20], image-space analysis method ^[21], monotone method ^[22], outer approximation algorithm ^[23] and B&B algorithms ^{[24,25,26,27,28]}. Among these algorithms, the B&B algorithm is a classical global optimization method, which is often adopted to solve many difficult optimization problems. Most B&B algorithms for solving SLR are implemented by employing various equivalent transformations and establishing corresponding relaxation strategies. Also, other strategies are sometimes combined to design algorithms. For instance, Benson ^[24] proposed a B&B algorithm for SLR by combining simplex-based branching operations with Lagrangian dual-bound strategies. By combining the two techniques of B&B and plane cutting, Benson ^[25] also proposed a global algorithm, which adds linear cuts but does not compute newly generated vertices. Kuno and Masaki ^[10] and Carlsson and Shi ^[26] constructed two B&B algorithms based on the linear relaxation technique, but their branching operations are all performed in the $n$-dimensional decision space, so that the computational efficiency decreases with the increase of the number of variables. For solving generalized sum-of-ratio programming problems, Ashtiani and Paulo ^[29] presented a cut-plane algorithm combining a B&B technique with linear relaxation, whose branching operations are performed in the $2p$-dimensional output space. By transforming the SLR problem into an equivalent bilinear programming problem with bilinear constraints, Jiao and Liu ^[30], Liu and Ge ^[31] and Liu et al. ^[32] respectively proposed different linear relaxation strategies to simultaneously relax the objective and constraint functions, and designed different B&B algorithms whose branching operations take place in $p$-dimensional outer space. Recently, Jiao and Ma ^[33] proposed a new linear relaxation strategy based on the essential structure of each fractional function in ten different cases, from which a B&B algorithm was designed by combining the corresponding acceleration techniques and branching operations in $p$-dimensional outer space. To reduce the dimension of the outer space where branching operations are performed, Zhang et al. ^[1,2] designed two B&B algorithms based on Charnes–Cooper (CC) transformation ^[14] and different linear relaxation strategies, both of which branching operations occur in the $(p-1)$-dimensional outer space. Similarly, Shen et al. ^[34] also designed a B&B algorithm with branching operations in a $(p-1)$-dimensional space, but it incorporated a second-order cone programming (SOCP) relaxation technique. For a more detailed introduction of SLR and its generalized form, it is recommended to refer to the fractional programming bibliography ^[35].

In this paper, a novel B&B algorithm is developed for solving the SLR problem globally. Our main work is to reformulate the SLR problem into a new equivalent problem (EP) with an non-convex objective function and $(p-1)$ non-convex constraints by introducing intermediate variables. Thus, a new nonlinear relaxation strategy is proposed based on the relaxation of these non-convex constraints. According to the characteristics of the objective function of the relaxation subproblem, a corresponding acceleration technique is designed. It is noted that Zhang et al. ^[1,2] and Shen et al. ^[34] firstly employed CC transformation to reduce the number of linear fractions in SLR from $p$ to $(p-1)$, and thus proposed new B&B algorithms that execute branching processes in $(p-1)$-dimensional space. Differently, based on the new equivalent problem, we study the problem from another point of view, and finally propose a nonlinear relaxation. Through an artful transformation, the nonlinear relaxation subproblem is finally reconstructed into a SOCP problem. Compared with some existing B&B algorithms, our algorithm does not perform branching operations in $p$-, $2p$- or $n$-dimensional space, so it may greatly save computation when solving some SLR instances. Furthermore, the SLR problem we studied only assumes that the denominator of each fractional function is positive, instead of the positive denominator and non-negative numerator in ^[20,30,36]. Of course, the computational complexity of the proposed algorithm is derived in detail, and its analysis method is different from those in the existing literature (e.g., ^[1,33,34]). This estimates the maximum number of iterations for our algorithm as lowly as possible. Finally, the numerical results show that the algorithm is feasible and effective. Overall, our algorithm can solve all small and medium-sized SLR problems well, and is quite stable and effective for large-scale problems.

The rest of this paper is organized as follows: In Section 2, we give the relevant theories of the algorithm, which mainly includes the equivalent problem, bounding operation, branching operation, rectangle-region reduction technique, detailed steps and computational complexity. Section 3 introduces some test examples in the existing literature, and gives the computation results and numerical analysis. Finally, a positive review and outlook are given for the research of this paper.

2.   Theoretical framework

To solve the problem of SLR globally, this section mainly presents a new B&B algorithm based on a nonlinear relaxation strategy.

2.1.   Equivalent problem and its analysis

In this section, in order to solve the problem SLR based on the B&B algorithm, we need to propose a new equivalent problem for it. To this end, we reformulate the SLR as the following form:

by introducing a vector $\mu = (\mu_i, \mu_2, \cdots, \mu_{p-1})^{\top}\in \mathbb{R}^{p-1}$, $\alpha_i > 0$.

The equivalence between problems EP and SLR is given by the following theorem.

Theorem 1. A point $x^*\in \mathbb{R}^{n}$ is global optimal for the problem SLR if and only if $(x^*, \mu^*)\in \mathbb{R}^{n+p-1}$ is global optimal for the problem EP with $\mu_i^* = \frac{c_i^{\top}x^*+d_i}{e_i^{\top}x^*+f_i}+\alpha_i\left(\frac{e_i^{\top}x^*+f_i}{e_p^{\top}x^*+f_p}\right)$, $i = 1, \cdots, p-1$.

Proof. For each $i = 1, \cdots, p-1$, the univariate function $\mu_i$ is monotonically increasing as $\mu_i$ increases, so the conclusion of the theorem clearly holds. □

Theorem 1 illustrates that the problem ESLR can be addressed by solving the EP. At the same time, a partial component $x^*$ of the optimal solution $(x^*, \mu^*)$ of EP becomes the optimal solution of SLR. Thus, the study of problem EP will be focused.

It can be found that the objective function and constraints

of EP are non-convex, so that the non-convexity of the problem is currently reflected in these places. However, we only investigate the relaxation of these non-convex constraints, while the objective function will be simply linearized later. To do so, it is necessary to know the initial upper bound $\overline{\mu}_{i}^0$ and lower bound $\underline{\mu}_{i}^0$ of $\mu_i^*$ such that $\underline{\mu}_{i}^0\leq \mu_i^*: = \frac{c_i^{\top}x^*+d_i}{e_i^{\top}x^*+f_i}+\alpha_i\left(\frac{e_i^{\top}x^*+f_i}{e_p^{\top}x^*+f_p}\right)\leq\overline{\mu}_{i}^0$, and to construct an initial box $H_0: = \prod_{i = 1}^{p-1}\left[\underline{\mu}_{i}^0, \overline{\mu}_{i}^0\right]$. Hence, for each $i = 1, 2, \cdots, p-1$, the following problems need to be resolved:

It is imperative to note that subsequent to the adoption of CC transformation, the problems in Eqs (2.2) and (2.3) can be reformulated into corresponding linear programming problems, thereby facilitating their resolution. Then let

which satisfies $\underline{\mu}_{i}^0\leq \mu_i^*\leq\overline{\mu}_{i}^0$ for $i = 1, 2, \cdots, p-1$.

Based on the above discussion, it can be concluded that $(x^*, \mu^*)$ must satisfy $x^*\in {\rm X}$ and $\underline{\mu}_i^0\leq \mu^*_i\leq \overline{\mu}_i^0$ ($i = 1, 2, \cdots, p-1$). Next, for each $i = 1, 2, \cdots, p-1$, we multiply $\frac{e_i^{\top}x+f_i}{e_p^{\top}x+f_p}$ onto both sides of the constraint (2.1) to obtain the following equivalent nonlinear constraint:

By adding $\frac{(\mu_i)^2}{4\alpha_i}$ to both sides of Eq (2.5) and doing a simple arrangement, the inequality can be rewritten as:

Accordingly, EP is clearly equivalent to the following problem:

Suppose that $H = \prod_{i = 1}^{p-1}[\underline{\mu}_i, \overline{\mu}_i]$ denotes any sub-rectangle of $H_0$, i.e., $H\subseteq H_0$, then the subproblem of EP over $H$ can be formulated as follows:

Based on the characteristics of the B&B algorithm, we will propose a nonlinear relaxation strategy of the subproblem EP ($H$) for the execution of the bounding operation.

2.2.   Nonlinear relaxation strategy

In this section, we mainly relax EP ($H$) as a nonlinear relaxation programming (NLRP) problem that can provide a lower bound for the optimal value of EP ($H$) in the proposed algorithm.

Now, after linearizing a term on the right-hand side of each non-convex constraint (2.6), the corresponding nonlinear relaxation subproblem can be obtained. It is well known that the concave envelope of a univariate convex function $(\mu_i)^2$ over the interval $[\underline{\mu}_i, \overline{\mu}_i]$ can be formulated as

which necessarily satisfy

According to Eq (2.8), each of the above constraints (2.6) can be relaxed into:

Thus, EP ($H$) is finally relaxed as the following nonconvex program:

From Eq (2.8), it can be known that $\vartheta_i(\mu_i)$ is actually a linear upper approximation function of $(\mu_i)^2$ over $[\underline{\mu}_i, \overline{\mu}_i]$, which implies that the feasible region of EP ($H$) always does not exceed that of problem NLRP ($H$), so that the optimal value of the latter is never greater than that of the former. This clarifies that solving the NLRP ($H$) yields an effective lower bound on the optimal value of EP ($H$).

For each $i = 1, 2, \cdots, p-1$, if the positive fractional function $\frac{e_p^{\top}x+f_p}{e_i^{\top}x+f_i}$ is multiplied by the left and right sides of Eq (2.9), the following inequality can be obtained:

After comparing Eqs (2.1) and (2.10), the relaxation process essentially magnifies $0$ to $\frac{(e_p^{\top}x+f_p)(\vartheta_i(\mu_i)- (\mu_i)^2)}{4\alpha_i(e_i^{\top}x+f_i)}$, thus relaxing the feasible region of the problem EP ($H$). From the above relaxation process, it can be found that different values of $\alpha_i$ will lead to relaxation problems NLRP ($H$) with different compactness. When $H = H^0$, by the definition of $\underline{\mu}_i^0$ and $\overline{\mu}_i^0$ in Eq (2.4), the upper limit of constraint error in Eq (2.10) is closely related to the value of $\alpha_i$, i.e.,

Over the interval $(0, +\infty)$, the minimum value of the univariate function $\xi(\alpha_i)$ is reached at the point $\frac{\overline{\eta}_{i}-\underline{\eta}_{i}}{\overline{\varsigma}_{i}-\underline{\varsigma}_{i}}$. Consequently, under the condition of $\alpha_i = \frac{\overline{\eta}_{i}-\underline{\eta}_{i}}{\overline{\varsigma}_{i}-\underline{\varsigma}_{i}}$, when each non-convex constraint (2.1) is relaxed, the upper bound of the error between the optimal values of EP ($H^0$) and NLRP ($H^0$) can be minimized as much as possible. Therefore, throughout this paper, the value of each parameter $\alpha_i$ will always be $\frac{\overline{\eta}_{i}-\underline{\eta}_{i}}{\overline{\varsigma}_{i}-\underline{\varsigma}_{i}}$.

Also, it can be observed from Eqs (2.7), (2.8) and (2.10) that the rectangles corresponding to the variable $\mu$ can be directly branching and thinning, which forces the optimal values of NLRP ($H$) and EP ($H$) to gradually approach each other in the limiting sense.

2.3.   Solving problem NLRP ($H$)

Given a rectangle $H\subseteq H_0$, if the problem NLRP ($H$) is solvable, we notice that the problem cannot be solved directly by using the existing convex optimization solver, which is extremely inconvenient. However, NLRP ($H$) is implicitly convex and can be revealed as follows:

It is observed that the linear fractional factors in NLRP ($H$) have the same denominator $e_p^{\top}x+f_p$. By introducing the CC transformation: $t=\frac{1}{e_p^{\top}x+f_p}$ and $y=tx$, the problem can be transformed into the following convex problem:

Remark 1. Let ${\rm W} = \{(y, t)|e_p^{\top}y+f_pt = 1, \; Ay-bt\leq 0, \; t > 0\}$, for any $(y, t)\in {\rm W}$, it holds that $t > 0$ and $y/t\in {\rm X}$. Besides, for any $x\in {\rm X}$, let $t = \frac{1}{e_p^{\top}x+f_p}$, $y = tx$, it can be verified that $(y, t)\in {\rm W}$ and $\omega(y, t, \mu) = \psi(x, \mu)$. Therefore, we can obtain the optimal solution $(\frac{\hat{y}}{\hat{t}}, \hat{\mu})$ of NLRP ($H$) from the optimal solution $(\hat{y}, \hat{t}, \hat{\mu})$ of CP ($H$).

The problem CP ($H$) is well defined, as is stated in ^[1,14]. As a result, the conclusions in Remark 1 are obvious. Although CP ($H$) can be directly handled by some existing convex optimization solvers, since the quadratic term of each convex constraint is the square of a linear factor, the problem can be essentially rewritten as the following SOCP problem:

This problem can be solved directly by the solver coneprog in MATLAB(2023a), which can also be called a SOCP relaxation of EP ($H$).

2.4.   Branching rule of rectangle

Branching operation is essential in B&B algorithm.

In our algorithm, the branching rule of $H = \prod_{i = 1}^{p-1}[\underline{\mu}_i, \overline{\mu}_i]\subseteq H_0$ can be summarized as follows:

(ⅰ) Let $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa} = \max\{\overline{\mu}_{i}-\underline{\mu}_{i}:i = 1, 2, \cdots, p-1\}$, $z_{\kappa} = \frac{1}{2}(\underline{\mu}_{\kappa}+\overline{\mu}_{\kappa})$;

(ⅱ) By adopting $z_{\kappa}$, the interval $[\underline{\mu}_{\kappa}, \overline{\mu}_{\kappa}]$ corresponding to the $\kappa$-edge of $H$ is divided into two intervals $[\underline{\mu}_{\kappa}, z_{\kappa}]$ and $[z_{\kappa}, \overline{\mu}_{\kappa}]$, and then $H$ is subdivided into two sub-rectangles

Based on the above discussion, we can know that $H_1\cap H_2 = \{\mu\in \mathbb{R}^{p-1}|\mu_\kappa = z_\kappa\}$ and $H_1\cup H_2 = H$.

2.5.   Region reduction technique

In this subsection, a simple region reduction technique is mainly derived, so as to delete some or all regions in a sub-rectangle $H$ that cannot obtain the global optimal solution, which can reduce the explored child nodes or compress the search domain, thus accelerating the convergence speed of the B&B algorithm.

Without loss of generality, let $H = \prod_{i = 1}^{p-1}[\underline{\mu}_i, \overline{\mu}_i]\subseteq H _0$. Let $\overline{UB}$ denote the currently known best objective function value of problem EP.

For any feasible solution $(x, \mu)$ of EP($H$) worth being considered, it must satisfy

then for every $\iota = 1, 2, \cdots, p-1$, we define

where $\hat{\mu} = \min\limits_{x\in {\rm X}}\frac{c_p^{\top}x+d_p-\sum_{i = 1}^{p-1}\alpha_i(e_i^{\top}x+f_i)}{e_p^{\top}x+f_p}$.

If the global optimal solution $(x^*, \mu^*)$ of EP can be obtained by employing $H$, there must be a necessary condition:

which is the key to the following rectangular reduction theorem.

Theorem 2. If $\overline{\alpha}_\iota < \underline{\mu}_\iota$ for a $\iota\in\{1, 2, \cdots, p-1\}$, the problem EP cannot obtain the global optimal solution over the rectangle $H$; otherwise, if $\overline{\alpha}_\iota < \overline{\mu}_\iota$ for some $\iota\in\{1, 2, \cdots, p-1\}$, the global optimal solution cannot be obtained from $\overline{H}_\iota$, where

Proof. If there is a $\iota\in\{1, 2, \cdots, p-1\}$ such that $\overline{\alpha}_\iota < \underline{\mu}_\iota$, it follows that

which contradicts Eq (2.11), so that the former conclusion of the theorem holds. Further, if $\underline{\mu}_\iota\leq\overline{\alpha}_\iota < \overline{\mu}_\iota$ for some $\iota\in \{1, 2, \cdots, p-1\}$, it follows from $\mu = (\mu_1, \mu_2, \cdots, \mu_{p-1})^{\top}\in \overline{H}_\iota$ and the definition of $\overline{\alpha}_\iota$ that $\overline{\alpha}_\iota < \mu_\iota\leq\overline{\mu}_\iota$ and

for all $x\in {\rm X}, \; \mu\in \overline{H}_\iota$. This means that no element $\mu$ in $\overline{H}_\iota$ can be a component of the optimal solution $(x^*, \mu^*)$, i.e., $\mu^*\neq \mu$ for any $\mu\in \overline{H}_\iota$. So the proof of the theorem is complete. □

2.6.   SOCP relaxation based Branch-and-Bound Reduction Algorithm

To find the global optimal solution to the lifted problem EP, we construct a SOCP relaxation based branch-and-bound reduction algorithm (SOCPRBBRA) by adding the proposed convex relaxation, rectangular branching technique and rectangle-reduction rule to the B&B framework.

Remark 2. In this algorithm, the optimal solution $(\hat{x}, \hat{\mu})$ of the relaxation problem NLRP ($H$) is not necessarily feasible for EP, but it can be verified that $(\hat{x}, \mu^{\hat{x}})$ is feasible for EP when $\mu^{\hat{x}} = (\mu^{\hat{x}}_1, \mu^{\hat{x}}_2, \cdots, \mu^{\hat{x}}_{p-1})^{\top}$ with $\mu^{\hat{x}}_i = \frac{c_i^{\top}\hat{x}+d_i}{e_i^{\top}\hat{x}+f_i}+\frac{\alpha_i(e_i^{\top}\hat{x}+f_i)}{e_p^{\top}\hat{x}+f_p}$ is set, in which case $\phi(\hat{x}, \mu^{\hat{x}}) = \varphi(\hat{x})$ is found. Therefore, we can directly choose $\varphi(\hat{x})$ (if possible) to update the upper bound instead of $\phi(\hat{x}, \mu^{\hat{x}})$.

In the above algorithm, $k$ is adopted as the iteration index. At each iteration, one subproblem is selected and up to two new subproblems are created to replace the old one. The optimal value of the new subproblem will gradually improve compared with the old subproblem, and the corresponding upper and lower bounds will be updated, so that the gap between the upper and lower bounds will gradually decrease. Indeed, SOCPRBBRA can output a global $\epsilon$-optimal solution for the problem EP or SLR with a given tolerance $\epsilon > 0$. Here, we call $x^v \in {\rm X}$ a global $\epsilon$-optimal solution to SLR if $\varphi(x^v)\leq V({\rm SLR})+\epsilon$, where $V({\rm SLR})$ denotes the optimal value of SLR.

Theorem 3. Given a tolerance $\epsilon > 0$, when SOCPRBBRA runs to Step 1 of the $k$th iteration, if the subproblem $\{[H_k, UB(H_k)]\}$ satisfies $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa}\leq 4\sqrt{\frac{\epsilon}{N}}$ with $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa} = \max\{\overline{\mu}_{i}-\underline{\mu}_{i}:i = 1, 2, \cdots, p-1\}$, $N = \sum_{i = 1}^{p-1}\frac{1}{\alpha_i\underline{\varsigma}_i}$, the algorithm must terminate and output a global $\epsilon$-optimal solution to problem SLR.

Proof. Without loss of generality, denote $H_k$ as $H = \prod_{i = 1}^{p-1}[\underline{\mu}_i, \overline{\mu}_i]$, $LB^k$ as $LB$, and $UB^k$ as $UB$. Since $H$ is the selected rectangle to be divided, the following formula must be established:

Now, let $(\tilde{x}, \tilde{\mu})$ be an optimal solution of NLRP ($H$). We have

where $\hat{\mu} = (\hat{\mu}_1, \hat{\mu}_2, \cdots, \hat{\mu}_{p-1})^{\top}$ with $\hat{\mu}_i = \frac{c_i^{\top}\tilde{x}+d_i}{e_i^{\top}\tilde{x}+f_i}+\frac{\alpha_i(e_i^{\top}\tilde{x}+f_i)}{e_p^{\top}\tilde{x}+f_p}$. Furthermore, it follows from Eqs (2.7) and (2.8) that

Hence, from Eqs (2.12)–(2.14), it holds that

where $\underline{\varsigma}_{i}$ is defined in Eq (2.3). When $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa}\leq 4\sqrt{\frac{\epsilon}{N}}$, it follows from Eq (2.15) that

Since $LB = LB(H)$ is the smallest lower bound at the current iteration, it holds that

where $\mu^v = (\mu^v_1, \mu^v_2, \cdots, \mu^v_{p-1})^{\top}$ with $\mu^v_i = \frac{c_i^{\top}x^v+d_i}{e_i^{\top}x^v+f_i}+\frac{\alpha_i(e_i^{\top}x^v+f_i)}{e_p^{\top}x^v+f_p}$, $i = 1, 2, \cdots, p-1$. When $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa}\leq 4\sqrt{\frac{\epsilon}{N}}$, it follows from Eqs (2.16) and (2.17) that

which clarifies that $x^v$ and $(x^v, \mu^v)$ are global $\epsilon$-optimal solutions to problems SLR and EP, respectively. □

Theorem 3 shows that the optimal value of EP over each selected sub-rectangle and that of its relaxation problem NLRP ($H$) are gradually approaching in the limiting sense. This implies that the bounding and branching operations are consistent, so the B&B algorithm is theoretically globally convergent.

Now, let us analyze the complexity of SOCPRBBRA based on Theorem 3 and the iterative mechanism of this algorithm.

Theorem 4. Given a tolerance $\epsilon > 0$, the maximum number of iterations required by SOCPRBBRA to obtain a global $\epsilon$-optimal solution for SLR is

where $N = \sum_{i = 1}^{p-1}\frac{1}{\alpha_i\underline{\varsigma}_i}$.

Proof. When SOCPRBBRA terminates, either $k = 0$ or $k\geq1$. If $k = 0$, the algorithm does not enter the iteration loop. Thus, let us talk about the case where the algorithm terminates after many iterations.

At the case of $k\geq1$, it follows from Theorem 3 that $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa}\leq 4\sqrt{\frac{\epsilon}{N}}$ is essentially a sufficient condition for the termination criterion of the algorithm, $UB^k-LB^k\leq\epsilon$, to hold. Further, according to the rectangular branching rule in Step 2, a total of $k+1$ sub-rectangles are generated for the initial rectangle $H_0$. For convenience, we denote these subrectangles as $H_1, H_2, \cdots, H_{k+1}$, respectively. Obviously, $H_0 = \bigcup\limits_{\iota = 1}^{k+1}H_\iota$. In the worst case, suppose that the longest edge of each subrectangle $H_\iota: = \prod_{i = 1}^{p-1}[\underline{\mu}_{i}, \overline{\mu}_{i}]$ satisfies $\overline{\mu}_{\kappa}-\underline{\mu}_{\kappa}\leq 4\sqrt{\frac{\epsilon}{N}}$, where $\kappa\in\arg\max\{\overline{\mu}_{i}-\underline{\mu}_{i}:i = 1, 2, \cdots, p-1\}$. At this point, every edge $[\underline{\mu}_{i}, \overline{\mu}_{i}]$ of $H_\iota$ satisfies

which implies that the volume $Vol(H_\iota)$ of $H_\iota$ does not exceed the volume $Vol(\bar{H}_\iota)$ of a rectangle $\bar{H}_\iota$ with a unique edge length $4\sqrt{\frac{\epsilon}{N}}$. Thus, we have

Next, by combining Eq (2.20), we have

However, when Eq (2.19) holds and $k = \left\lfloor\prod_{i = 1}^{p-1}(\overline{\mu}_i^0-\underline{\mu}_i^0) \left(\frac{N}{16\epsilon}\right)^{(p-1)/2}\right\rfloor$, these $k+1$ sub-rectangles must be deleted in Step 4. Thus, the number of iterations at which SOCPRBBRA terminates is at most $\left\lfloor\prod_{i = 1}^{p-1}(\overline{\mu}_i^0-\underline{\mu}_i^0) \left(\frac{N}{16\epsilon}\right)^{(p-1)/2}\right\rfloor$. This completes the proof. □

Remark 3. Theorem 4 reveals that when SOCPRBBRA finds a global $\epsilon$-optimal solution for SLR, the computational time required is at most

seconds, where $T$ denotes the upper bounds of the time required to solve a SOCP problem SOCP ($H$) (see Section 2.3).

Remark 4. Theorem 4 sufficiently guarantees that SOCPRBBRA completes termination in a finite number of iterations because of the existence of this most extreme number of iterations.

3.   Numerical experiments

To verify the effectiveness and feasibility of SOCPRBBRA, we compared it with the algorithms in ^[1,2,31,33] and the commercial solver BARON ^[37]. The corresponding codes were compiled and run on Matlab(2023a) and a series of numerical experiments were performed. All calculations were carried out on a desktop computer with Win7 operating system and an Intel(R) Core(TM) i5-8500 3.00 GHz power processor and 8 GB of memory. Besides, all linear programming and second-order cone programming problems are addressed by linprog and coneprog solvers in Matlab.

In all experiments of solving the random instances generated by Problem 1, the same tolerance $\epsilon$ adopted by all algorithms is $10^{-6}$. For each set of parameters $(p, m, n)$, ten random instances of the same size are generated and solved by related algorithms, and the average numerical results are recorded in Tables 1 and 2. The symbols in the header line of these tables are interpreted as: CPU: The average CPU running time after solving ten test instances by an algorithm; Iter: the average number of iterations after solving ten test instances by an algorithm; Opt.val: the average optimal value after solving ten test instances by an algorithm.

Problem 1.

where all $d_{ij}$, $c_{ij}$, $b_k$ and $a_{kj}$ are randomly generated in [0, 10]; all $g_i$ and $h_i$ are randomly generated in [0, 1].

From the numerical results of Tables 1 and 2, all optimal values of SOCPRBBRA are not much different from other algorithms, especially compared with the commercial software package BARON. Moreover, SOCPRBBRA is optimal in both the number of iterations and CPU time, which reflects the excellent computational ability of our algorithm in solving the SLR problem.

A fact that can be observed from Table 1 is that BARON seems to be only suitable for solving some small-scale problems, and can clearly know that problems with $(p, m, n) = (2, 5, 2000), (2, 5, 3000), (2, 5, 5000), (3, 5, 2000)$ cannot be handled by the package within 3600s. Nevertheless, it is not difficult to find from Tables 1 and 2 that the number $p$ of fractions is a major factor affecting the computational performance of our algorithm. However, compared with the algorithms in ^[1,2,31,33], this effect is relatively small. Particularly, the numerical results in Table 2 reveal that the algorithm in ^[33] cannot handle problems with $(p, m, n) = (4,100,500), (4,140,700)$ and $(5,100,500)$ in 3600s. Thus, SOCPRBBRA is expected to become a potential solver for solving some specific SLR problems.

In summary, although the number of fractional terms affects the computational performance of SOCPRBBRA, the computational ability of the algorithm is stronger than that of BARON and the algorithms in ^[1,2,31,33] when solving specific SLR problems. Moreover, our algorithm may be more suitable for solving SLR problems with fewer linear fractional terms, especially for some large-scale problems.

4.   Conclusions

In this paper, we study the SLR problem. By employing a new equivalent transformation technique, SLR is transformed into the problem EP. Then we reconstruct and relax these non-convex constraints, so that the non-convex relaxation subproblem of EP is obtained. Furthermore, a new global optimization algorithm SOCPRBBRA is constructed by combining non-convex relaxations with B&B technique. The branching operations of the algorithm takes place in the space $\mathbb{R}^{p-1}$, rather than space $\mathbb{R}^{p}$, $\mathbb{R}^{2p}$ or $\mathbb{R}^{n}$, which greatly saves the computational workload of the algorithm. A large number of numerical results show that SOCPRBBRA not only has stronger computing power than the commercial software package BARON, but also has higher computational efficiency than the four existing B&B algorithms (i.e., algorithms in ^[1,2,31,33]) when solving some specific SLR problems. The future work is to extend our algorithm to generalized nonlinear fractional programming problems.

Author contributions

Bo Zhang: Formal analysis, investigation, resources, methodology, writing-original draft, validation, data curation, and funding acquisition; Yuelin Gao: Formal analysis, invesigation, writing-review & editing, software, data curation; Ying Qiao: Conceptualization, supervision, project administration; Ying Sun: Project administration, methodology, validation, and formal funding acquisition. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

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

Acknowledgments

This research is supported by the National Natural Science Foundation of China under Grant [grant number 12301401] and the Basic discipline research projects supported by Nanjing Securities [grant number NJZQJCXK202201].

Conflict of interest

All authors declare no conflicts of interest in this paper.