Abstract

This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.

Keywords

Nonconvex Inhomogeneous Quadratic Constrained Quadratic Optimization, Semidefinite Programming Relaxation, Np-Hard

Share and Cite:

1. Introduction

Consider the following quadratic optimization problem with non-convex inhomogeneous quadratic constraints:

$\begin{array}{l}\underset{x\in R^n}{min}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}f\left(x\right)=x^{\text{T}}Ax\\ \text{s}\text{.t}\text{.}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}{x}^{\text{T}}{A}^{k}x+{\left(b^k\right)}^{\text{T}}x\ge \mathrm{1,}k=\mathrm{1,}\cdots \mathrm{,}m\mathrm{,}\end{array}$ (1)

where $A,A^k\in R^{n\times n}\left(k=1,\cdots ,m\right)$ are symmetric positive semidefinite matrices and $b^k\in R^n$ . Note that if $n=1,$ then the problem (1) is easily solved, so assume $n\ge 2.$ Generally, this problem is NP-hard [1] [2] [3] . It has a lot of applications in telecommunications, robust control, portfolio and so on. So it’s helpful to solve it.

By means of the work of Lovász and Schrijver [4] , Shor [5] , and others that certain NP-hard combinatorial optimization problems can be approximated by semidefinite programming (SDP) problems, for which efficient solution methods exist [6] [7] . So many mathematics workers with this motive put forward a lot of algorithms to solving quadratic optimization problem based on the semidefinite programming (SDP) relaxation. Recently, there were several results on solving different forms of quadratic problems. The results can be summarized as follows.

•  If all $A^k$ are symmetric positive semidefinite $n\times n$ matrices with positive definite sum and A is an arbitrary symmetric $n\times n$ matrix. A. Nemirov- ki [8] produce a feasible solution $\tilde{x}$ such that, with constant probability,

$f\left(\tilde{x}\right)\ge \frac{1}{2\ln \left(2m^2\right)}\cdot v\left(SDP\right).$ (2)

•  If $A\mathrm{,\; <mi>\; </mi>}{A}^k\succcurlyeq \mathrm{0,\; <mi>\; </mi>}{A}^k={\left(A^k\right)}^{\text{T}}\mathrm{,\; <mi>\; </mi>}{b}^k=\mathrm{0,}$ Luo et al. [9] showed that the ratio between the original optimal value and the SDP relaxation optimal value is bounded by $O\left(m^2\right)$ , have

$\frac{v\left(P\right)}{v\left(SDP\right)}\le \frac{27m^2}{\text{π}}\mathrm{.}$ (3)

•  If all $A^k\mathrm{,\; <mi>\; </mi>}A$ are symmetric matrices, and two or more of them are indefinite. S. He et al. [10] compute a feasible solution $\tilde{x}$ such that,

$f\left(\tilde{x}\right)\le \frac{{10}^6{m}^2}{\text{π}}\cdot v\left(SDP\right)\mathrm{.}$ (4)

•  Of special interest is the case of ellipsoid constraints

$\begin{array}{l}{A}^k={\left(F^k\right)}^{\text{T}}{F}^k,b^k=2{\left(F^k\right)}^{\text{T}},\\ c^k={\left(\Vert g^k\Vert \right)}^2-h^k,k=1,\cdots ,m,\end{array}$ (5)

where $F^k\in R^n,g^k\in R^n,h^k\in 0,\mathrm{1,}$ $\Vert \cdot \Vert$ denotes the Euclidean norm, so $x^{\text{T}}{A}^{k}x+b^{k}x+c^k={\Vert F^{k}x+g^k\Vert }^2-h^k,k=1,\cdots ,m$ . Nemirovski [8] show that if all $b^k=0$ and $A^k$ are positive semidefinite. Then a feasible solution $\tilde{x}$ can be generated from (SDP) satisfying

$f\left(\tilde{x}\right)\le \frac{1}{2\ln \left(2\left(m+1\right)\mu \right)}\cdot v\left(SDP\right),\mathrm{<mi>\; </mi>}\mu =\min \left\{m+1,{\max }_{k=1,\cdots ,m}rank\left(A^k\right)\right\}.$ (6)

