Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

Abstract

This paper extends and completes the discussion by Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).[PUBLICATION ABSTRACT]

J Glob Optim (2012) 54:275293

DOI 10.1007/s10898-010-9625-6

Joe-Mei Feng Gang-Xuan Lin Reuy-Lin Sheu

Yong Xia

Received: 10 August 2010 / Accepted: 26 October 2010 / Published online: 17 November 2010 Springer Science+Business Media, LLC. 2010

Abstract This paper extends and completes the discussion by Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarication technique developed in Xing et al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).

Keywords Non-convex quadratic programming Simultaneously diagonalizable via

congruence Slaters condition Duality Hidden convexity

1 Introduction

Let A and B be two n n real symmetric matrices, be a real number and f, g be two n 1

vectors. This paper concerns the (nonconvex) quadratic minimization problem (QP1QC)

P0 = min P(x) = 12 xT Ax f T x

s.t. 1

2 xT Bx gT x ,

J.-M. Feng G.-X. Lin R.-L. Sheu (B)

Department of Mathematics, National Cheng Kung University, Tainan, Taiwan e-mail: [email protected]

Y. Xia

LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing, Peoples Republic of China

Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

(1)

123

276 J Glob Optim (2012) 54:275293

which has a single non-homogeneous quadratic constraint. To make sense the problem, we assume that the problem (QP1QC) has a non-empty feasible domain, and that

(A1) there exists a 0 such that A + B 0,where the notation means positive definiteness. Although the assumption (A1) looks

restrictive, it can be shown that our results indeed cover more general cases when A and B are simultaneously diagonalizable via congruence (SDC in short). However, we can also prove that cases between (A1) and (SDC) are either unbounded below or transformed to an equivalent unconstrained problem. It is thus clear that the only relevant cases remained for study are those under (A1).

The problem (QP1QC) arises from many optimization algorithms, in particular, the trust region methods. See, e.g., [2,3,7,9,15,17,18,20,21]. Most cases dealed with B 0 and

g = 0. Extensions to an indefinite B but still with g = 0 are considered in [1,6,14,16,19,22].

Recently, a general non-convex function f (x) rather than a non-convex quadratic function P(x) over a single quadratic constraint was discussed by Jeyakumar et al. [13]. Stern and Wolkowicz [19] rst studied the two-sided nonconvex quadratically constrained problem

min (y) = yT By 2T y

s.t. yT Cy , y

Rn (2)

and gave the necessary and sufcient optimality conditions with no duality gap under various assumptions. Ben-Tal and Teboulle [1] further explained the surprising result by proving that, under the assumption (A1), the problem (2) is indeed equivalent to a convex minimization problem with linear constraints. Xing et al. [22] relaxed the assumption (A1) to

(A2) the domain J = { 0|A + B 0} has a non-empty interior; and

(A3) the vectors f, g R(A + B) for some int(J ),where R(A + B) denotes the column space of A + B and int(J ) means the interior of J .

(Remark: g = 0 in [22]). By applying the canonical duality of Gao [8], they formulate and

solve the dual problem of (QP1QC) (with g = 0) analytically. With a proper selection of the

dual optimal solution when there are multiple ones, they used a technique called boundarication to construct a primal global optimal solution with no duality gap. Xing et al. [22] also showed that problem (2) can be solved by doing (QP1QC) (with g = 0) at most twice.

As a result, it is sufcient to consider only (QP1QC).

In spite that all theoretical results were related to the quadratic form, direct applications of (QP1QC) having a nonhomogeneous quadratic constraint can be found in solving an inverse problem via regularization [5,10] and in minimizing the double well potential function [4]. Our purpose in this paper is to provide a complete mathematical treatment for (QP1QC) from the dual side. Following Xings derivation in [22], it is not difcult to formulate the canonical dual problem (D-QP1QC) (with the appearance of g) as follows.

Pd0 = sup Pd() = 12( f + g)T (A + B)1( f + g)

s.t. F = { 0|A + B 0}.

The Lagrange dual and the canonical dual of (QP1QC) are indeed equivalent in this case. We do not intend to distinguish them in the presentation.

In the next section, we shall discuss and compare various assumptions necessarily for solving (QP1QC), including (A1), (A2)+(A3), Slater conditions, and the (SDC) condition. We will show that the (SDC) condition is the broadest in the sense that it contains all three other assumptions. In fact, the (SDC) condition for more than two quadratic forms is the twelfth open question among 14 such ones in nonlinear analysis and optimization raised by

(3)

123

J Glob Optim (2012) 54:275293 277

J.-B. Hiriart-Urruty [11]. In the third section, we extend the analysis in Xing et al. [22] to provide a dual approach for solutions of (QP1QC), while focusing on new cases exclusively for g = 0. In the fourth section, a deeper view for the boundarication technique will be

also presented. In the fth section, we extend the idea in Ben-Tal and Teboulle [1] to derive the dual of the dual for (QP1QC). It is shown that the double dual of (QP1QC) is a linearly constrained convex minimization problem, which is equivalent to (QP1QC) itself under a one-one nonlinear transformation. Finally, we illustrate with some numerical examples.

2 Relaxed assumptions

In a constrained optimization problem, Slater condition requires a strictly feasible solution. The assumption (A1) can be viewed as the dual Slater condition. For the primal problem (1), the primal Slater condition requires an x0 such that 12 xT0 Bx0 gT x0 < . Ben-Tal

and Teboulle [1] and Xing et al. [22] needed the dual Slater condition (A1) whereas Ye and Zhangs exact semi-definite programming approach [23] did both. Although (A2)+(A3) is weaker than (A1), they can be reduced to (A1) after space reduction. See [22] for details.

