Linearly independent vectors are also affinely independent.

(1)

Affine sets ¨î |9½+Ë Linear Inequality Systems

Definition 6.12

The vectors v₁, v₂, . . ., v_k are affinely independent if v₂− v1, . . ., v_k− v1 is linearly independent; affinely dependent, otherwise.

We first check the subtracting vector is irrelevant in the definition: v2− v1, v3− v1, . . ., vk− v1are linearly independent ⇔ v1− v2, v3− v2, . . ., vk− v2are linearly independent ⇔ · · · . (Check it.) It is also easy to see that affine

independence is invariant with a translation.

Proposition 6.13

The vectors v1, v2, . . ., vk are affinely independent only λ = 0 satisfies the following. The converse is also true.

λ1v1+ · · · + λkvk = 0

λ1+ · · · + λk= 0. (6.15)

(6.15) is equivalent to that the following vectors are linearly independent.

v1

1

,

v2

1

, · · · ,

vk

1

.

(2)

Exercise 6.14

Linearly independent vectors are also affinely independent.

If we translate, by w / ∈ S, a basis of a subspace S, and add w to it, then the resulting set is a set of affinely independent vectors. Therefore, the maximum number of affinely independent vectors from S + w is ≥ dim(S) + 1. But it can not exceed dim(S) + 1 (why?).

Proposition 6.15

The maximum number of affinely independent vectors in S + w is dim S + 1.

Optimization Lab. 25th March 2018 43 / 50

(3)

FYIÃÐ¦

Let L and L − w with w ∈ L, respectively, be an affine space and its subspace.

Then {v1, v2, . . ., vk} ⊆ L ⇔ {v2− v1, . . ., vk− v1} ⊆ L − w.

Example 6.16

In the figure, v1, v2, v3 are linearly as well as affinely idependent. Also 0, v2− v1, v3− v1 is affinely independent but not linearly independent.

(4)

FYIÃÐ¦ Proposition 6.17

If an affine space does not contain the origin, its affinely independent vectors are linearly independent. (Therefore, their maximum number is the same as the dimension of the subspace plus 1.)

Proof: Let’s consider a subspace S and an affine space S + w for some w /∈ S.

Assume v1, v2, . . ., vk are affinely independent vectors in S + w and α1v1+ α2v2 + · · · + αkvk = 0. Then

α₁(v₁− w) + α2(v₂− w) + · · · + αk(v_k− w) = −(α1+ · · · + α_k)w. (6.16) While v1− w, . . ., vk− w are in S, w is not. Therefore (6.16) is possible only if α1 + · · · + αk = 0. Since vi’s are affinely independent, we have, by Exercise 6.13, α1= · · · = αk = 0.

Definition 6.18

The dimension of an affine space L is defined to be the maximum number of affinely independent vectors from L minus 1.

(5)

FYIÃÐ¦

Suppose w1, · · · , wk are affinely dependent vectors. Then there is β = (β1, . . ., βk) 6= 0:

β1w1+ β1w1+ · · · + βkwk= 0, β1+ β2+ · · · + βk = 0. (6.17) We may assume β₁6= 0. Then, if we write µi:= −β_i/β₁, (6.17) becomes

w1= µ2w2+ · · · + µk+1wk+1, µ2+ · · · + µk+1= 1

(6.18)

Hence w₁ is an affine combination of w₂, . . ., w_k. We can see that Proposition 6.19

The vectors w1, · · · , wk are affinely dependent if and only there is i such that wi

is an affine combination of the others.

(6)

FYIÃÐ¦

A subspace S is the set of linear combinations of a maximal linearly independent set of vectors it contains. Likewise, an affine set L is the set of affine

combinations of a maximal affinely independent set of vectors it has.

Proposition 6.20

A k-dimensional affine set is the set of affine combinations of its (k + 1) affinely independent vectors.

Definition 6.21

The dimension of a convex set is defined to be the the maximum number of its affinely independent vectors minus 1.

(7)

Valid inequalities Linear Inequality Systems

Definition 7.1

Valid inequalities ({©ôÇ ÂÒ1pxd) If the half space {x : a^Tx ≥ b} includes S, a^Tx ≥ b is called a valid inequality for S.

Valid inequality and supporting hyperplane Definition 7.2

Supporting hyperplanes (]X¨î) If a^Tx ≥ b is valid for S and S ∩ {x : a^Tx = b} 6= ∅, H = {x : a^Tx = b} is called a supporting hyperplane of S.

(8)

Definition 7.3

Separating hyperplane (ìroí¨î) H = {x : a^Tx = b} is called a separating hyperplane of a set S ⊆ Rⁿ and a point z ∈ Rⁿ− S if a^Tx ≥ b is valid for S but not for z.

A separating hyperplane of S and z.

(9)

Theorem 7.4

Separating heperplane theorem (ìroí¨î&ño) If S is a closed set and z /∈ S, then there is a separating hyperplane of z and S.

