A new accelerating method for global non-convex quadratic optimization with non-convex quadratic constraints

Abstract

In this paper, we combine the new global optimization method proposed by Qu et al. [S.J. Qu, K.C. Zhang, Y. Ji, A global optimization algorithm using parametric linearization relaxation, Appl. Math. Comput. 186 (2007) 763–771] with a suitable deleting technique to propose a new accelerating global optimization algorithm for solving the non-convex quadratic optimization problems with non-convex quadratic constraints (NQP). This technique offers a possibility to cut away a large part of the currently investigated region in which the global optimal solution of NQP does not exist, and can be seen as an accelerating device for the global optimization algorithm of the NQP problems. Compared with the method in Qu et al. (2007), numerical results show that the computational efficiency is obviously improved by using this new technique in the number of iterations, the required list length and the overall execution time of the algorithm.

Introduction

In this paper, we shall be concerned with the non-convex quadratic programming with non-convex quadratical constrained with bounded variables:

$$\mathrm{NQP}(X^0):\left\{\begin{array}{cc}\min \hfill & f^0(x)\hfill \\ \mathrm{s}.\mathrm{t}.\hfill & f^j(x)⩽b_j\text{,}j=1\text{,}\dots \text{,}m\hfill \\ \hfill & X^0=\left\{x:{\underline{x}}_i^0⩽x_i⩽{\overline{x}}_i^0\text{,}i=1\text{,}\dots \text{,}\right\}\hfill \end{array}\right.\text{,}$$

where $f^j(x)=(c^j{)}^{\mathrm{T}}x+\frac{1}{2}{x}^{\mathrm{T}}{Q}^{j}x\text{,}j=0\text{,}1\text{,}\dots \text{,}m\text{,}{c}^j\in R^n$, Q^j ∈ R^n×n and b_j ∈ R¹. Without loss generality, it can be assumed that matrices $Q^j={\left(q_{\mathit{ik}}^j\right)}_{n\times n}\text{,}j=0\text{,}1\text{,}\dots \text{,}m$ are all symmetric.

Quadratic constrained problems are worthy of study both because they frequently appear in applications [2] and because many other nonlinear problems can be transformed into this form [3], [4]. But solving problems of this sort is known to be NP-hard. Many global optimization algorithms have been developed for solving NQP based on the convexity assumptions on the objective function or the constrained functions of NQP (for example [5], [6]). But the global optimization algorithms of NQP without these assumptions are scarce. Recently, Tim and Faiz [7] gave a global optimization algorithm of NQP based on the convex relaxation. By using the parametric linearization method, Qu et al. [1] gave a new global optimization algorithm for finding the global minimum of NQP.

The main purpose of this paper is to provide an accelerating method for global optimization algorithm of NQP. Based on Ref. [1], a new deleting technique is given, and this technique offers the possibility to cut away a large part of the currently investigated feasible region which does not contain the global minimum of NQP. By using this new deleting technique which can be seen as an accelerating device of the global optimization algorithm for NQP, we can improve greatly the convergence of the algorithm by reducing the current investigated feasible region. Numerical experiments show that the computational efficiency can be obviously improved using this new technique, that is, the number of iterations, the required saving list length and the execution time of the algorithm can all be significantly reduced.

The remainder of this paper is organized as follows. In Section 2, the new deleting technique is presented. In Section 3, the proposed accelerating algorithm is given, and the convergence of the algorithm is proved. Numerical results of some problems in the area of engineering design are considered in Section 4. Section 5 provides a summary.