Notice that the Lagrange function

L(x, ) =

1

2 xT (A + B)x ( f + g)T x (4)

is unbounded below when A + B is not positive semi-definite. If J = { 0|A + B

0} = , the dual problem becomes identically negative innite and thus useless. Assump

tions like (A1) or (A2) are important since they guarantee that a sensible dual information is indeed there. Although J = implies no dual information, we show that those cases

satisfying either

(A4) F = {(, )

R2

| A + B 0} = , or more generally

(A5) (SDC) A and B are simultaneously diagonalizable via congruence

while J = can be reduced to some trivial quadratic problems.

Recall that the matrices A and B are said to be simultaneously diagonalizable via congruence if there exists a nonsingular matrix C with

CT AC = A := diag(1, , n), j

R, j [1 : n];

CT BC = B := diag(1, , n), j

R, j [1 : n].

It is different from being simultaneously diagonalizable via similarity in the usual sense. It is known that (A4)(A5), e.g. in [12]. Using the transformation x = Cy, = CT f , and

= CT g, the primal problem (1) can be written as a linear combination of separated squares

as follows:

P 0 = min P (y) =

n

i=1

1

2 i y2i i yi

s.t. S (y) =

n

i=1

1

2 i y2i i yi 0.

(5)

Similarly, the dual problem (3) becomes

Pd 0 = sup0 Pd () = 12

n

i=1

(i +i )2

i +i s.t. i + i > 0,

(6)

123

278 J Glob Optim (2012) 54:275293

and the condition (A4) becomes {(, )

| A + B 0} = .

We rst call the two matrices A and B to be of type I if there is some i [1 : n] for which

i 0 and i 0; and are of type II otherwise. When the two matrices A and B are of type

I, we may assume that it occurs to i = 1. Moreover, if (A4) is satised, 1 and 1 can not be

0 simultaneously. Therefore, when 1 = 0, 1 must be less than 0. When 1 < 0, 1 can be

non-positive. We now study cases of type I, satisfying (A4) while violating (A1).

(a) Suppose that 1 = 0, 1 < 0. Since 1 < 0, we observe that any y Rn will eventually

become feasible if the rst component y1 is increased to innity or decreased to negative innity while all others y2, y3, . . . , yn being xed. As a result, if 1 = 0 in the objective

function, we can pass y1 (of any selected y) to + for 1 > 0, or to for 1 < 0,

both of which imply that the Problem (5) is unbounded below. If 1 = 0, the objective

function lacks the y1 term and the constraint becomes redundant. The problem (5) is reduced to the unconstrained quadratic programming problem min n

i=2

1

2 i y2i i yi.

(b) Suppose that 1 < 0, 1 0. For any feasible solution y, replace y1 by y1 = sign(1)t

if 1 = 0, and by y1 = t otherwise. As t +, the constraint remains satised while

the objective value approaches to . The problem (5) is unbounded.

Next we assume that the two matrices A and B are of type II. That is, for all i [1 : n],

either i > 0 or i > 0. Then we can partition the index set [1 : n] = I1 I2 I3 where

I1 = {i : i > 0}, I2 = {i : i > 0, i < 0}, and I3 = {i : i > 0, i = 0}. We claim

that, if (A1) is violated, I1 = , I2 = and there exist two indices i I1, j I2 such that

i < 0, i > 0 and j > 0, j < 0.Suppose I1 = . Since i > 0, i [1 : n], the assumption (A1) is satised by setting

= 0, which is a contradiction and we conclude that I1 = . Suppose I2 = . We can

choose sufciently large to make a contradiction that (A1) is satised. Therefore, I2 = .

Secondly, we must have maxiI1 ii miniI2 ii . If this is not true, we can choose > 0, > 0 such that

max

iI1

i > 0 for all i [1 : n]. It

1

1 , miniI2 ii =

and 11 22 > 0. It follows that 1 < 0, 1 > 0, 2 > 0, 2 < 0, and there are two

possibilities:

(c) Suppose maxiI1 ii = miniI2 ii , i.e., 11 = 22 . Since

{(, ) | 1 + 1 > 0, 2 + 2 > 0} =

(, ) |

Assumption (A4) is violated.(d) Suppose maxiI1 ii > miniI2 ii , i.e., 11 > 22 . For any xed t (12 , 12 ),

we have 1 + 2t < 0 and 1 + 2t < 0. Consider y = (y1, y2, 0, 0, . . . , 0)t where y2

satises y22 = ty21. Then, y is feasible to (5) for all large enough |y1|, which decreases

the objective values indefinitely. In other words, the problem (5) is unbounded below.

R2

i

i <

< min iI2

i

i .

That is,

is again a contradiction.

In general, we may assume 1 I1, 2 I2, maxiI1 ii =

i + i > 0 for all i I1 I2. It follows that i +

2

2 ,

1

1 + > 0,

2

2 > 0

= ,

123

J Glob Optim (2012) 54:275293 279

Bearing the above discussion in mind, for cases that violate (A4), there is only one case in type I, that is i = i = 0 for some i [1 : n]; and only one case in type II, which is case

(c). We begin with type I by assuming that 1 = 1 = 0.(e) Suppose that 1 = 0, 1 = 0, 1 = 0, 11 0. For any feasible solution y, let

1y1 +. The problem (5) is unbounded below.

(f) Suppose that 1 = 0, 1 = 0, 11 < 0. Rewrite the constraint as 1y1

( n

i=2

1

2 i y2i i yi) . If 1 > 0, we substitute

y1

1 1

n

i=2

1 2i y2i i yi

1

into the objective and obtain

1y1 +

n

i=2

1 2i y2i i yi

1 1

n

i=2

1 2i y2i i yi

