µ-extended fuzzy b-metric spaces and related fixed point results

1.   Introduction

In this paper, we consider the following sum of affine ratios problem (where SARP is sum of affine ratios problem):

where $A$ is an $m\times n$ order real matrix and $b$ is an $m$ dimension column vector. $D\neq\emptyset$, $c_{ij}, d_{ij}\in \mathbb{R}^{n}$, and $f_{i}, g_{i}\in \mathbb{R}$. The denominator of each ratio

over $D$. Due to

and the continuity of the ratio

we can obtain that

or

If

letting

it is obvious that

Therefore, without loss of generality, we assume that

always holds.

The SARP is a specific class of fractional programming problem. It has a wide range of applications in laminate manufacturing ^[1,2], portfolio optimization ^[3,4,5], finance and investment ^[6], computer vision ^[7], system engineering ^[8], information theory ^[9], material layout ^[10,11], and so on. In addition, it is obvious that the objective function of the SARP is neither quasi-convex nor quasi-concave, which is extremely challenging in terms of theory and computation. Thus, the research on the approach to solve the SARP has both theoretical and practical significance value.

Up to now, a number of methods have been developed to solve the SARP. On the basis of the characteristics of the algorithms in each literature, it can be roughly separated into the following categories: the parametric simplex methods ^[12,13], the unified monotonic approach ^[14], the interior-point method ^[15,16], the image space analysis method ^[17], the trapezoidal branching searching algorithm ^[18], the branch-and-bound algorithms ^[19,20,21], and so on. It should be noted that the algorithms in the above references ^[19,20,21] can either only solve special forms of the SARP or the SARP with fewer variables. Recently, by exploiting equivalent transformation and the characteristics of general single ratio functions, Jiao and Ma ^[22] combined the acceleration technique to develop an efficient outer space rectangular branch-and-bound algorithm. Jiao et al. ^[23] put forward a practical algorithm for minimizing the SARP. In the same year, by using the equivalent conversion and linearization method, Jiao et al. ^[24] presented an effective branch-and-bound algorithm for the SARP. Meanwhile, Jiao et al. ^[25] also designed an image space branch-reduction-bound algorithm for globally solving the SARP. It should be emphasized that references ^[23,24,25] proposed several outer space branch-and-bound algorithms for the problem (SARP), and the partitioning spaces of these branch-and-bound algorithms all occur in the $p$-dimensional outer space. In addition, Pei and Zhu ^[26] designed a convex relaxation algorithm for maximizing the sum of the difference of convex functions ratios problems based on the branch-and-bound framework. Kuno ^[27] presented a trapezoidal branch-and-bound algorithm to solve the SARP. Based on the algorithm of Kuno ^[27], Shen et al. ^[28] proposed an accelerating trapezoidal branch-reduction-bound algorithm for globally solving the sum of linear ratios problems. By constructing the new accelerating technique, Jiao and Liu ^[29] developed a branch-reduction-bound algorithm for the sum of quadratic ratios problems. Especially, the literatures ^[30,31] provided for the first time an outer space branch-relaxation-bound algorithm for generalized linear fractional programming problems and generalized affine multiple product programming problems, respectively. However, the above-reviewed methods only deal with some particular forms of the SARP or are difficult to solve the SARP with large-scale variables. Therefore, it is still necessary to propose a practical efficient algorithm for addressing the general form of the SARP.

The main purpose of this paper is to design an effective outcome space branch-and-bound algorithm to globally solve the SARP. Initially, we employ two equivalence conversions to transform the SARP into an equivalent problem ($\rm EP_{3}$). Subsequently, we design a linearization technique that is used to construct the affine relaxation problem (ARP) of the problem ($\rm EP_{3}$). Based on the ARP and the branch-and-bound framework, we present an outcome space branch-and-bound algorithm. Ultimately, the numerical experimental results demonstrate that our algorithm is feasible. In addition, the branch search process in this paper occurs in the $(p-1)$-dimensional outer space, which makes the computational cost much lower. Compared with other methods that take place in the $n$-dimension or $p$-dimensional space, our method is more efficient. Furthermore, the algorithm is shown to converge to a global optimal solution of the SARP eventually. Meanwhile, the computational complexity of the algorithm is deduced in detail.