•  In particular, if (1) has a ball constraints, $\mu =\min \left\{m+1,n\right\}.$ Ye and Zhang(Corollary 2.6 in [11] ) showed that a feasible x satisfying

$f\left(x\right)\le \frac{1}{\min \left\{m-1,n\right\}}\cdot v\left(SDP\right),$ (7)

can be found in polynomial time.

•  Ye. [12] extended the above result to allow the ellipsoids not to have a common center but assuming $A\preccurlyeq 0$ . Ye showed that a feasible solution $\tilde{x}$ can be randomly generated such that

$E\left(\tilde{x}{A}^{\text{T}}\tilde{x}\right)\le \frac{{\left(1-\underset{k=1,\cdots ,m}{\max }\Vert g^k\Vert \right)}^2}{4\ln \left(4mn\cdot \underset{k=1,\cdots ,m}{\max }\left(rank\left(A^k\right)\right)\right)}\cdot v\left(SDP\right).$ (8)

However, the existing algorithms are just for the problem of discrete problems or continuous problems, which is mostly based on homogeneous or inhomogeneous convex constraint problems. For this kind of quadratic optimization problem with non-convex inhomogeneous quadratic constraints, cannot find a very effective algorithm. This paper will propose a new effective algorithm to solve this problem.

This paper is organized as follows. In Section 2, we present a semidefinite pro- gramming (SDP) relaxation of (1). In Section 3, we propose a new effective algorithm to get the feasible solution of quadratic optimization problem (1) with non-convex inhomogeneous quadratic constraints. At last, some conclusions and the future works are given in Section 4.

Notations. Throughout this paper, we denote by $R^n$ and $S_{+}^n$ the n-dimen- sional real vector space and $n\times n$ positive semidefinite symmetric matrices space. $A\succcurlyeq 0$ denotes that A is semidefinite. $Tr(\cdot )$ represents the trace of a matrix. The inner product of two matrices A and B is denoted by

$A•B=Tr\left(A{B}^T\right)={\displaystyle {\sum }_{i=1}^n}{\displaystyle {\sum }_{j=1}^n}{a}_{ij}{b}_{ij}\cdot Pr(\cdot )$ stands for the probability.

2. Semidefinite Programming (SDP) Relaxation

In this section, we present a semidefinite programming (SDP) relaxation of (1). To avoid trivial cases, we first make the following assumption.

Assumption Let $b^k=2A^k{y}^k$ , has a solution, $y^k\in R^n\mathrm{.}$

Assume t is a constant, and satisfy $t^2=1$ . (1) is equivalent to:

$\begin{array}{l}\underset{\left(x\mathrm{,}t\right)\in R^n\times R}{min}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}f\left(x\mathrm{,}t\right)=x^{\text{T}}Ax\\ \mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{s}\text{.t}\mathrm{.\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[x^{\text{T}}{A}^{k}x+{\left(b^k\right)}^{\text{T}}x\cdot t+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\cdot t^2\right]\ge \mathrm{1,}k=\mathrm{1,}\cdots \mathrm{,}m\\ \mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}{t}^2=1.\end{array}$ (9)

Let $x^{\mathrm{<mo>\; *\; </mo>}}$ be the global optimal solution of the above problem, the objective value is $v\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)$ . Assume $X\succcurlyeq 0$ , it’s block structure like this:

$X=\left[\begin{array}{cc}{X}^{\left(1\right)}& X^{\left(3\right)}\\ {\left(X^{\left(3\right)}\right)}^H& X^{\left(2\right)}\end{array}\right]\in S_{+}^{\left(n+1\right)\times \left(n+1\right)}.$ (10)

where

$B=\left[\begin{array}{cc}A& 0\\ 0& 0\end{array}\right]\succcurlyeq \mathrm{0,}{B}^k=\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[\begin{array}{cc}{A}^k& \frac{1}{2}{b}^k\\ \frac{1}{2}{\left(b^k\right)}^{\text{T}}& {\left(y^k\right)}^{\text{T}}{A}^k{y}^k\end{array}\right]\succcurlyeq \mathrm{0,}k=\mathrm{1,}\cdots \mathrm{,}m\mathrm{.}$ (11)