+

1

1

(7)

The problem (5) is equivalently reduced to the unconstrained quadratic programming problem: min n

i=2(12i y2i i yi) 11 ( ni=2(12i y2i i yi) ). For 1 < 0, the

same inequality (7) can be also established and the problem (5) is equivalently reduced

to the above unconstrained quadratic programming problem.(g) Suppose that 1 = 0, 1 = 0, 1 = 0, 1 = 0. Since limy1+ |1y1| = and

the objective function has no y1 term, the problem (5) is equivalent to the unconstrained quadratic programming problem: min n

i=2(12i y2i i yi).

(h) Suppose that 1 = 0, 1 = 0, 1 = 0, 1 = 0. The variable y1 can be directly removed

from the problem (5).

Next, we discuss the case left in type II, case (c). In this case, 1 < 0, 1 > 0, 2 >

0, 2 < 0 and 11 = 22 . We can further assume 1 = 0 and 2 = 0, by introducing the

linear transformations y1 = y1 11 and y2 = y2 22 if necessary. As a result,

1

21y21

+

n

i=2

1 2i y2i i yi

1

22y22 +

n

i=3

1 2i y2i i yi

.

(i) Suppose 1 = 0 and 2 = 0. We have 121y21 +

1

22y22 =

1

1

1

21y21

1

22y22

(8)

The problem (5) is reduced to an unconstrained quadratic programming problem: min n

i=3(12(i 11 i)y2i (i 11 i)yi) + 11 .

(j) Suppose 1 = 0 or 2 = 0. Let us assume 1 = 0. Set y1 = sign(1)t and if 2 = 0, y2 =

sign(2) 1

2 t2 + 22, otherwise y2 =

1

1

+

n

i=3

1 2i y2i i yi

1

2 t2 + 22. Notice that ( y1, y2, 0, . . . , 0)

is feasible for any large enough t. Furthermore, the corresponding objective function value is 121 y21 + 122 y22 1 y1 2 y2 =

2

2 1 y1 2 y2 =

2

2 |1|t

|2|

1

2 t2 + 22 as t +. That is, the problem (5) is unbounded below.

123

280 J Glob Optim (2012) 54:275293

Therefore, we only have to discuss problem (QP1QC) under the assumption (A1), while in principle we know how to deal with it under the (SDC) condition. Cases between (A1) and (SDC) are either unbounded below or reduced to an unconstrained problem.

In addition, we comment that the condition (A2)+(A3) in in Xing et al. [22] is also a

special case of (SDC). They have shown in [22] that, under (A2)+(A3), there exists an

orthogonal matrix W such that

W T AW =

0 0 0 A1

, W T BW =

0 0 0 B1

, W T (A + B)W =

0 00 A1 + B1

,

and A1+ B1 0. Since (A1) (A5), there is a nonsingular matrix U such that UT A1U =

diag(11, . . . , 1m) and UT B1U = diag(11, . . . , 1m). Therefore, A and B can be simultaneously diagonalizable via congruence with a nonsingular matrix C = W

I 0 0 U

such that

both CT AC and CT BC are diagonal matrices, which is (A5).

Finally, we remark that the primal Slater condition is redundant under the assumption (A1). The gap between these two assumptions is the case when B 0, g R(B), =

12 gT B+g, where B+ is the Moore-Penrose generalized inverse of B. This special case can

be treated by (case 7) discussed in the next section.

Proposition 1 Let F0 := {(B, g, ) : x,

1

2 xT Bx gT x } and F1 := {(B, g, ) :

x, 12 xT Bx gT x < }. Then it holds that

F0\F1 =

(B, g, ) : B 0, g R(B), =

1

2 gT B+g

.

Proof According to the definitions of F0 and F1, (B, g, ) F0\F1 if and only if =

minx{12 xT Bx gT x} > , which is equivalent to B 0 and the linear system Bx = g

has a solution. In this case, = 12 gT B+g.

3 Solutions to (QP1QC) via dual approach

In the general theoretical view of nonlinear programming, the problem (QP1QC) can be written as min{P(x)| S(x) 0} where P(x) = 12 xT Ax f T x and S(x) = 12 xT Bx gT x .

For the single inequality constrained problem, let 0 be the Lagrange multiplier. Then,

the dual problem is formulated as follows:

sup

D

(Pd() = inf

x

Rn

{P(x) + S(x)})

where a natural dual feasible domain D = { 0|Pd() > } { 0| A + B

0} = J . For any D, suppose x() is a global minimizer of the quadratic convex function

P(x) + S(x), we have Pd() = P(x()) + S(x()). Equivalently,

P(x()) Pd() = S(x()). (9)

123

J Glob Optim (2012) 54:275293 281

Moreover, if Pd() and x() are smooth with respect to , the rst derivative of Pd() can be computed using the implicit differentiation and the chain rule to get

dd Pd() = P(x())

dd x() + S(x()) + S(x())

dd x()

dd x() + S(x()) (10)

= S(x())where P(x()) + S(x()) = 0 since x() minimizes P(x) + S(x). Likely, we can

compute the second derivative of Pd() as

d2d2 Pd() =

dd S(x())

T

(2 P(x) + 2S(x))1

= [ P(x()) + S(x())]

dd S(x())

(11)

provided the Lagrangian Hessian 2 P(x) + 2S(x) is invertible.

Equations (9, 10, 11) are general results for any single constrained smooth nonlinear programming problem. They provide structural insight to many direct computation in Xing et al. [22]. When P(x) and S(x) are quadratic and F = { 0|A + B 0},x() = (A + B)1( f + g) (12)

is the unique minimum solution to P(x) + S(x). We thus have Lemma 1 For any int(F),d Pd()

