Linear Algebra Formula Sheet
ADVERTISEMENT
1
2Formula sheet for optimization SF1811/31/41, 2012
Linear Algebra
(A) =
(A )
(A ) =
(A)
(A) =
(A )
(A ) =
(A)
Simplex method for linear programming problems in standard form:
Let A = [ a
a
], A = [ a
a ],
1
1
A ¯ b = b
A y = c
r = c
y A
Stop if r
0. Otherwise, take
such that r
is the most negative component of r .
A ¯ a
= a
¯ b
¯ b
max
Stop if ¯ a
0. Otherwise find
such that
= min
¯ a
0 =
¯ a
¯ a
New basic tuple is taken as
= (
).
1
1
+1
Primal problem and its dual problem (in general form):
minimize c
x
+ c
x
maximize b
y
+ b
y
1
2
1
2
1
2
1
2
s.t. A
x
+ A
x
b
s.t. A
y
+ A
y
c
11
1
12
2
1
1
2
1
11
21
A
x
+ A
x
= b
A
y
+ A
y
= c
21
1
22
2
2
1
2
2
12
22
x
0
x
free
y
0
y
free
1
2
1
2
Network flow problem:
(Simplex multipliers)
=
for spanning tree edges (
).
(Reduced costs)
=
(
) for non-spanning tree edges (
)
Transportation problem:
(Simplex multipliers)
=
for basic variables (
).
(Reduced costs)
=
(
) for non-basic variables (
)
Quadratic optimization problems:
1
(x) =
x Hx + c x +
, with H symmetric.
0
2
(
)
min (x)
(ˆ x ) = Hˆ x + c = 0
min
(x)
(
)
=
s.t. Ax = b
Nullspace method: A¯ x = b, ˆ x = ¯ x + Zˆ v , and (Z HZ)ˆ v =
Z (H¯ x + c).
H
A
ˆ x
c
Lagrangian method:
=
A
0
ˆ u
b
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education