The overall structure of the study adopts the format of six sections, including this introductory section. In Section 2, we convert the SARP to an equivalent problem ($\rm EP_{3}$) and construct its affine relaxation programming problem. In Section 3, we design an outcome space branch-and-bound algorithm for globally solving the SARP, prove the convergence of the algorithm, and derive the derivation of the computational complexity. In Section 4, a comparison of the numerical experimental results indicates that the presented algorithm is reliable. Finally, some concluding remarks are given in Section 5.

2.   Equivalence transformation and its affine relaxation programming

2.1.   Equivalent transformation

To tackle the SARP globally, we transform the original problem (SARP) into an equivalence problem as below. For each $x\in D$, let

and

By utilizing the well-known Charnes-Cooper transformation ^[32], the SARP can be rewritten as problem ($\rm EP_{1}$), as shown below.

At this time, the index set becomes $i\in\{1, 2, \ldots, p-1\}$, and let

where the set $\chi$ is non-empty and bounded.

Then we focus on the following equivalence conversion, for each $i\in\{1, 2, \ldots, p-1\}$, by introducing the variable

the lower bound

and upper bound

can be calculated, and we can obtain the initial rectangle

where

and

Further, the problem ($\rm EP_{1}$) can be reduced into the problem ($\rm EP_{2}$) by the variable $s_{i}$ as follows:

Remark 1. If $(t^{*}, z^{*})$ is a global optimal solution of the problem ($\rm EP_{1}$), then $(s^{*}, t^{*}, z^{*})$ is a global optimal solution of the problem ($\rm EP_{2}$) with

Conversely, if $(s^{*}, t^{*}, z^{*})$ is a global optimal solution of the problem ($\rm EP_{2}$), then $(t^{*}, z^{*})$ is a global optimal solution of the problem ($\rm EP_{1}$). In addition, the global optimal value of the problems ($\rm EP_{1}$), ($\rm EP_{2}$), and (SARP) are equal.

Based on

the problem ($\rm EP_{2}$) can be rewritten as the following equivalent form:

Define $S$ to be $S^{0}$ or a sub-rectangle of $S^{0}$, where

and

2.2.   Affine relaxation programming

For any $S\subseteq S^{0}$, we construct the affine relaxation programming problem of the problem ($\rm EP_{3}$) over $S$ as follows:

First, investigating the objective function, we can follow that

Hence, we reformulate the objective function of the problem ($\rm EP_{3}$) as

Next, investigating the constrained function, for any $i\in\{1, 2, \cdots, p-1\}, s \in S\subseteq S^{0}$, define

and

Clearly, for any $i\in \{1, 2, \ldots, p-1\}$, we have that

always hold.

Integrating (1)–(3), for any $i\in \{1, 2, \ldots, p-1\}$, the affine relaxation programming problem of the problem ($\rm EP_{3}$) over $S$ is constructed as below:

By the construction process of the ARP, it is obvious that the optimal solution of the ARP provides a valid lower bound for that of the $\rm EP_{3}$ over $S^{0}$.

Theorem 1. For each $i\in \{1, 2, \ldots, p-1\}$, we have

where "$\rightarrow$" means "approaching".

Proof. Based on the previous definitions of the functions $\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$, $\Psi_{i}(s_{i}, t, z)$, and $\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$, for any $(t, z)\in \chi, s_{i}\in [\underline s_{i}, \overline s_{i}]$, we have that

Since $\sum\limits_{j = 1}^{n}d_{ij}z_{j}+g_{i}t$ is a bounded function, we have

