1 Introduction

The linear multiplicative problem we are attempting to solve is:

$$\begin{aligned} {\mathrm{(LMP)}}:\left\{ \begin{array}{lll} v=&{}\max &{}f({\mathbf {x}})=\sum \limits _{i=1}^{p} \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) \\ &{}\mathrm{s.t.}&{} {\mathbf {x}}\in \Omega =\left\{ {\mathbf {x}}\in {\mathbb {R}}^{n}\ |\ {{\mathbf {A}}}{{\mathbf {x}}}\le {\mathbf {b}},\ {\mathbf {x}}\ge {\mathbf {0}}\right\} , \end{array} \right. \end{aligned}$$

where \(p\ge 2\), \({\mathbf {c}}_{i},{\mathbf {d}}_{i}\in {\mathbb {R}}^{n}\), \(c_{0i},d_{0i}\in {\mathbb {R}}\), and \({\mathbf {A}}\in {\mathbb {R}}^{m\times n}\), \({\mathbf {b}}\in {\mathbb {R}}^{m}\).

The linear multiplicative problem (LMP) is one of the most successful fields today in nonlinear optimization problems. The reason is that problem (LMP) arises in a variety of practical applications including economy [1], engineering [2], finance [3, 4], robust optimization [5], network flows [6, 7] etc. Another reason is that it usually poses significant theoretical and computational difficulties. The major impediment is the existence of multiple local optima which are not globally optimal in such problems. Even, for \(p=1\), it is a special case of non-convex quadratic programming problems, which is known to be NP-hard [8]. It is much more difficult to solve problem (LMP) with \(p\ne 1\). In addition, some well known global optimization problems fall into the category of (LMP). For example, consider the general quadratic programming problem with the objective function \(f({\mathbf {x}})=\frac{1}{2}{\mathbf {x}}^{\top }{{\mathbf {Q}}}{{\mathbf {x}}}+{\mathbf {a}}^{\top }{\mathbf {x}}\), where \({\mathbf {a}}\in {\mathbb {R}}^{n}\), and \({\mathbf {Q}}\in {\mathbb {R}}^{n\times n}\) has rank \(p\le n\), then there exists linearly independent vectors \(\varvec{\alpha }_{1},\varvec{\alpha }_{2},\ldots ,\varvec{\alpha }_{p}\in {\mathbb {R}}^{n}\) and \(\varvec{\gamma }_{1},\varvec{\gamma }_{2},\ldots ,\varvec{\gamma }_{p}\in {\mathbb {R}}^{n}\) such that \(f({\mathbf {x}})=\sum _{i=1}^{p}(\varvec{\alpha }_{i}^{\top }{\mathbf {x}})(\varvec{\gamma }_{i}^{\top }{\mathbf {x}})+{\mathbf {a}}^{\top }{\mathbf {x}}.\) While the details discussion about decomposition of quadratic and bilinear forms that rely on the formulation (LMP), we can refer to surveys [9, 10]. Even so, it still evoked interest of researchers and practitioners.

A number of ingenious approaches for solving multiplicative programming problems have been proposed. For instance, Wang et al. [11] proposed a branch-and-bound algorithm for global minimization of a generalized linear multiplicative programming; Jiao et al. [12] presented a branch-and-bound algorithm for linear multiplicative programming with coefficient; Oliveira and Ferreira [13] gave an outcome space approach for generalized convex multiplicative programs; Also, Gao et al. [14], Zhou et al. [15] developed an outcome-space finite algorithm for solving linear multiplicative programming, and Shen et al. [16] presented an approximation algorithm for globally solving a class of generalized multiplicative programming problems using the feasibility of linear programs. Moreover, some practical algorithms have been proposed for solving linear generalized multiplicative programming problem that can be classified into optimal level solution methods [6, 7, 17, 18], linear decomposition method [19], branch and bound algorithms [20, 21], level set algorithm [22] and cutting plane method [23]. Additionally, branch and bound and branch and reduce approaches for these kind of functions have been proposed also in the papers [24, 25].

In this article, by exploiting the feature for problem (LMP), we develop a special-purpose branch-and-bound algorithm for globally solving problem (LMP). In the algorithm, a new linear programming relaxation is derived for the upper bound of the optimal value to problem (LMP), and the branching is performed in the variable space. The main computational work of the algorithm only involves the solutions of a sequence of linear programming subproblems, in which the solutions of these subproblems are as close to the globally optimal solution to problem (LMP) as possible through the successive subdivision procedure in the branching operation. Finally, the numerical computational results illustrate that the presented algorithm is efficient and effective.

The paper is structured as follows: In the Sect. 2 we show how to convert the linear relaxation program of problem (P) into p linear subproblems by using the proposed linear relaxation technique. A branch-and-bound algorithm with a simple and standard bisection rule and the proof of its convergence properties are presented in Sect. 3. Finally, the numerical results are given in Sect. 4, and some concluding remarks are given in Sect. 5.

2 Linear relaxation programming

In this section, for solving problem (LMP), we first construct a problem (P) equivalent to problem (LMP), and then we shall show how to decompose the linear relaxation program of problem (P) into p linear subproblems by using the proposed linear relaxation technique. To obtain an upper bound for v in the branch and bound algorithm to be proposed, we only need to solve the linear relaxation subproblems.

First, let us denote

$$\begin{aligned} T^{+}= & {} \left\{ i | \min \limits _{{\mathbf {x}}\in \Omega } \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) \ge 0,\quad i=1,\ldots ,p\right\} ,\\ T^{-}= & {} \left\{ i | \min \limits _{{\mathbf {x}}\in \Omega } \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) < 0, \quad i=1,\ldots ,p\right\} , \end{aligned}$$

then, the objective function to problem (LMP) can be transformed into:

$$\begin{aligned} f({\mathbf {x}})= & {} \sum \limits _{i=1}^{p}\left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) \\= & {} \sum \limits _{i \in T^{+}}\left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) \\&+\,\sum \limits _{i \in T^{-}}({\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}+\delta _{i})\left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) -\sum \limits _{i \in T^{-}}\delta _{i}\left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) \end{aligned}$$

where we select the constants \(\delta _{i} \in {\mathbb {R}}\) such that \({\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}+\delta _{i}>0\) for all \({\mathbf {x}}\in \Omega .\)

For simplicity, some notations are introduced as follows.

$$\begin{aligned} e_{0i}= & {} \left\{ \displaystyle \begin{array}{l@{\quad }l} c_{0i}, &{} i \in T^{+}\\ c_{0i}+\delta _{i}, &{} i \in T^{-}\\ \end{array} \right. \\ {\mathbf {a}}= & {} \sum \limits _{i \in T^{-}}(\delta _{i}{\mathbf {d}}_{i}) \in {\mathbb {R}}^{n}, \quad a_{0}=\sum \limits _{i \in T^{-}}(\delta _{i}d_{0i}) \in {\mathbb {R}} \end{aligned}$$

then, we can obtain

$$\begin{aligned} f({\mathbf {x}})=\sum \limits _{i=1}^{p} \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}+a_{0}\right) . \end{aligned}$$

where \({\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i}\ge 0\) for any \(x\in \Omega , i=1,\ldots ,p.\)

Next, we construct an initial rectangle \(H^{0}\) as follows

$$\begin{aligned} \Omega \subseteq H^{0}=\left[ {\mathbf {l}}^{0},{\mathbf {u}}^{0}\right] \triangleq \left\{ {\mathbf {x}}\in {\mathbb {R}}^{n}\mid \ l_{j}^{0}\le x_{j}\le u_{j}^{0},\quad j=1,\ldots ,n\right\} , \end{aligned}$$

where

$$\begin{aligned} l_{j}^{0}=\min \left\{ x_{j}\ |\ {\mathbf {x}}\in \Omega \right\} ,\quad u_{j}^{0}=\max \left\{ x_{j}\ |\ {\mathbf {x}}\in \Omega \right\} . \end{aligned}$$

Throughout this paper, assume that \(H=[{\mathbf {l}},{\mathbf {u}}]\) represents the initial rectangle \(H^{0}\) or its subrectangle to be subdivided in next iteration. Then, consider the following subproblem of problem (LMP):

$$\begin{aligned} {\mathrm{LMP}}(H){:}\,\left\{ \begin{array}{l} v(H)=\max f({\mathbf {x}})=\sum \limits _{i=1}^{p}\left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}+a_{0}\right) \\ \mathrm{s.t. } {\mathbf {x}}\in \Omega \cap H, \end{array} \right. \end{aligned}$$

By introducing auxiliary variables with

$$\begin{aligned} \beta _{i}={\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i},\quad \mathbf {y}_{\mathbf{i}}=\beta _{i}{\mathbf {x}},\quad i=1,\ldots ,p, \end{aligned}$$

problem (LMP(H)) would be rewritten as follows:

$$\begin{aligned} {(\mathrm{P}}(H)){:}\,\left\{ \begin{array}{rlll} v(H)=\mathrm{max}&{}\sum \limits _{i=1}^{p} \left( {\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}+d_{0i}\beta _{i}\right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}+a_{0}\right) &{}\\ \mathrm{s.t.} &{}{\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i}=\beta _{i}&{}i=1,\ldots ,p,\\ &{}{\mathbf {y}}_{i}=\beta _{i}{\mathbf {x}} &{}i=1,\ldots ,p,\\ &{}A{\mathbf {y}}_{i}-b\beta _{i}\le 0&{}i=1,\ldots ,p,\\ &{}{\mathbf {l}}\le {\mathbf {x}}\le {\mathbf {u}}. \end{array} \right. \end{aligned}$$

Theorem 1

If (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) is an optimal solution of problem (P(H)), then \({\mathbf {x}}^{*}\) is an optimal solution of problem (LMP(H)). Conversely, if \({\mathbf {x}}^{*}\) is an optimal solution of problem (LMP(H)), then (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) is an optimal solution of problem (P(H)), where \({\mathbf {y}}^{*}_{i}=\beta ^{*}_{i}{\mathbf {x}}^{*}\), \(\beta ^{*}_{i}={\mathbf {c}}_{i}^{\top }{\mathbf {x}}+e_{0i}\) for each \(i=1,\ldots ,p\).

Proof

Let (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) is an optimal solution of problem (P(H)), we first show that \({\mathbf {x}}^{*}\) is an optimal solution for problem (LMP(H)). Now, suppose \({\mathbf {x}}^{*}\) is not an optimal solution for problem (LMP(H)), then there exists a feasible solution \(\bar{\mathbf {{x}}}\in \Omega \cap H\) for problem (LMP(H)) such that \(f(\bar{\mathbf {{x}}})>f({\mathbf {x}}^{*}).\) Let

$$\begin{aligned} {\bar{\mathbf {{y}}}}_{i}=\bar{\beta _{i}}\bar{\mathbf {{x}}},\quad \bar{\beta _{i}}={\mathbf {c}}_{i}^{\top }\bar{\mathbf {{x}}}+e_{0i},\quad i=1,\ldots ,p, \end{aligned}$$
(1)

then (\(\bar{\mathbf {{x}}},{\bar{\mathbf{y}}},\varvec{{\bar{\beta }}}\)) is a feasible solution of problem (P(H)). Since \(f(\bar{\mathbf {{x}}})>f({\mathbf {x}}^{*}),\) we have

