• Không có kết quả nào được tìm thấy

perturbed strictly convex quadratic functions

N/A
N/A
Nguyễn Gia Hào

Academic year: 2023

Chia sẻ "perturbed strictly convex quadratic functions"

Copied!
24
0
0

Loading.... (view fulltext now)

Văn bản

(1)

On: 26 January 2015, At: 13:04 Publisher: Taylor & Francis

Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UK

Optimization: A Journal of

Mathematical Programming and Operations Research

Publication details, including instructions for authors and subscription information:

http://www.tandfonline.com/loi/gopt20

Some properties of boundedly

perturbed strictly convex quadratic functions

H.X. Phu a & V.M. Pho b

a Institute of Mathematics , 18 Hoang Quoc Viet Road, Hanoi , Vietnam

b Department of Computer Sciences , Le Qui Don Technical University , 100 Hoang Quoc Viet Road, Hanoi , Vietnam Published online: 07 May 2010.

To cite this article: H.X. Phu & V.M. Pho (2012) Some properties of boundedly perturbed strictly convex quadratic functions, Optimization: A Journal of Mathematical Programming and Operations Research, 61:1, 67-88, DOI: 10.1080/02331931003746114

To link to this article: http://dx.doi.org/10.1080/02331931003746114

PLEASE SCROLL DOWN FOR ARTICLE