Similarly, we demonstrate

and the proof of the theorem is accomplished. □

From Theorem 1, it follows that the functions $\underline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ and $\overline{\Psi}_{i}(\underline s_{i}, \overline s_{i}, t, z)$ can infinitely approximate the function $\Psi_{i}(s_{i}, t, z)$ as $|\overline s_{i}-\underline s_{i}|\rightarrow 0$, which guarantees the global convergence of the outcome space branch-and-bound algorithm.

3.   Algorithm and its computational complexity

An outcome space branch-and-bound method is provided in this part to resolve the SARP based on the previous ARP. By resolving a series of ARPs over the initial rectangle $S^{0}$ or a partitioned sub-rectangle of $S^{0}$, the algorithm is able to acquire a global optimal solution. The simplest standard rectangle bisection rule, which is provided as follows, is designated in the proposed algorithm.

(1) Let

and

(2) Let

The rectangle $S^{k}$ is split by the point $\widehat{s}$ into the following two rectangles:

and

3.1.   Algorithm outline

The steps of the outcome space branch-and-bound algorithm for solving the SARP are described below:

Algorithm 1. Outcome space branch-and-bound algorithm.

Step 0. Given the convergence error $\epsilon\geq 0$ and the initial outer space rectangle

Solve the problem (ARP) over $S^{0}$. If the problem (ARP) over $S^{0}$ is not feasible, then the problem (SARP) is not feasible, and the proposed algorithm stops.

Otherwise, we can obtain an optimal solution $(\hat{s}^{0}, t^{0}, z^{0})$ and the optimal value $LB(S^{0})$ of the problem (ARP) over $S^{0}$. Let

then $(s^{0}, t^{0}, z^{0})$ is a feasible solution of the problem ($\rm EP_{3}$). Let

and

If

then the algorithm stops executing, and $(s^{0}, t^{0}, z^{0})$ and $\frac{z^{0}}{t^{0}}$ are the global $\epsilon$-optimal solutions of the problems ($\rm EP_{3}$) and (SARP), respectively.

Otherwise, denote by the set of all active nodes $\Theta_{0} = \{S^{0}\}$, denote by the set of the initial feasible point

let $k = 0$, and proceed to Step 1.

Step 1. Set

Using the former branching rule, subdivide $S^{k}$ into two sub-rectangles $S^{k1}$ and $S^{k2}$. Let

Step 2. For each

solve the problem (ARP) over $S^{k\tau}$. If the problem (ARP) over $S^{k, \tau}$ is not feasible, then delete the rectangle $S^{k\tau}$. Otherwise, we get the optimal solution $(\hat{s}(S^{k\tau}), t(S^{k\tau}), z(S^{k\tau}))$ and the optimal value $LB(S^{k\tau})$ of the problem (ARP) over $S^{k\tau}$.

If

then let

Otherwise, let

update the feasible point set by

let

and denote by the currently best feasible solution $(s^{k}, t^{k}, z^{k})$, which corresponds to $UB_{k}$.

Step 3. Set

update

and let $S^{k}$ be the sub-rectangle which satisfies

Step 4. If

then the proposed algorithm stops, and $\frac{z^{k}}{t^{k}}$ and $(s^{k}, t^{k}, z^{k})$ are the $\epsilon$-global optimal solutions of the problems (SARP) and ($\rm EP_{3}$), respectively.

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

3.2.   Convergence analysis

In this subsection, the global convergence of the proposed algorithm is discussed as follows:

Theorem 2. If Algorithm 1 ceases finite iterations, then the proposed algorithm will produce a globally optimal solution to the SARP. Otherwise, Algorithm 1 fails to terminate within a finite number of iterations, and it will produce an infinite sequence $\{x^{k}\}$ such that any accumulation point will be a global optimal solution of the SARP.

