Numerical Methods and Optimization

200 Numerical Methods and Optimization: An Introduction

where A



F

is a (sparse) matrix with entries in {0, 1, −1}, x =[x

0

,...,x

n

]

T

,

e =[1,...,1]

T

,andc is a vector with the i

th

component c

i

given by c

i

= −|

¯

I

i

|.

Let A

F

be the (m +2n) × (n + 1) matrix, let b

F

be an (n + 1)-vector of

right-hand sides, and let x =[x

0

,...x

n

]

T

be the (n + 1)-vector of variables

that describe the following system of linear constraints in the form A

F

x ≥ b

F

:

A



F

x ≥

3

2

+ c

x

0

− x

i

≥−

1

2

,i=1,...,n

x

0

+ x

i

≥

1

2

,i=1,...,n

≡ A

F

x ≥ b

F

. (9.6)

We will use the following indefinite quadratic functions in the proof. Let

f

1

(x)=

n



i=1

(x

0

+ x

i

− 1/2)(x

0

− x

i

+1/2)

and

f

2

(x)=

n



i=1

(x

0

+ x

i

− 1/2)(x

0

− x

i

+1/2) −

1

2n

n



i