Global Optimality Conditions for Nonlinear Programming Problems with Linear Equality Constraints

Abstract

Some necessary global optimality conditions and sufficient global optimality conditions for nonconvex minimization problems with a quadratic inequality constraint and a linear equality constraint are derived. In particular, global optimality conditions for nonconvex minimization over a quadratic inequality constraint which extend some known global optimality conditions in the existing literature are presented. Some numerical examples are also given to illustrate that a global minimizer satisfies the necessary global optimality conditions but a local minimizer which is not global may fail to satisfy them.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Guoquan Li 1 and Yan Wang 2

Academic Editor:Xian-Jun Long

1, School of Mathematics, Chongqing Normal University, Chongqing 401331, China
2, School of Liberal Arts, Chongqing Normal University, Chongqing 401331, China

Received 14 March 2014; Accepted 2 April 2014; 22 April 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In this paper, we focus on the following nonconvex minimization model problem: [figure omitted; refer to PDF]

where f : ^{R n} [arrow right] R is a twice continuously differentiable function which is not necessarily a quadratic function, c ∈ R , b ∈ ^{R n} , B ∈ ^{S n} , d ∈ ^{R m} , ^{S n} is the set of all symmetric n × n matrices, and H is a m × n matrix. Model problems of the form QLNP are widespread in real-world applications [1, 2]. When the objective function is quadratic, problem (QLNP) is a general trust-region model problem with linear equality constraint (see [3, 4]). In [5], Jeyakumar and Srisatkunarajah presented some Lagrange multiplier necessary conditions for global optimality for problem (QLNP) by employing S-lemma and overestimators of the objective function, and they also show that the obtained necessary global optimality condition is not necessarily a sufficient condition for global optimality by a numerical example. Some global optimality conditions for nonconvex quadratic minimization problems with quadratic and/or linear constraints were recently developed in [6-11].

A theorem of the alternative is a key tool for developing local optimality conditions in continuous optimization. In [5, 11], some global optimality conditions for nonconvex minimization problems were derived by employing quadratic overestimators or underestimators of the object function that allows for the applications of the S-lemma.

The purpose of this paper is to establish some necessary and sufficient global optimality conditions for nonlinear programming problems with a quadratic inequality and linear equality constraints by employing an alternative theorem for systems of two quadratic inequalities given in [11]. As a consequence, we also present some global optimality conditions including necessary conditions and sufficient conditions for nonlinear programming problems over a quadratic inequality constraint extending several known global optimality conditions in the existing literature. Some global optimality conditions for problem (QLNP) in the case where the objective function is quadratic are derived at the same time.

The outline of this paper is as follows. In Section 2, we present global optimality conditions for nonlinear programming problems (QLNP) and extend the corresponding results given in [5]. We also provide two numerical examples to illustrate the significance of our optimality conditions. In Section 3, some global optimality conditions for general smooth minimization problems over quadratic and linear equality constraints are presented.

2. Global Optimality Conditions for Problem (QCNP)

We begin this section by presenting basic definitions and preliminary results that will be used throughout the paper. The real line is denoted by R and the n -dimensional Euclidean space is denoted by ^{R n} . For vectors x , y ∈ ^{R n} , x ...5; y means that _{x i} ...5; _{y i} , for i = 1 , ... , n . The notation A ... B means that A - B is positive semidefinite and A ... 0 means that - A ... 0 .

For problem (QLNP), let [figure omitted; refer to PDF]

The following theorem of the alternative (given in [11]) for systems of two quadratic inequalities plays an important role in deriving our main results; see Theorem 2.

Lemma 1 (generalizer S-lemma).

Let _{S 0} be a subspace, and let _{a 0} ∈ ^{R n} . Let _{g 1} : ^{R n} [arrow right] R be defined by _{g 1} ( x ) = ( 1 / 2 ) ^{x T} _{B 1} x + ^{x T} _{b 1} + _{c 1} , where _{B 1} ∈ ^{S n} , _{b 1} ∈ ^{R n} , and _{c 1} ∈ R . Suppose that there exists _{x 0} ∈ _{a 0} + _{S 0} , such that g ( _{x 0} ) < 0 . Then the following statements are equivalent:

(i) g ( x ) ...4; 0 , x ∈ _{a 0} + _{S 0} [implies] _{g 1} ( x ) ...5; 0 ;

(ii) ( ∃ λ ...5; 0 ) ( ∀ x ∈ _{a 0} + _{S 0} ) _{g 1} ( x ) + λ g ( x ) ...5; 0 , where g is defined by (1).

