Globally minimizing a class of linear multiplicative forms via simplicial branch-and-bound

Abstract

We consider in this paper a class of linear multiplicative programming problems that arise from numerous applications such as network flows and financial optimization. The problem is first transformed into an equivalent nonlinear optimization problem to provide a novel convex quadratic relaxation. A simplicial branch-and-bound algorithm is then designed to globally solve the problem, based on the proposed relaxation and simplicial branching process. The convergence and computational complexity of the algorithm are also analyzed. The results of numerical experiments confirm the efficiency of the proposed algorithm for tested instances.

1 Introduction

We consider the following linear multiplicative programming (LMP) problem:

$$\begin{aligned} \textrm{LMP}:\left\{ \begin{array}{ll} \min &{}f(\varvec{x})=\sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})\\ \mathrm {s.t.}&{} \varvec{x}\in D=\{\varvec{x}\in R^{n}\ | \ \varvec{A}\varvec{x}\le \varvec{b},\ \varvec{x}\ge \varvec{0}\}, \end{array} \right. \end{aligned}$$

where $\varvec{c}_{i}, \varvec{d}_{i}\in R^n,\ c_{0i}, d_{0i}\in R$, $\varvec{A}\in R^{m\times n}, \ \varvec{b}\in R^{m}$, and D is a nonempty bounded set.

As a special case of nonconvex programming problems, LMP problem covers many significant applications, such as robust optimization [1, 2], financial optimization [3], network flows [4,5,6], VLSI chip design [7]. Additionally, linear 0–1 programming, bilinear programming and general quadratic programming can be reformulated as LMP problem. For example, consider the following quadratic programming problem [8]

$$\begin{aligned} \begin{array}{ll} \min &{} \frac{1}{2}\varvec{x}^{T}\varvec{Q}\varvec{x}+\varvec{q}^{T}\varvec{x}+q_0\\ \mathrm {s.t.}&{}\varvec{A}\varvec{x}\le \varvec{b}, \end{array} \end{aligned}$$

where $\varvec{Q}\in R^{n\times n}$ is a symmetric matrix with the rank p, as pointed out by Tuy [9], there exists linearly independent vectors $\varvec{c}_1, \ldots ,\varvec{c}_p\in R^n$ and $\varvec{d}_1, \ldots ,\varvec{d}_p\in R^n$ such that

$$\begin{aligned} \varvec{Q}=\sum \limits _{i=1}^{p}\varvec{c}_{i}\varvec{d}_{i}^{T}. \end{aligned}$$

Therefore, the applications of LMP problem contain the applications of these special cases of LMP.

For solving LMP problem, various algorithms have been developed, such as the outer approximation algorithm [10], parametric simplex methods [11, 12], branch-and-bound methods [13,14,15], quadratic programming algorithms [16,17,18], monotonic approach [19], optimal level solution methods [6, 20,21,22]. Additionally, Wang et al. [23] developed a branch-and-bound algorithm by utilizing the convex envelope of bilinear function and constructing linear relaxation. Shen et al. [24, 25] proposed a linear relaxation method by exploiting the characteristics of the initial problem to present a branch-and-bound algorithm for solving LMP problem. Jiao et al. [15] gived a branch-and-bound algorithm for globally solving generalized LMP problem with coefficients. Shen et al. [26] presented a rectangular branch-and-bound algorithm for LMP problem. Zhao et al. [27] introduced an efficient inner approximation algorithm for solving the generalized LMP problem with generalized linear multiplicative constraints. For solving LMP problem, Zhao et al. [28] took advantage of the two-phase relaxation technique to develop a branch-and-bound algorithm.

In this paper, a simplicial branch-and-bound algorithm (SBBA) is presented for globally solving LMP problem. In the algorithm, we first lift LMP problem to a new equivalent problem (EP), and then further transform EP to another equivalent problem (EP1), so that the underestimation of the objective function of EP1 can be constructed easily to obtain the lower bounds of its optimal value. Thus the subproblems that must be solved for obtaining these lower bounds are all the convex quadratic programs, and so the main computational effort of the algorithm is only involved in solving a sequence of convex quadratic programming problems that do not grow in size from iteration to iteration. Compared with other branch-and-bound algorithms such as [23,24,25,26, 28], the main features of the proposed SBBA are as follows. (1) In the branch-and-bound search, SBBA not only uses the simplices rather than more complicated polytopes in [23,24,25,26] as partition elements, but also the working space for branching is $R^p$ instead of $R^n$ [23, 26]. This implies that the algorithm economizes the required computation cost. (2) Different from the algorithms in [23, 28], we analyze the computational complexity of SBBA. (3) For the bounding technique of the branch-and-bound search, we propose a convex quadratic relaxation by exploiting the characteristics of the problem, while the authors in Refs. [23,24,25] utilized the different linear relaxations to present the lower bounds of the optimal value of the problem. (4) It can be seen from Tables 1 and 2 in Sect. 4 that the CPU time of SBBA is more less than that of the algorithms in [24, 25] and the solver BARON. Especially, the numerical results show that the proposed SBBA can efficiently find the optimal solutions for all test instances.

The content of this paper is organized as follows. In Sect. 2, LMP problem is converted into the problem EP1 and the convex quadratic programming problem is constructed to provide the lower bound of the optimal value of EP1. In Sect. 3, we present a simplicial branch-and-bound algorithm which integrates the convex quadratic relaxation and simplicial branching rule. Additionally, the convergence and complexity analysis of the proposed algorithm are established. We report numerical comparison results in Sect. 4. Finally, we conclude the paper in the last section.

2 Reformulation and underestimation

In this section, we first transform LMP problem into an equivalent problem EP1, and then construct the convex quadratic relaxation to estimate the lower bound of the optimal value of EP1.

2.1 Problem reformulation

For solving LMP problem, we lift LMP problem to a new nonlinear optimization model that is equivalent to LMP problem. To this end, for each $\ i=1,\ldots ,p$, let us define

$$\begin{aligned} {y}_{i}^{min}=\min \limits _{\varvec{x}\in D}(\varvec{d}_{i}^{T}\varvec{x}-\varvec{c}_{i}^{T}\varvec{x})+d_{0i}-c_{0i},\ \ \ {y}_{i}^{max}=\max \limits _{\varvec{x}\in D}(\varvec{d}_{i}^{T}\varvec{x}-\varvec{c}_{i}^{T}\varvec{x})+d_{0i}-c_{0i}, \end{aligned}$$

and introduce an initial p-simplex

$$\begin{aligned} S_{0}=[\varvec{u}^{0,1},\ldots ,\varvec{u}^{0,p+1}] \end{aligned}$$

with $p+1$ vertices $\varvec{u}^{0,i}\ (i=1,\ldots , p+1)$, where

$$\begin{aligned} \varvec{u}^{0,1}=\varvec{y}^{min}, \varvec{u}^{0,i+1}=({y}_{1}^{min},\ldots ,{y}_{i}^{min}+p({y}_{i}^{max}-{y}_{i}^{min}), \ldots ,{y}_{p}^{min})^{T},\ i=1,\ldots ,p.\nonumber \\ \end{aligned}$$

(2.1)

By using the simplex $S_{0}$ that covers the hyper-rectangle $[\varvec{y}^{min},\varvec{y}^{max}]$, LMP problem can be translated into the following problem EP

$$\begin{aligned} \mathbf{\textrm{EP}:}\left\{ \begin{array}{ll} \min &{}\varphi (\varvec{x},\varvec{y})\\ \mathrm {s.t.}&{} \varvec{x}\in D,\ \varvec{y}\in S_0, \end{array} \right. \end{aligned}$$

where

$$\begin{aligned} \varphi (\varvec{x},\varvec{y})=\sum \limits _{i=1}^{p}\left\{ \frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})^2] +{y}_i(\varvec{c}_{i}^{T}\varvec{x}-\varvec{d}_{i}^{T}\varvec{x}+c_{0i}-d_{0i})\right\} +\frac{1}{2}\varvec{y}^{T}\varvec{y}. \end{aligned}$$

The equivalence result for EP and the original LMP problem is given by the following theorem.

Theorem 1

