Transcript Linear Programming (Optimization)

Backgrounds-Convexity
 Def: line segment joining two points x1, x 2  R n is the collection of
points x  x1  (1   ) x 2 , 0    1
( x  1 x1  2 x 2 , 1  2  1, 1 , 2  0)
(Generally, x  im1 i x i ,
im1 i  1, i  0 i, called convex combination)
x2
x 2   ( x1  x 2 )  x1  (1   ) x 2
x2
x1
x1
( x1  x2 )
OR-1 2011
1
 Def: C  R n is called convex set iff x1  (1   ) x 2  C
whenever x1  C , x 2  C , and 0    1.
Convex sets
OR-1 2011
Nonconvex set
2
 Def: The convex hull of a set S is the set of all points that are convex
combinations of points in S, i.e.
conv(S)={x: x = i = 1k i xi, k 1, x1,…, xkS, 1, ..., k 0, i = 1k i = 1}
 Picture: 1x + 2y + 3z, i  0, i = 13 i = 1
1x + 2y + 3z = (1+ 2){ 1 /(1+ 2)x + 2 /(1+ 2)y} + 3z
(assuming 1+ 2  0)
z
x
y
OR-1 2011
3
Proposition: Let C  R n be a convex set and for k  R , define
kC  { y  R n | y  kx for some x  C}
Then kC is a convex set.
Pf) If k = 0, kC is convex. Suppose k  0.
For any x, y kC,  x' , y' C such that x  kx' , y  ky'
Then x  (1   ) y  kx' (1   )ky'  k (x' (1   ) y' )
But (x' (1   ) y' )  C , hence k (x' (1   ) y' )  kC

Hence the property of convexity of a set is preserved under scalar
multiplication.
Consider other operations that preserve convexity.
OR-1 2011
4
Convex function
n
 Def: Function f : R  R is called a convex function if for all x1 and
x2, f satisfies
f (x1  (1   ) x 2 )  f ( x1 )  (1   ) f ( x 2 ), 0    1,
Also called strictly convex function if
f (x1  (1   ) x 2 )  f ( x1 )  (1   ) f ( x 2 ), 0    1,
f (x)
1
1
( x , f ( x ))  R
n1
( x2 , f ( x2 ))
f ( x1)  (1   ) f ( x2 )
f (x1  (1   ) x2 )
1
x
OR-1 2011
x
x1  (1   ) x2
x2
5
 Meaning: The line segment joining (x1, f(x1)) and (x2, f(x2)) is above or
on the locus of points of function values.
OR-1 2011
6
 Def: f: Rn  R. Define epigraph of f as epi(f) = { (x, )  Rn+1 :   f(x) }
 Equivalent definition: f: Rn  R is a convex function if and only if epi(f) is
a convex set.
 Def: f is a concave function if –f is a convex function.
 Def: xC is an extreme point of a convex set C if x cannot be expressed
as y + (1-)z, 0 <  < 1 for distinct y, z C ( x  y, z )
(equivalently, x does not lie on any line segment that joins two other
points in the set C.)
: extreme points
OR-1 2011
7
Review-Linear Algebra
2 x1  x2  5 x3  x4  20
x1  5 x2  4 x3  5 x4  30
3x1  x2
 6 x3
 2 x4
2  1 5 1 
A  1 5
4 5


3 1  6 2

 20
 x1 
x 
x   2
 x3 
 
 x4 
20
b  30
 
20
Ax  b in matrix, vector notation
 inner product of two column vectors x, y  Rn :
x’y = i = 1n xiyi
If x’y = 0, x, y  0, then x, y are said to be orthogonal. In 3-D, the
angle between the two vectors is 90 degrees.
( Vectors are column vectors unless specified otherwise. But, our text
does not differentiate it.)
OR-1 2011
8
 Submatrices multiplication
 a11 a12
A  a21 a22

 a31 a32
a13
a23
a33
a14 
 a11

a24  
  A21
a34 
A12 
A22 
 b1 
b 
2   b1 

B

b3   B2 
 
b4 
 a11b1  A12 B2 
AB  

 A21b1  A22 B2 
OR-1 2011
9
 submatrices multiplications which will be frequently used.
 a11 a12
a
a22
A   21
 

am1 am 2
Ax  b   A1
y ' A  y '  A1
y' A   y1
OR-1 2011
A2
a1n 
 a2n 
   A1

 

 amn 

 x1 