By employing a quadratic overestimator and Lemma 1, we derive necessary global optimality conditions for problem (QLNP).

Theorem 2 (necessary conditions).

For the problem (QLNP), let x ¯ ∈ D and let C be a convex set containing D . Assume that there exists A ∈ ^{S n} such that ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C , and that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 and H _{x 0} = b . If x ¯ is a global minimizer of QLNP then there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 , and ^{e T} ( A + λ B ) e ...5; 0 , whenever H e = 0 .

Proof.

Let l ( x ) = ( 1 / 2 ) ^{x T} A x + ( ∇ f ( x ¯ ) - A x ¯ ^{) T} x , ∀ x ∈ ^{R n} , and let [straight phi] ( x ) = f ( x ) - l ( x ) , x ∈ C ; then [figure omitted; refer to PDF]

So [straight phi] is a concave function over C . Moreover, ∇ [straight phi] ( x ¯ ) = ∇ f ( x ¯ ) - ∇ l ( x ¯ ) = 0 . Hence, [figure omitted; refer to PDF] That is, [figure omitted; refer to PDF]

If x ¯ is a global minimizer of QLNP , then [figure omitted; refer to PDF]

Let _{S 0} = { x ∈ ^{R n} |" H x = 0 } . Then [ g ( x ) ...4; 0 , x ∈ x ¯ + _{S 0} [implies] l ( x ) - l ( x ¯ ) ...5; 0 ] . So, by Lemma 1, there exists λ ...5; 0 , such that [figure omitted; refer to PDF]

In particular, [figure omitted; refer to PDF]

Hence, l + λ g attains its minimum at x ¯ over H x = d . Now, by the necessary optimality conditions at x ¯ , there exists μ ∈ ^{R m} such that [figure omitted; refer to PDF] and ^{e T} ( A + λ B ) e ...5; 0 whenever H e = 0 .

Theorem 3 (sufficient conditions).

For the problem (QLNP), let x ¯ ∈ D and let C be a convex set containing D . Assume that there exists A ∈ ^{S n} such that ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C . If there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 , and ^{e T} ( A + λ B ) e ...5; 0 whenever H e = 0 , then x ¯ is a global minimizer of QLNP.

Proof.

Let l ( x ) = ( 1 / 2 ) ^{x T} A x + ( ∇ f ( x ¯ ) - A x ¯ ^{) T} x , ∀ x ∈ ^{R n} , and let [straight phi] ( x ) = f ( x ) - l ( x ) , x ∈ C ; then [figure omitted; refer to PDF]

So [straight phi] is a convex function over C . Moreover, ∇ [straight phi] ( x ¯ ) = ∇ f ( x ¯ ) - ∇ l ( x ¯ ) = 0 . Hence, [figure omitted; refer to PDF] That is, [figure omitted; refer to PDF]

To prove that x ¯ is a global minimizer of QLNP, we just need to show l ( x ) - l ( x ¯ ) ...5; 0 , ∀ x ∈ D . For any x ∈ D , we have [figure omitted; refer to PDF] since H ( x - x ¯ ) = 0 and [figure omitted; refer to PDF]

Hence, l ( x ) - l ( x ¯ ) ...5; λ g ( x ¯ ) - λ g ( x ) = - λ g ( x ) ...5; 0 , ∀ x ∈ D .

Remark 4.

Note that matrix A in Theorem 2 (the necessary condition) satisfies ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C , but matrix A in Theorem 3 (the sufficient condition) satisfies ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C .

We now present two examples to show that a global minimizer satisfies our necessary condition, while a local minimizer that is not global fails to satisfy the necessary condition.

Example 5.

Consider the following nonconvex minimization problem: [figure omitted; refer to PDF]

Eliminating _{x 1} using the equality constraint, the problem (EXP1) becomes [figure omitted; refer to PDF]

which has a local minimizer _{x 2} = - 1 and a global minimizer _{x 2} = 4 . Thus, (EXP1) has a local minimizer y ¯ = ( 3 , - 1 ) and a global minimizer x ¯ = ( - 2,4 ) .

Let B = ( 2 0 0 2 ) , b = ( 0 , - 2 ^{) T} , c = 12 , f ( x ) = ^{x 1 2} + 4 _{x 2} - 3 ^{x 2 2} - ^{x 2 4} , H = ( 1,1 ) , and d = 2 ; then ^{∇ 2} f ( x ) = ( 2 0 0 - 6 - 12 ^{x 2 2} ) . We take A = ( 2 0 0 - 6 ) ; then we have ^{∇ 2} f ( x ) - A = ( 0 0 0 - 12 ^{x 2 2} ) ... 0 , for each x ∈ ^{R 2} . A direct calculation shows that λ = 27.2 and μ = 112.8 solve λ ...5; 0 , λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 . And A + λ B = ( 56.4 0 0 48.4 ) [succeeds] 0 . Hence, the necessary condition holds at x ¯ .

Note that the necessary condition is not satisfied at the local minimizer y ¯ = ( 3 , - 1 ^{) T} . By solving directly the following equations: [figure omitted; refer to PDF]

we obtain that λ = 4 / 5 and μ = - 54 / 5 . Then A + λ B = ( 1 / 5 ) ( 18 0 0 - 22 ) , and, for any e = ( _{e 1} , _{e 2} ) ∈ ^{R 2} satisfying _{e 1} + _{e 2} = 0 , ^{e T} ( A + λ B ) e = - ( 4 / 5 ) ^{e 2 2} ; that is, if _{e 2} < 0 , then ^{e T} ( A + λ B ) e < 0 . So the necessary condition does not hold at the local minimizer y ¯ .

Example 6.

Consider another nonconvex minimization problem as follows: [figure omitted; refer to PDF]

For problem (EXP2), we let _{D 2} = { x ∈ ^{R 2} : 2 ^{x 1 2} + ^{x 2 2} - 2 _{x 2} - 3 ...4; 0 , _{x 1} + _{x 2} = 3 } , B = ( 4 0 0 2 ) , b = ( 0 , - 2 ^{) T} , c = - 3 , f ( x ) = ^{x 1 2} - 3 ^{x 2 2} - ^{x 2 4} , H = ( 1,1 ) , d = 3 , and x ¯ = ( 0,3 ^{) T} . Taking C = [ 0 , 4 / 3 ] × [ 5 / 3 , 3 ] ⊇ _{D 2} and A = ( 2 0 0 - 114 ) , then, for any x ∈ C , ^{∇ 2} f ( x ) - A = ( 0 0 0 108 - 12 ^{x 2 2} ) ... 0 . A direct calculation shows that λ = 63 / 2 and μ = 0 solve [figure omitted; refer to PDF]

Then A + λ B = ( 128 0 0 - 51 ) . So for any e = ( _{e 1} , _{e 2} ^{) T} satisfying H e = 0 , that is, _{e 1} + _{e 2} = 0 , we have ^{e T} ( A + λ B ) e = 128 ^{e 1 2} - 51 ^{e 2 2} = 77 ^{e 1 2} ...5; 0 . Hence the sufficient global optimality condition holds at x ¯ and x ¯ is a global minimizer of the problem ( EXP 2 ) . It is easy to verify that the necessary global optimality condition holds at x ¯ by taking ^{A [variant prime]} = ( 2 0 0 - 6 ) .

We now deduce from Theorems 2 and 3 the corresponding result of [11].

Corollary 7.

For the problem (QLNP), let f ( x ) = ( 1 / 2 ) ^{x T} Q x + ^{a T} x suppose that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 and H _{x 0} = d ; then a feasible point x ¯ is a global minimizer of QLNP if and only if there exist λ ...5; 0 and μ ∈ ^{R m} such that Q x ¯ + a + λ ( B x ¯ + b ) + ^{H T} μ = 0 , and ^{e T} ( Q + λ B ) e ...5; 0 whenever H e = 0 .

Proof.

Take A = Q ; then the conclusion follows from Theorems 2 and 3.

Corollary 8 (sufficient condition).

For the problem (QLNP), let f ( x ) be a twice continuously differentiable convex function on ^{R n} and x ¯ ∈ D . If there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 and ^{e T} B e ...5; 0 whenever H e = 0 , then x ¯ is a global minimizer of QLNP.

Proof.

Take A = 0 ; then ^{∇ 2} f ( x ) - A = ^{∇ 2} f ( x ) ... 0 , as f ( x ) is convex on ^{R n} . Hence the conclusion follows from Theorem 3.

Consider the following nonconvex minimization problem over a quadratic constraint: [figure omitted; refer to PDF]

Corollary 9 (necessary conditions [5]).

For the problem (QP), let x ¯ ∈ D and let C be a convex set containing D . Assume that there exists A ∈ ^{S n} such that ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C , and that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 . If x ¯ is a global minimizer of (QP), then there exists λ ...5; 0 , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) = 0 and A + λ B ... 0 .