d = S(x())

1

2( f + g)T (A + B)1B(A + B)1( f + g) (13)

= gT (A + B)1( f + g) ,

and

d2 Pd()

d2 = uT (A + B)1u 0 (14)

where u = Bx() g = B(A + B)1( f + g) g. Moreover,

P(x()) Pd() =

d Pd()d . (15)

Observe from Lemma 1 that Pd() is a smooth concave function over int(F). Addition

ally, it has been shown in [22] that F is an interval. Let 0, 1 respectively be the left and

right boundary of F. According to the various places where the supremum of Pd() could

possibly attain over F, we can classify into the following cases. (case 1) Pd0 is attained at int(F). In this case, it is necessary that d P

d () d

= S(x())

= 0. By (15), P(x()) = Pd() so that(x(), ) is the primal-dual optimal pair.

(case 2) Pd0 is attained at the left boundary 0 of F and lim+

0

d Pd() d

= 0. In this case,

the limit

x(0) = lim+

0 (A + B)1( f + g) (16)

exists. By

123

282 J Glob Optim (2012) 54:275293

lim

+0

d Pd()d = lim

+0

S(x()) = S(x(0)) = 0,

x(0) is the primal boundary optimal solution. (case 3) Pd0 is attained at 0, 0 = 0 and lim+

d Pd()d < 0. In this case, let x(0) be

dened as in (16). Since S(x(0)) < 0 and 0 d P

0 d (0) d

= 0 in (15), x(0) is an interior

optimal solution. (case 4) Pd0 is attained at 0, 0 > 0 and lim+

d Pd()d < 0. Then, A + 0B 0 has at

least one zero eigenvalue so that Pd(0) = infxR

0 {P(x)+0S(x)} has multiple minimum

solutions. That is, the optimal set arg inf{P(x)+0S(x)} is not a singleton. Since the point

x(0) in (16) satises (A + 0B)x(0) = f + 0g, it belongs to the set arg inf{P(x) +

0S(x)} but has a positive duality gap: P(x(0)) Pd(0) = 0 d P

n

d (0)d > 0. The boundarication technique developed in [22] chooses from the set arg inf{P(x) + 0S(x)}

another more appropriate point than x(0) to close the gap. (case 5) Pd0 is attained at the right boundary 1 of F, 1 < and lim

1

dPd() d

= 0.

This case is analogous to (case 2). The limit x(1) = lim

1 (A + B)1( f + g) is a

boundary optimal solution. (case 6) Pd0 is attained at 1, 1 < and lim

1

dPd()d > 0. This case is similar to

(case 4) and requires a boundarication step to move x(1) from the exterior S(x(1)) > 0 to a boundary optimal solution. (case 7) Pd() approaches asymptotically to a nite value as +. This case can

happen only when B 0 and a specic is associated.

In the following, we write the above seven cases into a few theorems with proofs which extend from the previous work of Xing et al. [22]. We shall try to reduce the duplicate to a minimum, while keeping it self-contained.

Under (A1), there exists a 0 such that A+ B 0. The entire analysis relies heavily

on the simultaneous decomposition that converts A + B 0 to an identical matrix I and B

to a diagonal matrix H. First decompose A + B = L DLT with a lower triangular matrix

L and a diagonal matrix D having only positive diagonal entries. Let G1 = (L D

1

2 )1 so that

G1(A + B)GT1 = I. Since G1BGT1 is real and symmetric, there is an orthogonal matrix

G2 such that G2(G1BGT1 )G12 = H = diag(h1, h2, . . . , hn). Respectively, we have

G1(A + B)GT1 = I, G2G1(B)GT1 GT2 = H.

Lemma 2 (For cases 26) Suppose the dual optimal occurs at = 0 or at 1 < . Then

the corresponding (right/left) limit

x = lim

(A + B)1( f + g) (17)

exists. Moreover, x minimizes the Lagrange function P(x) + S(x). Proof Let G = G2G1. Then, for any F,

G(A + B)GT = G(A + B + B B)GT

= G(A + B)GT + ( )G BGT

= I + ( )H

= diag(d1(), d2(), . . . , dn()) (18)

123

J Glob Optim (2012) 54:275293 283

where di() = 1 + ( )hi > 0, i [1 : n]. In addition, we also have

Pd() =

11 + ( )hi

is monotone with a lower bound 0. As , d1i() might tend monotonically to a nite

positive number or to +. In the latter case if lim d1i() tends to + for some compo

nent i, the corresponding (G( f +g))i must be 0 or otherwise Pd0 could have been unbounded

below, which is impossible under (A1). In other words, lim d1i()(G( f + g))i will

be either 0 or a nite limit for all i [1 : n], so the limit

x = lim GT diag(d11(), d12(), . . . , d1n())G( f + g)= lim (A + B)1( f + g).

exists. Moreover, since A + B 0, the Lagrange function P(x) + S(x) is convex. By

(A + B) x = ( lim

(A + B))( lim

1

2( f + g)T GT diag(d11(), d12(), . . . , d1n())G( f + g) .

Note that, as a function of F,

d1i() =

> 0

(A + B)1( f + g)) = f + g, (19)

it is seen that x minimizes P(x) + S(x).

Theorem 1 (Boundarication Technique for cases (4) and (6)) For any x = 0 in the null

space of A + B, there exists at least one real number 0 satisfying

2 xT B x + 2( xT B x gT x) + xT B x 2gT x 2 = 0

such that x = x + 0 x is a required boundary global optimal solution for (1) with the

global minimum value 12(x)T Ax f T x.

Proof Let = 0. The case when = 1 can be done similarly. Since A+B is positive

