CS代考 COMP3530 Discrete Optimization

COMP3530 Discrete Optimization
Week 1: Background and Introduction
Julian of Computer Science University of Algebra Refresher

Scalars, Vectors, and Matrices
Def.: A scalar ↵ 2 R is a real number. O
✗=2or ✗=2.5
Def.: A (column) vector a 2 Rn is sequence of n scalars. Def.: A matrix A 2 Rm⇥n is an m ⇥ n table of scalars.
000e
If
a= [¥,] as= 1-7
A-[
An _ – 8
= [644 a:-[d) a:-[I]a:[
1

–
Multiplication and Dot Product
Def.: If↵2RandA2Rm⇥n then↵A2Rm⇥n. Def.: Ifa,b2Rn thena·b2R.
OO
Def.: IfA2Rm⇥p andB2Rp⇥n thenAB2Rm⇥n.
B=✗A
n
Bij= ✗ bi
a.
Ca,b>= a•b
6 A B =
=
i=1
[÷}[B. Bz – – – Bno] ai
9in
-3
(AB )ij=a;” 2

Linear Independence and Vector Spaces
Def.: VectoXrs x1, x2, . . . , xk 2 Rn are linearly independent (LI) if n
↵ixi =0 =) ↵i =0 8i=1,…,n. i=1
Def.: The span of S = {x1,.X..,xk} is the vector space (k)
span(S)= ↵ixi :8↵2Rk . i=1
= L: ]
basis of 4117 . It ] } is { I :] }
2.I:]+ c-it:] A
3

Basis and Rank
Def.: T ✓S isabasisofS if: 1. span(T) = span(S)
2. T are LI
Def.: The rank of S is the cardinality of its bases.
AY bases for a given set s have the same cardinality rank (1113,1-41) – i
4

Matrix Fundamental Subspaces
Def.: The four fundamental vector subspaces A 2 Rm⇥n are:
– [
An]
1. Column space: span(A)
2. Row space: span(AT )
3. Nullspace: ker(A)={x2Rn :Ax=0}
}
—
[A.Az.– An]
[ Aiki É=i
=
..
.
Sloan (
An
4.Leftnullspace:ker(AT)= y2Rm:ATy=0 n
)
{Ar Az ,
A-* =
[ ÷: ] =
✗~ ”
Sloan (A) I IR”
Ker (Ai) EIR Ker(A)ER”
→ Sloan(Ai)C- IR” ←
5

Fundamental Theorem of Linear Algebra
Thm.: For any matrix A 2 Rm⇥n:
1. rank(A) = rank(AT )
2. rank(A) + rank(ker(AT )) = m 3. rank(AT ) + rank(ker(A)) = n
Coro.: LetA2Rm⇥n andb2Rm,thesystemAx=bhasa solution if b 2 span(A). And the solution in unique if rank(A) = n.
A-✗= 6 ✗
=6
A (✗ -2-1=0 and X- Z=/0
A
2-
6

Introduction to Optimization

Optimization Problem
Def.: An optimzation problem is a pair (F , f ) where
1. F is the set of feasible solutions
2. f : F ! R is the objective function
Theobjectiveistofindx2Fsuchthatf(x)f(x) 8y2F.
Ex Minimum weight Spanning Tree
:
Problem
: 6=14 E)
E → IR
capacity
[ wle) 1- c- If-(t) Feet
{TEE : T is connected & Tis
_-
}W : value
=
acyclic
→ Wii size
→ bi Ewisw }
:
5-
knapsacki
n
]
items
:
W
5-
(f)
=-
if -1
7
}
Et:c, Ebi
in
=✗
.-
:
e- c-✗

