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.

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{array}{cc}\text{min}& J=\frac{1}{2}{x}^T\left({\omega }_{1}Q-{\omega }_{2}H\right)x+\left({\omega }_1{x}^T-{\omega }_2{f}^T\right)x\\ \text{s.t.}& {\tau }_i{\gamma }_{\text{AOC}i\left(k\right)}\le {\tau }_i\left({\gamma }_{\text{AOC}i\left(k\right)}+\Delta {\gamma }_{\text{AOC}i\left(k\right))}\right)\le \pi \\ & \text{max}\left[-{\Delta }_{\text{max}},-\left(V_{A\text{max}}+{\nu }_{\frac{Ax\left(k\right)}{T}}\right)\right]\le a_x\le \text{min}\left[{\Delta }_{\text{max}},\left(V_{A\text{max}}-{\nu }_{\frac{Ay\left(k\right)}{T}}\right)\right]\\ & \text{max}\left[-{\Delta }_{\text{max}},-\left(V_{A\text{max}}+{\nu }_{\frac{Ay\left(k\right)}{T}}\right)\right]\le a_y\le \text{min}\left[{\Delta }_{\text{max}},\left(V_{A\text{max}}-{\nu }_{\frac{Ay\left(k\right)}{T}}\right)\right]\\ & \text{max}\left[-{\Delta }_{\text{max}},-\left(V_{A\text{max}}+{\nu }_{\frac{Az\left(k\right)}{T}}\right)\right]\le a_z\le \text{min}\left[{\Delta }_{\text{max}},\left(V_{A\text{max}}-{\nu }_{\frac{Az\left(k\right)}{T}}\right)\right]\\ & \text{sin}{\theta }_m\text{cos}{\varphi }_n{a}_x+\text{sin}{\theta }_m\text{sin}{\varphi }_n{a}_y+\text{cos}{\varphi }_m{a}_z\le {\Delta }_{\text{max}}\end{array}$

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 ${\gamma }_{\text{AO}i\left(k\right)}$ , V _AO denotes the vehicle velocity relative to the obstacle, and L _AO denotes the vehicle position relative to the obstacle; ${\gamma }_{\text{AOC}i\left(k\right)}$ is the collision region angle in time step $i\left(k\right),{\gamma }_{\text{AO}i\left(k\right)}$ 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)