By letting $X=x{x}^{\text{T}}$ and dropping the rank one constraint, the semidefinite programming relaxation of (9) can be drawn up as follows.

$\begin{array}{l}min\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}B•X\\ \mathrm{<mi>\; </mi>}\text{s}\text{.t}\mathrm{.\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}{B}^k•X\ge \mathrm{1,}k=\mathrm{1,}\cdots \mathrm{,}m\\ \mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}{X}_{n+\mathrm{1,}n+1}=\mathrm{1,}X\succcurlyeq \mathrm{0,}X\in R^{\left(n+1\right)\times \left(n+1\right)}\mathrm{.}\end{array}$ (SDP)

An optimal solution of SDP relaxation (SDP) can be computed efficiently using, say, interior-point mathods; see [13] and references therein.

3. Algorithm

In this section, we bring an effective algorithm for solving (1). The algorithm is divided into two parts. The main idea as follows: the first stage produces a solution which satisfies the first constraint of problem (9). Making a small change to the solution which obtained in the first stage, we can get the solution of (9) in the second stage. We will set the randomization algorithm as follows.

3.1. The First Stage

The first stage of the algorithm uses the randomization algorithm, which is proposed by Luo et al. [3] . At first, we need obtain an optimal solution $X^{\mathrm{<mo>\; *\; </mo>}}$ of (SDP), then construct a feasible solution for the first constraint of problem (9) using the following randomization procedure:

First, it can be easily verified that $\tilde{x}={\left(x^{\text{T}}\mathrm{,}{\tilde{x}}_{n+1}\right)}^{\text{T}}$ satisfy the first constraint of problem (9).

$\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[x^{\text{T}}{A}^{k}x+{\left(b^k\right)}^{\text{T}}\cdot x\cdot {\tilde{x}}_{n+1}+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\cdot {\tilde{x}}_{n+1}^2\right]=\frac{{\xi }^{\text{T}}{B}^k\xi }{\underset{k}{min}{\xi }^{\text{T}}{B}^k\xi }\ge \mathrm{1,}$ (12)

(12) is equivalent to:

$\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[{\left(\frac{x}{{\tilde{x}}_{n+1}}\right)}^{\text{T}}{A}^k\frac{x}{{\tilde{x}}_{n+1}}+b^k\frac{x}{{\tilde{x}}_{n+1}}+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\right]\ge \frac{1}{{\tilde{x}}_{n+1}^2}\mathrm{,}\forall k=\mathrm{1,}\cdots \mathrm{,}m\mathrm{.}$ (13)

Lemma 1 For $\tilde{x}$ generated in step 2, we have that

$pr\left(\frac{1}{{\tilde{x}}_{n+1}^2}\ge \frac{4}{{10}^4{m}^2}\right)\ge \frac{1}{100}\mathrm{.}$ (14)

Proof. By the step 2, we first have

${\tilde{x}}_{n+1}=\frac{e_{n+1}^{\text{T}}\xi }{\sqrt{\underset{k}{min}{\xi }^{\text{T}}{B}^k\xi }}\mathrm{,}$ (15)

where $e_{n+1}\in R^{\left(n+1\right)\times 1}$ is a vector with the $\left(n+1\right)\text{th}$ element being 1 and all the other elements being 0. By denoting $Q=e_{n+1}{e}_{n+1}^{\text{T}},$ we obtain that

$\begin{array}{c}pr\left(\frac{1}{{\tilde{x}}_{n+1}^2}\le M\right)=pr\left(\frac{1}{M}\cdot \underset{k}{min}{\xi }^{\text{T}}{B}^k\xi \le {\xi }^{\text{T}}{e}_{n+1}{e}_{n+1}^{\text{T}}\xi \right)\\ =pr\left(\frac{1}{M}\cdot \underset{k}{min}{\xi }^{\text{T}}{B}^k\xi \le {\xi }^{\text{T}}Q\xi \right)\mathrm{.}\end{array}$ (16)

By using the total probability formula for the last term in (16), we have

