An efficient optimization algorithm for quadratic programming problem and its applications to mobile robot path planning

Abstract

The quadratic programming problem has broad applications in mobile robot path planning. This article presents an efficient optimization algorithm for globally solving the quadratic programming problem. By utilizing the convexity of univariate quadratic functions, we construct the linear relaxation programming problem of the quadratic programming problem, which can be embedded within a branch-and-bound structure without introducing new variables and constraints. In addition, a new pruning technique is inserted into the branch-and-bound framework for improving the speed of the algorithm. The global convergence of the proposed algorithm is proved. Compared with some known algorithms, numerical experiment not only demonstrates the higher computational efficiency of the proposed algorithm but also proves that the proposed algorithm is an efficient approach to solve the problems of path planning for the mobile robot.

Keywords

Quadratic programming problem global optimization linear relaxation programming pruning technique branch-and-bound optimization algorithm path planning

Introduction

The mobile robot has drawn more and more attention in scientific areas and engineering applications. One of the fundamental issues in mobile robot performing tasks in an unknown environment is the path planning resolution problem. That is, given the desired task, arriving at the destination or catching a target with the shortest distance, (or spending the least amount of energy), how can the mobile robot search from the environment to start from the initial position to achieve its own purpose by the best or suboptimal path according to some performance indicators? In the path planning, navigation involves a series of common problems, with collision avoidance in some form being almost universally needed, which underlaid by more general assumptions about the problem would be considered superior.¹ In dealing with aircraft (autonomous robot) navigation problems, second-order central difference filtering algorithm² and the new method based on wavelet multiresolution analysis and adaptive Kalman filter³ are proposed to perform better than the classical.

The most challenging problem for path planning is to arrive at the destination or catch a target with the shortest distance or least consumption of fuel when real time is demanded in dynamic environments involving multiple obstacles. The quadratic programming model is formulated as follows

{\begin{matrix} min & J = \frac{1}{2} x^{T} (ω_{1} Q - ω_{2} H) x + (ω_{1} x^{T} - ω_{2} f^{T}) x \\ s.t. & τ_{i} γ_{AOC i (k)} \leq τ_{i} (γ_{AOC i (k)} + Δ γ_{AOC i (k))}) \leq π \\ max [- Δ_{max}, - (V_{A max} + ν_{\frac{A x (k)}{T}})] \leq a_{x} \leq min [Δ_{max}, (V_{A max} - ν_{\frac{A y (k)}{T}})] \\ max [- Δ_{max}, - (V_{A max} + ν_{\frac{A y (k)}{T}})] \leq a_{y} \leq min [Δ_{max}, (V_{A max} - ν_{\frac{A y (k)}{T}})] \\ max [- Δ_{max}, - (V_{A max} + ν_{\frac{A z (k)}{T}})] \leq a_{z} \leq min [Δ_{max}, (V_{A max} - ν_{\frac{A z (k)}{T}})] \\ sin θ_{m} cos ϕ_{n} a_{x} + sin θ_{m} sin ϕ_{n} a_{y} + cos ϕ_{m} a_{z} \leq Δ_{max} \end{matrix}

where $Q \in R_{n \times n}$ is semidefinite matrix; $c \in R_{n \times 1}$ is coefficient vectors and $H \in R_{n \times 1}$ is right-hand side vectors; $x \in R_{n \times 1}$ is variable vector; ω₁ and ω₂ are the weights used to balance the relative distance and the optimal velocity direction; τ_i is assigned to evaluate the threat imposed by an obstacle on the robot; the angle between V _AO and L _AO is defined as obstacle angle, denoted by $γ_{AO i (k)}$ , V _AO denotes the vehicle velocity relative to the obstacle, and L _AO denotes the vehicle position relative to the obstacle; $γ_{AOC i (k)}$ is the collision region angle in time step $i (k), γ_{AO i (k)}$ represents the obstacle angle in step i(k) after robot’s movement, I denotes the label of the obstacle; Δ_max represents the upper bound of acceleration and V_{A max} stands for the upper bound of the robot velocity; a_x, a_y^, and a_z represent the acceleration elements of the mobile robot; T is the planning period; and k is the time step. Such problems can be expressed as the following general quadratic programming problem (QPP)