$\left(\text{QPP}\right):\{\begin{array}{ll}\text{min}\hfill & G_0\left(y\right)=\sum _{j=1}^n\sum _{k=1}^n{\beta }_{jk}^0{y}_j{y}_k+\sum _{k=1}^n{\alpha }_k^0{y}_k\hfill \\ \text{s}.\text{t}.\hfill & G_i\left(y\right)=\sum _{j=1}^n\sum _{k=1}^n{\beta }_{jk}^i{y}_j{y}_k+\sum _{k=1}^n{\alpha }_k^i{y}_k\le b_i, i=1,\dots ,m\hfill \\ \hfill & y\in Y^0=\left\{y\in R^n:{\text{l}}^0\le y\le u^0\right\}\hfill \end{array}$

where ${\beta }_{jk}^i,{\alpha }_k^i,b_i\in R, i=0,1,\dots ,m, j=1,\cdots ,n,k=1,\cdots ,n;{\text{l}}^0={({\text{l}}_1^0,\dots ,{\text{l}}_n^0)}^{\text{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=\left[l, u\right]\subseteq Y^0$ , by the convexity of univariate quadratic function $y_j^2, j=1,2,\cdots ,n,$ we have

$\left(l_j+u_j\right)y_j-\frac{{(l_j+u_j)}^2}{4}\le y_j^2\le \left(l_j+u_j\right)y_j-l_j{u}_j$

1

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

$\{\begin{array}{l}\left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\frac{{(l_j+u_j+l_k+u_k)}^2}{4}\le {(y_j+y_k)}^2\hfill \\ {(y_j+y_k)}^2\le \left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\left(l_j+l_k\right)\left(u_j+u_k\right)\hfill \end{array}$

2

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

$\begin{array}{c}\begin{array}{l}{y}_j{y}_k=\frac{1}{2}[{(y_j+y_k)}^2-y_j^2-y_k^2]\hfill \\ \ge \frac{1}{2}[(l_j+u_j+l_k+u_k)(y_j+y_k)\hfill \\ -\frac{{(l_j+u_j+l_k+u_k)}^2}{4}]\hfill \\ -\frac{1}{2}[(l_j+u_j)y_j-l_j{u}_j+(l_k+u_k)y_k-l_k{u}_k]\hfill \\ =\frac{1}{2}[(l_j+u_j)y_k+(l_k+u_k)y_j+l_j{u}_j+l_k{u}_k\hfill \\ -\frac{{(l_j+u_j+l_k+u_k)}^2}{4}\hfill \end{array}\end{array}$

and

$\begin{array}{l}{y}_j{y}_k=\frac{1}{2}[{(y_j+y_k)}^2-y_j^2-y_k^2]\hfill \\ \le \frac{1}{2}[(l_j+u_j+l_k+u_k)(y_j+y_k)-(l_j+l_k)(u_j+u_k)]\hfill \\ -\frac{1}{2}[(l_j+u_j)y_j-\frac{{(l_j+u_j)}^2}{4}+(l_k+u_k)y_k\hfill \\ -\frac{{(l_k+u_k)}^2}{4}]\hfill \\ =\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}\hfill \\ -(l_j+l_k)(u_j+u_k)]\hfill \end{array}$

Let

$\{\begin{array}{l}{f}_j^l(y)=(l_j+u_j)y_j-\frac{{(l_j+u_j)}^2}{4}\hfill \\ f_j^u(y)=(l_j+u_j)y_j-l_j{u}_j\hfill \\ f_{jk}^{{\rm I}}(y)=\frac{1}{2}[(l_j+u_j)y_k+(l_k+u_k)y_j+l_j{u}_j+l_k{u}_k\hfill \\ -\frac{{(l_j+u_j+l_k+u_k)}^2}{4}\hfill \\ f_{jk}^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}\hfill \\ -(l_j+l_k)(u_j+u_k)]\hfill \end{array}$

Obviously, we have

$f_j^l\left(y\right)\le y_j^2\le f_j^u\left(y\right), f_{jk}^l\left(y\right)\le y_j{y}_k\le f_{jk}^u\left(y\right)$

Since

$y_j^2-f_j^l\left(y_j\right)=y_j^2-\left[\left(l_j+u_j\right)y_j-\frac{{(l_j+u_j)}^2}{4}\right]$

is a convex function about y_j over the interval $\left[l_j,u_j\right]$ . Thus, at the point l_j or u_j, it can obtain the maximum value

$\text{max}\left[y_j^2-f_j^l\left(y_j\right)\right]=\frac{{(u_j-l_j)}^2}{4}$

Similarly, since

$f_j^u\left(y_j\right)-y_j^2=\left(l_j+u_j\right)y_j-l_j{u}_j-y_j^2$

is a concave function about y_j over the interval $\left[l_j,u_j\right]$ , therefore, at the point $\frac{l_j+u_j}{2},\left[f_j^u\left(y_j\right)-y_j^2\right]$ can obtain maximum value

$\text{max}\left[f_j^u\left(y_j\right)-y_j^2\right]=\frac{{(u_j-l_j)}^2}{4}$

Similarly, for any $y\in Y=\left[l, u\right]\subseteq Y^0,\text{ then }\left(y_j+y_k\right)\in \left[l_j+l_k,u_j+u_k\right]$ , we have

$\{\begin{array}{l}\text{max}\left\{{(y_j+y_k)}^2-\left[\left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\frac{{(l_j+u_j+l_k+u_k)}^2}{4}\right]\right\}=\frac{{(u_j+u_k-l_j-l_k)}^2}{4}\hfill \\ \text{max}\left\{\left[\left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\left(l_j+l_k\right)\left(u_j+u_k\right)\right]-{(y_j+y_k)}^2\right\}=\frac{{(u_j+u_k-l_j-l_k)}^2}{4}\hfill \end{array}$

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

$\{\begin{array}{l}\text{max}\left[y_j^2-f_j^l\left(y_j\right)\right]\to 0\hfill \\ \text{max}\left[f_j^u\left(y_j\right)-y_j^2\right]\to 0\hfill \\ \text{max}\left\{{(y_j+y_k)}^2-\left[\left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\frac{{(l_j+u_j+l_k+u_k)}^2}{4}\right]\right\}\to 0\hfill \\ \text{max}\left\{\left[\left(l_j+u_j+l_k+u_k\right)\left(y_j+y_k\right)-\left(l_j+l_k\right)\left(u_j+u_k\right)\right]-{(y_j+y_k)}^2\right\}\to 0\hfill \end{array}$

3

Since

$y_j{y}_k-f_{jk}^l(y)=y_j{y}_k-\left\{\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}\right\}=\frac{1}{2}[{(y_j+y_k)}^2-y_j^2-y_k^2]-\left\{\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}\right\}=\frac{1}{2}\left\{(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\right\}+\frac{1}{2}\left\{{(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}]\right\}\le \frac{1}{2}\text{max}[f_j^u(y_j)-y_j^2]+\frac{1}{2}\text{max}[f_k^u(y_k)-y_k^2]+\frac{1}{2}\text{max}\left\{{(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}]\right\}$

By equation (3), we have $y_j{y}_k-f_{jk}^l\left(y\right)\to 0\text{ as }\parallel u-l\parallel \to 0.$

Similarly, we can prove that $f_{jk}^u\left(y\right)-y_j{y}_k\to 0\text{ as }\parallel u-l\parallel \to 0.$

Let

$\begin{array}{l}{G}_i^L(y)={\displaystyle \sum _{k=1}^n{\alpha }_k^i{y}_k}+{\displaystyle \sum _{k=1,{\beta }_{kk}^i>0}^n{\beta }_{kk}^i{f}_k^l(y_k)+{\displaystyle \sum _{k=1,{\beta }_{kk}^i<0}^n{\beta }_{kk}^i{f}_k^u(y_k)}}+{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k=1,k\ne j,{\beta }_{jk}^i>0}^n{\beta }_{jk}^i{f}_{jk}^l(y)+{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k\ne 1,{\beta }_{jk}^i<0}^n{\beta }_{jk}^i{f}_{jk}^u(y)}}}}{G}_i^u(y)={\displaystyle \sum _{k=1}^n{\alpha }_k^i{y}_k}+{\displaystyle \sum _{k=1,{\beta }_{kk}^i<0}^n{\beta }_{kk}^i{f}_k^l(y_k)+{\displaystyle \sum _{k=1,{\beta }_{kk}^i>0}^n{\beta }_{kk}^i{f}_k^u(y_k)}}+{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k=1,k\ne j,{\beta }_{jk}^i<0}^n{\beta }_{jk}^i{f}_{jk}^l(y)+{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k\ne 1,{\beta }_{jk}^i>0}^n{\beta }_{jk}^i{f}_{jk}^u(y)}}}}\end{array}$

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