The theorem implies that any closed convex set C is the intersection of the half spaces separating C and the points not in C.

We can prove Farkas Lemma by using Separating hyperplane theorem.

(10)

Polyhedra,

Polyhedra

Optimization Lab.

IE department Seoul National University

23rd April 2018

Optimization Lab. 23rd April 2018 1 / 38

(11)

Polyhedra Polyhedra,

Definition 1.1

We call the feasible solution set of a linear system Ax ≥ b (A ∈ R^m×n) a polyhedron. In other words, a polyhedron is the intersection of a finite number of half spaces.

A =







0 3 2

0 −3 2

2 0 3

2 0 −3

3 2 0

−3 2 0

0 −3 −2

0 3 −2

−2 0 −3

−2 0 3

−3 −2 0

3 −2 0





 , b =





 5 6 5 4 5 5 6 5 6 5 4 6





 .

Dodecahedron ( 12 ^) - from “The representation of polyhedra by polynomial inequalities” M Gr¨otschel and M. Henk, (2004).

(12)

Regular dodecahedron (& ñ 12 ^ )

φ =

¹⁺

√5

2

, α > 0,

±φ

²

x ± φy ≤ α,

±φ

²

y ± φz ≤ α,

±φ

²

z ± φx ≤ α.

(13)

A polyhedron P is said to be bounded if it does not contain any half line (or unbounded ray), or equivalently if P has vector lower and upper bounds: there are l, u ∈ R

ⁿ

such that P ⊆ {x : l ≤ x ≤ u}.

If every point of P = {x|Ax ≥ b}

satisfies an inequality A

i·

x ≥ b

i

for some i with equality, we call it an implicit equality. The subsystem of implicit equalities of Ax ≥ b is called the implicit equality subsys- tem and denoted by A

⁼

x ≥ b

⁼

.

Exercise 1.2

There is a point of P satisfying each of the remaining subsystem with

strict inequality, “>.”

(14)

Lemma 1.3

If an affine set L ⊆ Rⁿ has a point u satisfying D^Tu > d, then L and L ∩ {x : D^Tx ≥ d} has the same dimension.

Proof: By the assumption, there is > 0 such that every point of L ∩ B(u) satisfies D^Tx ≥ d.

(The figure shows the case when Dx ≥ d is a^Tx ≥ β.) Let v1, v2, . . ., vk be affinely independent vectors in L. Since L is affine and hence closed under translation between its points, the following vectors are also in L: u, u +₂_kv^v²^−v¹

2−v1k, . . ., u + ₂_kv^v^k^−v¹

k−v₁k. They are also affinely independent vectors each contained in L ∩ B(u).

This implies L and L ∩ {x : D^Tx ≥ d} have the same dimension.

Proposition 1.4

P has the same dimension as the affine set A⁼x = b⁼: dim(P ) = n − r(A⁼).

(15)

Faces Polyhedra,

Definition 2.1

By a face of a polyhedron P , we mean its intersection with a supporting hyperplane.

}.

^◦

x ≥ b

^◦

is satisfied with >. Thus any point of P satisfying c

^T

x = δ is also in F : F ⊇ P ∩ {x : c

^T

x = δ}.

Assume c 6= 0 so that c

^T

x = δ is a hyperplane. Then by definition F is a face of P . For the case when c = 0, see Exercise 2.3.

(17)

Faces Polyhedra,

Exercise 2.3

Complete the proof for the case c = 0 (so that δ = 0). (Hint: P is a face.)

A face subsystem is, however, not unique in general. Furthermore even

their ranks can be different. In the left figure, the subsystems {a

₁

x ≥ b

₁

,

a

2

x ≥ b

2

} and {a

₃

x ≥ b

3

} determine the same face F . In the right, the

0-dimensional face F has the determining subsystems of rank 1, 2, and 3.

(18)

^◦

obtained by merging all the face subsystems of a face F is called the maximum face subsystem of F .

By definition, for any inequality not in its maximum face subsystem, F has a point satisfying it with strict inequality. Therefore, the dimension of F is the same as the dimension of the affine set A

^◦

x = b

^◦

: dim(F ) = n − r(A

^◦

).

(19)

Faces Polyhedra,

Example 2.5

The maximum subsystem of the top extreme point has five inequalities,

each set of three inequalities from which is also a face subsystem of it.

(20)

Faces Polyhedra,

Assume Ax = b has a solution.

Recall

Exercise 9.2 that if c

^T

increases the rank of A, the system Ax = b, c

^T

x = d has a solution. Otherwise, Ax = b, c

^T

x = d has either no solution or the same solution set as Ax = b.

Let F and F

⁰

be the faces of P having A

^◦

x ≥ b

^◦

and A

^◦◦

x ≥ b

^◦◦

^◦◦

) since, otherwise, the solution set does not change or is empty. Thus we have proved the