x 
 An  2   A1 x1  A2 x2    An xn  nj1 A j x j  b
 x3 
x 
 4
A2  An    y ' A1
y2
 a1' 
 a '
A2  An    2 
  
 
am '
y ' A2  y ' An 
 a1' 
a ' 
 ym  2    y1a1'  y2 a2'    ym am'   im1 yi ai '
  
a ' 
 m
10
1
2
m
1
2
m
 Def: {x , x ,  , x } is said to be linearly dependent if  c1 , c2 ,, cm
1
2
m
, not all equal to 0, such that c1 x  c2 x    cm x  0
1 2
m
( i.e., there exists a vector in {x , x ,  , x } which can be expressed as
a linear combination of the other vectors. )
 Def: {x , x ,  , x } linearly independent if not linearly dependent.
i
m
In other words, i 1 ci x  0 implies ci  0 for all i
1 2
m
(i.e., none of the vectors in {x , x ,  , x } can be expressed as a linear
combination of the remaining vectors.)
 Def: Rank of a set of vectors : maximum number of linearly independent
vectors in the set.
 Def: Basis for a set of vectors : collection of linearly independent vectors
from the set such that every vector in the set can be expressed as a linear
combination of them. (maximal linearly independent subset, minimal
generator of the set)
OR-1 2011
11
 Thm) r linearly independent vectors form a basis if and only if the
set has rank r.
 Def: row rank of a matrix : rank of its set of row vectors
column rank of a matrix : rank of its set of column vectors
 Thm) for a matrix A, row rank = column rank
 Def : nonsingular matrix : rank = number of rows = number of
columns. Otherwise, called singular
 Thm) If A is nonsingular, then unique inverse exists.
( AA 1  I  A 1 A)
OR-1 2011
12
Simutaneous Linear Equations
Thm: Ax = b has at least one solution iff rank(A) = rank( [A, b] )
Pf) ) rank( [A, b] )  rank(A). Suppose rank( [A, b] ) > rank(A).
Then b is lin. ind. of the column vectors of A, i,e., b can’t be
expressed as a linear combination of columns of A. Hence Ax
= b does not have a solution.
 ) There exists a basis in columns of A which generates b. So
Ax = b has a solution.

Suppose A: mn, rank(A) = rank [A, b] = r.
Then Ax = b has a unique solution if r = n.
Pf) Let y, z be any two solutions of Ax = b. Then Ay = Az = b, or Ay –
Az = A(y-z) = 0. A(y-z) = j=1nAj(yj – zj) = 0.
Since column vectors of A are linearly independent, we have yj
– zj = 0 for all j. Hence y = z.

(Note that m may be greater than n.)
OR-1 2011
13

OR-1 2011
14
 Operations that do not change the solution set of the linear
equations
(Elementary row operations)
Change the position of the equations
Multiply a nonzero scalar k to both sides of an equation
Multiply a scalar k to an equation and add it to another equation
X  {x | a1 ' x  b1 , a2 ' x  b2 ,, am ' x  bm }
Y  {x | (a1 'ka2 ' ) x  (b1  kb2 ), a2 ' x  b2 ,, am ' x  bm }
Show that x *  X implies x *  Y ( X  Y )
and x *  Y implies x *  X (Y  X )
Hence X = Y. Solution sets are same.
 The operations can be performed only on the coefficient matrix [A,
b], for Ax = b.
OR-1 2011
15
Solving systems of linear equations (Gauss-Jordan Elimination, 변수의
치환) (will be used in the simplex method to solve LP problems)
x1  x2
 x1  3x2
 4 x3
2 x2
 5 x3
 10
 10
x2
 22


 6 x3
 2 x3
x1
x3
 20
 10

2

x1  x2
2 x2
 4 x3  10
 4 x3  20
2 x2
 5 x3  22
x1  x2
x2
 4 x3  10
 2 x3  10
2 x2
 5 x3  22
OR-1 2011
x1
x2
 8
 6
x3  2
16
 Infinitely many solutions
x1  x2
 x1  3x2
 4 x3  x4
 x4
 10
 10
2 x2
 5 x3  x4
 22
 4 x3
 x4
 4 x3  2 x4
 10
 20
 5 x3
 22
x1
 x2
 2 x2
2 x2
 x4
x1  x2
x2
 4 x3  x4
 2 x3  x4
 10
 10
2 x2
 5 x3  x4
 22
x1
x2
 6 x3  2 x4
 2 x3
 x4
 x3
x1
x2
 x3
x1
x2
 x4
 20
 10

 8 x4
 3x4
 8
 6
 x4
 2
2
 8  8 x4
 6  3x4
 x3  2
 x4
Assign x4  t for arbitrary t and get
x1  8  8t , x2  6  3t , x3  2  t
OR-1 2011
17
x1
x2
 x3
 8  8 x4
 6  3x4
 2  x4
x4 is independent variable and x1 , x2 , x3 are dependent variables.
Particularly, the solution obtained by setting the indepent variables to 0
and solving for the dependent variables is called a basic solution.
Here x1  8, x2  6, x3  2, x4  0
(will be used in the simplex method)
OR-1 2011
18
x1
x2
 6 x3  2 x4
 2 x3
 x4
 x3
x1
x2
 x3
 8 x4
 3x4
 8
 6
 x4
 2
x1  8  8 x4 , x2  6  3x4 , x3  2  x4
 x4
 20
 10

2
x1
x2
 8 x3
 3x3
 x3  x4


24
12
 2
x1  24  8 x3 , x2  12  3x3 , x4  2  x3
Both systems have the same set of solutions, but representation is different
e.g.) x1  8, x2  6, x3  2, x4  0
OR-1 2011
19
 Elementary row operations are equivalent to premultiplying a
