Farkas alternative and Duality Theorem
There are theorems, called alternatives. They say that there are two and only two possibilities for
something, one of these possibilities must take place, and they can’t happen together. An example of an
alternative is, assuming that there is no state between life and death: a human being is alive or dead.
One side of the alternative, say alive, is called the obverse, and the other, in this case dead, the reverse.
In computer science, they use the word xor for exclusive or. Namely Mary xor Jane means Mary or
Jane, but not the two of them.
This set of notes proves one such theorem, called the Farkas alternative and shows that, in fact, it
underpins all the duality theory of linear programming. It underlies, in fact, most of optimisaiton, itself
being a particular case of the Separating Hyperplane Theorem.
First, some definitions (strictly speaking unnecessary, but de bon ton).
Cones. A set C ⊆ R
n
is called a cone if for any x ∈ C, one has λx ∈ C for all λ ≥ 0. This means that
the origin O is in C and, geometrically, if any x = 0 is in C, then the whole ray Ox is in C. With such a
general definition, a cone is not necessarily a closed or convex set.
Exercise: Later we shall deal with the notion of the dual cone. Namely, if C is any cone in R
n
, it dual
cone C
∗
is defined as C
∗
= {y ∈ R
n
: y · x ≥ 0, ∀x ∈ C}. Geometrically C
∗
contains all vectors y, such
that the angle between y and any vector x ∈ C is ninety degrees or less. From this point of view, it is
clear that (C
∗
)
∗
= C, so the dual of the dual is primal. Show this by definition.
If A is an m × n matrix, consider the set
C
A
= {y ∈ R
m
: y = Ax, x ∈ R
n
+
}.
Recall that R
n
+
means x ≥ 0. This set represents a closed convex cone, which is built on the columns
a
1
, . . . a
n
∈ R
m
of A. The reason it is closed and convex is simply because R
n
+
is a closed and convex
set, and C
A
is obtain from it via a linear transformation.
Now let A be a m × n matrix and b ∈ R
m
.
Theorem (Farkas alternative): One and only one of the following two cases is always true: Ax = b has
a solution x ∈ R
n
, x ≥ 0, xor there exists y ∈ R
m
, such that A
T
y ≥ 0 and y · b < 0.
Proof: Either b ∈ C
A
or not. If yes, then b = Ax for some x ≥ 0, by definition of C
A
.
If not, then we can apply the Separating Hyperplane Theorem. The two sets C
A
and {b} are closed
and convex and the latter set is b ounded. Then there exists a hyperplane that strictly separates these
two sets. I.e. for some y ∈ R
m
, β ∈ R, the equation of the hyperplane itself is y · z + β = 0, and for all
z ∈ C
A
, one has y · z + β > 0, while y · b + β < 0. Note that y is the normal vector to the hyperplane,
and z ∈ R
m
is a variable.
To get more info about y and β, let us try now some sp ecial points z from C
A
. First off, 0 ∈ C
A
, so
try z = 0. This implies, y · 0 + β > 0, hence β > 0. Therefore, y · b < 0. Now try z = M a
j
, where a
j
is the jth column of A, and M > 0 is a huge real. (For what x ≥ 0 do we have Ma
j
= Ax?) It follows
that for all j:
y · a
j
≥ −
β
M
, for any M > 0.
Passing to the limit M → ∞, we have that for all j, y · a
j
≥ 0, which is the matrix notation is written
exactly as A
T
y ≥ 0.
What if one replaces Ax = b in the obverse of the Farkas alternative by Ax ≤ b? The answer is easy:
add the slack variables. This augments the matrix A to [A I], where I is the m × m identity matrix.
On the reverse side A
T
y ≥ 0 should now apply to the augmented matrix, so it becomes A
T
y ≥ 0 and
Iy ≥ 0. In other words, here is one more formulation.
Farkas alternative, inequality formulation: One and only one of the following two cases is always true:
Ax ≤ b has a solution x ∈ R
n
+
, xor there exists y ∈ R
m
+
, such that A
T
y ≥ 0 and y · b < 0.
There is yet another interesting formulation that we’ll meet later speaking about Lagrange multipliers.
It bears a name of its own, the Fredholm alternative. It is obtained by changing the obverse of Farkas,
removing the non-negativity claim on x.
1
资源评论
星海浮生
- 粉丝: 196
- 资源: 10
最新资源
- MinGW-64 的 DirectX Headers 副本 .zip
- 基于图像分类的工业缺陷检测项目（视频讲解+代码）.zip
- MinGW,Zig 的 DirectX 12 标头，使用 Zig 等交叉编译 DX12,Metal,etc .zip
- AI指令合集-根据热点话题生成故事文案指令
- MinGW w32api 标头的替代 DirectX 标头.zip
- （Vim）mamba-ssm-1.1.1-cp310-cp310-win-amd64.whl
- mall项目是一套电商系统，包括前台商城系统及后台管理系统，基于SpringBoot+MyBatis实现，采用Docker容器化部署 前台商城系统包含首页门户、商品推荐、商品搜索、商品展示、购物车、
- 通信原理实验：PCM编译码
- java毕业设计-基于SSM的二手市场平台【代码+论文+PPT】.zip
- 同步代码工具，主要应用于git中
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