Proof. If Algorithm 1 ceases within a finite number of iterations, hypothesize that it is ceased at the $k_{th}$ iteration, denoted $LB_{k}$ as the current best lower bound, and denoted $UB_{k}$ as the current best upper bound, for any $\epsilon$, and we have that

Assume that $(s^{k}, t^{k}, z^{k})$ is a feasible solution of the problem ($\rm EP_{3}$) with that

Letting $\upsilon(\rm EP_{3})$ be the global optimal value of the problem ($\rm EP_{3}$), we can get

and

However, $(s^{k}, t^{k}, z^{k})$ is the feasible solution of the problem ($\rm EP_{3}$), and we can follow that

By the above inequalities (4)–(7), we can get

Therefore, $(s^{k}, t^{k}, z^{k})$ is an $\epsilon$-global optimum solution of the problem ($\rm EP_{3}$), and

is an $\epsilon$-global optimum solution of the SARP.

If Algorithm 1 fails to terminate within a finite number of iterations, then it will produce an infinite feasible solution sequence $\{x^{k}\}$ of the SARP and an infinite feasible solution sequence $(s^{k}, t^{k}, z^{k})$ of the problem ($\rm EP_{3}$) with

Letting $(t^{*}, z^{*})$ be an accumulation point of the sequence $\{(t^{k}, z^{k})\}$, we can get

By the continuity of the function

we can get that

Thus, $(s^{*}, t^{*}, z^{*})$ is a feasible solution of the problem ($\rm EP_{3}$).

Since $\Big\{LB_{k}\Big\}$ is a monotonic non-decreasing bounded sequence, we get that

and

and also since $\{UB_{k}\}$ is a non-increasing and bounded sequence, we get that

and

So, we have

Hence, from the termination condition of the algorithm, taking the limit on both side of the above inequalities, we get

Thus, the accumulation point $(s^{*}, t^{*}, z^{*})$ of the sequence ${(s^{k}, t^{k}, z^{k})}$ is a global optimal solution of the problem ($\rm EP_{3}$). At the same time, the accumulation point $x^{*}$ of the sequence $\{x^{k}\}$ with

is a global optimal solution of the SARP, and the proof is complete. □

Remark 2. The algorithm proposed in this paper is a rectangular branch-and-bound global optimization algorithm. As is well-known, based on the convergence theory of branch-and-bound global optimization algorithms ^[33], the exhaustiveness of the branching process and the approximation of upper and lower bounds indicate that the proposed rectangular branch-and-bound global optimization algorithm must be convergent.

3.3.   Computational complexity of the algorithm

Further, to examine the maximum number of iterations of Algorithm 1, we derive the computational complexity of Algorithm 1. First, we define the size $\Upsilon$ of the rectangle $S$ as

Theorem 3. Given a termination error $\epsilon > 0$, if there exists a rectangle $S$ formed by the proposed algorithm at the $k_{th}$ iteration satisfying

then we have that

where $LB(S)$ is the optimal value of the ARP over $S$, and $UB_{k}$ is the currently known best upper bound of the optimum value of the problem ($\rm EP_{3}$).

Proof. Without losing generality, suppose that $(t^{k}, z^{k})$ is the optimal solution of the ARP over $S$, and let

Then $(s^{k}, t^{k}, z^{k})$ is a feasible solution to the problem ($\rm EP_{3}$). By the method of updating the upper bound and lower bound, and the construction process of the ARP, we have that

By the definition of the size $\Upsilon(S)$ of the rectangle $S$ and

it follows that

The proof of Theorem 3 is complete.□

Then we can examine the maximum iterations of Algorithm 1, see the following Theorem 4:

Theorem 4. Given the convergent tolerance $\epsilon\in(0, 1)$, Algorithm 1 can acquire a global optimal solution of the SARP at most

iterations.

Proof. In general, we assume that the sub-rectangle $S$ is selected for partitioning in Algorithm 1 at each iteration. After $k\cdot(p-1)$ iterations, we can follow that