(QPP) : {\begin{array}{l} min & G_{0} (y) = \sum_{j = 1}^{n} \sum_{k = 1}^{n} β_{j k}^{0} y_{j} y_{k} + \sum_{k = 1}^{n} α_{k}^{0} y_{k} \\ s . t . & G_{i} (y) = \sum_{j = 1}^{n} \sum_{k = 1}^{n} β_{j k}^{i} y_{j} y_{k} + \sum_{k = 1}^{n} α_{k}^{i} y_{k} \leq b_{i}, i = 1, \dots, m \\ y \in Y^{0} = {y \in R^{n} : l^{0} \leq y \leq u^{0}} \end{array}

where $β_{j k}^{i}, α_{k}^{i}, b_{i} \in R, i = 0, 1, \dots, m, j = 1, \dots, n, k = 1, \dots, n; l^{0} = {(l_{1}^{0}, \dots, l_{n}^{0})}^{T}, u^{0} = {(u_{1}^{0}, \dots, u_{n}^{0})}^{T} .$

The QPPs have a wide variety of applications in information science, control science and engineering, management science, finance and economy, and so on.^4

–7 Except for the above reviewed applications, the QPP presents important theoretical and computational difficulties since the kind of problems possess many local optimum points which are not global optimal. So, the QPP has attracted attention from many scientists. In past several decades, many special optimization algorithms have been proposed for solving the special forms of the QPP, such as reformulation convexification,⁸ Lagrangian underestimate and interval Newton method,⁹ semidefinite relaxation,¹⁰ polyhedral approximation,¹¹ duality bound,¹² robust solution,¹³ parametric relaxation,¹⁴ branch and bound,^15
–17 and so on. Although some known algorithms can also be used to compute the QPP, it is rather challenging to globally compute the QPP because of its complication.^18
–20

In this article, we will present a branch-and-bound algorithm for globally solving the QPP. To accomplish this goal, by utilizing the convexity of univariate quadratic functions, we construct the linear relaxation programming problem (LRPP) of the QPP, which can be embedded within a branch-and-bound framework without introducing new variables and constraints. In addition, a new pruning technique is inserted into the branch-and-bound framework for improving the convergence of the algorithm. Next, by combining the linear relaxation bounding operation with the bisection rule and pruning operation, an efficient branch-and-bound optimization algorithm is presented for globally solving the QPP. Finally, compared with the known algorithms, numerical experiments demonstrate the higher computational efficiency of the proposed method.

The remaining sections of this article are listed as follows. By utilizing the convexity of univariate quadratic functions, “new linear relaxation programming” section derives a novel linear relaxation technique, and then the LRPP of the QPP is established. Based on the LRPP derived in “new linear relaxation programming” section, “optimization algorithm and its global convergence” section presents an efficient branch-and-bound optimization algorithm by combining the linear relaxation bounding operation with the bisection rule and pruning operation, and its global convergence is proved. In “numerical experiments” section, in order to compare with some known algorithms, numerical experiments are given to show the computational superiority of the proposed algorithm. Finally, some concluding remarks are discussed.

New linear relaxation programming

In this section, we derive a new linear relaxation technique, based on the relaxation technique, on which the LRPPs of the initial problem and its partitioned subproblems can be established, and the detailed deriving process is demonstrated as follows.

For any $y \in Y = [l, u] \subseteq Y^{0}$ , by the convexity of univariate quadratic function $y_{j}^{2}, j = 1, 2, \dots, n,$ we have

(l_{j} + u_{j}) y_{j} - \frac{{(l_{j} + u_{j})}^{2}}{4} \leq y_{j}^{2} \leq (l_{j} + u_{j}) y_{j} - l_{j} u_{j}

Similarly, for any $y \in Y = [l, u] \subseteq Y^{0}$ , we can easily derive the following inequalities

{\begin{array}{l} (l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4} \leq {(y_{j} + y_{k})}^{2} \\ {(y_{j} + y_{k})}^{2} \leq (l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - (l_{j} + l_{k}) (u_{j} + u_{k}) \end{array}

By equations (1) and (2), for any $y \in Y = [l, u] \subseteq Y^{0}$ , we can easily derive the following inequalities

\begin{matrix} \begin{array}{l} y_{j} y_{k} = \frac{1}{2} [{(y_{j} + y_{k})}^{2} - y_{j}^{2} - y_{k}^{2}] \\ \geq \frac{1}{2} [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) \\ - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}] \\ - \frac{1}{2} [(l_{j} + u_{j}) y_{j} - l_{j} u_{j} + (l_{k} + u_{k}) y_{k} - l_{k} u_{k}] \\ = \frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + l_{j} u_{j} + l_{k} u_{k} \\ - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4} \end{array} \end{matrix}