Taylor & Francis makes every effort to ensure the accuracy of all the information (the

“Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content.

This article may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms &

(2)

and-conditions

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(3)

Vol. 61, No. 1, January 2012, 67–88

Some properties of boundedly perturbed strictly convex quadratic functions

H.X. Phua* and V.M. Phob

aInstitute of Mathematics, 18 Hoang Quoc Viet Road, Hanoi, Vietnam;bDepartment of Computer Sciences, Le Qui Don Technical University, 100 Hoang Quoc Viet Road,

Hanoi, Vietnam

(Received 9 June 2009; final version received 2 March 2010) We investigate the problemðPÞ~ of minimizingf~ðxÞ:¼fðxÞ þpðxÞsubject to x2D, wheref(x) :¼xTAxþbTx,Ais a symmetric positive definite n-by-n matrix, b2Rn,DRn is convex andp:Rn!R satisfies supx2Djp(x)j s for some givens5þ1. Functionpis called a perturbation, but it may also describe some correcting term, which arises when investigating a real inconvenient objective function f~ by means of an idealized convex quadratic functionf. We prove that f~ is strictly outer-convex for some specified balanced setRn. As a consequence, a-local optimal solution ofðPÞ~ is global optimal and the difference of two arbitrary global optimal solutions ofðPÞ~ is contained in. By the property thatxx~212holds ifxis the optimal solution of the problem of minimizingfonDandx~is an arbitrary global optimal solution of ðPÞ, we show that the set~ Ss of global optimal solutions of ðPÞ~ is stable with respect to the Hausdorff metric dH(., .). Moreover, the roughly generalized subdifferentiability of f~and a generalization of Kuhn–Tucker theorem forðPÞ~ are presented.

Keywords: quadratic programming; bounded perturbation; global minimizer; generalized convexity; stability; subdifferentiability;

Kuhn–Tucker theorem

AMS Subject Classifications: 52A01; 47H14; 49K40; 90C20; 90C26;

90C31; 90C46

1. Introduction

LetAbe a symmetric positive definiten-by-n matrix,b2Rn, and fðxÞ:¼xTAxþbTx, x2Rn:

For a given nonempty convex setDRn, which in not necessarily closed, there arises the convex quadratic program

minimizefðxÞ subject tox2D:

ðPÞ

*Corresponding author. Email: hxphu@math.ac.vn

ISSN 0233–1934 print/ISSN 1029–4945 online ß2012 Taylor & Francis

http://dx.doi.org/10.1080/02331931003746114 http://www.tandfonline.com

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(4)

Our concern is not the above classical optimization problem, but the following program:

minimizef~ðxÞ:¼fðxÞ þpðxÞ subject tox2D, ðPÞ~

wherep:Rn!R is only assumed to be bounded by some given parameters:

sup

x2D

jpðxÞj s5 þ1: ð1:1Þ

Such a problemðPÞ~ may arise whenfis some original objective function andpis some perturbation, which comprises additional (deterministic or random) influences to the objective function and errors caused by modelling, measurement, calculation, etc. The particular point is that we restrict ourself to consider only bounded perturbation satisfying (1.1). An example for bounded perturbation always appears when solving any optimization problem (P) with a computer. Since most real numbers cannot be exactly represented by computers, for most of x2D the value f(x)¼xTAxþbTx cannot be exactly computed but only approximated by some floating-point numberf~ðxÞ, and the corresponding functionf~is neither convex nor quadratic, even not continuous. Then the discontinuous functionpðxÞ ¼f~ðxÞ fðxÞ describes the computing errors, and it is reasonable to assume that these computing errors are bounded by some upper bounds, which can be estimated. By using longer floating-point numbers and better algorithms, one can reduce the upper bounds.

Another scenario is that f~ is the proper objective function and f is just an idealized objective function. It is often the case that functions expressing some practical goals are assumed to be convex or quadratic, or to have some favourable properties which were already intensively investigated or which are more easy to study, although they do not really have these ideal properties. In such a situation, pðxÞ ¼f~ðxÞ fðxÞis the correcting term, which may be assumed to be bounded (at least on the feasible setD) by some sufficiently small positive numbers. An example for this scenario is given by the problem of economic power dispatch, for which it is often assumed that the total cost function is quadratic and strictly convex (see, for instance, [3,5,26,29]). This assumption is a strong idealization, since the real costs may be neither quadratic nor strictly convex. In particular, if the valve-point effect is considered, then the quadratic cost function must be rectified with a correcting term, which is bounded but neither quadratic nor convex, and even not continuously differentiable (see, for instance, [1,27,28]). In this scenario, we will use the idealized convex quadratic function f for investigating the real inconvenient objective functionf~.

For the sake of shortness, in this article we simply namepas the perturbation,f~ as the perturbed function andðPÞ~ as the perturbed problem, althoughf~may be the proper objective function,pmay be the correcting term and ðPÞ~ may be the proper problem, as explained above.

Since program (P) is both convex and quadratic and since there are already many papers dealing with different stability aspects of perturbed convex or/and quadratic programs, one might ask what is still to do? The first point is that in former investigations perturbations do not change the form or the main characteristics of the original programs. This means that perturbed convex programs remain convex as in [2,8–10,13,22–25,30,31], and perturbed quadratic programs remain quadratic as

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(5)

in [4,11,12,20]. In this article the perturbed program ðPÞ~ is neither convex nor quadratic. Moreover, since the perturbation p is only assumed to be bounded by some given positive parameters, the perturbed objective functionf~may be nowhere continuous, i.e. it may be quite wild from the analytical point of view. The second point is, beside stability aspects, we also study some other properties of the perturbed program.

In Section 2, we show that, despite of p satisfying (1.1), the strict convexity of f does not disappear completely, but the perturbed function f~ is still strictly and roughly convex in the following sense. For some given balanced subset Rn, f~:Rn !R is said to be outer -convex on DRn if for all x0,x12D satisfying x0x12=there is a closed subset[0, 1] containing {0, 1} such that

½x0,x1 fð1Þx0þx1 j 2g þ1

2 ð1:2Þ

and

82n f0, 1g: ~fðð1Þx0þx1Þ ð1Þf~ðx0Þ þf~ðx1Þ: ð1:3Þ (This definition, which was introduced in [18], is a generalization of some kinds of roughly generalized convexity presented in [6,14,15,19].) If

82n f0, 1g: ~fðð1Þx0þx1Þ5ð1Þf~ðx0Þ þf~ðx1Þ ð1:4Þ holds instead of (1.3), thenf~is calledstrictly outer-convex. Theorem 2.2 claims that f~is strictly outer-convex for¼M(2s), whereM(.) is defined in (2.4).

Section 3 deals with the consequence of the remaining strict outer-convexity of f~. Theorem 3.1 presents a key property of outer -convex functions, namely each -minimizer x2Doff~, which satisfies

f~ðxÞ ¼ inf

x2ðxþÞ\D

f~ðxÞ, is aglobal minimizer, i.e.

f~ðxÞ ¼ inf

x2D

f~ðxÞ:

Because of the unruly perturbation p, the existence of -minimizers is hardly warranted. Therefore, we are still interested in -infimizers, i.e. in such x2D satisfying

lim inf

x2D,x!x

f~ðxÞ ¼ inf

x2ðxþÞ\D

f~ðxÞ:

Theorem 3.2 says that each-infimizer off~is aglobal infimizer, i.e.

lim inf

x2D,x!x

f~ðxÞ ¼inf

x2D

f~ðxÞ:

(Note that in Theorems 3.1 and 3.2 we have to choose¼M(2s).) Theorems 3.3 and 3.4 assert that, ifx~0 andx~1 are two arbitrary global minimizers or global infimizers of problemðPÞ, then~ x~0x~12Mð2sÞ. This property corresponds to the uniqueness of the minimizer of a strictly convex function.

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(6)

The stability of the set of optimal solutions of the perturbed program is investigated in Section 4. If x is the minimizer of problem (P) andx~ is a global infimizer of problem ðPÞ, then Theorem 4.1 claims that~ xx~212Mð2sÞ.

Consequently, kxx~k ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p , where min is the smallest eigenvalue of matrix A (Corollary 4.2). This property is used to deduce in Theorem 4.4 that dHðfxg,SsÞ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p , wheredH(., .) is the Hausdorff distance andSsis the set of global infimizers ofðPÞ, and to infer the stability of the set of optimal solutions of~ ðPÞ~ in Corollary 4.5.

In Section 5, Theorem 5.1 describes the roughly generalized subdifferentiability of the perturbed function f~ and Theorem 5.2 states a generalization of the Kuhn–Tucker theorem for the problem of minimizing f~ðxÞsubject to x2D, where D¼{x2Cjg1(x)0,. . .,gm(x)0}.

Throughout this article,k.kdenotes then-dimensional Euclidean norm and the following notions are used:

x:¼ ð1Þx0þx1,

½x0,x1:¼ fxj01g, Bðx, rÞ:¼ fx02Xj kx0xk rg:

2. Outer!-convexity

The aim of this section is to show that an arbitrary perturbationp satisfying (1.1) does not completely destroy the strict convexity of the quadratic function f(x)¼xTAxþbTx, but the perturbed function f~¼fþp is still strictly outer -convex for some suitable setRn.

In [17] we used the convexity modulush1:Rþ!Roffdefined by h1ðÞ ¼ inf

x0,x12Rn,kx0x1

1 2

fðx0Þ þfðx1Þ f1

2ðx0þx1Þ

for characterizing the outer-convexity of the perturbed functionf~¼fþp. In order to improve our results, in this article we do not define the convexity modulus by taking infimum over the entire space, but dependently on individual directions as follows:

h1ð,zÞ:¼ inf

x2Rn

1 2

fðxÞ þfðxþzÞ f

2z

, ð2:1Þ

where2Randz2Rn, and use it to define mð,zÞ:¼inf

40h1ð,zÞ4 : ð2:2Þ Sinceh1(.,z) is nondecreasing, there holds

h1ð,zÞ4 if4mð,zÞ: ð2:3Þ Consider the balanced set

MðÞ:¼ fzjz2Rn, jj mð,zÞg, ð2:4Þ which plays a central role in this article. Next, we state some basic properties of m(., .) andM(.).

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(7)

PROPOSITION 2.1

(a) For any40 and z2Rn,there hold mð,zÞ ¼2

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðzTAzÞ1 q

ð2:5Þ and

1 2

fðxÞ þfðxþmð,zÞzÞ f

xþmð,zÞ

2 z

¼ for all x2Rn: ð2:6Þ (b) For any40,there holds

MðÞ ¼ fx2RnjxTAx4g: ð2:7Þ (c) Let min and max be the smallest eigenvalue and the greatest eigenvalue of

matrix A.Then B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffi

=max

p

MðÞ B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffi

=min

p

, ð2:8Þ

and MðÞ ¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffi

=min

p

if and only ifmax¼min. Proof (a) For anyx,z2Rnand40, there holds

1 2

fðxÞ þfðxþzÞ f

2z

¼1 2

xTAxþbTxþ ðxþzÞTAðxþzÞ þbTðxþzÞ

xþ 2z

T

A

xþ 2z

bT

2z

¼2 4 zTAz:

Therefore, due to (2.1) and (2.2),

h1ð,zÞ ¼2 4 zTAz and

mð,zÞ ¼infn 40

2

4 zTAz4o

¼2

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðzTAzÞ1 q

: Moreover, for anyx2Rn, we have

1 2

fðxÞ þfðxþmð,zÞzÞ f

xþmð,zÞ

2 z

¼1 4

2

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðzTAzÞ1

q 2

zTAz¼: (b) Forx¼z, (2.5) yields

mð,zÞ ¼2

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðzTAzÞ1 q

¼2jj

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðxTAxÞ1 q

:

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(8)

Hence, by definition,

x2MðÞ

,

x¼z, jj mð,zÞ ¼2jj

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðxTAxÞ1

q

,

xTAx4 : (c) By the spectral theorem, there is an orthonormal basis {e1,e2,. . .,en} ofRn consisting of unit eigenvectors ofA, i.e.

Aei¼iei, keik ¼1 fori¼1, 2,. . .,n, eTiej¼0 fori6¼j,

where1,2,. . .,nare the corresponding real eigenvalues. Then anyx2Rncan be represented byx¼Pn

i¼1iei and there hold kxk2¼xTx¼Xn

i,j¼1

ijeTiej¼Xn

i¼1

2i

and

xTAx¼Xn

i,j¼1

ijeTiAej¼Xn

i,j¼1

jijeTiej¼Xn

i¼1

ði2iÞ:

Thus we have the following:

minkxk2¼min

Xn

i¼1

2i xTAx¼Xn

i¼1

ði2iÞ max

Xn

i¼1

2i ¼maxkxk2: Therefore, (2.7) yields

MðÞ ¼ fx2RnjxTAx4g fx2Rnjminkxk24g

¼

x2Rnj kxk 2 ffiffiffiffiffiffiffiffiffiffiffiffiffi

=min

p

¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffi

=min

p

and

MðÞ fx2Rnjmaxkxk24g

¼

x2Rnj kxk 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffi

=max p

¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffi

=max

p

: In particular,MðÞ ¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffi

=min

p

if and only if min

Xn

i¼1

2i ¼Xn

i¼1

ði2iÞ when Xn

i¼1

2i 4=min,

which holds if and only ifmax¼min. g

Since M()¼{x2RnjxTAx4} and A is positive definite, M() is convex, closed and balanced. Moreover, if40 then 02Rnis an interior point ofM().

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(9)

We now useM(.) for characterizing the strict outer-convexity of the perturbed functionf~.

THEOREM 2.2 Suppose 05supx2Djp(x)j s5þ1. Then f~¼fþp is strictly outer -convex on D for ¼M(2s).

Proof Consider arbitrary x0,x12D with x0x12=¼M(2s). Let 40 be defined by

1

ðx0x1Þ 2@Mð2sÞ, ð2:9Þ where@M(2s) denotes the boundary of the set M(2s), and

¼ f0, 1g [ 1

2, 1 1 2

: ð2:10Þ

Obviously, x0x12=¼M(2s) yields 41. For x¼(1)x0þx1, ¼21 and¼121, we have

x1

2x0¼ 1 1

2

x0þ 1

2 x1x0¼ 1

2 ðx1x0Þ, x11

2x1¼ 1

2 x0þ 1 1 2

x1x1¼ 1

2 ðx0x1Þ,

ð2:11Þ

i.e.x1

2x02 12Mð2sÞandx11

2x1212Mð2sÞ, which imply x0,x1

2

x0,x1

2 þ1

2 Mð2sÞ x0,x1

2 þ1 2 , x11

2,x1

x11

2,x1 þ1

2 Mð2sÞ x11

2,x1 þ1 2: Therefore, by (2.10),

½x0,x1 ¼ x0,x1

2

[

x1

2,x11

2

[

x11

2,x1

fxj2g þ1 2, i.e. (1.2) is fulfilled.

Now consider an arbitrary fixed2 1

2, 121

and denote 0¼ 1

2, 00 ¼þ 1 2:

Since21 5125121, there holds 040 or0051. Therefore, it follows from the strict convexity offthat

fðx0Þ ð10Þfðx0Þ þ0fðx1Þ, fðx00Þ ð100Þfðx0Þ þ00fðx1Þ, where ‘5’ holds at least in one inequality. Hence,

fðx0Þ þfðx00Þ5ð2000Þfðx0Þ þ ð0þ00Þfðx1Þ

¼2ð1Þfðx0Þ þ2fðx1Þ: ð2:12Þ

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(10)

On the other hand,

x00x0¼ ð100Þx0þ00x1 ð10Þx00x1

¼ 1 x0þ1

x1

¼1

ðx1x0Þ,

i.e. by (2.9), x00x02@M(2s). Thus, (2.4) and (2.6) imply mð2s,x1x0Þ ¼1=, x0þm(2s,x1x0)(x1x0)¼x00 and

1 2

fðx0Þ þfðx00Þ f 1

2ðx0þx00Þ

¼2s:

Since

1

2ðx00þx0Þ ¼1 2

ð100Þx0þ00x1þ ð10Þx0þ0x1

¼1 2

ð2000Þx0þ ð0þ00Þx1

¼ ð1Þx0þx1

¼x, we have

1 2

fðx0Þ þfðx00Þ

fðxÞ ¼2s:

Combining this with (2.12) yields

ð1Þfðx0Þ þfðx1Þ fðxÞ42s, and following, by (1.1),

ð1Þf~ðx0Þ þf~ðx1Þ f~ðxÞ ð1Þðfðx0Þ sÞ þðfðx1Þ sÞ ðfðxÞ þsÞ

¼ ð1Þfðx0Þ þfðx1Þ fðxÞ 2s 40,

i.e. (1.4) holds true. Hence,f~is strictly outer-convex onDfor¼M(2s). g Due to (2.8), we have

Mð2sÞ B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

: ð2:13Þ

Therefore, it follows from Theorem 2.2 that f~ is strictly outer-convex on Dfor ¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

(see Proposition 2.1 in [18]). That means, for ¼2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p ,

f~ is outer -convex in the sense of [19] and strictly and roughly -convex in the sense of [16].

Since ¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

is a ball in the Euclidean spaceRn, it is, in general, simpler to determine and to describe than¼M(2s). Leteminbe a unit eigenvector of Acorresponding to the minimal eigenvaluemin. IfDis large enough to contain a pair of points x0 and x1 satisfying x0x1 ¼2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p emin, then ¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(11)

is the smallest ball for whichf~¼fþpis strictly outer-convex for any perturbationp satisfying 05supx2Djp(x)j s5þ1. Indeed, if52 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p and¼Bð0, Þ, then x0x12=and, by choosing a perturbationpsatisfying

pðð1Þx0þx1Þ ¼ s for2 f0, 1g, s for2 0, 1½,

it is easy to verify for all2]0, 1[ that

f~ðð1Þx0þx1Þ ¼fðð1Þx0þx1Þ þs

4ð1Þfðx0Þ þfðx1Þ 2sþs

¼ ð1Þf~ðx0Þ þf~ðx1Þ, i.e.f~cannot be outer-convex for¼Bð0, Þ.

By Proposition 2.1, if min5max then M(2s) is properly contained in the ball B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

. Hence, in general, the strict outer -convexity with respect to ¼M(2s) is stronger than the one with respect to¼B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

.

A basic property of convex functions is that all lower level sets are convex. Outer -convex functions also possess a similar property, namely all lower level sets are outer-convex. As in [18], a setSis said to beouter-convexif for allx0,x12Sthere exists a closed subset [0, 1] containing {0, 1} such that {xj2}S and

½x0,x1 fxj2g þ12. For the perturbed function f~¼fþp, we have the following property.

PROPOSITION 2.3 Suppose 05supx2Djp(x)j s5þ1. Then each lower level set fx2Djf~ðxÞ gof f is outer~ -convex for¼M(2s).

Proof Due to Proposition 3.3 in [18], iff~is outer-convex then each lower level set of f~ is outer -convex. Combining this fact with Theorem 2.2, we get the desired

conclusion. g

3. Global minimal solutions

In this section, we investigate some typical properties of global optimal solutions of the perturbed functionf~¼fþp, which is related to the strict outer-convexity off~. Recall that A is a symmetric positive definite n-by-n matrix, b2Rn, f(x)¼xTAxþbTx, andDRnis convex. Instead of the optimization problem

minimizefðxÞ subject tox2D, ðPÞ

we deal with the perturbed problem

minimizef~ðxÞ ¼fðxÞ þpðxÞ subject tox2D, ðPÞ~

wherep:Rn!R is only assumed to satisfy 05sup

x2D

jpðxÞj s5þ1: ð3:1Þ

A typical property of the convex program (P) is that a local minimum is global minimum. Because of the unruly perturbationp, problemðPÞ~ cannot have the

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(12)

above-mentioned property. However, since f~ is outer -convex as proved in the preceding section,ðPÞ~ still possesses the following similar property.

THEOREM 3.1 Suppose¼M(2s)and x2D is a-minimizer off~,i.e.

f~ðxÞ ¼ inf

x2ðxþÞ\D

f~ðxÞ: ð3:2Þ

Then xis a global minimizer of f~,i.e.

f~ðxÞ ¼inf

x2D

f~ðxÞ: ð3:3Þ

Proof For¼M(2s) ands40, Proposition 2.1 yields that the origin 02Rnis an interior point of . By Theorem 2.2, f~ is outer -convex. Therefore, Theorem 3.6

in [18] implies that (3.3) follows from (3.2). g

Since the considered perturbationpis not assumed to be lower semicontinuous, the perturbed problemðPÞ~ may not have minimizers. Therefore, it is more realistic to consider infimizers instead of minimizers, as done in the following theorem.

THEOREM 3.2 Suppose¼M(2s)and x2D is a-infimizer off~,i.e.

lim inf

x2D,x!x

f~ðxÞ ¼ inf

x2ðxþÞ\D

f~ðxÞ: ð3:4Þ

Then xis a global infimizer off~, i.e.

lim inf

x2D,x!x

f~ðxÞ ¼inf

x2D

f~ðxÞ: ð3:5Þ

Proof Assume the contrary that (3.5) is not true, i.e. there exists an x02Dn(xþ) with

:¼ lim inf

x2D,x!x

f~ðxÞ f~ðx0Þ40: ð3:6Þ Denote

:¼ kx0xk ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p ,

:¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p ,

":¼1

4ðþ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 24

p Þ,

ð3:7Þ

where max is the greatest eigenvalue of matrix A. Due to Proposition 2.1, Bð0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=max

p Þ is contained in M(2s). Therefore, x0x2=¼M(2s) implies that kx0xk42 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=max

p and thus 40. Since "40 and x0x2=M(2s), we can choosex12D\ ðxþ12Mð2sÞÞsuch that

kx1xk5", f~ðx1Þ5 lim inf

x2D,x!x

f~ðxÞ þ" ð3:8Þ and

x0x12=, x1þ1

2 Mð2sÞ xþMð2sÞ ¼xþ: ð3:9Þ

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(13)

Our aim is to show that there exists a2[0, 1] satisfying x¼ ð1Þx0þx12 ðxþÞ \D, f~ðxÞ5 lim inf

x2D,x!x

f~ðxÞ, ð3:10Þ in contradiction to (3.4). To this goal, first observe that

1

2ð ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 24

p Þ505"51

2ðþ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 24

p Þ,

i.e. the"defined in (3.7) lies between the two real roots of the quadratic equation

"2þ"þ ¼0. Therefore,

"2þ"þ ¼"2þ

kx0xk ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p

" ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p 50,

which implies

4 kx0xk þ"

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p 1

": ð3:11Þ Take again41 defined by (2.9), i.e.1ðx0x1Þ 2@Mð2sÞ. The inclusion

B

0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p

Mð2sÞ yields

1

kx0x1k 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p :

Combining with

kx0x1k kx0xk þ kxx1k5kx0xk þ", we get

2 kx0x1k ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p 5kx0xk þ"

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=max

p :

This along with (3.11) yield4ð21Þ", and the following:

1

2 ðÞ þ 1 1 2

"50: ð3:12Þ In the proof of Theorem 2.2, we have already proved for x0x12=, which is warranted by (3.9), and¼121 that

f~ðx11

2Þ5 1

2 f~ðx0Þ þ 1 1 2

f~ðx1Þ:

Hence, by (3.6), (3.8) and (3.12), there holds f~

x11 2

5 1

2

f~ðx0Þ þ 1 1 2

lim inf

x2D,x!x

f~ðxÞ þ"

¼ 1 2

f~ðx0Þ lim inf

x2D,x!x

f~ðxÞ

þ 1 1 2

"þ lim inf

x2D,x!x

f~ðxÞ

¼ 1

2 ðÞ þ 1 1 2

"þ lim inf

x2D,x!x

f~ðxÞ 5 lim inf

x2D,x!x

f~ðxÞ: ð3:13Þ

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(14)

On the other hand, (2.9) and (2.11) imply that x11

2x1¼ 1

2 ðx0x1Þ 21 2Mð2sÞ, i.e. by (3.9),

x11

22x1þ1

2Mð2sÞ xþ: ð3:14Þ

Properties (3.13) and (3.14) mean that we get the desired contradiction stated in

(3.10) for¼121. Thus, (3.5) must be true. g

Note that the proof of Theorem 3.2 may be shorter by applying Theorem 3.1, whose proof in turn uses Theorem 2.2. It is our intention to present a longer proof but without using Theorem 2.2.

It follows from Theorems 3.1 and 3.2 and (2.13) that ifx2Dis a-minimizer (or -infimizer) of f~ for ¼Bð0, 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p Þ, thenx is a global minimizer (or global infimizer, respectively).

A typical property of strictly convex functions is that their minimizer is unique.

In [16] we have already dealt with a similar property of strictly and roughly convex- like functions. Next, we present a similar typical property of strictly -convex functions.

THEOREM 3.3 Letx~0andx~1be two arbitrary global minimizers of problemðPÞ.~ Then

~

x0x~12Mð2sÞ.

Proof Assume the contrary thatx~0x~12=Mð2sÞ. By Theorem 2.2,f~is strictly outer -convex for ¼M(2s). By definition, there exists a closed subset [0, 1]

containing {0, 1} and satisfying (1.2) and (1.4), i.e.

½x~0,x~1 fð1Þx~0þx~1 j2g þ1

2 ð3:15Þ

and

82n f0, 1g: ~fðð1Þx~0þx~1Þ5ð1Þf~ðx~0Þ þf~ðx~1Þ ¼ inf

x2D

f~ðxÞ: ð3:16Þ The property x~0x~12=Mð2sÞ ¼ and (3.15) imply that n{0, 1}6¼ ;. Therefore, by (3.16), there exists a 2]0, 1[ such that f~ðð1Þx~0þx~1Þ5infx2Df~ðxÞ,

a contradiction. Hence,x~0x~12Mð2sÞ. g

SinceAis positive definite, (2.7) yields that whilestends to 02Rthe setM(2s) shrinks to {0}Rn, therefore Theorem 3.3 implies that the diameter of the set of global minimizers off~¼ f þp converges to zero, too.

What happens if global minimizers are replaced by global infimizers to be more realistic, as explained before Theorem 3.2? In general, the distance between the global infimizers of a strictly outer -convex function may be unbounded. For instance, the functiong:R!Rdefined by

gðxÞ ¼ ½x x, x2R,

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(15)

where [x] denotes the integer part ofx2R, is strictly outer-convex onD¼R for ¼[1, 1], and each integer number is a global infimizer ofg. Hence, x~0x~12 does not hold true for any pair of global infimizersx~0 andx~1 ofg.

But for the particular function f~ðxÞ ¼xTAxþbTxþpðxÞ, where A is positive definite andpsatisfies (3.1), we get the following result for global infimizers, which is similar to Theorem 3.3.

THEOREM 3.4 Letx~0andx~1 be two arbitrary global infimizers of problemðPÞ.~ Then

~

x0x~12Mð2sÞ.

Proof (a) Assume thatxis the minimizer of problem (P). By Theorem 4.1 (which will be proved in the next section), x~0x2 12Mð2sÞ andxx~1212 Mð2sÞ. Since M(2s) is convex, it follows that

~

x0x~1¼ ðx~0xÞ þ ðxx~1Þ 2Mð2sÞ:

(b) Assume that problem (P) has no minimizer. Sincef(x)¼xTAxþbTxandAis positive definite, it is only possible ifDis not closed. In this case, we replace the setD by its closure clDand the substitute problem of minimizingfon clDhas now exactly one optimal solution, sayx. In addition, we change the functionpoutside ofDby

pðxÞ ¼s forx2=D,

which does not violate the only characteristic property ofp, namely 05sup

x2D

jpðxÞj sup

x2clD

jpðxÞj ¼sup

x2Rn

jpðxÞj s5þ1:

Obviously,

x2clinfDnD

f~ðxÞ ¼ inf

x2clDnD

fðxÞ þpðxÞ

¼sþ inf

x2clDnDfðxÞ sþ inf

x2clDfðxÞ and

sþinf

x2DfðxÞ ¼inf

x2D

fðxÞ þs inf

x2D

fðxÞ þpðxÞ

¼inf

x2D

f~ðxÞ:

Since infx2clDf(x)¼infx2Df(x) holds because of the continuity off, it follows that

x2clinfDnD

f~ðxÞ inf

x2D

f~ðxÞ: ð3:17Þ

This along with

lim inf

x2D,x!x~0

f~ðxÞ ¼ lim inf

x2D,x!x~1

f~ðxÞ ¼ inf

x2D

f~ðxÞ,

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(16)

yield

lim inf

x2clD,x!x~0

f~ðxÞ ¼ lim inf

x2clD,x!x~1

f~ðxÞ ¼ inf

x2clD

f~ðxÞ,

i.e. x~0 and x~1 are also global infimizers of the problem of minimizing f~ on clD.

Hence, due to part (a),x~0x~12Mð2sÞ. g

Note that the assertion of Theorems 3.3 and 3.4 cannot be further improved.

To illustrate this fact, just consider the example with

fðxÞ ¼xTAx forx2D¼Rn, ð3:18Þ i.e.b¼02Rn, and

pðxÞ ¼ sfðxÞ forx212Mð2sÞ,

0 otherwise.

ð3:19Þ Then (2.7) yields

fðxÞ 2 ½0, 2s forx2 12Mð2sÞ 42s otherwise.

Therefore,jp(x)j sfor allx2Rnand

f~ðxÞ ¼ s forx212Mð2sÞ fðxÞ42s otherwise.

ð3:20Þ Hence, each global infimizer ofðPÞ~ is a global minimizer and

1

2Mð2sÞ ¼ fx~jx~ is a global infimizer ofðPÞg~ ð3:21Þ and

Mð2sÞ ¼ fx~0x~1jx~0,x~1 are global infimizers ofðPÞg,~

i.e. there exists no other set which is smaller thanM(2s) and contains the difference

~

x0x~1 of any pair of global infimizers ofðPÞ.~

Inclusion (2.13) and Theorem 3.4 immediately imply the following corollary.

COROLLARY 3.5 Let x~0 and x~1 be two arbitrary global infimizers of problem ðPÞ.~ Thenkx~0x~1k 2 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p .

4. Stability

In this section we investigate the relation between the global optimal solutions of the original problem (P) and of the perturbed problemðPÞ; in particular, the stability of~ the set of global optimal solutions of ðPÞ~ with respect to the Hausdorff metric.

Although the following results are only formulated for global infimizers ofðPÞ, they~ are also valid for its global minimizers because each global minimizer is a global infimizer.

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(17)

Next, we estimate the distance between the minimizer of problem (P) and any global infimizer of problem ðPÞ. Since a local minimizer of the strictly convex~ functionfon the convex setDis global and it is unique, we simply call the minimizer of (P) if it exists.

THEOREM 4.1 Let xbe the minimizer of problem(P)andx~ be any global infimizer of problemðPÞ.~ Thenx~x212Mð2sÞ.

Proof Assume the contrary thatx~x2=12 Mð2sÞ. Then there exist ans04sand a neighbourhoodUðx~Þofx~ such that

xþ1

2Mð2s0Þ

\Uðx~Þ ¼ ;: ð4:1Þ Consider an arbitraryx~2Uðx~Þ \Dand denotez~¼x~x. Sincef(x)f(x) for all x2Dwhile bothxandx~ are contained in the convex setD, there holds

0 d

dtfðxþt~zÞ

t¼0

¼ d dt

z~TAzt~2þ ð2AxþbÞTzt~ þxTAxþbTx

t¼0

¼ ð2AxþbÞTz:~ In consequence, we have

fðxþz~Þ þfðxz~Þ ¼

~

zTAz~þ ð2AxþbÞTz~þxTAxþbTx þ

~

zTA~z ð2AxþbÞTz~þxTAxþbTx

¼2

~

zTA~zþxTAxþbTx

¼2

fðxþz~Þ ð2AxþbÞTz~ 2fðxÞ,~

which implies that

fðxÞ ~ fðxÞ 1 2

fðxþz~Þ þfðxz~Þ

fðxÞ:

On the other hand, z~¼x~x2=12Mð2s0Þ because x~2=

xþ12Mð2s0Þ

follows from (4.1) andx~2Uðx~Þ \D. Therefore, it follows from (2.1) and (2.3) and (2.4) that

1 2

fðxþz~Þ þfðxz~Þ

fðxÞ42s0: As a result, we obtainfðxÞ ~ fðxÞ42s0, which yields immediately

f~ðxÞ ~ f~ðxÞ ¼fðxÞ ~ fðxÞ þpðxÞ ~ pðxÞ42s02s¼2ðs0sÞ40: ð4:2Þ This relation is valid, as chosen above, for anyx~2Uðx~Þ \D. Thus,

lim inf

x2D,x!x~

f~ðxÞ f~ðxÞ 2ðs0sÞ40,

i.e. x~ cannot be a global infimizer of problem ðPÞ, a contradiction of the~ assumption. Hence,x~x212 Mð2sÞmust be true. g

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(18)

The assertion of Theorem 4.1 cannot be further improved. This fact can be demonstrated by example (3.18)–(3.20) again, for which x¼02Rn is the unique minimizer of (P) and (3.21) yields

1

2Mð2sÞ ¼ fx~jx~ is a global infimizer of ðPÞg~

¼ fx~xjx~ is a global infimizer ofðPÞg,~

i.e. there exists no other set which is smaller than 12Mð2sÞ and contains all such differencesx~x.

Inclusion (2.13) and Theorem 4.1 immediately imply the following corollary.

COROLLARY 4.2 Let x be the minimizer of problem (P) and x~ be any global infimizer of problemðPÞ.~ Thenkxx~k ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p .

Applying the above result, we can estimate the Hausdorff distance dHðS0,SsÞ ¼maxfsup

x2S0

yinf2Ss

kxyk, sup

y2Ss

x2Sinf0

kxykg ð4:3Þ between the setS0of minimizers of the original problem (P) and the setSsof global infimizers of the perturbed problemðPÞ.~

Of course, we are only interested in the case where bothS0andSsare nonempty.

SinceD is not assumed to be closed, it is nota priori sure whether S0and Ss are nonempty. Therefore, the existence of global optimal solutions must be explicitly assumed or ensured, as done in the following.

LEMMA 4.3 Assume that problem(P)has a minimizer called xand

xþ1 2 Mð2sÞ

\D is closed: ð4:4Þ

Then there exist global infimizers of problemðPÞ.~

Proof If f~ðxÞ ¼infx2Df~ðxÞ then x is a global infimizer of ðPÞ~ we look for.

Otherwise, we can choose a sequence (xi) inDsuch that f~ðxÞ4f~ðxiÞ inf

x2D

f~ðxÞ for alli2Nand lim

i!þ1

f~ðxiÞ ¼inf

x2D

f~ðxÞ:

Since the relation (4.2) is valid for anyx~2Dn ðxþ12Mð2sÞÞ, i.e.

f~ðxÞ~ 4f~ðxÞ for allx~2Dn

xþ1 2 Mð2sÞ

, ð4:5Þ

the entire sequence (xi) must be contained in the set ðxþ12 Mð2sÞÞ \D, which is compact. Hence, we can assume without loss of generality that (xi) converges to a pointx~2D, which implies that

lim inf

x2D,x!x~

f~ðxÞ ¼inf

x2D

f~ðxÞ,

i.e.x~ is a global infimizer of ðPÞ.~ g

The preceding lemma is a preparation for the next theorem.

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(19)

THEOREM 4.4 Assume that problem(P)has a minimizer called xand

ðxþBð0, rÞÞ \D is closed for some given r40: ð4:6Þ If

sup

x2D

jpðxÞj s1

2r2min, ð4:7Þ

then the set Ssof global infimizers ofðPÞ~ is nonempty and dHðfxg,SsÞ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p : ð4:8Þ

Proof Inequality (4.7) implies that ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p r. Therefore, it follows from (2.13) that

1

2 Mð2sÞ B

0, ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2s=min

p

B 0,rÞ:

Since

xþ1 2Mð2sÞ

\D¼

xþ1 2Mð2sÞ

\ ððxþBð0, rÞÞ \DÞ,

(4.6) yields (4.4). Hence, by Lemma 4.3,Ssis nonempty. By applying Corollary 4.2

for (4.3) andS0¼{x}, we finally get (4.8). g

COROLLARY 4.5 Assume that problem (P)has a minimizer called xand (4.6)holds true.For all"40,if

sup

x2D

jpðxÞj s5:¼1

2 ðminf",rgÞ2min, ð4:9Þ then dH({x},Ss)5".

Proof On the one hand, (4.9) impliess512r2min, i.e. (4.7) holds true. Therefore, by Theorem 4.4, we get (4.8). On the other hand, (4.9) yieldss512"2min. Hence, it follows from (4.8) thatdHðfxg,SsÞ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2s=min

p 5". g

The above result describes the stability of the set Ssof global optimal solutions (in a generalized sense as global infimizers) of the perturbed problemðPÞ. It says that~ dH({x},Ss) tends to zero whens!0.

5. Generalized subdifferentiability and optimality condition

As usual, a convex functiong:DRn!Ris said to besubdifferentiableatx2Dif there exists a so-calledsubgradient2Rnsatisfying (see, e.g. [21])

gðxÞ gðxÞ þTðxxÞ for all x2D: ð5:1Þ For the convex function g(x)¼f(x)¼xTAxþbTx,x2D, ¼ rf(x)¼2Axþb is a subgradient atxand it is the only subgradient ifxis in the interior ofD. Sincepis only assumed to be bounded by some given parameter s, the perturbed function f~¼fþp is no more subdifferentiable in the above classical sense. Our aim is to

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(20)

show, similarly to [18], thatf~is subdifferentiable in a generalized sense. In pursuit of this aim, we transform (5.1) equivalently to

gðxÞ Tx gðxÞ Tx for allx2D

and replace the term on the left with infx02 ðxþÞ\Dðf~ðx0Þ Tx0Þ for some suitable balanced set and the term on the right withf~ðxÞ Txto get

x02 ðxinfþÞ\Dðf~ðx0Þ Tx0Þ f~ðxÞ Tx for allx2D,

which states the definition of theroughly generalized subgradient of f~. In such a way, theroughly generalized subdifferentiabilityof the functionf~may be described as in Theorem 5.1. Note that we only use the information supx2Djp(x)j s of p, i.e.

pmay be unspecified outside ofD. Therefore,f~is only given onDalthoughfis well known on the entire spaceRn. That is why we consider the subdifferentiability of f~only on D.

THEOREM 5.1 Suppose 05supx2Djp(x)j s5þ1 and f~ðxÞ ¼xTAxbTxþpðxÞ.

Then,for any x2D,there holds inf

x02ðxþ12Mð2sÞÞ\D

f~ðx0Þ ð2AxþbÞTx0

f~ðxÞ ð2AxþbÞTx for all x2D: ð5:2Þ In particular, if D is closed and p is lower semicontinuous, then for any x2D there exists

~

x2 xþ1 2 Mð2sÞ

\D ð5:3Þ

such that

f~ðx~Þ ð2AxþbÞTx~¼ min

x02 ðxþ12Mð2sÞÞ\D

f~ðx0Þ ð2AxþbÞTx0

ð5:4Þ and

f~ðx~Þ ð2AxþbÞTx~ f~ðxÞ ð2AxþbÞTx for all x2D, ð5:5Þ or,equivalently,

f~ðxÞ f~ðx~Þ þ ð2AxþbÞTðxx~Þ for all x2D:

Proof Consider any fixedx2Dand the function f:Rn!Rdefined by

fðxÞ:¼fðxÞ ð2AxþbÞTx¼xTAx2xTAx: ð5:6Þ Sincefis strictly convex andrfðxÞ ¼02Rn,xis the only minimizer offon Rn. This fact does not change if x is only restricted toD. Applying (4.5) for f instead fandfþpinstead f~¼fþp, we get

fðxÞ þ~ pðxÞ~ 4fðxÞ þpðxÞ for allx~2Dn

xþ1 2 Mð2sÞ

:

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

(21)

By (5.6), we have

f~ðxÞ ð2AxþbÞTx5f~ðxÞ ð2Ax~ þbÞTx~ for allx~2Dn

xþ1 2Mð2sÞ

, which yields immediately

inf

x02 ðxþ12Mð2sÞÞ\D

f~ðx0Þ ð2AxþbÞTx0

5f~ðxÞ ð2Ax~ þbÞTx~ for allx~2Dn

xþ1

2 Mð2sÞ

and, therefore, (5.2).

In particular, if D is closed and p is lower semicontinuous, then the set ðxþ12Mð2sÞÞ \D is compact and the function x°f~ðxÞ ð2AxþbÞTx is lower semicontinuous. Therefore, there exists x~ satisfying (5.3) and (5.4). Then (5.5)

follows from (5.2) and (5.4). g

Finally, we state a generalization of the Kuhn–Tucker theorem for the problem of minimizingf~ðxÞ ¼fðxÞ þpðxÞsubject tox2D, where

D¼ fx2Cjg1ðxÞ 0,. . .,gmðxÞ 0g, ð5:7Þ CRnis closed and convex, and all functionsg1,. . .,gmare convex and continuous on C. As usual, @gi(x) denotes the subdifferential of gi and N(x j C) denotes the normal cone to the setCat the pointx.

THEOREM 5.2 Suppose that D is defined by(5.7).

(a) If x~2D is a global infimizer of problem ðPÞ,~ then there exist an x2 ðx~þ12Mð2sÞÞ \D and Lagrange multipliers 00, 10,. . .,m0, not all zero,such that

020ð2AxþbÞ þ1@g1ðxÞ þ þm@gmðxÞ þNðxjCÞ,

igiðxÞ ¼0, i¼1,. . .,m: ð5:8Þ If the Slater condition is fulfilled,i.e.

9x2C:g1ðxÞ50,. . .,gmðxÞ50, ð5:9Þ then 06¼0and it can be assumed that0¼1.

(b) If x2D satisfies (5.8)for0¼1,then there exits anx~2 ðxþ12Mð2sÞÞ \D which is a global infimizer of problem ðPÞ.~

Proof (a) Assume thatx~2Dis a global infimizer of problemðPÞ. Since~ Dis closed, f(x)¼xTAxþbTx and A is positive definite, problem (P) has exactly one global minimizer x2D. Due to Theorem 4.1, x2 ðx~þ12Mð2sÞÞ \D. Moreover, by Theorem 20 in [7, p. 69], there exist Lagrange multipliers 00, 10,. . .,m0, not all zero, such that

020@fðxÞ þ1@g1ðxÞ þ þm@gmðxÞ þNðxjCÞ, igiðxÞ ¼0, i¼1,. . .,m,

where06¼0 if (5.9) is fulfilled. This yields (5.8) since@f(x)¼{2Axþb}.

Downloaded by [Selcuk Universitesi] at 13:04 26 January 2015

Tài liệu tham khảo

Tài liệu liên quan

II. Complete the second sentence so that it has a similar meaning to the first sentence, using the word given. Do not change the word given... a) I waited for him until 6.30 and

Disables: - Students will be able to review suggesting activities and saying where they want to