$\begin{array}{l}\le pr\left(\frac{1}{M}\cdot M\le {\xi }^{\text{T}}Q\xi \right)\cdot pr\left(M\le \underset{k}{min}{\xi }^{\text{T}}{B}^k\xi \right)+pr\left(M\mathrm{<mo>\; >\; </mo>}\underset{k}{min}{\xi }^{\text{T}}{B}^k\xi \right)\cdot 1\\ \le pr\left(1\le {\xi }^{\text{T}}Q\xi \right)+pr\left(M\mathrm{<mo>\; >\; </mo>}\underset{k}{min}{\xi }^{\text{T}}{B}^k\xi \right)\mathrm{.}\end{array}$ (17)

By Lemma 3.1 and Lemma 3.2 in [10] ,

$pr\left(1\le {\xi }^{\text{T}}Q\xi \right)=pr\left(Tr\left(Q{X}^{*}\right)\le {\xi }^{\text{T}}Q\xi \right)=pr\left(E\left({\xi }^{\text{T}}Q\xi \right)\le {\xi }^{\text{T}}Q\xi \right)<1-\frac{3}{100}.$ (18)

Since $X^{\mathrm{<mo>\; *\; </mo>}}$ is feasible for (SDP), it follows that $Tr\left(B^k{X}^{\mathrm{<mo>\; *\; </mo>}}\right)\ge 1$ for all $k=1,\cdots ,m$ . Since $E\left({\xi }^{\text{T}}{B}^k\xi \right)=Tr\left(B^k{X}^{\mathrm{<mo>\; *\; </mo>}}\right)\ge \mathrm{1,}$ so

$\begin{array}{l}pr\left(M>\underset{k}{\min }{\xi }^{\text{T}}{B}^k\xi \right)\le pr\left(MTr\left(B^k{X}^{*}\right)>\underset{k}{\min }{\xi }^{\text{T}}{B}^k\xi \right)\\ =\mathrm{<mi>\; </mi>}pr\left(ME\left({\xi }^{\text{T}}{B}^k\xi \right)>\underset{k}{\min }{\xi }^{\text{T}}{B}^k\xi \right)\le {\displaystyle \underset{k=1}{\overset{m}{\sum }}}pr\left(ME\left({\xi }^{\text{T}}{B}^k\xi \right)>{\xi }^{\text{T}}{B}^k\xi \right).\end{array}$ (19)

According to Lemma 1 in [9] , we have

$pr\left(ME\left({\xi }^{\text{T}}{B}^k\xi \right)>{\xi }^{\text{T}}{B}^k\xi \right)\le \max \left\{\sqrt{M},\frac{2\left(\sqrt{2\left(m+1\right)}-1\right)M}{\text{π}-2}\right\}.$ (20)

Thus, it follows from (17), (18), (19) and (20) that:

$pr\left(\frac{1}{{\tilde{x}}_{n+1}^2}\le M\right)\le 1-\frac{3}{100}+m\cdot \max \left\{\sqrt{M},\frac{2\left(\sqrt{2\left(m+1\right)}-1\right)M}{\text{π}-2}\right\}.$ (21)

The proof is completed by setting $M=\frac{4}{{10}^4{m}^2}.$

Note that by Lemma 1 and (13), it can be concluded that

$pr\left\{\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[{\left(\frac{x}{{\tilde{x}}_{n+1}}\right)}^{\text{T}}{A}^k\frac{x}{{\tilde{x}}_{n+1}}+b^k\frac{x}{{\tilde{x}}_{n+1}}+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\right]\ge \frac{4}{{10}^4{m}^2}\right\}\ge \frac{1}{100}\mathrm{.}$ (22)

So there is a $\bar{x}$ , for any $k=1,\cdots ,m$ satisfies:

$\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[{\left(\bar{x}\right)}^{\text{T}}{A}^k\bar{x}+b^k\bar{x}+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\right]\ge \frac{4}{{10}^4{m}^2}\mathrm{.}$ (23)

3.2. The Second Stage

In this part, we make a change to the solution which constructed in the first stage in order to satisfy the problem (9). In this stage, we will by ways of the algorithm in [14] .

The procedure as follows:

Let $f\left(\tau \right)={\tau }^2{\hat{x}}^{\text{T}}{A}^k\hat{x}+\tau {\left(b^k\right)}^{\text{T}}\hat{x}$ , so $f\left(\tau \right)$ can be seen as a quadratic function for $\tau$ . The symmetry axis of $f\left(\tau \right)$ is:

$x=\frac{-{\left(b^k\right)}^{\text{T}}\hat{x}}{2{\hat{x}}^{\text{T}}{A}^k\hat{x}}\mathrm{.}$ (24)

Because the $\hat{x}$ can’t make ${\left(\hat{x}\right)}^{\text{T}}{A}^k\left(\hat{x}\right)+{\left(b^k\right)}^{\text{T}}\left(\hat{x}\right)\ge 1$ for all $k=1,\cdots ,m$ set up. We introduce a parameter $\hat{\tau }$ , and construct a new solution $\hat{\tau }\hat{x}$ . It’s the feasible solution of (1).

When ${\hat{x}}^{\text{T}}{A}^k\hat{x}+{\left(b^k\right)}^{\text{T}}\hat{x}>1$ , the symmetry axis of $f\left(\tau \right)$ satisfies:

$x=\frac{-{\left(b^k\right)}^{\text{T}}\hat{x}}{2{\hat{x}}^{\text{T}}{A}^k\hat{x}}<\frac{{\hat{x}}^{\text{T}}{A}^k\hat{x}-1}{2{\hat{x}}^{\text{T}}{A}^k\hat{x}}=\frac{1}{2}-\frac{1}{2{\hat{x}}^{\text{T}}{A}^k\hat{x}}<\frac{1}{2}.$ (25)

So for all $\tau >1,$ can make ${\left(\tau \hat{x}\right)}^{\text{T}}{A}^k\left(\tau \hat{x}\right)+{\left(b^k\right)}^{\text{T}}\left(\tau \hat{x}\right)>1$ set up. It’s helpful for us to solve the problem, because we only need to find $\tau$ satisfying ${\left(\tau \hat{x}\right)}^{\text{T}}{A}^k\left(\tau \hat{x}\right)+{\left(b^k\right)}^{\text{T}}\left(\tau \hat{x}\right)>1$ in the situation of ${\hat{x}}^{\text{T}}{A}^k\hat{x}+{\left(b^k\right)}^{\text{T}}\hat{x}\le 1$

When ${\hat{x}}^{\text{T}}{A}^k\hat{x}+{\left(b^k\right)}^{\text{T}}\hat{x}\le 1$ , because $A^k\succcurlyeq \mathrm{0\; <mi>\; </mi>}\left(k=\mathrm{1,}\cdots \mathrm{,}m\right)$ are symmetric, $b^k=2A^k{y}^k$ . To simplify the writing, we introduce the following notations:

$\stackrel{}{\stackrel{︷}{x_k}}=\Vert {\left(A^k\right)}^{\frac{1}{2}}\hat{x}\Vert ,\mathrm{<mi>\; </mi>}\stackrel{}{\stackrel{︷}{y_k}}=\Vert {\left(A^k\right)}^{\frac{1}{2}}{y}^k\Vert ,\mathrm{<mi>\; </mi>}\stackrel{}{\stackrel{︷}{z_k}}=\Vert {\left(A^k\right)}^{\frac{1}{2}}\hat{x}+{\left(A^k\right)}^{\frac{1}{2}}{y}^k\Vert ,$ (26)

So