$$\begin{aligned}&\sum \limits _{i=1}^{p} \left( {\mathbf {d}}_{i}^{\top }\bar{{\mathbf {y}}}_{i}+d_{0i}\bar{\beta _{i}}\right) -\left( {\mathbf {a}}^{\top }\bar{{\mathbf {x}}}+a_{0}\right) \nonumber \\&\quad >\sum \limits _{i=1}^{p} \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}^{*}+e_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}^{*}+d_{0i}\right) - \left( {\mathbf {a}}^{\top }{\mathbf {x}}^{*}+a_{0}\right) . \end{aligned}$$
(2)

Additionally, (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) is a feasible solution of problem (P(H)) implies that

$$\begin{aligned} {\mathbf {y}}^{*}_{i}=\beta ^{*}_{i}{\mathbf {x}}^{*}\ge {\mathbf {0}},\quad \beta ^{*}_{i}={\mathbf {c}}_{i}^{\top }{\mathbf {x}}^{*}+e_{0i}\ge 0,\quad i=1,\ldots ,p, \end{aligned}$$

therefore,

$$\begin{aligned}&\sum \limits _{i=1}^{p}\left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}^{*}+e_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}^{*}+d_{0i}\right) - \left( {\mathbf {a}}^{\top }{\mathbf {x}}^{*}+a_{0}\right) \nonumber \\&\quad =\sum \limits _{i=1}^{p} \left( {\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}^{*}+d_{0i}\beta _{i}^{*} \right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}^{*}+a_{0}\right) . \end{aligned}$$
(3)

Combining (2) with (3), we can obtain

$$\begin{aligned} \sum \limits _{i=1}^{p}\left( {\mathbf {d}}_{i}^{\top }\bar{{\mathbf {y}}}_{i}+d_{0i}{\bar{\beta }}_{i}\right) -\left( {\mathbf {a}}^{\top }\bar{{\mathbf {x}}}+a_{0}\right) > \sum \limits _{i=1}^{p}\left( {\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}^{*}+d_{0i}\beta _{i}^{*}\right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}^{*}+a_{0}\right) . \end{aligned}$$

Since (\({\bar{\mathbf {{x}}},{\bar{\mathbf{y}}}},\varvec{{\bar{\beta }}}\)) is a feasible solution of problem (P(H)), this contradicts the optimality of (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) for problem (P(H)). Therefore, the supposition that \({\mathbf {x}}^{*}\) is not a global optimal solution for problem (LMP(H)) must be false.

Next, we show the converse case. Assume that \({\mathbf {x}}^{*}\) is a global optimal solution for problem (LMP(H)), and let

$$\begin{aligned} {\mathbf {y}}^{*}_{i}=\beta ^{*}_{i}{\mathbf {x}}^{*},\quad \beta ^{*}_{i}={\mathbf {c}}_{i}^{\top }{\mathbf {x}}^{*}+e_{0i},\quad i=1,\ldots ,p, \end{aligned}$$
(4)

then (\(\mathbf {x}^{*},\mathbf{y}^{*},\varvec{\beta ^{*}}\)) with \({\mathbf {x}}^{*}\in \Omega \) is a feasible solution of problem (P(H)). Now, suppose the problem (P(H)) exists a feasible solution \(({\bar{\mathbf {{x}}}},{\bar{\mathbf{y}}},\varvec{{\bar{\beta }}})\) such that

$$\begin{aligned} \sum \limits _{i=1}^{p}\left( {\mathbf {d}}_{i}^{\top }\bar{{\mathbf {y}}}_{i}+d_{0i}{\bar{\beta }}_{i}\right) -\left( {\mathbf {a}}^{\top }\bar{{\mathbf {x}}}+a_{0}\right) > \sum \limits _{i=1}^{p}\left( {\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}^{*}+d_{0i}\beta _{i}^{*}\right) -\left( {\mathbf {a}}^{\top }{\mathbf {x}}^{*}+a_{0}\right) .\quad \end{aligned}$$
(5)

Since (\({\bar{\mathbf {{x}}}},{\bar{\mathbf{y}}},\varvec{{\bar{\beta }}}\)) is a feasible solution of problem (P(H)), we see that (1) must be hold. Hence, combining (1), (4) with (5), it holds that

$$\begin{aligned} f\left( \bar{\mathbf {{x}}}\right) >f\left( {\mathbf {x}}^{*}\right) . \end{aligned}$$

Since \(\bar{\mathbf {{x}}}\in \Omega \cap H\), this contradicts that \({\mathbf {x}}^{*}\) is an optimal solution of problem (LMP(H)), hence, the supposition that the problem (P(H)) exists a feasible solution (\({\bar{\mathbf {{x}}}},{\bar{\mathbf{y}}},\varvec{{\bar{\beta }}}\)) satisfies (5) must be false, and the theorem is complete. \(\square \)

The main drawback of problem (P(H)) is that its feasible set is neither a polyhedron nor a convex set, therefore, problem (P(H)) is not solved easily. However, we can relax it to the following problem (P1(H)) which does not have this drawback through the proposed linear relaxation technique, given by