semi-definite but not positive definite, there exists some x = 0 such that (A + B) x = 0.

However, xT (A + B) x > 0 as (A + B) 0 for F. Then,

xT (A + B) x xT (A + 0B) x = ( ) xT B x > 0 (20)

implies that xT B x > 0.

Now we consider the following quadratic function of one variable :

2 xT B x + 2( xT B x gT x) + xT B x 2gT x 2 = 0. (21)

Since xT B x > 0 and xT B x 2gT x 2 < 0, we nd

= (2 xT B x 2gT x)2 4( xT B x)( xT B x 2gT x 2) > 0

so that a real number 0 satisfying (21) exists, and

123

284 J Glob Optim (2012) 54:275293

S(x) =

1

2(x)T Bx gT x

=

1

2( x + 0 x)T B( x + 0 x) gT ( x + 0 x)

=

1

2[20 xT B x + 20( xT B x gT x) + xT B x 2gT x 2]

= 0.

Since (A + B)x = (A + B)( x + 0 x) = ( f + g), the point x also minimizes

P(x) + S(x). By (9), P(x) Pd0 = S(x) = 0 and proves the optimality of x. Recall that B 0 if and only if 1 = +. For convenience, let the rst r diagonal

elements of H = G BGT are 0 and the remaining n r positive. When r = 0, B is positive

definite. We denote G f = w = (

wT , wT )T ; Gg = s = ( sT , sT )T where

w means the

rst r components of w whereas w the last n r. Similarly for s, and H 0 represents

diag(hr+1, hr+2, . . . , hn).

Theorem 2 (Case 7) If Pd0 is achieved when tends to +, then = hi >0

s2i2hi and

si = 0 for hi = 0. Otherwise, Pd0 is unbounded above and problem (1) is infeasible. In case

B 0, the limit

x = lim+(A + B)1( f + g) = B1g

exists and x is a boundary optimal solution for problem (1). In case B 0,

x = GT ( wT , (H1s)T )T

is the boundary optimal solution for problem (1).

Proof Expand Pd() into a rational polynomial of terms 2, , 0, 1 as follows:

Pd() =

1

2( f + g)T (A + B)1( f + g)

=

1

2(G( f + g))T (I + ( )H)1(G( f + g))

=

1

2

n

i=1

(wi + si)21 + ( )hi

=

1

2

hi =0

(wi + si)2

1

2

hi >0

(wi + si)21 + ( )hi

=

1

22

hi =0

s2i

hi =0

wisi

1

2

hi =0

w2i

1

22

hi >0

s2i

1 + ( )hi

hi >0

wisi

1 + ( )hi

1

2

hi >0

w2i

1 + ( )hi

=

1

22

hi =0

s2i

hi =0

wisi

1

2

hi =0

w2i

123

J Glob Optim (2012) 54:275293 285

s2i

hi

1

2

hi >0

s2i(1 hi)h2i +

s2i(1 hi)2 h2i(1 + ( )hi)

wisi

hi

wisi(1 hi) hi(1 + ( )hi)

1

2

hi >0

w2i

1 + ( )hi

s2i

hi +

=

1

22

hi =0

s2i

hi =0

wisi +

1

2

hi >0

1

2

hi =0

w2i

1

2

hi >0

s2i(1 hi)h2i +

hi >0

wisi

hi

s2i(1 hi)2

2h2i

wisi(1 hi)hi +

1

2w2i

1

1 + ( )hi

.

By the fact that Pd0 = lim+ Pd() < , it is necessary that si = 0 if hi = 0 and =

hi >0

s2i2hi , or Pd0 is unbounded above, causing an infeasible primal problem.

When B 0, hi > 0 for all i [1 : n]. Then,

lim

+

d1i()(G( f + g))i = lim

+

wi + si1 + ( )hi =

si hi

and

x = lim+(A + B)1( f + g)

= lim

+

GT (I + ( )H)1G( f + g)

= GT lim

+

(I + ( )H)1G( f + g)

= GT H1Gg

= B1g.

Consequently,

P( x) Pd0 = lim

+

(P(x()) Pd())

= lim

+

S(x())

0,

= S(x()) 0 on int(F). This forces P( x) = Pd0 and S( x) = 0 so

that x is a boundary optimal solution of (1).

In the case that B 0, we have G AGT = I H = diag(1, 1, . . . , 1, 1 hr+1, 1

hr+2, . . . , 1 hn). Let x = GT t, and by the fact that si = 0 if hi = 0, problem (1)

becomes

P0 = min P(t) =

1

2 tT

since, in case 7, d P

d () d

I 00 I H

t (

wT , wT )t

(22)

s.t. 12tT

0 0

0 H

t (0r, sT )t ,

123

286 J Glob Optim (2012) 54:275293

which can be divided into two separated subproblems, an unconstrained ( P) and a smaller

(P) with t = ( tT , tT )T :

( P) :

P0 = min P( t) =

1

2 tT t

wT t

and

(P) : P0 = min P(t) =

1

2 tT (I H)t wT t

s.t. 12tT Ht sT t .

(23)

The unconstrained convex subproblem ( P) attains the minimum at a t for which d Pd t( t) = 0.

Hence t =

w and

P0 = 12

wT

w. As for (P), the minimum occurs at t = H1s due to H 0. Combining both t and t together, x = GT (

wT , (H1s)T )T is the boundary optimal solution for problem (1).

4 Insights into boundarication

To look into the boundarication technique for more insights, we work on the (SDC) form (P ) in (5) and (Pd ) in (6) by thinking of A as diag(1, . . . , n); B as diag(1, . . . , n);

f as = (1, 2, . . . , n)T ; and g as = (1, 2, . . . , n)T . In (case 4), Pd0 occurs at the

