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
资源评论
星海浮生
- 粉丝: 197
- 资源: 10
最新资源
- 并联P3+AMT混合动力车辆建模与性能计算分析，电机在变速箱后，利用Simulink建模，采用成熟软件架构，考虑发动机，变速箱挡瞬态变化，蓄电池模型包含初始化文件，整车模型，以及说明文档等 可用于计
- 中微无感BLDC商用方案替代STM 昂宝: Mcu:中微cms32m5533 体积小适合紧凑型产品 采用adc方案，脉冲定位，直接闭环+失败重启，面对不同负载启动速度极快，成功率高，还具有运行中再次
- 四波混频(FWM)-光纤通信四波混频仿真 matlab代码 多个文件共约几千行，含文件开头注释 波分复用系统 简并条件下 四波混频 非线性效应 增益随波长变图 可跑通 运行结果如图1
- 大厂的PFC+T型三电平逆变仿真模型 ups仿真模型
- 双馈风电机组四机两区域 三机九节点 惯量 转子动能控制 桨距角控制 减载控制调频 结合储能调频
- 纯verilog逻辑udp，arp,imcp千兆网万兆网，支持各种fpga 平台 送仿真文件
- comsol sofc错流式（交叉流）固体氧化物燃料电池 基于仿真软件comsol探究了错流式SOFC的内特性，考虑了传热传质下的SOFC内特性，电池片的厚度来自于实际电池SEM扫描结果，输出结果包括
- 损耗和增益实现非厄米拓扑态的计算代码
- 永磁同步电机参数辨识模型，在线辨识，离线辨 机械参数在线离线，电气参数在线离线 永磁同步电机模型预测控制仿真，三矢量，双矢量，占空比 滑模控制，SMC，滑模抖振削弱，模糊滑模，动态滑模，高阶滑模
- 基于混合模型磁链观测器的异步电机 感应电机矢量控制 混合模型磁链观测器集合了电压模型和电流模型磁链观测器的优势，实现在全速范围内较为准确地观测转子磁链 仿真验证了混合模型磁链观测器的优越性
- 光储蓄电池交直流微电网控制(恒压&下垂&同步)恒压控制，下垂控制，同步VSG 仿真使用视频讲解 研究内容:在直流微电网的基础上进行改进，组成了交直流微电网控制 优势：该模型可以继续在该基础上拓展，比如
- Comsol 磁力耦合，磁弹性体在磁场作用下发变形仿真
- xilinx fpga GTX收发器实现 SDI视频信号接收及发送，已将GTX IP一起封装成网表，使用起来非常方便，接口清晰明了
- 永磁同步电机SVPWM双闭环滑膜控制矢量控制仿真模型
- 基于MPC的智能车运动预测和控制算法 Motion predication; Kinematic model . MATLAB coding . 加入求解步骤进而得到自定义成本函数的可扩展
- 永磁同步电机瞬态场仿真 永磁同步电机，直流电机双闭环，双馈异步电机 变频器，曲线拟合，三相整流，电机控制，电机调制， SVPWM ，直接转矩控制
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