Proof.

The conclusion easily follows from Theorem 2 by taking H = 0 and d = 0 .

Corollary 10 (sufficient conditions).

For the problem (QP), let x ¯ ∈ D and let C be a convex set containing D . Assume that there exists A ∈ ^{S n} such that ^{∇ 2} f ( x ) - A ... 0 , for each x ∈ C . If there exist λ ...5; 0 , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) = 0 and A + λ B ... 0 , then x ¯ is a global minimizer of (QP).

Proof.

The global optimality at x ¯ follows from Theorem 3, by taking H = 0 and d = 0 .

Corollary 11 (necessary conditions).

For problem (QLNP), let f ( x ) = ( 1 / 2 ) ^{x T} Q x + ^{x T} a - k ( x ) , where k ( x ) is a twice continuously differentiable convex function on ^{R n} . Assume that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 and H _{x 0} = b . If x ¯ is a global minimizer of QLNP, then there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , Q x ¯ + a - ∇ k ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 and ^{e T} ( Q + λ B ) e ...5; 0 , whenever H e = 0 .

Proof.

Take Q = A ; then ^{∇ 2} f ( x ) - A = Q - ^{∇ 2} k ( x ) - Q ... 0 , for each x ∈ ^{R n} . Hence, the conclusion follows immediately from Theorem 2.