Based on the former proof of Theorem 3, if

i.e.,

we can follow that

Therefore, after at most

iterations, we can get

where $(s^{*}, t^{*}, z^{*})$ is the optimal solution of the problem ($\rm EP_{3}$), and $(s^{k}, t^{k}, z^{k})$ is the best currently know feasible solution for the problem ($\rm EP_{3}$). This implies that $(s^{k}, t^{k}, z^{k})$ is an $\epsilon$-global optimal solution of the problem ($\rm EP_{3}$) when Algorithm 1 terminates. At the same time, we can follow that $\frac{z^{k}}{t^{k}}$ is an $\epsilon$-global optimal solution of the SARP, and we complete the proof.□

Remark 3. From the above complexity analysis of the algorithm in Theorem 4, letting

the running time of Algorithm 1 is bounded by

for finding an $\epsilon$-global optimal solution of the SARP, where $T(m+2p+1, n+1)$ denotes the time taken to solve a linear programming problem with $n+1$ variables and $m+2p+1$ linear constraints.

4.   Numerical experiments

In this section, we numerically compare Algorithm 1 with some known extant branch-and-bound algorithms. All tests were implemented in MATLAB R2018a and run on a microcomputer with Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz processor and 8 GB RAM. For all test problems, we provide their computational results. The maximum time limit was set to $10000s$ for all algorithms.

First of all, some small-size certainty examples (see the Appendix Examples 1–12) were tested with Algorithm 1 for comparison with the known extant algorithms ^{[14,21,34,35,36,37,38,39,40]}, and a numerical comparison between some existing algorithms and Algorithm 1 on Examples 1–12 were reported in Table 1 with the given convergence tolerance, where some notations have been used for column headers: Opt. val.: global optimal value; Iter.: number of iterations of the algorithm; Time: the CPU execution time of the algorithm in seconds.

From the numerical results in Table 1, for Examples 2, 5, 6, 10 and 12, we can follow that Algorithm 1 can obtain the better global optimal solutions and optimal values than the existing algorithms of Jiao and Liu ^[39] and Shen and Lu ^[37]. Algorithm 1 performs better than the method of Jiao and Liu ^[39] for finding the optimal solution in less time and fewer iterations. Therefore, in terms of test Examples 1–12, their experimental results verify that Algorithm 1 is valid and feasible.

Next, we chose two large-scale test problems generated randomly to verify the proposed algorithm further, see Problems 1 and 2 for details. With the given approximation error $\epsilon = 10^{-2}$, we first tested Problem 1 with large-size variables, numerical comparisons among Algorithm 1, the algorithm of Jiao and Liu ^[39], and the algorithm of Li et al. ^[41], which are reported in Table 2.

In Tables 2 and 3, Avg.Iter denotes the average number of iterations of the algorithm, Avg.Time denotes the average execution CPU time of the algorithm in seconds, "$*$" denotes the situation that the proposed algorithm failed to terminate in $10000s$ for some of the arbitrary $50$ independently generated test examples. For random Problems 1 and 2, we solved $50$ independently generated test instances and recorded their average results among these $50$ tests, and we highlighted in bold the winner of average results in numerical comparisons.

Problem 1. (Li et al. ^[41])

where $\bar{c}_{i}\in \mathbb{R}^{n}$, $\bar{d}_{i}\in \mathbb{R}^{n}$, $\bar{A}\in \mathbb{R}^{m\times n}$, $\bar{b}\in \mathbb{R}^{m}$, $\bar{f}_{i}\in\mathbb{R}, \bar{g}_{i}\in\mathbb{R}, i = 1, 2, \ldots, p$; each element of $\bar{c}_{i}$, $\bar{d}_{i}$, and $\bar{A}$ is randomly generated from the interval $[0, 10]$; each element of $\bar{b}$ is equal to $10$, and each element of $\bar{f}_{i}$ and $\bar{g}_{i}$ is randomly generated from the interval $[0, 1]$.