If $(\varvec{x}^{*},\varvec{y}^{*})$ is an optimal solution of EP problem, then $\varvec{x}^{*}$ is an optimal solution of LMP problem, and $f(\varvec{x}^*)=\varphi (\varvec{x}^*,\varvec{y}^*)$. Conversely, if $\varvec{x}^{*}$ is an optimal solution of LMP problem, then $(\varvec{x}^{*},\varvec{y}^{*})$ is an optimal solution of EP problem, where ${y}_{i}^{*}=\varvec{d}_{i}^{T}\varvec{x}^{*}-\varvec{c}_{i}^{T}\varvec{x}^{*}+d_{0i}-c_{0i},\ i=1,\ldots ,p$.

Proof

If $(\varvec{x}^{*},\varvec{y}^{*})$ is an optimal solution of EP problem, then $\varvec{x}^{*}$ is a feasible solution for LMP problem. Suppose that $\varvec{x}^{*}$ is not an optimal solution of LMP problem, then there exists a feasible solution $\overline{\varvec{x}}\in D$ such that

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\overline{\varvec{x}}+c_{0i})(\varvec{d}_{i}^{T}\overline{\varvec{x}}+d_{0i}) <\sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}^{*}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}^{*}+d_{0i}). \end{aligned}$$

(2.2)

Since the inequalities

$$\begin{aligned} (\varvec{c}_{i}^{T}\varvec{x}+c_{0i}-(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})+{y}_i)^2\ge 0 \end{aligned}$$

hold for any $\varvec{x}\in D,\ \varvec{y}\in S_0$, $i=1,\ldots ,p$, it follows that

$$\begin{aligned}&(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})\\&\quad \le \frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})^2] +{y}_i(\varvec{c}_{i}^{T}\varvec{x} -\varvec{d}_{i}^{T}\varvec{x}+c_{0i}-d_{0i})+\frac{1}{2}{y}_{i}^2 \end{aligned}$$

for each $i=1,\ldots ,p$. Summing up from $i=1$ to p on both sides of the above inequalities, we get

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}+d_{0i}) \le \varphi (\varvec{x},\varvec{y}), \ \ \forall \varvec{x}\in D,\ \forall \varvec{y}\in S_0. \end{aligned}$$

(2.3)

Further, the equality in (2.3) holds if and only if ${y}_{i}=\varvec{d}_{i}^{T}\varvec{x}-\varvec{c}_{i}^{T}\varvec{x}+d_{0i}-c_{0i},\ i=1,\ldots ,p.$ Now, let $\overline{{y}}_{i}=\varvec{d}_{i}^{T}\overline{\varvec{x}}-\varvec{c}_{i}^{T}\overline{\varvec{x}}+d_{0i}-c_{0i}$, then $(\overline{\varvec{x}},\overline{\varvec{y}})$ is a feasible solution of EP, and it follows from (2.3) that

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\overline{\varvec{x}}+c_{0i})(\varvec{d}_{i}^{T}\overline{\varvec{x}}+d_{0i}) =\varphi (\overline{\varvec{x}},\overline{\varvec{y}}). \end{aligned}$$

(2.4)

According to $\varvec{x}^*\in D,\ \varvec{y}^*\in S_0$ and (2.3), we have

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}^{*}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}^{*}+d_{0i}) \le \varphi (\varvec{x}^{*},\varvec{y}^{*}). \end{aligned}$$

(2.5)

Then, by (2.2), (2.4) and (2.5), we follow that $\varphi (\overline{\varvec{x}},\overline{\varvec{y}})<\varphi (\varvec{x}^{*},\varvec{y}^{*}),$ which contradicts the optimality of $(\varvec{x}^{*},\varvec{y}^{*})$ for EP. Thus, $\varvec{x}^{*}$ is an optimal solution of LMP problem. In addition, for the optimal solution $(\varvec{x}^*,\varvec{y}^*)$ of EP problem, it must hold

$$\begin{aligned} {y}_{i}^{*}=\varvec{d}_{i}^{T}\varvec{x}^{*}-\varvec{c}_{i}^{T}\varvec{x}^{*}+d_{0i}-c_{0i}, \ i=1,\ldots ,p. \end{aligned}$$

(2.6)

In fact, if the formula (2.6) is not true, that is, ${y}_{i}^{*} \ne \varvec{d}_{i}^{T}\varvec{x}^{*}-\varvec{c}_{i}^{T}\varvec{x}^{*}+d_{0i}-c_{0i}, i=1,\ldots ,p$, let $\overline{{y}_{i}} =\varvec{d}_{i}^{T}\varvec{x}^{*}-\varvec{c}_{i}^{T}\varvec{x}^{*}+d_{0i}-c_{0i}, i=1,\ldots ,p$. Clearly, $\overline{{y}_{i}}\ne {y}_{i}^{*}$ for each i, and $(\varvec{x}^{*},\overline{\varvec{y}})$ is a feasible solution of EP. It follows from (2.3) that

$$\begin{aligned} \varphi (\varvec{x}^{*},\varvec{y}^{*})> \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}^{*}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}^{*}+d_{0i}) =\varphi (\varvec{x}^{*},\overline{\varvec{y}}). \end{aligned}$$

This contradicts the fact that $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution of EP. Additionally, since the soution of EP satisfies (2.6), by (2.3) we have $\varphi (\varvec{x}^*,\varvec{y}^*)=f(\varvec{x}^*).$

Conversely, assume that $\varvec{x}^{*}$ is an optimal solution of LMP problem. Let ${y}_{i}^{*}=\varvec{d}_{i}^{T}\varvec{x}^{*}-\varvec{c}_{i}^{T}\varvec{x}^{*}+d_{0i}-c_{0i},\ i=1,\ldots ,p.$ Then $(\varvec{x}^{*},\varvec{y}^{*})$ is the feasible solution of EP. Now, suppose EP exists a feasible solution $(\overline{\varvec{x}},\overline{\varvec{y}})$ such that

$$\begin{aligned} \varphi (\overline{\varvec{x}},\overline{\varvec{y}})<\varphi (\varvec{x}^{*},\varvec{y}^{*}). \end{aligned}$$

(2.7)

From (2.3), we obtain

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\overline{\varvec{x}}+c_{0i})(\varvec{d}_{i}^{T}\overline{\varvec{x}}+d_{0i}) \le \varphi (\overline{\varvec{x}},\overline{\varvec{y}}), \end{aligned}$$

(2.8)

and

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}^{*}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}^{*}+d_{0i}) = \varphi (\varvec{x}^{*},\varvec{y}^{*}). \end{aligned}$$

(2.9)

According to (2.7)–(2.9), we get

$$\begin{aligned} \sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\overline{\varvec{x}}+c_{0i})(\varvec{d}_{i}^{T}\overline{\varvec{x}}+d_{0i}) <\sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}^{*}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}^{*}+d_{0i}). \end{aligned}$$

This contradicts the optimality of $\varvec{x}^{*}$ to LMP problem. Therefore, $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution of EP problem. This completes the proof. $\square$

From Theorem 1, it is easy to see that we can solve LMP problem by solving EP problem. Next, for convenience, we further reformulate EP into the problem EP1 by

$$\begin{aligned} \mathbf{\textrm{EP1}:}\ \ \min \limits _{\varvec{y}\in S_{0}}{\psi (\varvec{y})} \end{aligned}$$

where $\psi (\varvec{y})=\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}).$ The following theorem illustrates that problems EP and EP1 are equivalent.

Theorem 2

$\varvec{y}^{*}$ is the optimal solution of EP1 if and only if $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution of EP with $\varvec{x}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*)$, and $\psi (\varvec{y}^*)=\varphi (\varvec{x}^*,\varvec{y}^*)$.

Proof

If $\varvec{y}^{*}$ is an optimal solution of EP1, it follows from $\varvec{x}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*)$ that

$$\begin{aligned} \varphi (\varvec{x}^*,\varvec{y}^*)=\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*). \end{aligned}$$

(2.10)

Let $(\overline{\varvec{x}},\overline{\varvec{y}})$ be the feasible solution of EP. Clearly, $\overline{\varvec{y}}$ is a feasible solution of EP1, then we have

$$\begin{aligned} \psi (\varvec{y}^*)\le \psi (\overline{\varvec{y}}). \end{aligned}$$

By the definition of $\psi (\varvec{y})$ and $\overline{\varvec{x}}\in D$, it follows that