and

\begin{array}{l} y_{j} y_{k} = \frac{1}{2} [{(y_{j} + y_{k})}^{2} - y_{j}^{2} - y_{k}^{2}] \\ \leq \frac{1}{2} [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - (l_{j} + l_{k}) (u_{j} + u_{k})] \\ - \frac{1}{2} [(l_{j} + u_{j}) y_{j} - \frac{{(l_{j} + u_{j})}^{2}}{4} + (l_{k} + u_{k}) y_{k} \\ - \frac{{(l_{k} + u_{k})}^{2}}{4}] \\ = \frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + \frac{{(l_{j} + u_{j})}^{2}}{4} + \frac{{(l_{k} + u_{k})}^{2}}{4} \\ - (l_{j} + l_{k}) (u_{j} + u_{k})] \end{array}

Let

{\begin{array}{l} f_{j}^{l} (y) = (l_{j} + u_{j}) y_{j} - \frac{{(l_{j} + u_{j})}^{2}}{4} \\ f_{j}^{u} (y) = (l_{j} + u_{j}) y_{j} - l_{j} u_{j} \\ f_{j k}^{Ι} (y) = \frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + l_{j} u_{j} + l_{k} u_{k} \\ - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4} \\ f_{j k}^{u} (y) = \frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + \frac{{(l_{j} + u_{j})}^{2}}{4} + \frac{{(l_{k} + u_{k})}^{2}}{4} \\ - (l_{j} + l_{k}) (u_{j} + u_{k})] \end{array}

Obviously, we have

f_{j}^{l} (y) \leq y_{j}^{2} \leq f_{j}^{u} (y), f_{j k}^{l} (y) \leq y_{j} y_{k} \leq f_{j k}^{u} (y)

Since

y_{j}^{2} - f_{j}^{l} (y_{j}) = y_{j}^{2} - [(l_{j} + u_{j}) y_{j} - \frac{{(l_{j} + u_{j})}^{2}}{4}]

is a convex function about y_j over the interval $[l_{j}, u_{j}]$ . Thus, at the point l_j or u_j, it can obtain the maximum value

max [y_{j}^{2} - f_{j}^{l} (y_{j})] = \frac{{(u_{j} - l_{j})}^{2}}{4}

Similarly, since

f_{j}^{u} (y_{j}) - y_{j}^{2} = (l_{j} + u_{j}) y_{j} - l_{j} u_{j} - y_{j}^{2}

is a concave function about y_j over the interval $[l_{j}, u_{j}]$ , therefore, at the point $\frac{l_{j} + u_{j}}{2}, [f_{j}^{u} (y_{j}) - y_{j}^{2}]$ can obtain maximum value

max [f_{j}^{u} (y_{j}) - y_{j}^{2}] = \frac{{(u_{j} - l_{j})}^{2}}{4}

Similarly, for any $y \in Y = [l, u] \subseteq Y^{0}, then (y_{j} + y_{k}) \in [l_{j} + l_{k}, u_{j} + u_{k}]$ , we have