$\begin{array}{c}f\left(\tau \right)={\tau }^2{\hat{x}}^{\text{T}}{A}^k\hat{x}+\tau {\left(b^k\right)}^{\text{T}}\hat{x}\\ =\left({\tau }^2-\tau \right){\left(\stackrel{}{\stackrel{︷}{x_k}}\right)}^2+\tau \left[{\left(\stackrel{}{\stackrel{︷}{x_k}}\right)}^2+{\left(b^k\right)}^{\text{T}}\hat{x}+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right]-\tau {\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\\ =\left({\tau }^2-\tau \right){\left(\stackrel{}{\stackrel{︷}{x_k}}\right)}^2+\tau {\left(\stackrel{}{\stackrel{︷}{z_k}}\right)}^2-\tau {\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2.\end{array}$ (27)

According to the norm inequality:

$\Vert x-y\Vert \ge \left|\Vert x\Vert -\Vert y\Vert \right|\mathrm{.}$ (28)

we have

${\left(\stackrel{}{\stackrel{︷}{x_k}}\right)}^2={\left(\Vert {\left(A^k\right)}^{\frac{1}{2}}\hat{x}\Vert \right)}^2\ge {\left(\left|\Vert {\left(A^k\right)}^{\frac{1}{2}}\hat{x}+{\left(A^k\right)}^{\frac{1}{2}}{y}^k\Vert -\Vert {\left(A^k\right)}^{\frac{1}{2}}{y}^k\Vert \right|\right)}^2={\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\mathrm{.}$ (29)

For $\tau \in \left[\mathrm{1,}+\infty \right)\mathrm{,}$ using (28), (29). The last term in (27) can be simplified to be

$\begin{array}{l}\ge \left({\tau }^2-\tau \right){\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2+\tau {\left(\stackrel{}{\stackrel{︷}{z_k}}\right)}^2-\tau {\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\\ ={\tau }^2{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2+2\tau \left(\left(\stackrel{}{\stackrel{︷}{y_k}}\right)\left(\stackrel{}{\stackrel{︷}{z_k}}\right)-{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)={\tau }^2{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2+2\tau \left(\stackrel{}{\stackrel{︷}{y_k}}\right)\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right),\end{array}$ (30)

Whenever $\tau \ge \frac{-\left(\stackrel{}{\stackrel{︷}{y_k}}\right)\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)+\sqrt{{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\left(1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)}}{{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2},$ it can be easily checked that ${\left(\tau \hat{x}\right)}^{\text{T}}{A}^k\left(\tau \hat{x}\right)+{\left(b^k\right)}^{\text{T}}\left(\tau \hat{x}\right)\ge 1.$

From (23), we can get

$\begin{array}{l}\frac{1}{1+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k}\left[{\left(\hat{x}\right)}^{\text{T}}{A}^k\hat{x}+b^k\hat{x}+{\left(y^k\right)}^{\text{T}}{A}^k{y}^k\right]\ge \frac{4}{{10}^4{m}^2}\\ \iff \stackrel{}{\stackrel{︷}{z_k}}\ge \sqrt{\frac{1}{50m}\left(1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)}\mathrm{,}\end{array}$ (31)

and we also have

${\hat{x}}^{\text{T}}{A}^k\hat{x}+{\left(b^k\right)}^{\text{T}}\hat{x}\le 1\iff \stackrel{}{\stackrel{︷}{z_k}}\le \sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}\mathrm{.}$ (32)

Thus

$\hat{\tau }\le \underset{k=1,\cdots ,m}{\max }\frac{-\left(\stackrel{}{\stackrel{︷}{y_k}}\right)\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)+\sqrt{{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\left(1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)}}{{\left(\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}\le \underset{k=1,\cdots ,m}{\max }\frac{\sqrt{{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2+1}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\left|\stackrel{}{\stackrel{︷}{z_k}}-\stackrel{}{\stackrel{︷}{y_k}}\right|}.$ (33)

Using (31) and (32), the last term in (33) can be simplified as

$\le \underset{k=1,\cdots ,m}{\max }\left\{\frac{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\left|\sqrt{\frac{1}{50m}\left(1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)}-\stackrel{}{\stackrel{︷}{y_k}}\right|}\mathrm{,}\frac{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}-\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}\right\}\mathrm{.}$ (34)

We will give the analysis of (34) as follows.

First, let

$f\left(\stackrel{}{\stackrel{︷}{y_k}}\right)=\frac{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}-\left(\stackrel{}{\stackrel{︷}{y_k}}\right)},\mathrm{<mi>\; </mi>}g\left(\stackrel{}{\stackrel{︷}{y_k}}\right)=\frac{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\left|\sqrt{\frac{1}{50m}\left(1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2\right)}-\stackrel{}{\stackrel{︷}{y_k}}\right|}.$ (35)

we can simplified $f\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$

$f\left(\stackrel{}{\stackrel{︷}{y_k}}\right)=\frac{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}{\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}-\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}={\left(\sqrt{1+{\left(\stackrel{}{\stackrel{︷}{y_k}}\right)}^2}+\left(\stackrel{}{\stackrel{︷}{y_k}}\right)\right)}^2.$ (36)

Since $\stackrel{}{\stackrel{︷}{y_k}}\ge 0$ , we know that $f\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$ is an increasing function about $\stackrel{}{\stackrel{︷}{y_k}}$ .

However, $g\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$ is a function depend on $\stackrel{}{\stackrel{︷}{y_k}}$ and the number of the constraints. According to simple calculations, we find, when satisfies $\stackrel{}{\stackrel{︷}{y_k}}<\sqrt{\frac{1}{50m-1}}$ , $g\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$ is an increasing function about $\stackrel{}{\stackrel{︷}{y_k}}$ . In this situation, we also have $g\left(\stackrel{}{\stackrel{︷}{y_k}}\right)>f\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$ . When $\stackrel{}{\stackrel{︷}{y_k}}>\sqrt{\frac{1}{50m-1}}$ , $g\left(\stackrel{}{\stackrel{︷}{y_k}}\right)$ becomes smaller with the increase of $\stackrel{}{\stackrel{︷}{y_k}}$ .

where

${\gamma }_1=\underset{k=1,\cdots ,m}{\max }\left(\stackrel{}{\stackrel{︷}{y_k}}\right),{\gamma }_2=\underset{k=1,\cdots ,m}{\min }\left(\stackrel{}{\stackrel{︷}{y_k}}\right).$ (37)

we can write (34) as a piecewise function about ${\gamma }_1$ and ${\gamma }_2$

$f\left({\gamma }_1,{\gamma }_2\right)=\{\begin{array}{l}\frac{\sqrt{{\left({\gamma }_1\right)}^2+1}+{\gamma }_1}{\left|\sqrt{\frac{1}{50m}\left(1+{\left({\gamma }_1\right)}^2\right)}-{\gamma }_1\right|}{\gamma }_1,{\gamma }_2<\sqrt{\frac{1}{50m-1}}\\ +\infty {\gamma }_1>\sqrt{\frac{1}{50m-1}},{\gamma }_2<\sqrt{\frac{1}{50m-1}}\\ \max \left\{\frac{\sqrt{{\left({\gamma }_2\right)}^2+1}+{\gamma }_2}{\left|\sqrt{\frac{1}{50m}\left(1+{\left({\gamma }_2\right)}^2\right)}-{\gamma }_2\right|},\frac{\sqrt{{\left({\gamma }_1\right)}^2+1}+{\gamma }_1}{\sqrt{{\left({\gamma }_1\right)}^2+1}-{\gamma }_1}\right\}{\gamma }_1,{\gamma }_2>\sqrt{\frac{1}{50m-1}}.\end{array}$ (38)

So it can be easily verified that

$x=f\left({\gamma }_1,{\gamma }_2\right)\cdot \hat{x},\mathrm{<mi>\; </mi>}\text{with}\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{\gamma }_1=\underset{k=1,\cdots ,m}{\max }\left(\stackrel{}{\stackrel{︷}{y_k}}\right),{\gamma }_2=\underset{k=1,\cdots ,m}{\min }\left(\stackrel{}{\stackrel{︷}{y_k}}\right),$ (39)

is a feasible solution of the original problem.

4. Conclusions

For the quadratic optimization problem with non-convex inhomogeneous quadratic constraints, it’s NP-hard. We can’t find an effective algorithm solving it. In this paper, we put forward an effective algorithm. According to it, many problems in life can be solved. Through the algorithm, we can get the feasible solution of (1). Transforming the original problem into (SDP) is a very important step in solving the problem. So we give the semidefinite programming (SDP) relaxation of (1) in Section 2, then propose an effective algorithm which given in Section 3 to construct the feasible solution of (1).

In the future, I will do the following work: discusses the quality of the feasible solution about (1), and gives some numerical experiments to verify it, we will consider the problem with inhomogeneous objective function. To this problem, we want to find an algorithm solve it by ways of the effective algorithm which put forward in this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

References