Problem 2. (Li et al. ^[41])

where $\tilde{\gamma}_{ij}, \tilde{\xi}_{i}, \tilde{\delta}_{ij}, \tilde{\eta}_{i}\in \mathbb{R}$, $i = 1, 2, \ldots, p, j = 1, 2, \ldots, n; \; \tilde{A}\in \mathbb{R}^{m\times n}$, $\tilde{b}\in \mathbb{R}^{m}$; all $\tilde{\gamma}_{ij}$ and $\tilde{\delta}_{ij}$ are randomly generated from $[-0.1, 0.1]$; all elements of $\tilde{A}$ are randomly generated from $[0.01, 1]$; all elements of $\tilde{b}$ are equal to $10$; and all $\tilde{\xi}_{i}$ and $\tilde{\eta}_{i}$ satisfy

and

From the results in Table 2, for Problem 1 with the large-size number of variables, we first get the observation that the algorithm proposed in Jiao and Liu ^[39] is more time-consuming than Algorithm 1. Especially, when $p = 3$, $m = 100, \; n = 3000$; $p = 3$, $m = 100, \; n = 5000$; $p = 3$, $m = 100, \; n = 7000$; $p = 3$, $m = 100, \; n = 10000$; $p = 4$, $m = 100, \; n = 1000$; the algorithm of Jiao & Liu ^[39] failed to solve all $50$ independently generated instances in $10000s$, but Algorithm 1 can obtain the global optimal solution of test Problem 1 with higher computational efficiency. Second, the computational efficiency of Algorithm 1 is superior to the algorithm of Li et al. ^[41] in all cases.

From the numerical comparisons for Problem 2 in Table 3, the computational efficiency of Algorithm 1 is superior to the algorithm of Li et al. ^[41] in all cases.

From the numerical comparisons in Tables 1–3, we can get that Algorithm 1 can globally solve the sum of affine ratios problem to obtain their global optimal solutions and optimal values with higher computational efficiency.

5.   Conclusions

This paper studies the sum of affine ratios problem and presents an outcome space branch-and-bound algorithm. In this algorithm, we proposed a novel linearization technique for constructing the affine relaxation problem of the equivalent problem. Moreover, the computational complexity of the algorithm is analyzed, and the maximum number of iterations of the algorithm is derived. Algorithm 1 can find an $\epsilon$-global optimal solution in at most

iterations. Numerical comparisons show the effectiveness and superiority of Algorithm 1. Future work will extend Algorithm 1 to solve the sum of nonlinear ratios problem.

Author contributions

Yan Shi: formal analysis, investigation, resources, methodology, writing-original draft, validation, and data curation; Qunzhen Zheng: formal analysis, invesigation, writing-review & editing, software, data curation, conceptualization, supervision, project administration; Jingben Yin: 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 paper is supported by the Key Scientific and Technological Research Projects in Henan Province (202102210147, 192102210114).

Conflict of interest

The authors declare no conflicts of interest.

Appendix

Test Examples 1–12 are given as follows:

Example 1. (Benson ^[34])

Example 2. (Phuong and Tuy ^[14] and Shen et al. ^[35])

Example 3. (Shen et al. ^[35], Shen and Wang ^[36])

Example 4. (Shen et al. ^[35])

Example 5. (Shen and Lu ^[36], Gao and Jin ^[38])

Example 6. (Shen and Lu ^[37])

Example 7. (Shen and Lu ^[37], Gao and Jin ^[38])

Example 8. (Shen and Lu ^[37])

Example 9. (Shen and Lu ^[37], Gao and Jin ^[38])

Example 10. (Jiao and Liu ^[39], Jiao et al. ^[40], Shen Wang ^[36])

Example 11. (Shen and Wang ^[36], Shi ^[21])

Example 12. (Shi ^[21])