$$\begin{aligned} \min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*)\le \min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}})\le \varphi (\overline{\varvec{x}},\overline{\varvec{y}}). \end{aligned}$$

(2.11)

From (2.10)–(2.11) we conclude that

$$\begin{aligned} \varphi (\varvec{x}^*,\varvec{y}^*)\le \varphi (\overline{\varvec{x}},\overline{\varvec{y}}). \end{aligned}$$

So, $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution to problem EP. Additionally, by invoking the definitions of $\varvec{x}^*$ and the function $\psi (\varvec{y})$, we have $\psi (\varvec{y}^*)=\varphi (\varvec{x}^*,\varvec{y}^*).$

Additionally, if $(\varvec{x}^{*},\varvec{y}^{*})$ is an optimal solution of EP, then $\varvec{y}^{*}$ is a feasible solution to EP1. Suppose that $\varvec{y}^{*}$ is not the optimal solution of EP1, then there exists $\overline{\varvec{y}}\in S_0$ such that

$$\begin{aligned} \psi (\overline{\varvec{y}})<\psi (\varvec{y}^*). \end{aligned}$$

(2.12)

From the definition of the function $\psi (\varvec{y})$ and $\varvec{x}^{*}\in D$, we conclude

$$\begin{aligned} \min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}) <\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*)\le \varphi (\varvec{x}^*,\varvec{y}^*). \end{aligned}$$

(2.13)

Note that $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution of problem EP, then

$$\begin{aligned} \varphi (\varvec{x}^*,\varvec{y}^*)=\min \limits _{\varvec{x}\in D,\varvec{y}\in S_0}\varphi (\varvec{x},\varvec{y})\le \min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*). \end{aligned}$$

(2.14)

Let $\overline{\varvec{x}}=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}).$ Then $(\overline{\varvec{x}},\overline{\varvec{y}})$ is a feasible solution of EP, and we have

$$\begin{aligned} \varphi (\overline{\varvec{x}},\overline{\varvec{y}})=\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}). \end{aligned}$$

(2.15)

Using (2.13)–(2.15), we obtain

$$\begin{aligned} \varphi (\overline{\varvec{x}},\overline{\varvec{y}})<\varphi (\varvec{x}^*,\varvec{y}^*). \end{aligned}$$

This contradicts that $(\varvec{x}^{*},\varvec{y}^{*})$ is the optimal solution of EP. Thus $\varvec{y}^{*}$ is the optimal solution of EP1. The proof is finished $\square$

According to Theorems 1 and 2, if $\varvec{y}^{*}$ and $\varvec{x}^{*}$ are the optimal solutions of problems EP1 and LMP, respectively, then we must have $\varvec{x}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y}^*)$ such that

$$\begin{aligned} \psi (\varvec{y}^*)=\varphi (\varvec{x}^*,\varvec{y}^*)=f(\varvec{x}^*), \end{aligned}$$

that is, problems EP1 and LMP have the same optimal value. In the following, we will focus on how to solve EP1.

2.2 Underestimation of EP1

In this subsection, for solving EP1 we first propose a lower bounding function for the objective function $\psi (\varvec{y})$ of EP1, then construct a convex quadratic relaxation to estimate the lower bound of the optimal value of EP1.

Let $S=[\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}]$ be $S_{0}$ or a sub-simplex of $S_{0}$, and define two sets of vertices and edges of S as follows:

$$\begin{aligned} V(S)=\{\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}\}, \ E(S)=\{[\varvec{u}^{i},\varvec{u}^{j}] \mid i,j=1,\ldots ,p+1,\ i<j\}. \end{aligned}$$

Define the length $\delta (S)$ of the longest side of S by

$$\begin{aligned} \delta (S)=\max \{\Vert \varvec{w}-\varvec{v}\Vert \ \mid \ [\varvec{w},\varvec{v}]\in E(S)\}. \end{aligned}$$

Now, the corresponding $\textrm{EP1}$ over S can be written as

$$\begin{aligned} {\mathbf{\textrm{EP1}}(S)}:\ \ \ \overline{\psi }_{S}=\min \limits _{\varvec{y}\in S}\psi (\varvec{y}), \end{aligned}$$

where $\psi (\varvec{y)}=\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{y})$.

We next present a result to show a lower bounding function for the objective function $\psi (\varvec{y})$ of problem EP1(S), by relaxing $\sum \nolimits _{i=1}^{p}\frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x} +c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}+d_{0i})^2]$ and $\varvec{c}_{i}^{T}\varvec{x}-\varvec{d}_{i}^{T}\varvec{x}+c_{0i}-d_{0i}$ in the function $\varphi (\varvec{x},\varvec{y})$, to $w\in R$ and ${z}_i\in R$, respectively.

Theorem 3

For any given $\varvec{y}\in S=[\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}]$, consider the problem $(\mathrm{{P}}_{\varvec{y}})$ by

$$\begin{aligned} \mathbf{\mathrm {(P}}_{\varvec{y}}):\left\{ \begin{array}{lcl} \phi (\varvec{y})=&{}\min \limits _{w\in R, \varvec{z}\in R^{p}}&{}g(w,\varvec{z})=w+\varvec{y}^{T}\varvec{z}+\frac{1}{2}\varvec{y}^{T}\varvec{y}\\ &{}\mathrm {s.t.}&{} w+{\varvec{u}^{j}}^{T}\varvec{z}\ge \psi (\varvec{u}^{j})-\frac{1}{2}{\varvec{u}^{j}}^{T}\varvec{u}^{j},\ j=1,\ldots ,p+1, \end{array} \right. \end{aligned}$$

then we have $\psi (\varvec{y)}\ge \phi (\varvec{y})$.

Proof

For any given $\varvec{y}\in S,$ let

$$\begin{aligned} \varvec{x}(\varvec{y})=\mathop {\arg \min }\{\varphi (\varvec{x},\varvec{y})\ |\ \varvec{x}\in D\}, \end{aligned}$$

then we have $\varvec{x}(\varvec{y})\in D$ and $\psi (\varvec{y})=\varphi (\varvec{x}(\varvec{y}),\varvec{y}).$ By using $\varvec{x}(\varvec{y})\in D$ and the definition of the function $\varphi$, we can obtain

$$\begin{aligned} \begin{array}{lll} \psi (\varvec{u}^{j})&{}=&{}\min \limits _{\varvec{x}\in D}\varphi (\varvec{x},\varvec{u}^{j})\\ &{}\le &{}\varphi (\varvec{x}(\varvec{y}),\varvec{u}^{j})\\ &{}=&{}\sum \limits _{i=1}^{p}\frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x}(\varvec{y}) +c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+d_{0i})^2]\\ &{}&{}+\sum \limits _{i=1}^{p}{u}_{i}^{j} (\varvec{c}_{i}^{T}\varvec{x}(\varvec{y})-\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+c_{0i}-d_{0i}) +\frac{1}{2}{\varvec{u}^{j}}^{T}\varvec{u}^{j}. \end{array} \end{aligned}$$

(2.16)

Now, for simplifying the right-hand side of the inequality (2.16), let us denote

$$\begin{aligned} \begin{array}{l} \overline{w}=\sum \limits _{i=1}^{p}\frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x}(\varvec{y}) +c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+d_{0i})^2],\\ \overline{{z}}_{i}=\varvec{c}_{i}^{T}\varvec{x}(\varvec{y})-\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+c_{0i}-d_{0i}, \ i=1,\ldots ,p. \end{array} \end{aligned}$$

Thus, it follows from (2.16) that

$$\begin{aligned} \psi (\varvec{u}^{j})\le \overline{w}+{\varvec{u}^{j}}^{T}\overline{\varvec{z}}+\frac{1}{2}{\varvec{u}^{j}}^{T}\varvec{u}^{j},\ j=1,\ldots ,p+1. \end{aligned}$$

As a result, $(\overline{w},\overline{\varvec{z}})$ is the feasible solution of problem ($\textrm{P}_{\varvec{y}}$), and its corresponding objective function value is as follows:

$$\begin{aligned} \begin{array}{ll} g(\overline{w},\overline{\varvec{z}})&{}=\overline{w}+\varvec{y}^{T}\overline{\varvec{z}} +\frac{1}{2}{\varvec{y}}^{T}\varvec{y}\\ &{}=\sum \limits _{i=1}^{p}\{\frac{1}{2}[(\varvec{c}_{i}^{T}\varvec{x}(\varvec{y}) +c_{0i})^2+(\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+d_{0i})^2]\\ &{}\quad +{y}_{i}(\varvec{c}_{i}^{T}\varvec{x}(\varvec{y})-\varvec{d}_{i}^{T}\varvec{x}(\varvec{y})+c_{0i}-d_{0i})\} +\frac{1}{2}{\varvec{y}}^{T}\varvec{y}. \end{array} \end{aligned}$$

According to the definition of $\varphi (\varvec{x},\varvec{y})$, we get

$$\begin{aligned} g(\overline{w},\overline{\varvec{z}})=\varphi (\varvec{x}(\varvec{y}),\varvec{y}). \end{aligned}$$

Since $\psi (\varvec{y})=\varphi (\varvec{x}(\varvec{y}),\varvec{y})$, we have $\psi (\varvec{y})=g(\overline{w},\overline{\varvec{z}})$. Note that $\phi (\varvec{y})$ is the optimal value of problem ($\textrm{P}_{\varvec{y}}$), we can conclude $\psi (\varvec{y})=g(\overline{w},\overline{\varvec{z}})\ge \phi (\varvec{y})$. The proof of the theorem is completed. $\square$

For any fixed $\varvec{y}\in S$, notice that ($\textrm{P}_{\varvec{y}}$) problem in Theorem 3 is a linear program, then the dual problem of ($\textrm{P}_{\varvec{y}}$) is as follows:

$$\begin{aligned} \mathbf{\textrm{DP}}_{\varvec{y}}:\left\{ \begin{array}{lcl} \overline{\phi }(\varvec{y})=&{}\max &{}\sum \limits _{j=1}^{p+1}{\xi }_{j}(\psi (\varvec{u}^{j})-\frac{1}{2}{\varvec{u}^{j}}^{T}\varvec{u}^{j}) +\frac{1}{2}{\varvec{y}}^{T}\varvec{y}\\ &{}\mathrm {s.t.}&{}\sum \limits _{j=1}^{p+1}{\xi }_{j}=1,\\ &{}&{}\sum \limits _{j=1}^{p+1}{\xi }_{j}\varvec{u}^{j}-\varvec{y}=0,\\ &{}&{}{\xi }_{j}\ge 0,\ j=1,\ldots ,p+1. \end{array} \right. \end{aligned}$$

By the strong duality, we get $\phi (\varvec{y})=\overline{\phi }(\varvec{y})$. Additionally, for any $\varvec{y}\in S$, we know that there exists the unique $\varvec{\lambda }\in R^{p+1}$ such that

$$\begin{aligned} \varvec{y}=\sum \limits _{j=1}^{p+1}{\lambda }_{j}\varvec{u}^{j},\ \sum \limits _{j=1}^{p+1}{\lambda }_{j}=1,\ {\lambda }_{j}\ge 0,\ j=1,\ldots ,p+1. \end{aligned}$$

(2.17)

Thus problem $\textrm{DP}_{\varvec{y}}$ has an unique feasible solution $\varvec{\lambda }$, that is, the optimal solution to $\textrm{DP}_{\varvec{y}}$ is $\varvec{\lambda }$ and the optimal value is

$$\begin{aligned} \overline{\phi }(\varvec{y})=\sum \limits _{j=1}^{p+1}{\lambda }_{j}(\psi (\varvec{u}^{j}) -\frac{1}{2}{\varvec{u}^{j}}^{T}\varvec{u}^{j})+\frac{1}{2}{\varvec{y}}^{T}\varvec{y}. \end{aligned}$$

(2.18)

Additionally, let us denote

$$\begin{aligned} \varvec{m}_{\varvec{u}}=[\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}],\ \ \varvec{m}_{\psi }=[\psi (\varvec{u}^{1}),\ldots ,\psi (\varvec{u}^{p+1})]^{T}, \end{aligned}$$

and let $\mathrm{{diag}}(\cdot )$ be a vector whose components are the diagonal elements of a square matrix $(\cdot )$. Substituting $\varvec{y}=\sum \limits _{j=1}^{p+1}{\lambda }_{j}\varvec{u}^{j}$ into (2.18) and utilizing Theorem 3, we have

$$\begin{aligned} \psi (\varvec{y})\ge \phi (\varvec{y})=\overline{\phi }(\varvec{y})={\varvec{\lambda }}^{T}M_{S}\varvec{\lambda }+{\varvec{m}_{S}}^{T}\varvec{\lambda }, \end{aligned}$$

(2.19)

where

$$\begin{aligned} M_{S}=\frac{1}{2}\varvec{m}_{\varvec{u}}^{T}\varvec{m}_{\varvec{u}}, \ \ \ \varvec{m}_{S}=\varvec{m}_{\psi }-\frac{1}{2}\mathrm{{diag}} (\varvec{m}_{\varvec{u}}^{T}\varvec{m}_{\varvec{u}}). \end{aligned}$$

Note that the matrix $M_{S}$ is a positive semi-definite matrix, and the corresponding convex quadratic programming (CQP) problem with respect to S will be considered as follows:

$$\begin{aligned} \mathbf{\textrm{CQP}}(S):\left\{ \begin{array}{lcl} \widehat{\phi }_{S}=&{}\min &{}{\varvec{\lambda }}^{T}M_{S}\varvec{\lambda }+{\varvec{m}_{S}}^{T}\varvec{\lambda }\\ &{}\mathrm {s.t.}&{}\sum \limits _{j=1}^{p+1}{\lambda }_{j}=1,\\ &{}&{}{\lambda }_{j}\ge 0,\ j=1,\ldots ,p+1, \end{array} \right. \end{aligned}$$

whose optimal value can be used as a lower bound on the optimal value of EP1(S) (see Theorem 4).

Theorem 4

For any $S\subseteq S_0$, we have

$$\begin{aligned} \min \limits _{\varvec{y}\in S}{\psi (\varvec{y})}\ge \min \limits _{\varvec{y}\in S}\phi (\varvec{y})= \min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})=\widehat{\phi }_{S}. \end{aligned}$$

where $\widehat{\phi }_{S}$ is the optimal value of $\textrm{CQP}(S)$ problem.

Proof

From Theorem 3 and the dual problem $\textrm{DP}_{\varvec{y}}$, we can easily get

$$\begin{aligned} \min \limits _{\varvec{y}\in S}{\psi (\varvec{y})}\ge \min \limits _{\varvec{y}\in S}\phi (\varvec{y})= \min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y}). \end{aligned}$$

Next, we will show $\min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})=\widehat{\phi }_{S}.$ For convenience, let us consider the following problem:

$$\begin{aligned} \mathrm{(\widehat{P}}_{S}): \ \ \min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})=\overline{\phi }(\varvec{y^*}), \end{aligned}$$

where $\varvec{y^*}$ is the optimal solution to problem $\mathrm{(\widehat{P}}_{S})$. Now, assume that $S=[\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}]$, then there exists the unique $\varvec{\lambda }^{*}\in R^{p+1}$ such that

$$\begin{aligned} \varvec{y}^{*}=\sum \limits _{j=1}^{p+1}{\lambda }_{j}^{*}\varvec{u}^{j},\ \sum \limits _{j=1}^{p+1}{\lambda }_{j}^{*}=1,\ {\lambda }_{j}^{*}\ge 0,\ j=1,\ldots ,p+1. \end{aligned}$$

(2.20)

Substituting $\varvec{y}^*$ into the objective function of problem $\mathrm{(\widehat{P}}_{S})$ and using (2.18)–(2.19), we have

$$\begin{aligned} \overline{\phi }(\varvec{y}^{*})={\varvec{\lambda }^{*}}^{T}M_{S}\varvec{\lambda }^{*}+{\varvec{m}_{S}}^{T}\varvec{\lambda }^{*}. \end{aligned}$$

Thus, it follows from (2.20) that $\varvec{\lambda }^{*}$ is the feasible solution of CQP(S) problem, and so $\overline{\phi }(\varvec{y}^{*})\ge \widehat{\phi }_{S},$ i.e.,

$$\begin{aligned} \min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})\ge \widehat{\phi }_{S}. \end{aligned}$$

(2.21)