$G_i^U\left(y\right)\ge G_i\left(y\right)\ge G_i^L\left(y\right), G_i\left(y\right)-G_i^L\left(y\right)\to 0\text{ and }{G}_i^U\left(y\right)-G_i\left(y\right)\to 0.$

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

$\text{LRPP}\left(Y\right):\{\begin{array}{ll}\text{min}\hfill & G_0^L\left(y\right)\hfill \\ \text{s}.\text{t}.\hfill & G_i^L\left(y\right)\le b_i, i=1,\dots , m\hfill \\ \hfill & y\in Y=\left\{y: l\le y\le u\right\}\subseteq Y^0\hfill \end{array}$

where

$\begin{array}{l}{G}_i^L\left(y\right)=\sum _{k=1}^n{\alpha }_k^i{y}_k+\sum _{k=1,{\beta }_{kk}^i>0}^n{\beta }_{kk}^i{f}_k^l\left(y_k\right)+\sum _{k=1,{\beta }_{kk}^i<0}^n{\beta }_{kk}^i{f}_k^u\left(y_k\right)\hfill \\ +\sum _{j=1}^n\sum _{k=1, k\ne j,{\beta }_{jk}^i>0}^n{\beta }_{jk}^i{f}_{jk}^l\left(y\right)+\sum _{j=1}^n\sum _{k=1, k\ne j,{\beta }_{jk}^i<0}^n{\beta }_{jk}^i{f}_{jk}^u\left(y\right).\hfill \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=\left[l^k,u^k\right]\subseteq Y^0$ . This bisection rule is as follows.

Assume that $\eta \in \text{argmax}\{u_i-l_i|i=1,\dots , n\},\text{ then }{Y}^k$ can be partitioned into two subboxes: $Y^{k,1}=\{y\in R^n|l_i\le y_i\le u_i, i\ne \eta ; l_{\eta }\le y_{\eta }\le \frac{l_{\eta }+u_{\eta }}{2}\}\text{ and }{Y}^{k,2}=\{y\in R^n|l_i\le y_i\le u_i, i\ne \eta ; \frac{l_{\eta }+u_{\eta }}{2}\le y_{\eta }\le u_{\eta }\}.$

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}\text{ with }{Y}_j=\left[l_j,u_j\right] \left(j=1,\dots , n\right)$ , we assume that