$$\begin{aligned} {\mathrm{P1}}(H){:}\,\left\{ \begin{array}{llll} {\bar{v}}(H)=&{} \max &{}\sum \limits _{i=1}^{p}\left( {\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}+d_{0i}\beta _{i}\right) -\gamma ^{H}&{}\\ &{}\mathrm{s.t.} &{}t_{i}\le \beta _{i}\le T_{i}&{}i=1,\ldots ,p,\\ &{} &{}\beta _{i}{\mathbf {l}}\le {\mathbf {y}}_{i}\le \beta _{i}{\mathbf {u}} &{}i=1,\ldots ,p,\\ &{} &{}{{\mathbf {A y}}}_{i}-{\mathbf {b}}\beta _{i}\le 0&{}i=1,\ldots ,p, \\ &{} &{} {\mathbf {y}}_{i}\ge {\mathbf {0}},\quad \beta _{i}>0 &{}i=1,\ldots ,p, \end{array} \right. \end{aligned}$$

where \(\gamma ^{H}=\sum _{j=1}^{n}\min \{a_{j}l_{j},a_{j}u_{j}\}+a_{0},\) and

$$\begin{aligned} t_{i}{=}\sum _{j=1}^{n}\min \left\{ c_{ij}l_{j},c_{ij}u_{j} \right\} +e_{0i},\quad T_{i}{=}\sum _{j=1}^{n}\max \left\{ c_{ij}l_{j},c_{ij}u_{j}\right\} +e_{0i},\quad i=1,\ldots ,p. \end{aligned}$$

Remark that we can obtain an upper bound \({\bar{v}}(H)\) for v(H) by solving linear relaxation programming problem (P1(H)). A further point to note on problem (P1(H)) is that it is decomposable into p linear subproblems, each of which is of the form:

$$\begin{aligned} {\mathrm{Q}_{i}}(H){:}\,\left\{ \begin{array}{llll} \bar{r_{i}}=&{}\max &{}{\mathbf {d}}_{i}^{\top }{\mathbf {y}}_{i}+d_{0i}\beta _{i}\\ &{}\mathrm{s.t.} &{}t_{i}\le \beta _{i}\le T_{i},\\ &{} &{}\beta _{i}{\mathbf {l}}\le {\mathbf {y}}_{i}\le \beta _{i}{\mathbf {u}},\\ &{} &{}\mathbf {A y}_{i}-{\mathbf {b}}\beta _{i}\le 0,\\ &{} &{} {\mathbf {y}}_{i}\ge {\mathbf {0}},\quad \beta _{i}>0. \end{array} \right. \end{aligned}$$

Theorem 2

The relaxed problem (P1(H)) has an optimal solution (\({\mathbf {y}}^{*},\varvec{\beta }^{*}\)) if and only if the linear programming problem (\(\hbox {Q}_{i}(H))\) has an optimal solution (\({\mathbf {y}}_{i}^{*},\varvec{\beta }_{i}^{*}\)) for each \(i=1,\ldots ,p\).

Proof

It is obvious from the above observation. \(\square \)

Clearly, by solving each linear programming problem (\(\hbox {Q}_{i}(H)\)), we can obtain optimal value \(\bar{r_{i}}\) for each \(i=1,\ldots ,p\), and let \(UB(H)=\sum _{i=1}^{p}\bar{r_{i}}-\gamma ^{H}\), then, it holds that \(UB(H)={\bar{v}}(H)\ge v(H)\). According to the above discussion, as the branch and bound algorithm search proceeds, for each \(k\ge 0\), we can find an upper bound \({ UB}_{k}\) for v in the k-th iteration. The upper bound is given by

$$\begin{aligned} { UB}_{k}=\max \left\{ UB(H)|\ H\in F_{k}\right\} , \end{aligned}$$

where \(F_{k}\) is the partition created by the algorithm near the end of the k-th iteration, which is not yet excluded from branch and bound search.

3 Branch-and-bound algorithm and its convergence

In this section, we shall present a branch-and-bound algorithm with a simple and standard bisection rule which can guarantee such algorithm to be convergent for solving problem (LMP). Moreover, we give the detail proof of its convergence.

3.1 Branch-and-bound algorithm

The partition process iteratively subdivides the initial rectangle \(H^{0}\) into subrectangles to help the algorithm to identify a location of a global optimal solution in \(\Omega \) for problem (LMP). In addition, we note that for any optimal solution \((\bar{\mathbf {{y}}}_{i},{\bar{\beta }}_{i})\) of problem (\(\hbox {Q}_{i}(H)\)) for each \(i\in \{1,\ldots ,p\}\), and let \(\bar{\mathbf {{x}}_{i}}=\bar{\mathbf {{y}}_{i}}/{\bar{\beta }}_{i},~ i=1,\ldots ,p\), it follows that \(\bar{{\mathbf {x}}}_{i}\) is a feasible solution for problem (LMP(H)). Therefore, we can update lower bound of v by the feasible solutions \(\bar{\mathbf {{x}}_{i}}\). The proposed branch-and-bound (BB) algorithm is summarized as follows.

figure a

3.2 Convergence of the algorithm

Theorem 3

Given \(\varepsilon \in [0,1)\), if BB algorithm terminates finitely at the k-th iteration, then \({\mathbf {x}}^{k}\) is an \(\varepsilon \)-globally optimal solution for problem (LMP), otherwise, every accumulation point of the sequence \(\{{\mathbf {x}}^{k}\}\) is a global optimal solution for problem (LMP).

Proof

If the algorithm is finite, then suppose it terminates at k-th iteration. For \(k=0\), we have \({ UB}_{0}-{ LB}_{0}\le \varepsilon { UB}_{0}\), \({ LB}_{0}=f({\mathbf {x}}^{0})\), and \({\mathbf {x}}^{0}\in \Omega \cap H^{0}\), therefore, \({\mathbf {x}}^{0}\) is an \(\varepsilon \)-globally optimal solution for problem (LMP). For \(k\ge 1\), this implies that all subrectangles \(H\in F_{k}\) satisfy that

$$\begin{aligned} UB(H)-{ LB}_{k}\le \varepsilon UB(H). \end{aligned}$$

By taking the maximum over all subrectangles \(H\in F_{k}\) on both sides of the above inequality, we can have \({ UB}_{k}-{ LB}_{k}\le \varepsilon { UB}_{k}\), where \(\varepsilon \in [0,1)\), \({ UB}_{k}=\max \{UB(H)\ |\ H\in F_{k}\}\), \({ LB}_{k}=f({\mathbf {x}}^{k})\). Since \({ UB}_{k}>v\), this means that \(v-f({\mathbf {x}}^{k})\le \varepsilon v\). Hence, from \({\mathbf {x}}^{k}\in \Omega \), \({\mathbf {x}}^{k}\) is an \(\varepsilon \)-globally optimal solution for problem (LMP).

If the algorithm is infinite, it generates at least one infinite sequence of nested rectangles, such as \(H^{k+1}\subseteq H^{k},\quad k=0,1,\ldots \). From the description of the algorithm, it holds that

$$\begin{aligned} 0<f({\mathbf {x}}^{k})= { LB}_{k}\le v\le { UB}_{k},\quad k=0,1,2,\ldots \end{aligned}$$

Note that \(\{{ LB}_{k}\}\) is nondecreasing with an upper bound v, and converges to v. Let \(\bar{\mathbf {{x}}}\) be any accumulation point of \(\{{\mathbf {x}}^{k}\}\). Without loss of generality, let \(\{{\mathbf {x}}^{k}\}\) converge to \(\bar{\mathbf {{x}}}\). Since,

$$\begin{aligned} { UB}_{k}=\sum \limits _{i=1}^{p} \left( {\mathbf {d}}_{i}^{\top }\bar{\mathbf {{y}}}_{i}^{k}+d_{0i}{\bar{\beta }}_{i}^{k}\right) -\gamma ^{H^{k}} =\sum \limits _{i=1}^{p}{\bar{\beta }}_{i}^{k} \left( {\mathbf {d}}_{i}^{\top }\bar{{\mathbf {x}}}_{i}^{k}+d_{0i}\right) -\gamma ^{H^{k}}, \end{aligned}$$
Table 1 Computational results of test Examples 1–11
Full size table
Table 2 Average performance of the algorithm when \((n,m)=(5,100)\) and \(\varepsilon =0.01\)
Full size table
Table 3 Average performance of the algorithm when \(p=50\), \(m=100\) and \(\varepsilon =0.01\)
Full size table
Table 4 Computational results of Problem 2
Full size table

where \(\bar{{\mathbf {x}}}_{i}^{k}=\bar{{\mathbf {y}}_{i}}^{k}/{\bar{\beta }}_{i}^{k}\in H^{k}\). According to the branching process, the algorithm can always generate an infinite rectangles sequence \(\{H^{k}\}\) such that \(H^{k+1}\subseteq H^{k}\) and \(\bigcap \nolimits _{k\rightarrow \infty }H^{k}=\{\bar{\mathbf {{x}}}\}\). Therefore, we see that

$$\begin{aligned} \lim \limits _{k\rightarrow +\infty }{\bar{\beta }}_{i}^{k}= {\mathbf {c}}_{i}^{\top }\bar{{\mathbf {x}}}+e_{0i},\quad \ \lim \limits _{k\rightarrow +\infty }{\mathbf {x}}_{i}^{k}=\bar{{\mathbf {x}}},\quad \ i=1,\ldots ,p. \end{aligned}$$

Then it holds that \(\lim \nolimits _{k\rightarrow \infty }({ UB}_{k}-{ LB}_{k})=\lim \nolimits _{k\rightarrow \infty }({ UB}_{k}-f({\mathbf {x}}^{k}))=0,\) This implies that \(\lim \nolimits _{k\rightarrow \infty }({ UB}_{k}-v)=0,\, \lim \nolimits _{k\rightarrow \infty }(v-{ LB}_{k})=0.\) Therefore, we can see that

$$\begin{aligned} \lim \limits _{k\rightarrow \infty }{} { UB}_{k}=v,\quad \ \lim \limits _{k\rightarrow \infty }{} { LB}_{k}=v. \end{aligned}$$
(6)

Noting that

$$\begin{aligned} \lim \limits _{k\rightarrow \infty }{} { LB}_{k}=\lim \limits _{k\rightarrow \infty }f\left( {\mathbf {x}}^{k}\right) =f(\bar{\mathbf {{x}}}). \end{aligned}$$
(7)

Combining (6) with (7), it follows that \(f(\bar{\mathbf {{x}}})=v\), so \(\bar{\mathbf {{x}}}\) is an optimal solution of problem (LMP). \(\square \)

Table 5 Growths of CPU for Problem 2
Full size table
Table 6 Computational results of BB algorithm for Problem 3
Full size table
Table 7 The average and standard deviation of CPU time for Problem 3
Full size table
Table 8 Growths of CPU for Problem 3 with \(r=1\)
Full size table

4 Numerical examples

In this section, we test the performance of BB algorithm with a set of numerical examples. The algorithm is coded in MATLAB(2012b) and all computations are implemented on a Intel(R) Core(TM) i5-3550S CPU 3.00 GHz with 4G memory microcomputer.

Some notations in the following Tables 1, 2, 3, 4, 5, 6, 7 and 8 have been used:

  • Ref: reference;

  • Iter: the number of the algorithm iterations;

  • Optimum: the optimal value;

  • Solution: the optimal solution;

  • CPU: the execution time in seconds;

  • SD: standard deviation value given by the algorithm on the random problem;

  • Ave: average performance by the algorithm on the random problem;

  • Node: the maximal number of the active nodes necessary.

  • DLPS: the results using subproblems (\(\hbox {Q}_i(H)\)) in BB algorithm.

  • IDLP: the results using the linear programming (P1(H)) in BB algorithm. item LPs: the total number of linear programs solved in the corresponding algorithm.

First of all, in order to illustrate the performance of BB algorithm, some examples were tested to compare with Refs. [11, 14, 21], the corresponding computational results are listed in Table 1, where, the calculation formulas of “LPs” in [11, 21] and BB algorithm are “\(2(n+2)\times \mathrm{Iter}\)”, “\(2(4p+1)\times \mathrm{Iter}\)”, and “\(2p\times \mathrm{Iter}\)” about “DLPS”, “\(2\times \mathrm{Iter}\)” about “IDLP”, respectively. In our computation, the tolerance parameter \(\varepsilon \) was set \(10^{-4}\) for all examples.

Example 1

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}&{}3x_{1}-4x_{2}+(x_{1}+2x_{2}-1.5)\times (2x_{1}-x_{2}+4)\\ &{} &{}+\,(x_{1}-2x_{2}+8.5)\times (2x_{1}+x_{2}-1)\\ &{}{\mathrm{s.t.}}&{}5x_1-8x_2\ge -24,\quad 5x_1+8x_2\le 44,\\ &{} &{}6x_1-3x_2\le 15,\quad 4x_1+5x_2\ge 10,\quad x_{1}\ge 0. \end{array} \end{aligned}$$

Example 2

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min} &{}\displaystyle {(0.813396x_{1}+0.6744x_{2}+0.305038x_{3}+0.129742x_{4}+0.217796)}\\ &{} &{}\displaystyle {\times \,(0.224508x_{1}+0.063458x_{2}+0.93223x_{3}+0.528736x_{4}+0.091947)}\\ &{}{\mathrm{s.t. }}&{}0.488509x_{1}+0.063458x_{2}+0.945686x_{3}+0.210704x_{4}\le 3.562809,\\ &{} &{}-\,0.324014x_{1}-0.501754x_{2}-0.719204x_{3}+0.099562x_{4}\le -0.052215,\\ &{} &{}0.445225x_{1}-0.346896x_{2}+0.637939x_{3}-0.257623x_{4}\le 0.42792,\\ &{} &{} -\,0.202821x_{1}+0.647361x_{2}+0.920135x_{3}-0.983091x_{4}\le 0.84095,\\ &{} &{}-\,0.886420x_{1}-0.802444x_{2}-0.305441x_{3}-0.180123x_{4}\le -1.353686,\\ &{} &{} -\,0.515399x_{1}-0.424820x_{2}+0.897498x_{3}+0.187268x_{4}\le 2.137251,\\ &{} &{}-\,0.591515x_{1}0.060581x_{2}-0.427365x_{3}+0.579388x_{4}\le -0.290987,\\ &{} &{}0.423524x_{1}+0.940496x_{2}-0.437944x_{3}-0.742941x_{4}\le 0.37362,\\ &{} &{}x_{1},x_{2},x_{3},x_{4}\ge 0. \end{array} \end{aligned}$$