Additionally, suppose that the optimal solution of CQP(S) problem is $\overline{\varvec{\lambda }}$, then

$$\begin{aligned} \sum \limits _{j=1}^{p+1}\overline{{\lambda }}_j=1,\ \overline{{\lambda }}_j\ge 0,\ j=1,\ldots ,p+1, \end{aligned}$$

and the corresponding optimal value is

$$\begin{aligned} \widehat{\phi }_{S}={\overline{\varvec{\lambda }}}^{T}M_{S}\overline{\varvec{\lambda }}+{\varvec{m}_{S}}^{T}\overline{\varvec{\lambda }}. \end{aligned}$$

Let $\overline{\varvec{y}}=\sum \limits _{j=1}^{p+1}\overline{{\lambda }}_{j}\varvec{u}^{j},$ and it is clear that $\overline{\varvec{y}}$ is a feasible solution of problem $\mathrm{(\widehat{P}}_{S})$. Substituting $\overline{\varvec{y}}$ into the objective function of problem $\mathrm{(\widehat{P}}_{S})$ and using (2.18)–(2.19) again, we know that

$$\begin{aligned} \overline{\phi }(\overline{\varvec{y}})={\overline{\varvec{\lambda }}}^{T}M_{S}\overline{\varvec{\lambda }}+{\varvec{m}_{S}}^{T}\overline{\varvec{\lambda }} =\widehat{\phi }_{S}. \end{aligned}$$

This implies that $\min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})\le \widehat{\phi }_{S}.$ By (2.21) we have $\min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})=\widehat{\phi }_{S}.$ This completes the proof. $\square$

In the following, we will show that the optimal value of CQP(S) problem is sufficiently close to one of EP1(S) problem, when the length of the longest side of the simplex S is sufficiently small.

Theorem 5

Given $\varepsilon >0$ and the simplex $S=[\varvec{u}^{1},\ldots ,\varvec{u}^{p+1}]$, let $\delta _{0}=\max \limits _{1\le j\le p+1}\Vert \varvec{u}^{j}\Vert$. Assume that $\overline{\psi }_{S}$ and $\widehat{\phi }_{S}$ are the optimal values of problems $\textrm{EP1}(S)$ and $\textrm{CQP}(S)$, respectively. Then we have

$$\begin{aligned} \overline{\psi }_{S}-\widehat{\phi }_{S}\le \varepsilon \end{aligned}$$

if $\delta (S)\le \varepsilon /\delta _{0}.$

Proof

Let $\psi _{0}=\min \limits _{1\le j\le p+1}\psi (\varvec{u}^j)$, and suppose that $\Vert \varvec{u}^{j0}\Vert ^{2}=\max \limits _{1\le j\le p+1}\Vert \varvec{u}^{j}\Vert ^{2}$. From $\varvec{u}^j\in S$ we can conclude that

$$\begin{aligned} \psi _{0}\ge \min \limits _{\varvec{y}\in S}\psi (\varvec{y})=\overline{\psi }_{S}. \end{aligned}$$

(2.22)

In addition, Theorem 4 implies $\widehat{\phi }_{S}=\min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})$. For any $\varvec{y}\in S$, there exists the unique $\varvec{\lambda }$ satisfying (2.17). According to (2.18), we know that

$$\begin{aligned} \overline{\phi }(\varvec{y})\ge \sum \limits _{j=1}^{p+1}{\lambda }_{j}(\psi _0 -\frac{1}{2}\Vert \varvec{u}^{j0}\Vert ^2)+\frac{1}{2}{\varvec{y}}^{T}\varvec{y} =\psi _{0}+\frac{1}{2}(\Vert \varvec{y}\Vert ^{2}-\Vert \varvec{u}^{j0}\Vert ^{2}). \end{aligned}$$

Thus

$$\begin{aligned} \widehat{\phi }_{S}=\min \limits _{\varvec{y}\in S}\overline{\phi }(\varvec{y})\ge \psi _{0}+\min \limits _{\varvec{y}\in S}\{\frac{1}{2}(\Vert \varvec{y}\Vert ^{2}-\Vert \varvec{u}^{j0}\Vert ^{2})\}. \end{aligned}$$

(2.23)

Using $\varvec{y}=\sum \limits _{j=1}^{p+1}{\lambda }_{j}\varvec{u}^{j}$ for any $\varvec{y}\in S$, we can derive that

$$\begin{aligned} \Vert \varvec{y}\Vert +\Vert \varvec{u}^{j0}\Vert&=\Vert \sum \limits _{j=1}^{p+1}{\lambda }_{j}\varvec{u}^{j}\Vert +\Vert \varvec{u}^{j0}\Vert \le \sum \limits _{j=1}^{p+1}{\lambda }_{j}\Vert \varvec{u}^{j}\Vert +\Vert \varvec{u}^{j0}\Vert \le 2\delta _{0},\\ \Vert \varvec{y}\Vert -\Vert \varvec{u}^{j0}\Vert&\ge -\Vert \varvec{y}-\varvec{u}^{j0}\Vert \\&=-\Vert \sum \limits _{j=1}^{p+1}{\lambda }_{j}(\varvec{u}^{j}-\varvec{u}^{j0})\Vert \\&\ge -\sum \limits _{j=1}^{p+1}{\lambda }_{j}\Vert \varvec{u}^{j}-\varvec{u}^{j0}\Vert \\&\ge -\sum \limits _{j=1}^{p+1}{\lambda }_{j}\max \limits _{1\le j\le p+1}\Vert \varvec{u}^{j}-\varvec{u}^{j0}\Vert \\&\ge -\delta (S) \end{aligned}$$

which implies that

$$\begin{aligned} \Vert \varvec{y}\Vert ^{2}-\Vert \varvec{u}^{j0}\Vert ^{2}=(\Vert \varvec{y}\Vert +\Vert \varvec{u}^{j0}\Vert )(\Vert \varvec{y}\Vert -\Vert \varvec{u}^{j0}\Vert ) \ge -2\delta _{0}\delta (S). \end{aligned}$$

(2.24)

This, together with (2.23)–(2.24), yields

$$\begin{aligned} \widehat{\phi }_{S}\ge \psi _{0}-\delta _{0}\cdot \delta (S), \end{aligned}$$

(2.25)

and so it follows from (2.22) and (2.25) that

$$\begin{aligned} \overline{\psi }_{S}-\widehat{\phi }_{S}\le \delta _{0}\cdot \delta (S). \end{aligned}$$

This achieves the proof. $\square$

3 Simplicial branch-and-bound algorithm

Based on the above discussion, by combining the CQP problem and the simplicial branching rule to be proposed, we will develop a simplicial branch-and-bound algorithm for globally solving LMP problem within a prescribed $\varepsilon$ tolerance. We also establish the convergence of the algorithm and estimate its complexity.

The main idea of the proposed algorithm consists of two basic operations: successively refined partitioning of the simplices and estimation of bounds for the optimal value of LMP problem given by Theorem 4.

3.1 Simplicial partitioning rule

In order to give the partitioning rules needed for the proposed algorithm, we first introduce the relevant definitions and notations as follows.

Given a simplex $S\subseteq S^0$, we say that a finite set of nonempty simplices, denoted ${\mathscr {P}}=\{S_{i}\ | \ i\in {\mathscr {I}}\}$, is called as a simplicial partition of S, if

$$\begin{aligned} S=\bigcup _{i\in {\mathscr {I}}}S_{i},\ S_{i}\bigcap S_{j}=\mathrm{{rbd}}S_{i}\bigcap \mathrm{{rbd}}S_{j},\ \forall \ i,j\in {\mathscr {I}},\ i\ne j, \end{aligned}$$

where ${\mathscr {I}}$ denotes a finite index set, and $\mathrm{{rbd}}$ stands for the relative boundary of a set.

For a simplicial partition ${\mathscr {P}}$, its vertex collection $V({\mathscr {P}})$, the boundary set $E({\mathscr {P}})$ and the diameter $\delta ({\mathscr {P}})$ can be defined separately, given by

$$\begin{aligned} V({\mathscr {P}})=\bigcup _{S_{i}\in {\mathscr {P}}}V(S_{i}), \ \ E({\mathscr {P}})=\bigcup _{S_{i}\in {\mathscr {P}}}E(S_{i}), \ \ \delta ({\mathscr {P}})=\max \{\delta (S_{i})|S_{i}\in {\mathscr {P}}\}. \end{aligned}$$