left boundary 0 > 0 so that the index set

I0 := {i|i + 0i = 0} = . (24)

We assume that I0 = [1 : r], r 1. Hence, i + 0i > 0, i [r + 1 : n].

Lemma 3 (Case 4) For all i I0, i > 0 and i < 0. Moreover,0 =

i

i =

ii . (25)

Proof From (24), if i I0 and i = 0, i = 0. However, from assumption (A1), i = 0

implies i > 0. The contradiction shows that i = 0. On the other hand, suppose i < 0.

To make i + i > 0 for i < 0, we need < 0, which contradicts to the fact that 0 is

a left boundary of F. Therefore, i > 0, i I0 in Case 4. By 0 > 0, we immediately have

i < 0.

From Lemma 2, it is shown that

y = lim

+0

(A + B)1( f + g) = lim

+0

ii and thus

ii =

i + i i + i

exists. Since i + 0i = 0 for i I0, it is necessary that i + 0i = 0, i I0 and

yi =

i + 0i i + 0i

, if i I0, ii , if i I0,

(26)

which proves (25). From the condition of case (4),

lim

+0

d Pd()d = S ( y) =

n

i=1

i

2 y2i i yi

< 0

123

J Glob Optim (2012) 54:275293 287

and there is a duality gap P ( y) Pd 0 = 0S ( y) > 0. Since i > 0 for i I0, we

observe that limt i2 t2 it = +. To improve S ( y) to 0, it is sufcient to increase

(or decrease) any (or all) yi for i I0, while keeping all other yi xed if i I0. This amounts

to moving y in the null space of A + 0 B as for any yin the null space of A + 0B, it must

have

yi = 0, if i I0.

This explains why in Eq. (21) there is a real root 0.

From Theorem 1, we also see that the moving direction in the null space of A + 0 B is

indifferent to global optimality. It has to do with the specialty of case 4 as revealed in Lemma 3. For simplicity, let r = 2 and consider the problem:

min 1

2 y21 1y1

+

2

2 y22 2y2

+

n

i=3

1

2i y2i i yi

s.t. 1

2 y21 1y1

+

2

2 y22 2y2

+

n

i=3

1

2i y2i i yi 0. (27)

By (25), we can assume

11 =

11 = c1 and

22 =

22 = c2

so that (27) becomes

min P (y) = 1

y21

2 c1y1

+ 2

y22

2 c2y2

+

n

i=3

1

2i y2i i yi

s.t. S (y) = 1

y21

2 c1y1

+ 2

y22

2 c2y2

+

n

i=3

1

2i y2i i yi 0. (28)

Since 1( y

2 1

2 c1y1) + 2( y

2 2

2 c2y2) 1c

2 1

2

2c

2 2

2 , we have

1c21

2 +

2c22

2 + . (29)

let = {(y3, y4, . . . , yn)| ni=3

n

i=3

1

2i y2i i yi

1

2 i y2i i yi 1c

2 1

2

+ 2c

2 2

2 + }. Rewrite (28) as

min

(y1,y2) 1

y21

2 c1y1

+ 2

y22

2 c2y2

+

n

i=3

1

2 i y2i i yi

min

(y3,y4,...,yn)

s.t. 1

y21

2 c1y1

+ 2

y22

2 c2y2

.

(30)

n

i=3

1

2 i y2i + i yi

As 11 = 22 = 0 by Lemma 3, the inner minimization in (30) becomes

min

(y1,y2) 01

y21

2 c1y1

02

y22

2 c2y2

+

n

i=3

1

2i y2i i yi

s.t. 1

y21

2 c1y1

+ 2(

y22

2 c2y2)

n

i=3

1

2i y2i + i yi, (31)

123

288 J Glob Optim (2012) 54:275293

which can be easily solved as

n

i=3

1

2(i + 0i)y2i (i + 0i)yi 0 (32)

so that (30) becomes

min

(y3,y4,...,yn)

1

2(i + 0i)y2i (i + 0i)yi 0. (33)

Since i + 0i > 0 for i I0, problem (33) has a convex objective function of which

the only critical point is yi = i+0ii+0i , i [3 : n] as dened in (26). Since y is an interior

feasible solution in (case 4), ( y3, y4, . . . , yn) is also an interior point in and thus the unique

minimizer of (33).

We have just seen that any global minimizer of problem (28) must have its ith component equal to yi for i [3 : n]. The remaining is to determine the optimal y1 and y2 from (31)

by substituting yi with yi for i [3; n]. Then problem (31) has an ellipsoid constraint in

variables (y1, y2). The optimal (y1, y2) happens if and only if it is on the boundary of the ellipsoid. The solution

y1 = lim

+0

1 + 11 + 1 =

n

i=3

22 = c2

is the center of the ellipsoid. The boundarication technique moves it to the boundary and solves case 4.

5 Dual of the dual problem

In this section, we show that the dual of the dual problem reveals the hidden convex nature of

the primal problem (1). Notice that if i = 0, (i + i)2 =

i iii + ii (i + i)

2

.

11 = c1 and y2 = lim

+0

2 + 22 + 2 =

Dene indices sets

J0 = {i [1 : n] : i = 0}, J1 =

i [1 : n] : i = 0, i

ii

i = 0

,

ii

i = 0

J2 =

i [1 : n] : i = 0, i

with which we can write the above dual problem (6) as

Pd 0 = sup

0

iJ2 (i iii )ii 12

iJ2

(i i ii )2 i +i

12

iJ1J2

2i2i (i + i) 12

iJ0

(i +i )2

i

(34)

s.t. i + i > 0, i J1 J2.

123

J Glob Optim (2012) 54:275293 289