Example 3

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min} &{}\displaystyle {(x_{1}+x_{2})\times (x_{1}-x_{2}+7)}\\ &{}{\mathrm{s.t. }}&{}2x_1+x_2\le 14,\quad x_1+x_2\le 10,\quad -4x_1+x_2\le 0,\\ &{} &{} 2x_1+x_2\ge 6,\quad x_1+2x_2\ge 6,\quad x_1-x_2\le 3,\\ &{} &{}x_1+x_2\ge 0,\quad x_1-x_2+7\ge 0,\quad x_1,x_2\ge 0. \end{array} \end{aligned}$$

Example 4

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min} &{}\displaystyle {x_{1}+(2x_{1}-3x_{2}+13)\times (x_{1}+x_{2}-1)}\\ &{}{\mathrm{s.t. }}&{}-x_1+2x_2\le 8,\quad -x_2\le -3,\\ &{} &{}x_1+2x_2\le 12,\quad x_1-2x_2\le -5,\quad x_1,x_2\ge 0. \end{array} \end{aligned}$$

Example 5

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min} &{}\displaystyle {-x_{1}^{2}-x_{2}^{2}+(-\,x_{1}-3x_{2}+2)\times (4x_{1}+3x_{2}+1)}\\ &{}{\mathrm{s.t. }}&{}x_1+x_2\le 5,\quad -x_1+x_2\le 6,\quad x_1,x_2\ge 0. \end{array} \end{aligned}$$