For two simplicial partitions ${\mathscr {P}}_1=\{S_{i}\ | \ i\in {\mathscr {I}}_1\},$ ${\mathscr {P}}_2=\{S_{j}\ | \ j\in {\mathscr {I}}_2\},$ we say that ${\mathscr {P}}_2$ is nested in ${\mathscr {P}}_1$, if there exists $i\in {\mathscr {I}}_1$ such that $S_{j}\subseteq S_{i}$, for all $j\in {\mathscr {I}}_2$. We say that a sequence of simplicial partitions $\{{\mathscr {P}}_k\ | \ k\in {\mathbb {N}}\}$ is a sequence of nested partitions if ${\mathscr {P}}_{k+1}$ is nested in ${\mathscr {P}}_k$ for all $k\in {\mathbb {N}}$, where ${\mathbb {N}}$ is the set of natural numbers.

Now, we begin with the establishment of the simplicial partitioning rule to present the branch-and-bound algorithm for solving LMP. At every iteration of the algorithm, the proposed partitioning rule is adopted to subdivide simplices. The partition approach used in each iteration is that we first choose the longest edge of the current sub-simplices and then simultaneously subdivide all sub-simplices with the common selected longest edge. The detailed simplicial partitioning rule is given as follows:

Simplicial partitioning rule:

Input: An initial p-simplex $S_0$.

Output: A sequence of nested partitions of $S_0$, denoted $\{{\mathscr {P}}_{k}| k \in {\mathbb {N}} \}$.

• Step 1: Let ${\mathscr {P}}_{0}=\{S_{0}\},\ k=0.$

• Step 2: for $k \in {\mathbb {N}}$ do The nested simplicial partitions ${\mathscr {P}}_{k+1}$ of ${\mathscr {P}}_{k}$ is generated by Steps 2.a and 2.b:

  • (Step 2.a) Select the longest edge $[\varvec{w},\varvec{v}]$ from $E({\mathscr {P}}_{k})$, and let $\varvec{t}=(\varvec{w}+\varvec{v})/2.$

  • (Step 2.b) For every $S_{i}\in {\mathscr {P}}_{k}$ satisfying $[\varvec{w},\varvec{v}]\in E(S_{i})$, let $\{\varvec{u}^{1},\ldots ,\varvec{u}^{p-1}\}=V(S_{i})\backslash \{\varvec{w},\varvec{v}\}.$ Update ${\mathscr {P}}_{k+1}={\mathscr {P}}_{k}\backslash S_{i}\bigcup \{S_{i,1},S_{i,2}\},$ where $S_{i,1}=[\varvec{w},\varvec{t},$ $\varvec{u}^{1},\ldots ,\varvec{u}^{p-1}],$ $S_{i,2}=[\varvec{t},\varvec{v},\varvec{u}^{1},\ldots ,\varvec{u}^{p-1}].$

• Step 3: end for

From the above simplicial partition, the following lemma follows immediately.

Lemma 1

For an initial p-simplex $S_0$, consider the above simplicial partition rule, then the following three statements are valid.

• (i) The sequence of nested partitions $\{{\mathscr {P}}_{k}\}$ is exhaustive, i.e., $\delta ({\mathscr {P}}_{k})\rightarrow 0, k\rightarrow \infty .$

• (ii) If a parameter q is selected such that $q\in (0,\delta (S_0)]$, and let

  $$\begin{aligned} \eta =\frac{\sqrt{3}}{2},\ \beta =\lceil \log _{\eta }(q/\delta (S_0))\rceil ,\ K=(p+1)^{2^{\beta }}, \end{aligned}$$

  then we have

  $$\begin{aligned} \delta ({\mathscr {P}}_{k})\le q, \ \mathrm{for\ all }\ k\ge K. \end{aligned}$$

• (iii) K is a strict upper bound on the total number of vertices at the K-th iteration.

Proof

For the proof of this lemma, we can refer to Theorem 4.3 and Lemmas 4.5 and 4.9 in [29]. $\square$

3.2 Simplicial branch-and-bound algorithm

In this subsection, we develop a simplicial branch-and-bound algorithm (SBBA) that can find a global optimal solution to LMP problem within a pre-specified $\varepsilon$-tolerance by combining the simplicial partitioning rule and the proposed CQP relaxation. The algorithm is assumed that an initial p-simplex $S_0$ containing $[\varvec{y}^{min},\varvec{y}^{max}]$ has been constructed by using (2.1), and such an initial algorithm may be stated as follows.

Algorithm: SBBA

Step 0 :

(Initialization): Given the convergence tolerance $\varepsilon >0$, solve problem $\textrm{CQP}(S_{0})$ to obtain the optimal value $\widehat{\phi }_{S_{0}}.$ Let $LB_{0}=\widehat{\phi }_{S_{0}}$ be the lower bound of the optimal value of $\textrm{EP1}$. Let $\psi (\varvec{u}^{0j_0})=\min \{\psi (\varvec{u}^{0j})\ |\ j=1,\ldots ,p+1\}$, $\overline{\varvec{y}}^*=\varvec{u}^{0j_0}.$ Let $\overline{UB}=\psi (\overline{\varvec{y}}^*)$ be the upper bound of the optimal value of $\textrm{EP1}$. If $\overline{UB}-LB_{0}\le \varepsilon$, stop, $\overline{\varvec{y}}^*$ is the global $\varepsilon$-optimal solution of EP1, $\overline{\varvec{x}}^*$ is the global $\varepsilon$-optimal solution of LMP problem, where $\overline{\varvec{x}}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}^*)$. Otherwise, set $k=0,\ \Omega =\{S_{0}\}.$

Step 1::

Let $\overline{S}=\mathop {\arg \max }_{S\in \Omega }\delta (S).$ Select the longest edge $[\varvec{w},\varvec{v}]\in E(\overline{S})$ of $\overline{S}$ satisfying $\Vert \varvec{w}-\varvec{v}\Vert =\delta (\overline{S}).$ Let $\varvec{t}=(\varvec{w}+\varvec{v})/2$ and calculate $\psi (\varvec{t})$. If $\overline{UB}>\psi (\varvec{t}),$ update $\overline{UB}=\psi (\varvec{t}), \ \overline{\varvec{y}}^*=\varvec{t}.$

Step 2::

For every $S_{k}\in \Omega$ satisfying $[\varvec{w},\varvec{v}]\in E(S_{k})$, bisect each $S_{k}$ into two new sub-simplices $S_{k,1}, S_{k,2}$ by $\varvec{t}$ (see details in (Step2.b) of the simplicial partitioning rule above). Set $H=\{S_{k,1},S_{k,2}\}.$

Step 3::

For each simplex $S_{k,j}(j=1,2),$ solve the corresponding problem $\textrm{CQP}(S_{k,j})$ to obtain the optimal value $\widehat{\phi }_{S_{k,j}}.$ Let $LB(S_{k,j})=\widehat{\phi }_{S_{k,j}}.$ If $LB(S_{k,j})>\overline{UB},$ set $H=H\backslash {S_{k,j}}.$ Let $\Omega =(\Omega \backslash S_{k})\bigcup H,\ LB_{k}=\min \{LB(S)\ | \ S\in \Omega \}.$

Step 4::

Set $\Omega =\Omega \backslash \{S \ |\ \overline{UB}-LB(S)\le \varepsilon ,S\in \Omega \}.$ If $\Omega =\emptyset ,$ stop, $\overline{\varvec{y}}^*$ is the global $\varepsilon$-optimal solution of EP1, and $\overline{\varvec{x}}^*$ is the global $\varepsilon$-optimal solution of LMP problem, where $\overline{\varvec{x}}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}^*)$; Otherwise, set $k=k+1$ and go to Step 1.

3.3 Convergence and complexity of SBBA

In this subsection, we present the new convergence result of the proposed SBBA and estimate its computational complexity.

Lemma 2

For any $\varvec{y}\in S_0=[\varvec{u}^{0,1},\ldots ,\varvec{u}^{0,p+1}]$, there exists a positive constant $\alpha$ such that $\Vert \varvec{y}\Vert \le \alpha ,$ where