$G_i^L\left(y\right)=\sum _{j=1}^n{\gamma }_{ij}{y}_j+{\eta }_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\text{min}\left\{{\gamma }_{0j}{l}_j,{\gamma }_{0j}{u}_j\right\}+{\eta }_0>U{B}_k$ , then the subbox Y should be deleted; else if $\sum _{j=1}^n\text{min}\left\{{\gamma }_{0j}{l}_j,{\gamma }_{0j}{u}_j\right\}+{\eta }_0\le U{B}_k$ , then for each $p\in \left\{1,2,\dots , n\right\}$ , we have

If ${\gamma }_{0p}>0$ , then the interval $\left(\frac{U{B}_k-\left({\sum }_{j=1}^n\text{min}\left\{{\gamma }_{0j}{l}_j,{\gamma }_{0j}{u}_j\right\}+{\eta }_0\right)+\text{min}\left\{{\gamma }_{0p}{l}_p,{\gamma }_{0p}{u}_p\right\}}{{\gamma }_{0p}},u_p\right]\underset{}{\cap }{Y}_p$ should be deleted;

If ${\gamma }_{0p}<0$ , then the interval $\left[l_p,\frac{U{B}_k-\left({\sum }_{j=1}^n\text{min}\left\{{\gamma }_{0j}{l}_j,{\gamma }_{0j}{u}_j\right\}+{\eta }_0\right)+\text{min}\left\{{\gamma }_{0p}{l}_p,{\gamma }_{0p}{u}_p\right\}}{{\gamma }_{0p}}\right)\cap Y_p$ should be deleted.

If $\sum _{j=1}^n\text{min}\left\{{\gamma }_{ij}{l}_j,{\gamma }_{ij}{u}_j\right\}+{\eta }_i>b_i$ for some $i\in \left\{1,\dots , m\right\}$ , then the subbox Y should be deleted; else if $\sum _{j=1}^n\text{min}\left\{{\gamma }_{ij}{l}_j,{\gamma }_{ij}{u}_j\right\}+{\eta }_i\le b_i$ for some $i\in \left\{1,\dots , m\right\}$ , then for each $p\in \left\{1,\dots , n\right\}$ , we have

If ${\gamma }_{ip}>0$ , then the interval $\left(\frac{b_i-\left({\sum }_{j=1}^n\text{min}\left\{{\gamma }_{ij}{l}_j,{\gamma }_{ij}{u}_j\right\}+{\eta }_i\right)+\text{min}\left\{{\gamma }_{ip}{l}_p,{\gamma }_{ip}{u}_p\right\}}{{\gamma }_{ip}},u_p\right]\cap Y_p$ should be deleted.