Example 6

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}&{}-2x_{1}^{2}-x_{2}^{2}-2+(-\,2x_{1}-3x_{2}+2)\times (4x_{1}+6x_{2}+2)\\ &{} &{}+\,(3x_{1}+5x_{2}+2)\times (6x_{1}+8x_{2}+1)\\ &{}{\mathrm{s.t. }}&{}2x_1+x_2\le 10,\quad -x_1+2x_2\le 10,\quad x_1,x_2\ge 0. \end{array} \end{aligned}$$

Example 7

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}&{}x_{1}+(x_{1}-x_{2}+5)\times (x_{1}+x_{2}-1)\\ &{}{\mathrm{s.t. }}&{}-2x_1-3x_2\le -9,\quad 3x_1-x_2\le 8,\\ &{}&{}-x_1+2x_2\le 8,\quad x_1+2x_2\le 12,\\ &{}&{}x_1\ge 0. \end{array} \end{aligned}$$

Example 8

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}&{}(x_{1}+x_{2})\times (x_{1}-x_{2})+(x_{1}+x_{2}+1)\times (x_{1}-x_{2}+1)\\ &{}{\mathrm{s.t. }}&{}x_1+2x_2\le 20,\quad x_1-3x_2\le 20,\quad 1\le x_1\le 3,\quad 1\le x_2\le 3.\\ \end{array} \end{aligned}$$

Example 9

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}&{}(x_{1}+x_{2})\times (x_{1}-x_{2})+(x_{1}+x_{2}+2)\times (x_{1}-x_{2}+2)\\ &{}{\mathrm{s.t. }}&{}x_1+2x_2\le 20,\quad x_1-3x_2\le 20,\\ &{}&{}\quad 1\le x_1\le 4,\quad 1\le x_2\le 4.\\ \end{array} \end{aligned}$$