{\begin{array}{l} max {{(y_{j} + y_{k})}^{2} - [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}]} = \frac{{(u_{j} + u_{k} - l_{j} - l_{k})}^{2}}{4} \\ max {[(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - (l_{j} + l_{k}) (u_{j} + u_{k})] - {(y_{j} + y_{k})}^{2}} = \frac{{(u_{j} + u_{k} - l_{j} - l_{k})}^{2}}{4} \end{array}

Obviously, when $∥ u - l ∥ \to 0$ , we have

{\begin{array}{l} max [y_{j}^{2} - f_{j}^{l} (y_{j})] \to 0 \\ max [f_{j}^{u} (y_{j}) - y_{j}^{2}] \to 0 \\ max {{(y_{j} + y_{k})}^{2} - [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}]} \to 0 \\ max {[(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - (l_{j} + l_{k}) (u_{j} + u_{k})] - {(y_{j} + y_{k})}^{2}} \to 0 \end{array}

Since

y_{j} y_{k} - f_{j k}^{l} (y) = y_{j} y_{k} - {\frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + l_{j} u_{j} + l_{k} u_{k} - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}} = \frac{1}{2} [{(y_{j} + y_{k})}^{2} - y_{j}^{2} - y_{k}^{2}] - {\frac{1}{2} [(l_{j} + u_{j}) y_{k} + (l_{k} + u_{k}) y_{j} + l_{j} u_{j} + l_{k} u_{k} - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}} = \frac{1}{2} {(l_{j} + u_{j}) y_{j} - l_{j} u_{j} - y_{j}^{2} + \frac{1}{2} (l_{k} + u_{k}) y_{k} - l_{k} u_{k} - y_{k}^{2}} + \frac{1}{2} {{(y_{j} + y_{k})}^{2} - [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}]} \leq \frac{1}{2} max [f_{j}^{u} (y_{j}) - y_{j}^{2}] + \frac{1}{2} max [f_{k}^{u} (y_{k}) - y_{k}^{2}] + \frac{1}{2} max {{(y_{j} + y_{k})}^{2} - [(l_{j} + u_{j} + l_{k} + u_{k}) (y_{j} + y_{k}) - \frac{{(l_{j} + u_{j} + l_{k} + u_{k})}^{2}}{4}]}

By equation (3), we have $y_{j} y_{k} - f_{j k}^{l} (y) \to 0 as ∥ u - l ∥ \to 0.$

Similarly, we can prove that $f_{j k}^{u} (y) - y_{j} y_{k} \to 0 as ∥ u - l ∥ \to 0.$

Let

\begin{array}{l} G_{i}^{L} (y) = \sum_{k = 1}^{n} α_{k}^{i} y_{k} + \sum_{k = 1, β_{k k}^{i} > 0}^{n} β_{k k}^{i} f_{k}^{l} (y_{k}) + \sum_{k = 1, β_{k k}^{i} < 0}^{n} β_{k k}^{i} f_{k}^{u} (y_{k}) + \sum_{j = 1}^{n} \sum_{k = 1, k \neq j, β_{j k}^{i} > 0}^{n} β_{j k}^{i} f_{j k}^{l} (y) + \sum_{j = 1}^{n} \sum_{k \neq 1, β_{j k}^{i} < 0}^{n} β_{j k}^{i} f_{j k}^{u} (y) G_{i}^{u} (y) = \sum_{k = 1}^{n} α_{k}^{i} y_{k} + \sum_{k = 1, β_{k k}^{i} < 0}^{n} β_{k k}^{i} f_{k}^{l} (y_{k}) + \sum_{k = 1, β_{k k}^{i} > 0}^{n} β_{k k}^{i} f_{k}^{u} (y_{k}) + \sum_{j = 1}^{n} \sum_{k = 1, k \neq j, β_{j k}^{i} < 0}^{n} β_{j k}^{i} f_{j k}^{l} (y) + \sum_{j = 1}^{n} \sum_{k \neq 1, β_{j k}^{i} > 0}^{n} β_{j k}^{i} f_{j k}^{u} (y) \end{array}

Obviously, by equation (3), we can derive that as $∥ u - l ∥ \to 0$

G_{i}^{U} (y) \geq G_{i} (y) \geq G_{i}^{L} (y), G_{i} (y) - G_{i}^{L} (y) \to 0 and G_{i}^{U} (y) - G_{i} (y) \to 0.

Based on the above linearizing process, we can derive the LRPP of the QPP over Y as follows