If ${\gamma }_{ip}<0$ , then the interval $\left[l_p,\frac{b_i-\left({\sum }_{j=1}^n\text{min}\left\{{\gamma }_{ij}{l}_j,{\gamma }_{ij}{u}_j\right\}+{\eta }_i\right)+\text{min}\left\{{\gamma }_{ip}{l}_p,{\gamma }_{ip}{u}_p\right\}}{{\gamma }_{ip}}\right)\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 $LB\left(Y^k\right)\text{ and }{y}^k=y\left(Y^k\right)$ 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, ${\Lambda }_0=\left\{Y^0\right\},F=\varnothing ,\epsilon >0,U{B}_0=+\infty$ .

  Solve the LRPP $\left(Y^0\right)$ to obtain LB ₀ = LB(Y ⁰) and     $y^0=y\left(Y^0\right).\text{ If }{y}^0$ is satisfied with the feasibility of the QPP, then let $F=\left\{y^0\right\}\text{ and }U{B}_0=G_0\left(y^0\right)$ .

 If $U{B}_0-L{B}_0\le \epsilon$ , 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 {\Lambda }_k$ , using the proposed bisection method, partition the box Y_k into two subboxes and denote the new subboxes set by ${\breve{Y}}^k$ .

Step 3. For each subbox $Y\in {\breve{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 ${\breve{Y}}^k$ .

Step 4. For each subbox $Y\in {\breve{Y}}^k$ , solve the LRPP $\left(Y\right)$ to get $\text{LB}\left(Y\right)$ and y(Y); if $\text{LB}\left(Y\right)>U{B}_k$ , then let ${\breve{Y}}^k={\breve{Y}}^k\backslash 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={\text{min}}_{y\in F}{G}_0\left(y\right)$ and denote the current best feasible solution by $y^k={\text{ argmin }}_{y\in F}{G}_0\left(y\right).\text{ Let }{\Lambda }_k=\left({\Lambda }_k\backslash Y^k\right)\cup {\breve{Y}}^k\text{ and }L{B}_k={\text{inf}}_{Y\in {\Lambda }_k}LB\left(Y\right)$ .

Step 5. If $U{B}_k-L{B}_k\le \epsilon ,$ 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={\text{ argmin }}_{Y\in {\Lambda }_k}LB\left(Y\right)$ , 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 $\left\{y^{k_q}\right\}\text{ of }\left\{y^k\right\}$ 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\le \epsilon .$

From the bounding process, we know that there does exist a feasible solution y_k such that $U{B}_k=G_0\left(y^k\right),$ so we have $G_0\left(y^k\right)-\epsilon \le L{B}_k.$

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

Since y_k is a feasible solution for the QPP, then we follow that $G_0\left(y^k\right)\ge v.$

From comprehensive analysis of the above results, we can follow that $v\ge L{B}_k\ge G_0\left(y^k\right)-\epsilon \ge v-\epsilon .$ 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 ${\text{lim}}_{k\to \infty }\left(U{B}_k-L{B}_k\right)=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

$\left(\text{QPP}\right):\{\begin{array}{ll}\text{min}\hfill & G_0\left(y\right)=\sum _{j=1}^n\sum _{k=1}^n{\beta }_{jk}^0{y}_j{y}_k+\sum _{k=1}^n{\alpha }_k^0{y}_k\hfill \\ \text{s}.\text{t}.\hfill & G_i\left(y\right)=\sum _{j=1}^n\sum _{k=1}^n{\beta }_{jk}^i{y}_j{y}_k+\sum _{k=1}^n{\alpha }_k^i{y}_k\le b_i, i=1,\dots , m\hfill \\ \hfill & y\in Y^0=\left\{y\in R^n:l^0\le y\le u^0\right\}\hfill \end{array}$

where ${\beta }_{jk}^0\text{ and }{\alpha }_k^0$ are randomly generated in $\left[-1,1\right],{\beta }_{jk}^i\text{ and }{\alpha }_k^i, i=1,\cdots , m$ are randomly generated in $\left[-1,1\right]$ , and b_i is randomly generated in $\left[-300,-90\right],{\text{l}}^0=\left[0,\cdots ,0{]}^T,\text{and\hspace{0.17em}}{u}^0=\right[10,\cdots ,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.