following proposition.

Proposition 2.6

Suppose two faces F and F

⁰

of a polyhedron satisfy F ( F

⁰

. Then dim(F ) < dim(F

⁰

).

(21)

Some “typical” arguments Faces Polyhedra,

1 If a face F of P (or P itself) has at the same time the points satisfying its constraint a^Tx ≥ β with = and >, then F⁰ := F ∩ {a^Tx = β} is a face of P such that F⁰ ( F .

2 Consider a face F (F can be P itself) and ¯x any point of F . Take any straight line passing through ¯x. Suppose there is the last point ¯z of P on the line. Then there should be a constraint a^Tx ≥ β which ¯z satisfies with equality and the later points on the line will violate.

If ¯x 6= ¯z, we have a^Tx > β (since¯ if a^Tx = β, the hyperplane a¯ ^Tx = β includes the whole line.)

Therefore, from 1, we get a face F⁰ := F ∩ {a^Tx = β} ( F .

Therefore, if a face F (or P ) contains no face among its proper subsets, it should include every line passing through two distinct point of it. Namely, F (or P ) is an affine set.

Linearly independent vectors are also affinely independent.

Exercise 6.14

Linearly independent vectors are also affinely independent.

If we translate, by w / ∈ S, a basis of a subspace S, and add w to it, then the resulting set is a set of affinely independent vectors. Therefore, the maximum number of affinely independent vectors from S + w is ≥ dim(S) + 1. But it can not exceed dim(S) + 1 (why?).

Proposition 6.15

The maximum number of affinely independent vectors in S + w is dim S + 1.

Polyhedra

Optimization Lab.

23rd April 2018

Regular dodecahedron (& ñ 12   ^ )

φ =

, α > 0,

±φ

x ± φy ≤ α,

±φ

y ± φz ≤ α,

±φ

z ± φx ≤ α.

A polyhedron P is said to be bounded if it does not contain any half line (or unbounded ray), or equivalently if P has vector lower and upper bounds: there are l, u ∈ R

such that P ⊆ {x : l ≤ x ≤ u}.

If every point of P = {x|Ax ≥ b}

satisfies an inequality A

x ≥ b

for some i with equality, we call it an implicit equality. The subsystem of implicit equalities of Ax ≥ b is called the implicit equality subsys- tem and denoted by A

x ≥ b

.

Exercise 1.2

There is a point of P satisfying each of the remaining subsystem with

strict inequality, “>.”

Definition 2.1

By a face of a polyhedron P , we mean its intersection with a supporting hyperplane.

If there is an implicit equality a

x ≥ β, H = {x| a

x = β} is a supporting hyperplane which includes P . Hence P itself is a face. By a proper face, we mean a face other than P .

Proposition 2.2

Face-subsystem proposition (  -Â Òì  r r Û ¼% 7  $ í | 9 ) Let F be a face of P = {x : Ax ≥ b}. Then there is a subsystem A

x ≥ b

of Ax ≥ b such that F = {x ∈ P : A

x = b

}. Conversely, if P ∩ {x : A

x = b

} 6= ∅ for a subsystem A

x ≥ b

, F := P ∩ H is a face of P .

(Will call A

x = b

} in the proposition a face subsystem of F .)

Proof: Let F be a face of P and c

x = d be the supporting hyperplane.

I.e. F = {x ∈ P : c

x = d} and c

x ≥ d for every x ∈ P . This means exactly that F is the set of optimal solutions of LP min{c

x : Ax ≥ b}.

By strong duality, there is dual optimal solution y ≥ 0. Let A

x ≥ b

be a subsystem of Ax ≥ b corresponding to positive components of y. Then by complementary slackness theorem, an element x of P is optimal if and only if A

x = b

. Hence F = {x ∈ P : A

x = b

}.

Conversely, suppose there is a subsystem A

x ≥ b

such that F := P ∩ {x : A

x = b

} 6= ∅. Suppose we have taken the sum of the equations of A

x

= b

to get equation c

x = δ. The equation is satisfied by every element of F and hence F ⊆ P ∩ {x : c

x = δ}.

For the reverse inclusion, consider any x ∈ P − F . Then by definition at least one inequality from A

x ≥ b

is satisfied with >. Thus any point of P satisfying c

x = δ is also in F : F ⊇ P ∩ {x : c

x = δ}.

Assume c 6= 0 so that c

x = δ is a hyperplane. Then by definition F is a face of P . For the case when c = 0, see Exercise 2.3.

Exercise 2.3

Complete the proof for the case c = 0 (so that δ = 0). (Hint: P is a face.)

A face subsystem is, however, not unique in general. Furthermore even

Regular dodecahedron (& ñ 12 ^ )

Face-subsystem proposition ( -Â Òì r r Û ¼% 7 $ í | 9 ) Let F be a face of P = {x : Ax ≥ b}. Then there is a subsystem A