LRPP (Y) : {\begin{array}{l} min & G_{0}^{L} (y) \\ s . t . & G_{i}^{L} (y) \leq b_{i}, i = 1, \dots, m \\ y \in Y = {y : l \leq y \leq u} \subseteq Y^{0} \end{array}

where

\begin{array}{l} G_{i}^{L} (y) = \sum_{k = 1}^{n} α_{k}^{i} y_{k} + \sum_{k = 1, β_{k k}^{i} > 0}^{n} β_{k k}^{i} f_{k}^{l} (y_{k}) + \sum_{k = 1, β_{k k}^{i} < 0}^{n} β_{k k}^{i} f_{k}^{u} (y_{k}) \\ + \sum_{j = 1}^{n} \sum_{k = 1, k \neq j, β_{j k}^{i} > 0}^{n} β_{j k}^{i} f_{j k}^{l} (y) + \sum_{j = 1}^{n} \sum_{k = 1, k \neq j, β_{j k}^{i} < 0}^{n} β_{j k}^{i} f_{j k}^{u} (y) . \end{array}

By the above linearizing process, for any $Y \subseteq Y^{0},$ every feasible point of the QPP is also feasible to the LRPP, the LRPP can provide a reliable lower bound for the global optimum value of the QPP.

Optimization algorithm and its global convergence

In this section, we first introduce several fundamental techniques; next, by combining these techniques, we present an efficient branch-and-bound optimization algorithm for globally solving the QPP. The detailed contents are given as follows.

Several fundamental techniques

Firstly, we introduce a bisection rule as partitioning method. This selected bisection rule is exhaustiveness, which can guarantee the global convergence of the proposed optimization algorithm. For any given subbox, $Y^{k} = [l^{k}, u^{k}] \subseteq Y^{0}$ . This bisection rule is as follows.

Assume that $η \in argmax {u_{i} - l_{i} | i = 1, \dots, n}, then Y^{k}$ can be partitioned into two subboxes: $Y^{k, 1} = {y \in R^{n} | l_{i} \leq y_{i} \leq u_{i}, i \neq η; l_{η} \leq y_{η} \leq \frac{l_{η} + u_{η}}{2}} and Y^{k, 2} = {y \in R^{n} | l_{i} \leq y_{i} \leq u_{i}, i \neq η; \frac{l_{η} + u_{η}}{2} \leq y_{η} \leq u_{η}} .$

Secondly, to improve the convergent efficiency of the proposed branch-and-bound optimization algorithm, we introduce a pruning technique for deleting a part of the investigated box Y, which does not contain any global optimum point of the QPP. Without loss of generality, for any $y \in Y = {(Y_{j})}_{n \times 1} with Y_{j} = [l_{j}, u_{j}] (j = 1, \dots, n)$ , we assume that

G_{i}^{L} (y) = \sum_{j = 1}^{n} γ_{i j} y_{j} + η_{i}, i = 0, 1, \dots, m

Assume that UB_k be a currently known upper bound of the proposed optimization algorithm at kth iteration, by utilizing the structure of the branch-and-bound optimization algorithm, similar as Voorhis,¹¹ for any subbox $Y = {(Y_{j})}_{n \times 1} \subseteq Y^{0}$ , we can get the following conclusions.

If $\sum_{j = 1}^{n} min {γ_{0 j} l_{j}, γ_{0 j} u_{j}} + η_{0} > U B_{k}$ , then the subbox Y should be deleted; else if $\sum_{j = 1}^{n} min {γ_{0 j} l_{j}, γ_{0 j} u_{j}} + η_{0} \leq U B_{k}$ , then for each $p \in {1, 2, \dots, n}$ , we have

If $γ_{0 p} > 0$ , then the interval $(\frac{U B_{k} - (\sum_{j = 1}^{n} min {γ_{0 j} l_{j}, γ_{0 j} u_{j}} + η_{0}) + min {γ_{0 p} l_{p}, γ_{0 p} u_{p}}}{γ_{0 p}}, u_{p}] \underset{}{\cap} Y_{p}$ should be deleted;

If $γ_{0 p} < 0$ , then the interval $[l_{p}, \frac{U B_{k} - (\sum_{j = 1}^{n} min {γ_{0 j} l_{j}, γ_{0 j} u_{j}} + η_{0}) + min {γ_{0 p} l_{p}, γ_{0 p} u_{p}}}{γ_{0 p}}) \cap Y_{p}$ should be deleted.

If $\sum_{j = 1}^{n} min {γ_{i j} l_{j}, γ_{i j} u_{j}} + η_{i} > b_{i}$ for some $i \in {1, \dots, m}$ , then the subbox Y should be deleted; else if $\sum_{j = 1}^{n} min {γ_{i j} l_{j}, γ_{i j} u_{j}} + η_{i} \leq b_{i}$ for some $i \in {1, \dots, m}$ , then for each $p \in {1, \dots, n}$ , we have

If $γ_{i p} > 0$ , then the interval $(\frac{b_{i} - (\sum_{j = 1}^{n} min {γ_{i j} l_{j}, γ_{i j} u_{j}} + η_{i}) + min {γ_{i p} l_{p}, γ_{i p} u_{p}}}{γ_{i p}}, u_{p}] \cap Y_{p}$ should be deleted.

If $γ_{i p} < 0$ , then the interval $[l_{p}, \frac{b_{i} - (\sum_{j = 1}^{n} min {γ_{i j} l_{j}, γ_{i j} u_{j}} + η_{i}) + min {γ_{i p} l_{p}, γ_{i p} u_{p}}}{γ_{i p}}) \cap Y_{p}$ should be deleted.

From the above conclusions, we can construct the new pruning technique to prune a part of the investigated box which does not contain the global optimal point of the QPP, so that the computational speed of the proposed branch-and-bound optimization algorithm can be improved and accelerated.

Thirdly, the bounding process is needed to update the lower bounds and upper bounds of the optimal value of the QPP. Here, we update the lower bounds by solving the former LRPP using simple method. At the same time, we update the upper bounds by computing the objective function value of feasible points for the QPP.

Fourthly, denote $L B (Y^{k}) and y^{k} = y (Y^{k})$ as the global optimum value and the global optimum solution for the LRPP in the subbox Y_k, respectively. Based on the above bisection rule, the pruning technique and bounding process, we design the following branch-and-bound optimization algorithm for the QPP. The detailed steps of algorithm are given as follows.

Steps for optimization algorithm are follows:

Step 1. Initialize k = 0, $Λ_{0} = {Y^{0}}, F = \emptyset, ε > 0, U B_{0} = + \infty$ .

Solve the LRPP $(Y^{0})$ to obtain LB ₀ = LB(Y ⁰) and $y^{0} = y (Y^{0}) . If y^{0}$ is satisfied with the feasibility of the QPP, then let $F = {y^{0}} and U B_{0} = G_{0} (y^{0})$ .

If $U B_{0} - L B_{0} \leq ε$ , then the algorithm terminates; at the same time, we get the global optimal solution y₀ of the QPP. Otherwise, continue to step 2.

Step 2. For the investigated box $Y^{k} \in Λ_{k}$ , using the proposed bisection method, partition the box Y_k into two subboxes and denote the new subboxes set by ${\overset{˘}{Y}}^{k}$ .

Step 3. For each subbox $Y \in {\overset{˘}{Y}}^{k}$ , using the former pruning technique to delete a part of the investigated box which does not contain the global optimal point of the QPP¹¹, and let the remaining subbox be Y and the remaining partitioning set be ${\overset{˘}{Y}}^{k}$ .

Step 4. For each subbox $Y \in {\overset{˘}{Y}}^{k}$ , solve the LRPP $(Y)$ to get $LB (Y)$ and y(Y); if $LB (Y) > U B_{k}$ , then let ${\overset{˘}{Y}}^{k} = {\overset{˘}{Y}}^{k} \ Y$ . Otherwise, we detect the feasibilities of the midpoint y^mid and y(Y) and update the feasible point set. At the same time, update $U B_{k} = {min}_{y \in F} G_{0} (y)$ and denote the current best feasible solution by $y^{k} = {argmin}_{y \in F} G_{0} (y) . Let Λ_{k} = (Λ_{k} \ Y^{k}) \cup {\overset{˘}{Y}}^{k} and L B_{k} = {inf}_{Y \in Λ_{k}} L B (Y)$ .

Step 5. If $U B_{k} - L B_{k} \leq ε,$ then the algorithm terminates; UB_k and y_k are the global optimum value and the global optimum point for the QPP, respectively. Otherwise, let k = k + 1, and select $Y^{k} = {argmin}_{Y \in Λ_{k}} L B (Y)$ , and return to step 2.

Global convergence of the algorithm

The global convergence of the above branch-and-bound optimization algorithm is discussed as follows.

Theorem 1

If the proposed optimization algorithm terminates at kth iteration, then a global optimal solution y_k can be obtained. Otherwise, the proposed optimization algorithm will generate an infinite subsequence ${y^{k_{q}}} of {y^{k}}$ such that its accumulation point is the global optimal solution for the QPP.

Proof

If the proposed optimization algorithm stops after finite k iteration, then from the termination condition of algorithm, it is obvious that $U B_{k} - L B_{k} \leq ε .$

From the bounding process, we know that there does exist a feasible solution y_k such that $U B_{k} = G_{0} (y^{k}),$ so we have $G_{0} (y^{k}) - ε \leq L B_{k} .$

Let v* be the global optimal value, then from the structure of the proposed optimization algorithm, we have $L B_{k} \leq v .$

Since y_k is a feasible solution for the QPP, then we follow that $G_{0} (y^{k}) \geq v .$

From comprehensive analysis of the above results, we can follow that $v \geq L B_{k} \geq G_{0} (y^{k}) - ε \geq v - ε .$ Obviously, y_k is a global optimal solution of the QPP.

If the proposed optimization algorithm does not stop after finite k iterations, based on the sufficient condition of the convergence of the branch-and-bound optimization algorithm, we can draw a conclusion that the bounding operation of the proposed optimization algorithm must be consistent and its selection operation may be improved.

From the construction of the above optimization algorithm, the selected bisection method is exhaustive, so that any unfathomed box can be further partitioned by the branching process. By the deriving process of the LRPP, it is easy to follow that ${lim}_{k \to \infty} (U B_{k} - L B_{k}) = 0$ must hold. Therefore, the bounding operation must be consistent.

From the proposed bisection method, the selected subbox Y_k of which the lower bound can be immediately attained from further partitioning process. Therefore, the selecting operation of the proposed optimization algorithm that satisfies the bound must be improved.

From comprehensive analysis of the above discussions, we have that the bounding operation of the proposed algorithm must be consistent and its selection operation may be improved. Finally, according to literature,^15
–17 we can follow that the proposed optimization must be globally convergent to the optimal solution of the initial problem (QPP).

Numerical experiments

In this section, to verify the feasibility and efficiency of the proposed branch-and-bound optimization algorithm, some random numerical test problems in recent literatures are solved using the proposed optimization algorithm on microcomputer, the algorithm procedure is coded in C++, and the LRPPs are solved by simplex approach. These random numerical test problems and their computational results are demonstrated as follows

(QPP) : {\begin{array}{l} min & G_{0} (y) = \sum_{j = 1}^{n} \sum_{k = 1}^{n} β_{j k}^{0} y_{j} y_{k} + \sum_{k = 1}^{n} α_{k}^{0} y_{k} \\ s . t . & G_{i} (y) = \sum_{j = 1}^{n} \sum_{k = 1}^{n} β_{j k}^{i} y_{j} y_{k} + \sum_{k = 1}^{n} α_{k}^{i} y_{k} \leq b_{i}, i = 1, \dots, m \\ y \in Y^{0} = {y \in R^{n} : l^{0} \leq y \leq u^{0}} \end{array}

where $β_{j k}^{0} and α_{k}^{0}$ are randomly generated in $[- 1, 1], β_{j k}^{i} and α_{k}^{i}, i = 1, \dots, m$ are randomly generated in $[- 1, 1]$ , and b_i is randomly generated in $[- 300, - 90], l^{0} = [0, \dots, 0]^{T}, and u^{0} = [10, \dots, 10]^{T}$ .

The numerical experimental results for these test problems are listed in Table 1, where n represents the number of variable and m represents the number of constraints. The numerical results indicate the feasibility of the proposed optimization algorithm.

Table 1.

Numerical results for test problem.

	Our algorithm
(m, n)	Iteration	L _max	Time (s)
(5, 5)	582	202	0.983
(10, 5)	625	213	1.458
(20, 5)	492	180	1.445
(30, 5)	419	189	2.985
(40, 5)	545	199	6.544
(50, 5)	595	223	12.566
(60, 5)	545	227	16.589
(70, 5)	606	265	27.743
(80, 5)	519	201	31.603
(90, 5)	548	212	46.646

Concluding remarks

Path planning for the mobile robot is still a challenging problem because the inherent constraints arising from the robot body and the exterior environment cannot be solved. Thus, the major difficulties are that most of existing methods can only get local optimal value instead of global one. To address these difficulties, in this article, we present an efficient optimization algorithm for globally solving the QPP. Based on the convexity of univariate quadratic function, we derive the LRPP of the initial problem, which is embedded into a branch-and-bound framework, so that we can construct a global optimization branch-and-bound algorithm. In addition, a new pruning technique is inserted into the branch-and-bound optimization algorithm to improve the global convergent speed of the proposed optimization algorithm. Finally, the global convergence of the proposed algorithm is proved, and compared with the known algorithms, numerical experiment demonstrates the higher computational efficiency of the proposed algorithm. Therefore, the bounding operation of the proposed algorithm must be consistent and its selection operation may be improved, and it provides an efficient approach to solve the problems of path planning for the mobile robot.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (61703143, 61503123, U1504616), Scientific and Technological Innovation Talents in Xinxiang (CXRC17004), Science and Technology Project of Henan Province (162102210294), and the Key Scientific Research Project of Universities in Henan Province (17B413002).

References

Cai

Zhang

Second order central difference filtering algorithm for SINS/GPS integrated navigation in guided munitions. In: AICI 2010, Part I, LNAI 6319 (eds Wang

Deng

Gao

Lei

), 2010, pp. 193–200. Heidelberg, Berlin: Springer.

Cai

Kong

Chang

. Wavelet multi-resolution analysis aided adaptive Kalman filter for SINS/GPS integrated navigation in guided munitions. In: AICI 2011, Part II, LNAI 7003, 2011, pp. 455–462.

Hoy

Matveev

Savkin

. Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey. Robotica 2015; 33(3): 463–497.

Chen

Han

. Quadratic programming-based approach for autonomous vehicle path planning in space. Chin J Mech Eng-en 2012; 25(4): 655–673.

Lin

Zhao

. A nonintrusive load identification method for residential applications based on quadratic programming. Electr Pow Syst Res 2016; 133: 241–248.

Wang

. Group decision making with incomplete intuitionistic preference relations based on quadratic programming models. Comput Ind Eng 2016; 93: 162–170.

Wen

Wang

Geng

. Event-based distributed recursive filtering for state-saturated systems with redundant channels. Inform Fusion 2018; 39: 96–107.

Wen

Cai

Liu

. A reduced-order approach to filtering for systems with linear equality constraints. Neurocomputing 2016; 193(12): 219–226.

Bose

Gayme

Chandy

. Quadratically constrained quadratic programs on acyclic graphs with application to power flow. IEEE Trans Control NetSyst 2015; 2(3): 278–287.

10.

Sherali

Tuncbilek

. A reformulation-convexification approach for solving nonconvex quadratic programming problems. J Glob Optim 1995; 7: 1–31.

11.

Voorhis

. A global optimization algorithm using lagrangian underestimates and the interval newton method. J Glob Optim 2002; 24: 349–370.

12.

Burer

Vandenbussche

. A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math Program 2008; 113: 259–282.

13.

Zheng

Sun

. Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation. Math Program 2011; 129: 301–329.

14.

Thoai

. Duality bound method for the general quadratic programming problem with quadratic constraints. J Optim Theory Appl 2000; 107(2): 331–354.

15.

Shen

Duan

. A robust solution approach for nonconvex quadratic programs with additional multiplicative constraints. Appl Math Comput 2008; 201: 514–526.

16.

Jiao

Liu

. A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming. Appl Math Comput 2015; 250: 973–985.

17.

Jiao

Liu

Yin

. Outcome space range reduction method for global optimization of sum of affine ratios problem. Open Math 2016; 14: 736–746.

18.

Jiao

Chen

. A global optimization algorithm for generalized quadratic programming. J Appl Math 2013. DOI: 10.1155/2013/215312.

19.

Jiao

Liu

Zhao

. Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints. Appl Math Model 2015; 39: 7568–7582.

20.

Horst

Tuy

. Global optimization: deterministic approaches, 2nd ed. Berlin: Spring Verlag, 1993.