Example 10

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}\quad (2x_{1}-2x_{2}+x_{3}+2)\times (-\,2x_{1}+3x_{2}+x_{3}-4)\\ &{}\quad \quad +(-\,2x_{1}+x_{2}+x_{3}+2)\times (x_{1}+x_{2}-3x_{3}+5)\\ &{}\quad \quad +(-\,2x_{1}-x_{2}+2x_{3}+7)\times (4x_{1}-x_{2}-2x_{3}-5)\\ &{}{\mathrm{s.t. }}\quad x_1+x_2+x_3\le 10,\quad x_1-2x_2+x_3\le 10,\\ &{}\quad \quad -2x_1+2x_2+3x_3\le 10,\quad -x_1+x_2+3x_3\ge 6,\\ &{}\quad \quad x_1\ge 1,x_2\ge 1,x_3\ge 1. \end{array} \end{aligned}$$

Example 11

$$\begin{aligned} \begin{array}{lll} &{}\mathrm{min}\quad (-\,x_{1}+2x_{2}-5)\times (-\,4x_{1}+x_{2}+3)+(3x_{1}-7x_{2}+3)\times (-\,x_{1}-x_{2}+3)\\ &{}{\mathrm{s.t. }}\quad -2x_1+3x_2\le 8,\quad 4x_1-5x_2\le 8,\\ &{}\quad \quad \ 4x_1+3x_2\le 15, \quad -4x_1-3x_2\le -12,\\ &{}\quad \quad x_1\ge 0,x_2\ge 0. \end{array} \end{aligned}$$

From Table 1, compared with other methods in Refs. [11, 14, 21], numerical results show that the proposed BB algorithm can find the global optimal solution in a shorter time and one iteration for Examples 1–10, and can achieve a better solution than that reported in [21] for Example 11 even if BB algorithm required the larger computational effort. And from Table 1 it can be seen that the total number of linear programs solved by using problem P1(H) in BB algorithm is less than or equal to those required by other methods (e.g. Refs. [11, 14, 21]). Additionally, by Table 1 it is observed that the running time of BB algorithm is decreasing if the decomposable subproblems \({\mathrm{Q}_{i}}(H)\) rather than problem P1(H) were applied to obtain the upper bound in the branch and bound procedure, although the total number of linear programs to be solved increases in BB algorithm. The reason is that the difficulty of each subproblem \({\mathrm{Q}_{i}}(H)\) solved is much lower than that of problem P1(H), and so the numerical results gained by solving decomposable linear programming subproblems are better than that by solving indecomposable linear problems. In a short, BB algorithm in this paper for globally solving problem (LMP) is more efficient than ones in Refs. [11, 14, 21].

Next, we choose three types of generalized linear multiplicative programming generated randomly to test our algorithm further. Based on the above results, we adopt decomposable subproblems \({\mathrm{Q}_{i}}(H)\) to calculate the upper bound in the proposed branch and bound process for the following randomly generated Problems 1–3.

Problem 1

$$\begin{aligned} \left\{ \begin{array}{lll} &{}\mathrm{max}&{}\displaystyle {\sum \limits _{i=1}^{p}\left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+c_{0i}\right) \left( {\mathbf {d}}_{i}^{\top }{\mathbf {x}}+d_{0i}\right) },\\ &{}\mathrm{s.t. }&{} {{\mathbf {A}}}{{\mathbf {x}}}\le {\mathbf {b}},\quad 0\le x_{j}\le 1,\quad j=1,\ldots ,n, \end{array} \right. \end{aligned}$$

where \(c_{0i}\), \(d_{0i}\) and the elements of \({\mathbf {c}}_{i}\), \({\mathbf {d}}_{i}\in {\mathbb {R}}^{n}\) were generated randomly in the interval \([-\,1,1]\), \({\mathbf {A}}\in {\mathbb {R}}^{m\times n}\), \({\mathbf {b}}\in {\mathbb {R}}^{m}\), and each element of them is a random number in the unit interval [0, 1] so that the problem is feasible.

All computational results in Tables 2 and 3 were obtained by running the BB algorithm for 10 times with \(\varepsilon =0.01\). Tables 2 and 3 show the variation of the average computational time, number of iterations and maximal number of the active nodes, respectively, required by each program when (n, m) was fixed at (5, 100) with the change of p from 100 to 1400, and when n was changed from 5 to 60 for the fixed \((p,m)=(50,100)\).

From the numerical results in Tables 2 and 3, when (n, m) or (p, m) is fixed in Problem 1, it is obvious that the average computational time, number of the active nodes of the proposed BB algorithm increase with the increase of the numbers of multiplicatives and variables in the objective function.

Based on the above computational results, it can be seen that the proposed BB algorithm in this article can be used to globally solve the problem (LMP). Test results also show that the proposed BB algorithm is effective and can solve the middle scale problems.

Additionally, in order to further compare with Refs. [13, 21], the following two types problems (Problems 2, 3) taken from Refs. [13, 21] respectively were tested by the proposed BB algorithm.

Problem 2

(See [21])