3. Global Optimality Conditions for Smooth Nonconvex Minimization Problems

In this section we present global optimality conditions for smooth nonconvex minimization problems over quadratic and linear equality constraints. Now we show a way of finding a matrix A ∈ ^{S n} such that ^{∇ 2} f ( x ) - A ... 0 or ^{∇ 2} f ( x ) - A ... 0 , for each x in a convex set C containing the feasible set D .

Let the Hessian of f be denoted by ^{∇ 2} f ( x ) = ( _{f i j} ( x ) ) and let C be a convex and compact set containing D . We define [figure omitted; refer to PDF]

Theorem 12 (sufficient conditions).

For problem (QLNP), let x ¯ ∈ D and let _{A α} = diag ... ( _{α 1} , _{α 2} , ... , _{α n} ) . If there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 , and ^{e T} ( _{A α} + λ B ) e ...5; 0 , whenever H e = 0 , then x ¯ is a global minimizer of QLNP.

Proof.

By (22), we know that _{α i} ...4; _{f i i} - ^{∑ j ...0; i , j = 1 n} ... | _{f i j} ( x ) | , ∀ x ∈ C . So [figure omitted; refer to PDF] Hence, ^{∇ 2} f ( x ) - _{A α} is diagonally dominant for each x in C ; therefore ^{∇ 2} f ( x ) - _{A α} ... 0 , ∀ x ∈ C . Thus the conclusion follows from Theorem 3.

Theorem 13 (necessary conditions).

For problem (QLNP), let x ¯ ∈ D and let _{A β} = diag ... ( _{β 1} , _{β 2} , ... , _{β n} ) . Suppose that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 and H _{x 0} = b . If x ¯ is a global minimizer of QLNP, then there exist λ ...5; 0 and μ ∈ ^{R m} , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) + ^{H T} μ = 0 and ^{e T} ( _{A β} + λ B ) e ...5; 0 , whenever H e = 0 .

Proof.

It is easy to verify that _{A β} - ^{∇ 2} f ( x ) is diagonally dominant for each x in C ; therefore ^{∇ 2} f ( x ) - _{A β} ... 0 , ∀ x ∈ C . Hence the conclusion follows from Theorem 2.

Example 14.

Consider the following minimization problem: [figure omitted; refer to PDF]

For problem (EXP3), we let _{D 3} = { x ∈ ^{R 2} : 2 ^{x 1 2} + ^{x 2 2} - 2 _{x 2} - 3 ...4; 0 , _{x 1} + _{x 2} = 3 } , B = ( 4 0 0 2 ) , b = ( 0 , - 2 ^{) T} , c = - 3 , f ( x ) = ^{x 1 2} - ( 1 / 3 ) _{x 1} ^{x 2 3} - ^{x 2 4} , H = ( 1,1 ) , d = 3 , and x ¯ = ( 0,3 ^{) T} . Taking C = [ 0,2 ] × [ 1,3 ] ⊇ _{D 3} , ∇ f ( x ¯ ) = ( - 9 , - 108 ^{) T} , and ^{∇ 2} f ( x ) = ( 2 - ^{x 2 2} - ^{x 2 2} - 2 _{x 1 x 2} - 12 ^{x 2 2} ) , then _{α 1} = mi _{n x ∈ C} { 2 - | - 2 ^{x 2 2} | } = - 7 , _{α 2} = mi _{n x ∈ C} { - 2 _{x 1 x 2} - 12 ^{x 2 2} - | - 2 ^{x 2 2} | } = - 129 , and _{A α} = ( - 7 0 0 - 129 ) . A direct calculation shows that λ = 99 / 4 and μ = 9 solve [figure omitted; refer to PDF]

