Documentation
Atlas
.
CombinatorialOptimization
.
code
.
LP
.
Farkas
Search
return to top
source
Imports
Init
Mathlib
Imported by
isClosed_nonneg_cone_image
clm_repr
farkas_lemma
source
theorem
isClosed_nonneg_cone_image
{
m
n
:
ℕ
}
(
A
:
Matrix
(
Fin
m
)
(
Fin
n
)
ℝ
)
:
IsClosed
{
b
:
Fin
m
→
ℝ
|
∃ (
x
:
Fin
n
→
ℝ
),
(∀ (
j
:
Fin
n
),
0
≤
x
j
)
∧
A
.
mulVec
x
=
b
}
source
theorem
clm_repr
{
m
:
ℕ
}
(
f
:
(
Fin
m
→
ℝ
)
→L[
ℝ
]
ℝ
)
(
v
:
Fin
m
→
ℝ
)
:
f
v
=
(fun (
i
:
Fin
m
) =>
f
(
Pi.single
i
1
)
)
⬝ᵥ
v
source
theorem
farkas_lemma
{
m
n
:
ℕ
}
(
A
:
Matrix
(
Fin
m
)
(
Fin
n
)
ℝ
)
(
b
:
Fin
m
→
ℝ
)
:
(∃ (
x
:
Fin
n
→
ℝ
),
(∀ (
j
:
Fin
n
),
0
≤
x
j
)
∧
A
.
mulVec
x
=
b
)
↔
¬
∃ (
y
:
Fin
m
→
ℝ
),
(∀ (
j
:
Fin
n
),
0
≤
A
.
transpose
.
mulVec
y
j
)
∧
b
⬝ᵥ
y
<
0