$$\begin{aligned} \left\{ \begin{array}{lll} &{}\mathrm{min}&{}\displaystyle {f\left( {\mathbf {x}}\right) =\sum \limits _{i=1}^{p} \left( {\mathbf {c}}_{i}^{\top }{\mathbf {x}}+d_{i}\right) \left( {\mathbf {e}}_{i}^{\top }{\mathbf {x}}+f_{i}\right) },\\ &{}\mathrm{s.t. }&{} {\mathbf {x}}\in D=\left\{ {\mathbf {x}}|{\mathbf {x}}\in R^n, {{\mathbf {A}}}{{\mathbf {x}}}\le {\mathbf {b}}\right\} \end{array} \right. \end{aligned}$$

where the elements of \({\mathbf {c}}_\mathbf{i}, d_i, {\mathbf {e}}_\mathbf{i}, f_i\) are pseudo-randomly generated in the range \([-\,0.5,0.5]\), and each element of \({\mathbf {A}}\in {\mathbb {R}}^{m\times n}\), \({\mathbf {b}}\in {\mathbb {R}}^{m}\) is pseudo-randomly generated in the range [0.01, 1]. In our computation, the tolerance parameter \(\varepsilon \) was set \(10^{-6}\) for Problem 2, as given in [21].

The average value of computational results for Problem 2 are presented in Table 4, where only average execution time and iterations are listed for the comparison between BB algorithm and the reported method in [21].

Based on the numerical results in Table 4, for both the algorithm in [21] and BB algorithm, when the value of p was fixed at 5 for Problem 2, it is clear that the average CPU time grows slowly as (m, n) varies from (10, 10) to (20, 20), and when \(p=10\), the average CPU time increases fast as (m, n) goes from (30, 30) to (40, 40). Specially, it can be observed that the CPU time required by BB algorithm is less than that of [21] although the iterations of BB algorithm are more than the ones of the algorithm in [21]. This is because both the algorithm in [21] and BB algorithm are branch and bound frames, and the main computational cost of them lies in solving the relaxed linear programming problems, in which the number of variables and constraints in the proposed relaxed linear programs are less than that of [21].

Since the results in Table 4 provided by Ref. [21] and BB algorithm were obtained by using different computational resources, for facilitating comparison, the following relative performance measure is adopted:

$$\begin{aligned} \displaystyle \xi _{p,m,n}:=\frac{{\mathrm{average\; time\; for\;}} (p,m,n)}{ {\mathrm{average time for }} (p,m,n)=(5,10,10)}. \end{aligned}$$

The growths of the computing time required by the algorithm in [21] and BB algorithm are shown in Table 5.

From Table 5 one observes that the value of \(\xi _{p,m,n}\) in BB algorithm is less than that of [21] as (p, m, n) goes from (5, 10, 10) to (10, 40, 40) except for (5, 20, 20). This implies that the growth rate of computing time in BB algorithm tends to be smaller than that presented by the algorithm in [21] as (p, m, n) increases. As can be seen in Tables 4 and 5, the comparison between the two algorithms indicates that the proposed BB algorithm in this article is effective.

Problem 3

(See [13])

$$\begin{aligned} \left\{ \begin{array}{lll} &{}\mathrm{min}&{}\left\langle \mathbf {c}^{\mathbf{1}},{\mathbf {x}}\right\rangle +\frac{1}{2}\mathbf {x}^{\mathbf{T}}{} \mathbf{C}^{\mathbf{T}}{} \mathbf{Cx}+\sum _{i=1}^{r}\left\langle \mathbf {c}^{\mathbf{2i}},{\mathbf {c}}^{\mathbf{1}}\right\rangle \left\langle \mathbf {c}^{\mathbf{2i+1}},\mathbf{x}\right\rangle ,\\ &{}\mathrm{s.t. }&{} {{\mathbf {A}}}{{\mathbf {x}}}\ge {\mathbf {b}}, {\mathbf {x}}\in R_{+}^{n} \end{array} \right. \end{aligned}$$

where \({\mathbf {A}}\in R^{m\times n}, {\mathbf {b}}\in R^m, {\mathbf {C}}\in R^{n\times n}\) and \(\mathbf {c}^\mathbf{i}\in R^n, i=1,2,\ldots ,m\), are constant matrices with pseudo-randomly entries generated in the interval [0, 100]. In the computation of Problem 3, the tolerance parameter \(\varepsilon \) was set \(10^{-5}\), and the numerical results of BB algorithm are listed in Table 6.

As can be seen in Table 6, the average and standard deviation of iterations are not more than 3 for the different (r, n, m), as shown in Table 6, except for \((r,n,m)=(3,50,30)\), and the maximal numbers of the active nodes necessary are nearly one. This shows that the proposed BB algorithm requires smaller memory with less iterations for solving Problem 3.

In order to compare with Ref. [13], only the computational time is presented in Table 7 for Problem 3, since the solution process of the two algorithms ([13] and ours) is completely different.

From Table 7, it can be seen that the average and standard deviation of CPU time of BB algorithm are almost less than that of [13] other than \((r,n,m)=(1,150,130)\). Additionally, consider that the results in Table 7 provided by [13] and BB algorithm were gained by applying different computational resources, similar to Problem 2, for comparison, the relative performance measure is adopted as follows:

$$\begin{aligned} \eta _{n,m}:=\frac{{\mathrm{average\; time\; for\;}} (n,m)}{ {\mathrm{average\; time\; for\;}} (n,m)=(20,10)}. \end{aligned}$$

And the growths of the computing time required by the algorithm in [13] and BB algorithm are shown in Table 8 for Problem 3 with \(r=1\).

By analysing Table 8, it can be observed that the growth rate of CPU time in the proposed BB algorithm is nearly smaller than that of [13] as (n, m) varies from (20, 10) to (100, 130). When \((n,m)=(150,130)\), different from the constraint enumeration procedure applied in [13], the size of the linear programs to be solved gets larger in BB algorithm, so that the value of \(\eta _{150,130}\) in BB algorithm gets larger, in contrast with \(\eta _{150,130}=244.0\) reported in [13]. Additionally, the variation behavior between different values of \(\eta _{n,m}\) observed in Table 8 indicates that the growth of CPU time in BB algorithm tends to be much more slowly than that in [13] except for \(\eta _{150,130}\). Test results illustrate the proposed BB algorithm is effective.

5 Conclusion

In this paper, a global optimization algorithm is proposed for solving problem (LMP) which arises in various practical applications. By exploiting variable transformation and a new linear relaxation method, a sequence of linear relaxation programming of the initial problem (LMP) are derived for the bounding operation in the proposed BB algorithm. The global convergence of the proposed BB algorithm is proved, and numerical computational results are presented to demonstrate the computational advantages and effectiveness of BB algorithm.