nonsingular square matrix to both sides of the equations
Ax = b
x1  x2
 x1  3x2
 4 x3
 10
 10
2 x2
 5 x3
 22
x1  x2
2 x2
 4 x3  10
 4 x3  20
2 x2
 5 x3  22
 1  1 4  x1  10
 1 3 0  x   10

 2   
 0 2 5  x3  22
1
  1  1 4  x1   1
 10
 1 1   1 3 0  x    1 1  10


 2  
 
1  0 2 5  x3  
1 22

 1  1 4  x1  10
 0 2 4  x2   20

   
0 2 5  x3  22
OR-1 2011
20
x1  x2
2 x2
 4 x3  10
 4 x3  20
2 x2
 5 x3  22
x1  x2
x2
 4 x3  10
 2 x3  10
2 x2
 5 x3  22
1
  1  1 4  x1   1
 10
 1 1   1 3 0  x    1 1  10


 2  
 
1  0 2 5  x3  
1 22

1
 1
  1  1 4  x1   1
 1
 10
 1/ 2   1 1   1 3 0  x    1/ 2   1 1  10



 2  

 
1 
1  0 2 5  x3  
1 
1 22

OR-1 2011
21
1
 1
  1  1 4  x1   1
 1
 10
 1/ 2   1 1   1 3 0  x    1/ 2   1 1  10



 2  

 
1 
1  0 2 5  x3  
1 
1 22

1
  1  1 4  x1   1
 10
  1/ 2  0 2 4  x2    1/ 2  20


  
 
1 0 2 5  x3  
1 22

 1
  1  1 4  x1   1
 10
 1/ 2 1/ 2   1 3 0  x2   1/ 2 1/ 2  10


  
 
1  0 2 5  x3  
1 22

OR-1 2011
22
 So if we multiply all elementary row operation matrices, we get the
matrix having the information about the elementary row operations
we performed
x1  x2
 x1  3x2
 4 x3
2 x2
 5 x3
 10
 10
 22

x1
x2
 8
 6
x3  2
7.5 6.5  6  1  1 4  x1  7.5 6.5  6 10
2.5 2.5  2  1 3 0  x   2.5 2.5  2 10


 2  
 
1  0 2 5  x3    1  1
1 22
  1  1
 1 0 0  x1   8
 0 1 0  x2   6

   
0 0 1  x3  2
OR-1 2011
7.5 6.5  6
A1  2.5 2.5  2


1
  1  1
23
 Finding inverse of a nonsingular matrix A.
Perform elementary row operations (premultiply elementary row
operation matrices) to make [A : I ] to [ I : B ]
Let the product of the elementary row operations matrices be C.
Then C [ A : I ] = [ CA : C ] = [ I : B]
Hence CA = I  C = A-1 and B = A-1.
OR-1 2011
24
B 1Ax  B 1b
B 1 A  B 1  A1

A2  An   B 1 A1
B 1 A2  B 1 An

Suppose A  B N  where B : m  m, (nonsingular) N : m  (n  m)

 
Then B1 A  B1B N   B1B B1 N  I
OR-1 2011
B1 N

25