Linear Programming
Def.: A linear program is an optimization problem
minimizec·x subject to Ax b x 2 Rn
5-=/✗ c-R!Ax> b)
f-G) = : Xiii how much to spend on
c . ✗
FB Ti
16 reached
defined by A 2 Rm⇥n,b 2 Rm,c 2 Rn. Tx YFB ”
CLFDXFB-1
t
bit
✗oo : min ✗ +✗ ✗
how much to stand on
ri rotFBI Ari ✗it 1- Goo✗,,
✗it ✗eo?0 ,
a,→=
audience
by $ stent in TT
– ✗it
?-
✗FB+ ✗pg SbFB-16 8

Polyhedra
Def.: ApolyhedronisasetP={x2Rn :Axb}definedby A2Rm⇥n andb2Rm.
a-2
P = }(✗ i ,✗z) :
→
,
,
I
a,, ✗it9,2✗iz Zb,
+922 ✗ iz ? bz } :.-9
Az, ✗ .
:÷_÷:
‘E
–
←
C. ✗
‘
–
a
–
,
¥.-
-✗
,
.9
.
.

Extreme Point
Def.: A x 2 P is an extreme point if @ y,z 2 P x and 2 (0,1) such that x = y + (1 )z.
y .
2-
10

Vertex
Def.: A x 2 P is an vertex if 9c 2 Rn such that c · x < c · y for all y 2 P x. C- X ' i ' : 11 Basic Feasible Solution Def.:Ax2Rn suchthatajTx=bj implies ajT y = bj for all j. If additionally x 2 P then we say that x is a basic feasible solution. É€→= 12 Equivalence Thm.: Let P be a polyhedron and x 2 P. The following are equivalent a) x is an extreme point b) x is a vertex c) x is a basic feasible solution 13 Equivalence: Vertex ! Extreme Point Def.: A x 2 P is an extreme point if @ y,z 2 P x and 2 (0,1) such that x = y + (1 )z. Def.: A x 2 P is an vertex if 9c 2 Rn such that c · x < c · y for all y 2 P x. Since ✗ is a vertex we know that t c. ✗ = c. (dy+ G-d)7)= d c.yt G-d)c.2- yep - + Suppose ✗ is not EP⇒ F ✗= dy+G-d)2- Fc : c.✗ ✗ c.✗ + G-d)c. ✗
=
C.✗
contradiction !☐ 14

Equivalence: Extreme Point ! Basic Feasible Solution
Def.: A x 2 P is an extreme point if @ y,z 2 P x and 2 (0,1) such that x = y + (1 )z.
Def.:Ax2Rn suchthatajTx=bj implies ajT y = bj for all j. If additionally x 2 P then we say that x is a basic feasible solution.
Suppose
✗
i s
not
B F S l e t y b e f=✗te (Y- e)EP
t h e
counter
example
⇒
7c->o
:
=D✗=
t¥
() contradiction
P
9- i
✗- C 4-x c-
☐
15

Equivalence: Basic Feasible Solution ! Vertex
Def.: A x 2 P is an vertex if 9c 2 Rn such that c · x < c · y for all y 2 P x. Def.:Ax2Rn suchthatajTx=bj implies ajT y = bj for all j. If additionally x 2 P then we say that x is a basic feasible solution. Letc= [ai⇒ I i c- I are tight constr. c.✗= Eai•✗= 2-bi [ I IE I e. c- ai. 's>Eti IE I
where
I={i•✗= } J
:
c.Y=
ai bi IGI
because ✗ is BFS ☐
16

Polyhedra in Standard Form
Def.: A polyhedron P is in standard form if it has the following definition
P ={x 2Rn :Ax =b,x 0} where A 2 Rm⇥n has linearly independent rows.
forms to standard form ✗ so }
ye Rh
IÑ”A=b✗ } {(×y)c- :✗-Y70,470
We c a n of ✗c-
reduce
other
”
A
36
=/
IR
:
✗
introduce
,
P
.
-,,
17

Administratrivia

Announcements
• Tutorials starts on Week 2
• Lecture notes are available in Ed (resource tab) • Assignment 1 will be out today!
• available in Ed (resource tab) • due on August 27
• submission is via Gradescope
18

Related Posts