$$\begin{aligned} \alpha =\sqrt{\sum \limits _{i=1}^{p}(2p-1)^{2}{\max \{|{y}_{i}^{min}|,|{y}_{i}^{max}|\}}^{2}}. \end{aligned}$$

Proof

For any $\varvec{y}\in S_0=[\varvec{u}^{0,1},\ldots ,\varvec{u}^{0,p+1}]$, there exists $\varvec{\lambda }$ satisfying

$$\begin{aligned} \varvec{y}=\sum \limits _{j=1}^{p+1}{\lambda }_{j}\varvec{u}^{0j},\ \sum \limits _{j=1}^{p+1}{\lambda }_{j}=1,\ {\lambda }_{j}\ge 0,\ j=1,\ldots ,p+1. \end{aligned}$$

Then, for the i-th component ${y}_{i}$ of $\varvec{y}$, $i\in \{1,\ldots ,p\}$, we have

$$\begin{aligned} |{y}_{i}|=|\sum \limits _{j=1}^{p+1}{\lambda }_{j}{u}_{i}^{0j}| \le \sum \limits _{j=1}^{p+1}{\lambda }_{j}|{u}_{i}^{0j}| ={\lambda }_{i+1}|{u}_{i}^{0,i+1}| +\sum \limits _{j\ne i+1}{\lambda }_{j}|{u}_{i}^{0j}|. \end{aligned}$$

(3.1)

From (2.1), the i-th component of the $(i+1)$-th vertex $\varvec{u}^{0,i+1}$ of $S_0$ satisfies

$$\begin{aligned} |{u}_{i}^{0,i+1}|= & {} |{y}_{i}^{min}+p({y}_{i}^{max}-{y}_{i}^{min})| \le (p-1)|{y}_{i}^{min}|+p|{y}_{i}^{max}|\\\le & {} (2p-1)\max \{|{y}_{i}^{min}|,|{y}_{i}^{max}|\}, \end{aligned}$$

and for the i-th component of the j-th vertex $\varvec{u}^{0,j}$ of $S_0$, we have

$$\begin{aligned} |{u}_{i}^{0j}|=|{y}_{i}^{min}| \le (2p-1)\max \{|{y}_{i}^{min}|,|{y}_{i}^{max}|\},\ \forall j\in \{1,\ldots ,p+1\},\ j\ne i+1. \end{aligned}$$

According to the above relation and (3.1), it holds that

$$\begin{aligned} |{y}_{i}|\le (2p-1)\max \{|{y}_{i}^{min}|,|{y}_{i}^{max}|\},\ i=1,\ldots ,p.\\ \end{aligned}$$

Further, we have

$$\begin{aligned} \Vert \varvec{y}\Vert _2^{2}=\sum \limits _{i=1}^{p}{|{y}_{i}|}^2\le \sum \limits _{i=1}^{p}(2p-1)^{2}{\max \{|{y}_{i}^{min}|,|{y}_{i}^{max}|\}}^{2}=\alpha . \end{aligned}$$

Thus, the proof is finished. $\square$

Theorem 6

Given $\varepsilon >0$, let $f^*$ be the optimal value of LMP problem. At the k-th iteration, if the sequence of simplicial partitions $\{{\mathscr {P}}_{k}\}$ satisfies that $\delta ({\mathscr {P}}_{k})\le \varepsilon /\alpha$, where $\alpha$ is given by Lemma 2, then the proposed SBBA stops and returns an $\varepsilon$-optimal solution of LMP problem in the sense that

$$\begin{aligned} f(\overline{\varvec{x}}^*)\le f^*+\varepsilon . \end{aligned}$$

Proof

At the k-th iteration, let $\widehat{S}_k=\mathop {\arg \min }_{S\in \Omega }LB(S)$. By Step 3 of SBBA, it follows that $LB_k=LB(\widehat{S}_k)=\widehat{\phi }_{\widehat{S}_k}.$ Assume that the set of all vertices of the simplex $\widehat{S}_k$ is $\{\widehat{\varvec{u}}^{k1},\ldots ,\widehat{\varvec{u}}^{k,p+1}\}.$ From Lemma 2 we have $\Vert \widehat{\varvec{u}}^{kj}\Vert \le \alpha$ for each $j\in \{1,\ldots ,p+1\}$. This implies that

$$\begin{aligned} \max \limits _{1\le j\le p+1}\Vert \widehat{\varvec{u}}^{kj}\Vert \le \alpha . \end{aligned}$$

(3.2)

Similar to the proof of Theorem 5, by using (3.2) and (2.25) we obtain

$$\begin{aligned} \widehat{\phi }_{\widehat{S}_k}\ge \min \limits _{1\le j\le p+1}\psi (\widehat{\varvec{u}}^{kj})-\max \limits _{1\le j\le p+1}\Vert \widehat{\varvec{u}}^{kj}\Vert \delta (\widehat{S}_k)\ge \min \limits _{1\le j\le p+1}\psi (\widehat{\varvec{u}}^{kj})-\alpha \delta (\widehat{S}_k). \end{aligned}$$

Let $\psi (\widehat{\varvec{u}}^{kj_{0}})=\min \limits _{1\le j\le p+1}\psi (\widehat{\varvec{u}}^{kj}),$ and from the above inequality it follows that

$$\begin{aligned} \psi (\widehat{\varvec{u}}^{kj_0})-\widehat{\phi }_{\widehat{S}_k} \le \psi (\widehat{\varvec{u}}^{kj_0})-\min \limits _{1\le j\le p+1}\psi (\widehat{\varvec{u}}^{kj}) +\alpha \delta (\widehat{S}_k)=\alpha \delta (\widehat{S}_k). \end{aligned}$$

Furthermore, since $\overline{UB}$ is updated by the value of $\psi (\varvec{y})$ at the vertexes of the simplex, and so

$$\begin{aligned} \overline{UB}-LB_k\le \psi (\widehat{\varvec{u}}^{kj_0})-LB_k =\psi (\widehat{\varvec{u}}^{kj_0})-\widehat{\phi }_{\widehat{S}_k}\le \alpha \delta (\widehat{S}_k). \end{aligned}$$

(3.3)

If the sequence of simplicial partitions $\{{\mathscr {P}}_{k}\}$ satisfies that $\delta ({\mathscr {P}}_{k})\le \varepsilon /\alpha$, we see from $\widehat{S}_k\in {\mathscr {P}}_{k}$ that $\delta (\widehat{S}_k)\le \varepsilon /\alpha$. According to Steps 3 and 4 of the algorithm, using (3.3) we get for any $S\in \Omega$

$$\begin{aligned} \overline{UB}-LB(S)\le \overline{UB}-LB_k\le \varepsilon . \end{aligned}$$

(3.4)

Thus the algorithm stops. Let $\psi ^*$ denote the optimal value of EP1. From the algorithm we have $\overline{UB}=\psi (\overline{\varvec{y}}^*)$, and it follows from (3.4) that

$$\begin{aligned} \psi (\overline{\varvec{y}}^*)-\psi ^*=\overline{UB}-\psi ^*\le \overline{UB}-LB_k\le \varepsilon . \end{aligned}$$

(3.5)

Therefore, $\overline{\varvec{y}}^*$ is the global $\varepsilon$-optimal solution of EP1. Now, let us consider problems LMP and EP1 again. Denote $\overline{\varvec{x}}^*=\mathop {\arg \min }_{\varvec{x}\in D}\varphi (\varvec{x},\overline{\varvec{y}}^*)$. The definition of $\psi (\varvec{y})$ implies that $\varphi (\overline{\varvec{x}}^*,\overline{\varvec{y}}^*)=\psi (\overline{\varvec{y}}^*).$ According to (2.3) in the proof of Theorem 1, for any $\overline{\varvec{x}}^*\in D,\ \overline{\varvec{y}}^*\in S_0$, we have

$$\begin{aligned} f(\overline{\varvec{x}}^*)\le \varphi (\overline{\varvec{x}}^*,\overline{\varvec{y}}^*). \end{aligned}$$

Using Theorems 1 and 2 it holds that $f^*=\psi ^*$. Further, from (3.5) we obtain

$$\begin{aligned} f(\overline{\varvec{x}}^*)-f^*\le \varphi (\overline{\varvec{x}}^*,\overline{\varvec{y}}^*)-\psi ^* =\psi (\overline{\varvec{y}}^*)-\psi ^*\le \varepsilon . \end{aligned}$$