Then _{A α} + λ B = ( 92 0 0 - 155 / 2 ) . So, for any e = ( _{e 1} , _{e 2} ^{) T} satisfying H e = 0 , that is, _{e 1} + _{e 2} = 0 , we have ^{e T} ( _{A α} + λ B ) e = 92 ^{e 1 2} - ( 155 / 2 ) ^{e 2 2} = - ( 29 / 2 ) ^{e 1 2} ...5; 0 . Hence the sufficient global optimality condition holds at x ¯ and x ¯ is a global minimizer of the problem (EXP3).

For x ¯ , we have _{β 1} = ma _{x x ∈ C} { 2 + | - 2 ^{x 2 2} | } = 11 and _{β 2} = ma _{x x ∈ C} { - 2 _{x 1 x 2} - 12 ^{x 2 2} + | - 2 ^{x 2 2} | } = - 11 ; then _{A β} = ( 11 0 0 - 11 ) . Hence it is easy to verify that the necessary global optimality condition holds at x ¯ by taking λ = 99 / 4 and μ = 9 .

Now, we can deduce some global optimality conditions for problem (QP) from Theorems 12 and 13.

Corollary 15 (sufficient conditions).

For problem (QP), let x ¯ ∈ D and let A = diag ... ( _{α 1} , _{α 2} , ... , _{α n} ) . If there exists λ ...5; 0 , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) = 0 and A + λ B ... 0 , then x ¯ is a global minimizer of (QP).

Proof.

The conclusion easily follows from Theorem 12 by taking H = 0 and d = 0 .

Corollary 16 (necessary conditions [5]).

For the problem (QP), let x ¯ ∈ D and let A = diag ... ( _{β 1} , _{β 2} , ... , _{β n} ) . Suppose that there exists _{x 0} ∈ ^{R n} , such that g ( _{x 0} ) < 0 . If x ¯ is a global minimizer of (QP), then there exists λ ...5; 0 , such that λ g ( x ¯ ) = 0 , ∇ f ( x ¯ ) + λ ( B x ¯ + b ) = 0 and A + λ B ... 0 .

Proof.

The global optimality condition at x ¯ follows from Theorem 13 by taking H = 0 and d = 0 .

Acknowledgments

This research is partially supported by the Natural Science Foundation of Chongqing (cstc2013jcyjA00021) and Research Foundation of Chongqing Normal University (12XLB038).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] C. A. Floudas, V. Visweswaran, "Quadratic optimization," Handbook of Global Optimization , vol. 2, of Nonconvex Optim. Appl., pp. 217-269, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.

[2] P. Pardalos, H. Romeijn Handbook in Global Optimization , vol. 2, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.

[3] T. F. Coleman, J. Liu, W. Yuan, "A new trust-region algorithm for equality constrained optimization," Computational Optimization and Applications , vol. 21, no. 2, pp. 177-199, 2002.

[4] W. Sun, Y.-X. Yuan, "A conic trust-region method for nonlinearly constrained optimization," Annals of Operations Research , vol. 103, pp. 175-191, 2001.

[5] V. Jeyakumar, S. Srisatkunarajah, "Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma," Optimization Letters , vol. 3, no. 1, pp. 23-33, 2009.

[6] J.-M. Peng, Y.-X. Yuan, "Optimality conditions for the minimization of a quadratic with two quadratic constraints," SIAM Journal on Optimization , vol. 7, no. 3, pp. 579-594, 1997.

[7] V. Jeyakumar, A. M. Rubinov, Z. Y. Wu, "Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions," Mathematical Programming , vol. 110, no. 3, pp. 521-541, 2007.

[8] Y. Ye, S. Zhang, "New results on quadratic minimization," SIAM Journal on Optimization , vol. 14, no. 1, pp. 245-267, 2003.

[9] J.-B. Hiriart-Urruty, "Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints," Journal of Global Optimization , vol. 21, no. 4, pp. 445-455, 2001.

[10] J.-B. Hiriart-Urruty, "Conditions for global optimality. II," Journal of Global Optimization , vol. 13, no. 4, pp. 349-367, 1998.

[11] V. Jeyakumar, G. M. Lee, G. Y. Li, "Alternative theorems for quadratic inequality systems and global quadratic optimization," SIAM Journal on Optimization , vol. 20, no. 2, pp. 983-1001, 2009.