Proposition 2 A Lagrangian dual of Problem (34) is the following linearly constrained convex minimization problem

Pdd =

iJ2

i

ii

i

i i

iwi +

iw2i

2

+

inf

z,w

iJ1J2

i zi

iJ2

|i

ii

i |

2zi +

2i

2i +

iJ0

s.t.

iJ0

iwi , zi +

2i

22i

0, i J1 J2; wi

R, i J0

iJ1J2

i zi +

.

(35)

Proof The dual problem (34) can be equivalently written as

sup

0

iJ2

(i

ii

i )

ii

1

2

iJ2

(i iii )2 ti

1

2

iJ1J2

2i

2i

ti

1

2

iJ0

t2i

i

s.t. i + i = ti, i J2,

i + i = ti, i J1,

i + i = ti, i J0,

ti > 0, i J1 J2. (36)

Let zi

R, i J2; zi

R, i J1 and wi

R, i J0 be the dual multipliers associated with

the rst, second and third linear equality constraints in (36), respectively. The dual problem of Problem (34) becomes

iJ2

i

ii

i

i

i + inf

z,w

iJ1J2

i zi +

iJ0

iwi + v(z) + v(w)

iJ1J2

+ sup

ti >0, iJ1

2i

22i

ti ziti

+ sup

0

i zi +

iJ0

iwi

(37)

where

2

v(z) :=

iJ2

sup

ti >0

ti zi

2i

22i

ti

i iii

,

2ti

iw2i

v(w) :=

sup

t2i

2i witi

=

iJ0

2 . (38)

The computation of the rst inner maximization in (37) with respect to ti > 0, i J1, leads to the optimal value zero with the linear constraint zi +

2 i

22i 0 and that of the second inner

123

290 J Glob Optim (2012) 54:275293

maximization in (37) with respect to 0 leads to the optimal value zero with the linear

constraint iJ1J2 i zi + iJ0 iwi . Finally, for i J2 in (38)

sup

ti >0

ti zi

2i

22i

ti

(i iii )2 2ti

|i iii |

#2zi +

2 i

2i , if zi +

2i22i 0,

= +, if zi +

2i22i < 0.

(39)

Substituting the above computations into (37), we get (35).

Theorem 3 Under the assumption (A1), the primal problem (5) is equivalent to the convex programming problem (35).

Proof First we can rewrite the primal problem (5) as follows

P 0 = min

iJ1J2

i

1 2

yi

i i

2i

22i

i

ii

i

2

yi

+

1 2i y2i i yi

s.t.

1 2

yi

i i

2

2i

22i

iJ0

i yi .

Under the assumption (A1), according to the 7 cases discussed in Sect. 3, the global minimizer of the primal problem (5) exists, denoted by y. Let i0 J2 be arbitrary. Construct y

according to:

yi =

iJ1J2

i

2ii yi, if i = i0 J2, yi, if i = i0.

Then y is feasible to (5). Since ni=1

2 yi2 i yi and i0 J2

is arbitrary, we must have (i iii )(yi ii ) 0 for all i J2. In addition, by the

definition of J1, the objective function is homogeneous in terms of (yi ii ) for i J1. That

is, we can also restrict (yi ii ) to be nonnegative for i J1. Therefore, the problem (5) is

further equivalent to

P 0 = min

iJ1J2

i

2 (yi)2 i yi ni=1

i

i

1

2

yi

i i

2i

22i

i

ii

i

2

yi

+

1 2i y2i i yi

s.t.

1

2

yi

i i

2

2i

22i

iJ0

i yi ,

iJ1J2

i

ii

i > 0,

yi

ii 0, i J2 and i

ii

i < 0,

yi

ii 0, i J2 and i

ii 0, i J1.

Introducing zi = 12(yi ii )2 i

2

yi

2i 2 for i J1 J2 (which is now a one-to-one map between

zi and yi) and wi = yi for i J0, we exactly obtain the dual of the dual problem (35).

123

J Glob Optim (2012) 54:275293 291

That is, problem (5) is equivalent to (35) via the following nonlinear transformation

yi =

ii +

|i

ii

i |

i

ii

i

2zi +

2i

2i

, if i J2,

, if i J1,

wi, if i J0.

(40)

ii +

2zi +

2i

2i

Theorem 3 explains why the nonconvex problem (QP1QC) has a strong duality with no duality gap under condition (A1).

6 Examples

A few examples are selected to demonstrate the validity of the dual method for solving (QP1QC).

Example 1 (Illustration for case 4) Let A =

2 1 1 0

, B =

4 2 2 2

, f =

1

1

,

g =

4

1 , and = 5.

We can calculate that F = { 0|A + B 0} = (0.5, +) with 0 = 0.5 > 0. Since

lim0.5+

dPd() d

= 7.375 < 0, this is (case 4). One can verify that x = lim0.5+ (A +

B)1( f + g) = (1.25, 1)T is an interior feasible point. Applying the boundarication technique, we select a vector x = (1, 2)T from the null space of A + 0.5B =

4 2 2 1

,

and then solve the quadratic equation

2 xT B x + 2( xT B x gT x) + xT B x 2gT x 2 = 0

to obtain two roots: 1.92 and 1.92. If 0 = 1.92, x1 = x + 0 x = (3.17, 4.84)T is the

global minimizer for the problem with the optimal value 3.625. If 0 = 1.92, x2 = x + 0 x = (0.67, 2.84)T is the other global minimizer. Since the null space of A + 0.5B

is one-dimensional, x1 and x2 are the only two global minimizers.

Example 2 (Illustration for case 7) Let A =

1 3 2 3 2 0

2 0 1

, B =

4 1 2

1 5 2 2 2 2

,

, g =