So $\overline{\varvec{x}}^*$ is the $\varepsilon$-optimal solution of LMP problem, and the proof of the theorem is completed. $\square$

Next, by using Lemma 1 we can summarize the result on the worst-case complexity of the proposed SBBA. Let $T(a_1,a_2)$ be the time taken to solve a CQP problem with $a_1$ variables and $a_2$ constraints. Based on the above analysis, we have the following results.

Theorem 7

For sufficiently small $\varepsilon >0$ satisfying $\varepsilon /\alpha \in (0,\delta (S_0)]$, let

$$\begin{aligned} \widehat{\beta }=\lceil \log _{\sqrt{3}/2}(\varepsilon /(\alpha \delta (S_{0})))\rceil , \ \ \widehat{K}=(p+1)^{2^{\widehat{\beta }}}, \end{aligned}$$

then the complexity of the proposed SBBA for solving $\textrm{LMP}$ problem is bounded above by

$$\begin{aligned} C_{\widehat{K}}^{p+1} T(p+1,1)+\widehat{K} T(n,m), \end{aligned}$$

where $\alpha$ is given in Lemma 2, and $C_{\widehat{K}}^{p+1}=\widehat{K}!/((\widehat{K}-p-1)!(p+1)!).$

Proof

Since the sufficiently small $\varepsilon >0$ satisfies $\varepsilon /\alpha \in (0,\delta (S_0)]$, we see from Lemma 1 that after at most $\widehat{K}$ iterations the sequence of simplicial partitions $\{{\mathscr {P}}_{k}\}$ implies that $\delta ({\mathscr {P}}_{k})\le \varepsilon /\alpha$. According to Theorem 6, SBBA finds the $\varepsilon$-optimal solution of LMP in at most $\widehat{K}$ iterations. Additionally, Lemma 1 also indicates that after $\widehat{K}$ iterations the total number of vertices of all simples S is strictly less than $\widehat{K}$. Note that each p-dimensional simplex has $p+1$ vertices. Thus, after $\widehat{K}$ iterations the number of all simplices S is strictly less than $C_{\widehat{K}}^{p+1}$. This implies that the total number of CQP(S) problems associated with these simplices S is also strictly less than $C_{\widehat{K}}^{p+1}$. Moreover, we also notice that the main computation cost is to estimate $\psi (\varvec{t})$ (see Step 2) and to acquire ${\widehat{\phi }_{S}}$ (see Step 3) at each iteration of SBBA, in which they are obtained by solving different CQP problems. Hence, the complexity of the proposed SBBA for solving $\textrm{LMP}$ is bounded above by

$$\begin{aligned} C_{\widehat{K}}^{p+1} T(p+1,1)+\widehat{K} T(n,m), \end{aligned}$$

and the proof is completed. $\square$

4 Numerical experiment

In this section, we report the numerical comparison for the proposed SBBA, the two algorithms in [24, 25] and the global optimization software BARON [30]. All the experiments were implemented in Matlab(2018a) and ran on a PC(Intel(R) Core(TM) i7-7700 M CPU (3.6GHz)). The linear programming problems in [24, 25] were solved by the LP solver linprog in Matlab Optimization Toolbox, and CQP problems were solved by the QP solver in CPLEX [31].

In computational experiments, the tolerance is set as $\varepsilon =10^{-6}$, and the average numerical results are listed in Tables 1 and 2. Some notations in Tables 1 and 2 are given as follows:

• Opt.val: the average optimal value obtained by the algorithm for five test instances;

• CPU: the average CPU time of the algorithm in seconds for five test instances;

• Iter: the average number of iterations of the algorithm for five test problems;

• “−” denotes that the algorithm fails to find the solution within 3600 s for all instances.

We first consider the following rank-one nonconvex quadratic programming problem (see [32]):

$$\begin{aligned} \mathrm{(P1):} \left\{ \begin{array}{ll} \min &{}\varvec{c}_{1}^{T}\varvec{x}\varvec{c}_{2}^{T}\varvec{x}\\ \mathrm {s.t.}&{} \varvec{A}\varvec{x}\le \varvec{b}, \varvec{x}\ge \varvec{0}, \end{array} \right. \end{aligned}$$

where the components of $\varvec{c}_{1}, \varvec{c}_{2}\in R^{n}$ are randomly generated in $[-1,1]$, and all elements of $\varvec{A}\in R^{m\times n}$, $\varvec{b}\in R^{m}$ are the random numbers in the interval [0.1, 1]. This problem is known to be NP-hard [33].

For each setting (n, m), we tested the proposed SBBA, the solver BARON and the algorithms in [24, 25] for five randomly generated instances of (P1), and Table 1 lists the average performance of the numerical results about the four algorithms. As can be seen in Table 1, BARON is the most inefficient one among the four methods, and the largest dimension n of the problems solved is $n<200$. Also, for each solved instance, we observe from Table that BARON spends the longest CPU time and the algorithms in [24, 25] require much more CPU time than one of SBBA, in which their CPU time grow very fast as the number of (n, m) increases, compared with SBBA. Moreover, the algorithm in [25] fails to find the global solutions within 3600 s for large scale problems with $(n,m)=(5000,500)$.

Next, we further tested four methods (ours, BARON and ones in [24, 25]) on the following problem:

$$\begin{aligned} \mathrm{(P2):} \left\{ \begin{array}{ll} \min &{}\sum \limits _{i=1}^{p}(\varvec{c}_{i}^{T}\varvec{x}+c_{0i})(\varvec{d}_{i}^{T}\varvec{x}+c_{0i})\\ \mathrm {s.t.}&{} \varvec{A}\varvec{x}\le \varvec{b},\ \varvec{x}\ge \varvec{0}, \end{array} \right. \end{aligned}$$

where all elements of $\varvec{c}_{i}, \varvec{d}_{i}\in R^{n}$ and $c_{0i}, d_{0i}\in R$ are randomly generated in the interval $[-0.5,0.5]$, and the elements of $\varvec{A}\in R^{m\times n},\ \varvec{b}\in R^{m}$ are the random numbers in [0.1, 1].

In computational test for problem (P2), the number of summation terms p varies from 2 to 4 and the dimension (n, m) increases from (100, 10) to (5000, 500). We observe from Table that BARON spends the longest CPU time among the several methods for each solved instance. But the other advantage of BARON is that it seems to be insensitive to p, although the largest dimension of problem (P2) solved by it is $(m,n)=(800,80)$. Moreover, except for the proposed SBBA in this paper, the other methods fail to find the global optimal solution for some cases. For example, for the case $(n,m)>(1500,150)$ with $p=3$, the algorithm in [24] fails to find the global solution within 3600 s, and the approach in [25] fails to terminate in 3600 s when $(n,m)>(3000,30)$ with $p=2$.

As a contrast, SBBA is more efficient than other algorithms (BARON and ones in [24, 25]) for low-dimensional instances, say $p<5$, and SBBA can successfully solve higher dimensional problems in the case of small p. For example, SBBA solves the instances with $(n,m,p) = (5000,500,2)$ in hundreds of seconds. Similar to the Refs. [24, 25], the disadvantage of SBBA is that the CPU time increases rapidly in the number of summation terms p.

5 Conclusions

In this paper, we first lift LMP problem to an equivalent nonlinear optimization problem EP1 by using reformulation techniques. A new convex quadratic relaxation is then constructed to provide a lower bound on the optimal value of EP1. Combined with the simplicial branching rule and the new relaxation, we present a simplicial branch-and-bound algorithm for globally solving LMP problem. Additionally, we establish the convergence of the proposed algorithm and analyze its computational complexity. Finally, numerical results demonstrate that the proposed algorithm is more efficient than other algorithms in the literature for test instances.

There are several issues left open. First, is it possible (and how) to estimate the tighter lower bound than that provided by CQP relaxation for LMP? A deep consideration in this direction will help to establish the theoretical basis of nonlinear relaxations. Secondly, can we develop similar nonlinear relaxations for other hard optimization problems, which are stronger than CQP relaxation and how to solve the resulting relaxation effectively? More study is needed to address these issues.

Table 1 Computational results for problem (P1)

Table 2 Computational results for problem (P2)