3

4

2

6 2 3

f =

, and = 6.95. Note that B is positive denite and F = (1.2673

+). Since lim1.2673+

dPd() d

= + and lim+ dP

d () d

= 0, this is (case 7). By

Theorem 2, x = lim+(A + B)1( f + g) = B1g = (0.8, 1.4, 2.1)T is the global

minimizer for the problem with the optimal value 5.15.

123

292 J Glob Optim (2012) 54:275293

, f =

5 3 2 3 6 0 2 0 4

, B =

3 1 2

1 3 2 2 2 2

Example 3 (Another illustration for case 7) Let A =

0 3 1

, g =

3 1

2

, and = 1.5.

Since A 0 and B 0, we have F = [0, +). Since lim0+

dPd() d

= 6.05 > 0 and

lim+ dP

d () d

= 0, this is (case 7) with B 0. Choose = 5 F, by (18), we have

G =

0.156 0.156 0.312 0.168 0.061 0.147

0.117 0.214 0.052

,

with G(A + B)GT = diag(1, 1, 1) and G BGT = H = diag(0, 0.182, 0.154). Then,

compute w = G f = (0.78, 0.33, 0.59)T and s = Gg = (0, 0.74, 0.03)T to obtain that x = GT (

wT , (H1s)T )T = (0.83, 0.17, 0.34)T is the global minimizer for the problem

with the optimal value 1.9.

7 Conclusion

Quadratic programming is very important not only because many real world applications from physics, statistics, management sciences, etc. can be formulated in quadratic forms, but also because it can be used as a second-order approximation model for more complex systems. Quadratic problems with multiple quadratic constraints are known to be NP-hard. Nevertheless, this paper provides a thorough and comprehensive study, from the assumptions, solution methods, duality, to the hidden convexity for us to understand better about the single quadratic constrained problem. Hopefully, with the new insights it leads a way to study the global optimization for more general nonconvex programming problems.

Acknowledgments This research was undertaken while Y. Xia visited National Cheng Kung University, Tainan, Taiwan. Sheus research work was sponsored by Taiwan NSC 98-2115-M-006 -010 -MY2. Xias research work was supported by the fundamental research funds for the central universities under grant YWF-10-02-021 and by National Natural Science Foundation of China under grant 11001006.

References

1. Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72, 5163 (1996)

2. Fang, S.C., Gao, D.Y., Sheu, R.L., Wu, S.Y.: Canonical dual approach to solve 0-1 quadratic programming problems. J. Ind. Manag. Optim. 4(1), 125142 (2008)

3. Fang, S.C., Gao, D.Y., Sheu, R.L., Xing, W.: Global optimization for a class of fractional programming problems. J. Global Optim. 45(3), 337353 (2009)

4. Fang, S.C., Lin, G.X., Sheu, R.L., Xing, W.: Canonical dual solutions for the double well potential problem (preprint)

5. Fehmers, G.C., Kamp, L.P.J., Sluijter, F.W.: An algorithm for quadratic optimization with one quadratic constraint and bounds on the variables. Inverse Probl. 14, 893901 (1998)

6. Fortin, C., Wolkowicz, H.: The trust region subproblem and semidefinite programming. Optim. Methods Softw. 19(1), 4167 (2004)

7. Gao, D.Y.: Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. J. Global Optim. 17, 127160 (2000)

123

J Glob Optim (2012) 54:275293 293

8. Gao, D.Y.: Canonical duality theory and solutions to constrainted nonconvex quadratic programming.J. Global Optim. 29, 377399 (2004)9. Gay, D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2(2), 186197 (1981)10. Golub, G.H., Von Matt, U.: Quadratically constrained least squares and quadratic problems. Numer. Math. 59, 186197 (1991)

11. Hiriart-Urruty, J.-B.: Potpourri of conjectures and open questions in nonlinear analysis and optimization. SIAM Rev. 49(2), 255273 (2007)

12. Horn, R., Johnson, C.R.: Matrix analysis. Cambridge University Press, Cambridge (1985)13. Jeyakumar, V., Srisatkunarajah, S.: Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma. Optim. Lett. 3(1), 2333 (2009)

14. Martnez, J.M.: Local minimizers of quadratic functions on euclidean balls and spheres. SIAM J. Optim.

4, 159176 (1994)15. More, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553572 (1983)16. Palanthandalam-Madapusi , H.J., Van Pelt, T.H., Bernstein, D.S.: Matrix pencils and existence conditions for quadratic programming with a sign-indefinite quadratic equality constraint. J. Global Optim. 45(4), 533549 (2009)

17. Pardalos, P.M., Resende, M.G.C.: Interior point methods for global optimization problems. In: Terlaky, T. (ed.) Interior point methods of mathematical programming, pp. 467500. Kluwer, Dordrecht (1996)

18. Pardalos, P.M., Resende, M.G.C. (eds.): Handbook of applied optimization. Oxford University Press, Oxford (2002)

19. Stern, R.J., Wolkowicz, H.: Indefinite trust region subproblems and nonsymmetric perturbations. SIAMJ. Optim. 5(2), 286313 (1995)20. Sturm, J.F., Zhang, S.: On cones of nonnegtive quadratic functions. Math. Oper. Res. 28(2), 246 267 (2003)

21. Wang, Z., Fang, S.C., Gao, D.Y., Xing, W.: Global extremal conditions for multi-integer quadratic programming. J. Ind. Manag. Optim. 4(2), 213225 (2008)

22. Xing, W., Fang, S.C., Gao, D.Y., Sheu, R.L., Zhang, L.: Canonical dual solutions to the quadratic programming over a quadratic constraint, (submitted)

23. Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14(1), 245267 (2003)

123