交通 | Introduction to Linear Optimization——Farkas引理及其应用

科技 2024-10-19 20:13 德国

前言

上一节，我们重点关注了标准形式的问题并介绍如何使用对偶单纯形法进行求解。

本节将介绍Farkas引理，并运用对偶理论对其进行简单证明。其后采用几何图形来阐述该定理，并基于此提供了另一种证明方法。最后进一步探讨了Farkas引理在资产定价问题中的应用。

Farkas 引理

考虑线性规划标准形式的一组约束，其中。假设存在某个向量 , 使得且。那么，对于任意，均满足，且由于，可得。由此可知，对于所有，。此论证表明，若存在一个满足和的向量，则标准形式的约束将无可行解，且向量可作为不可行性的证明。由此也引出下面的Farkas引理。

【Farkas引理】

设是一个的矩阵，是一个维的向量。那么，以下两项中有且仅有一个成立：

(a) 存在使得。

(b) 存在向量使得且。

【证明】

若存在满足，且，那么, 这表明第二种情况不可能成立。

假设不存在向量满足，考虑以下两个互为对偶的问题：

\begin{array}{lrl} \operatorname{maximize} &\mathbf{0}^{\prime} \mathbf{x}&\\ \text {subject to} &\mathbf{A}\mathbf{x}&=\mathbf{b}\\ &\mathbf{x}& \geq \mathbf{0},\\ \end{array}

\begin{array}{lll} \operatorname{minimize} &\mathbf{p}^{\prime}\mathbf{b}&\\ \text {subject to} &\mathbf{p}^{\prime}\mathbf{A}& \geq \mathbf{0}^{\prime},\\ \end{array}

其中，最大化问题是不可行的，这意味着最小化问题要么是无界的（最优成本为），要么是不可行的。由于是最小化问题的一个可行解，因此可以推断出最小化问题是无界的。因此，存在一些可行的，满足 , 且其成本为负，即。

下面用几何图形来阐述Farkas引理（见图1）。设是矩阵的列，有。因此，存在一个向量满足，等同于要求向量位于由向量的所有非负线性组合构成的集合中，该集合在图1中用阴影区域表示。若不属于这个阴影区域（此时Farkas引理的第一种情况不成立），直观上认为，存在一个向量和一个与之相关联的超平面使得向量位于超平面的某一侧，而阴影区域位于另一侧，由此可得和（对于所有），或者等价地，，从而Farkas引理的第二种情况成立。

Farkas引理早在线性规划发展之前就已存在，但通过对偶理论可以对其进行简单证明。下一部分将基于前述几何论证提供另一种证明方法。此外，Farkas引理还有如下等价表述。

【推论1】

设和是给定的向量，并假设任何满足的向量也必须满足。那么，可以表示为向量的非负线性组合。

由此引出的定理2具有相似的性质。

【定理2】

设线性不等式至少有一个解，且为某个标量，那么，以下条件是等价的：

(a) 的每一个可行解都满足。

(b) 存在某个向量，使得且。

【证明】

考虑以下两个互为对偶的问题：

\begin{array}{lrl} \operatorname{maximize} &\mathbf{c}^{\prime} \mathbf{x}&\\ \text {subject to} &\mathbf{A}\mathbf{x}&\leq \mathbf{b},\\ \end{array}

\begin{array}{lll} \operatorname{minimize} &\mathbf{p}^{\prime}\mathbf{b}&\\ \text {subject to} &\mathbf{p}^{\prime}\mathbf{A}& = \mathbf{c}^{\prime}\\ & \mathbf{p} &\geq \mathbf{0},\\ \end{array}

若有可行解且每个可行解都满足，那么第一个问题有一个最优解，且最优成本受到的上界限制。根据强对偶理论，第二个问题也有一个最优解，其成本以为界，且满足，以及。

相反地，若某个满足，以及，根据弱对偶定理可得，第一个问题的每一个可行解也必须满足。

Farkas定理在资产定价中的应用

考虑一个在单个周期内运行的市场，其中交易着种不同的资产。根据该周期内的各种事件，期末时会有种可能的自然状态。若投资一美元于某资产，且最终的自然状态为，则将获得的回报。因此，每种资产都由一个回报向量（）来描述，以下是一个的回报矩阵，给出了在种自然状态下种资产的回报:

\left.\mathbf{R}=\left[ \begin{array}{cc} r_{11}&\cdots&r_{1n}\\ \vdots&\ddots&\vdots\\ r_{m1}&\cdots&r_{mn}\\ \end{array}\right. \right]

设为持有的资产的数量，资产组合则是一个向量。资产组合的分量可以是正数或负数，为正值表明已经购买了单位的资产，因此状态发生时，可以获得的回报；为负值表示资产卖出的期货合同：这相当于在期初卖出了单位的资产，并承诺在期末买回。因此，如果状态发生，则必须支付，等同于获得的回报（这里的是负数）。

状态下投资组合带来的收益由下面的式子给出:

\begin{equation} w_{s}=\sum_{i=1}^{n}r_{si}x_{i}. \nonumber \end{equation}

引出向量，可得：

\begin{equation} \mathbf{w}=\mathbf{Rx} \nonumber \end{equation}

设为该周期开始时资产的价格，为资产价格向量，则获得投资组合的成本为。

资产定价中的核心问题是确定价格，为此引入无套利条件：没有任何投资者能通过负向投资获得有保障的非负回报。即，任何投资组合，若在每种自然状态下的回报均为非负值，则其对投资者一定是有价值的，因此其成本一定是非负值。从数学上，无套利条件可以表达如下：

若 \ \mathbf{Rx}\geq 0，则必有\ \mathbf{p'x}\geq 0。

给定一组由回报矩阵描述的特定资产，符合无套利条件的价格具有哪些特点？无套利假设对资产价格施加了哪些限制？Farkas引理给出了答案。

【定理3】

当且仅当存在一个非负向量，使得每种资产的价格满足以下公式时，无套利条件成立。

\begin{equation} p_{i}=\sum_{s=1}^{m}q_{s}r_{si} \nonumber \end{equation}

【证明】

无套利条件表明不存在向量使得且，这与Farkas引理（即定理1）中的条件（b）具有相同的形式。因此，根据Farkas引理，当且仅当存在某个非负向量，满足时，无套利条件成立，这与定理中的条件相同。

定理3表明，只要市场运作效率足够高，以至于可以消除套利可能性时，就一定存在可用于评估现有资产的“状态价格”，即，直观地说，该定理为基本资产确定了一个非负价格，若自然状态为，则资产价值为1美元，否则为0。另外，要求每种资产都必须以一致的价格定价，总价值是由其基本资产价值的总和。一般来说，除非资产数量等于或超过状态数量，否则状态价格向量不唯一。

总结

本节基于对偶理论，探讨了如何确定一个给定的线性不等式系统是否不可行的问题，进而引出Farkas引理及其证明。下一节，我们将展示反向证明的可能性，即从第一原理出发，证明关于分离超平面的一般结果，然后建立Farkas引理，最后从Farkas引理中得出对偶理论。

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

文章作者：交通与优化

责任编辑：江镕行

微信编辑：疑疑

文章转载自『交通与优化』公众号，原文链接：书籍导读 | Introduction to Linear Optimization 第15节：Farkas引理及其应用

关注我们

http://mp.weixin.qq.com/s?__biz=Mzk0ODMwMjMwMA==&mid=2247681441&idx=1&sn=f85dd1d690b4e34f3fce377b4c144f67

运筹OR帷幄

致力于成为全球最大的运筹学中文线上社区

最新文章

供应链｜OR论文精读：在不确定考虑集合下的需求估计

Qaekwy，一个崭新的Python运筹优化库

交通 | Introduction to Linear Optimization——从分离超平面到对偶的反向论证

运筹优化库PyMathProg使用介绍

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.10(3)

交通 | Introduction to Linear Optimization——Farkas引理及其应用

主编推荐 | 当我们求解数学规划问题时，如何区分数学建模和算法设计

供应链｜MnSc论文精读：采用 RSOME 轻松实现稳健的随机优化

【10.19全球美食圆桌交友会纽约站】探讨全球价值洼池：欧洲VS北美？

优化 | 整数规划预求解算法的核心技术：Domain Propagation

全奖｜澳洲阿德莱德大学招收能源系统方向博士

供应链｜POMS论文精读：新产品生产时机内生下的竞争厂商信息共享

COPT里的线性规划与整数规划

服务运营 | POMS: 分销渠道中奢侈品的社会定价

学界|澳大利亚阿德莱德大学招募博士(复杂能源基础设施的稳健解决方案)

服务运营 | 上门配送成本控制：如何通过激励机制优化成本？

FelooPy，一个Python的算法建模集成库介绍

论文速递|Management Science 月9文章合集

除了经典优化问题的求解，利用Pyomo还可以做什么

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.10(2)

读博士，去哪找那么多创新点？水水得了...

最新的几个VRP问题求解的开源工具

优化 | 分块结构整数规划的增广拉格朗日方法：论文详细解读及代码复现

学界招聘|奥地利格拉茨科技大学招募算法与复杂性博士后

优化 | 边缘智能的新时代：端侧大模型的研究进展综述

全奖｜西班牙巴塞罗那招收离散与计算几何专业博士

优化 |『运筹OR帷幄』优化版块2024招新

中国运筹学会数学规划分会第十届研究生论坛第一轮通知

INFORMS 2024 Fellow：表彰拯救生命算法和全球供应链等领域的杰出贡献者

学界招聘|韩国基础科学研究所离散数学小组招募研究员

报道 | 2024年11月-2024年12月国际运筹优化会议汇总

『运筹OR帷幄』招募令 | 期待你的加入

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.10(1)

优化 | 如何判断一个变量是否是冗余的？

一款小型求解器使用介绍

优化 | Gurobi 加速混合整数规划问题求解速度的建议

东南大学交通学院运输与物流工程系董智捷教授团队诚聘硕士、博士、博士后及研究助理

直播预告｜神户大学Yusuke Zennyo：零售竞争与商业模式的多产品视角「Ad OR Talk 11」

【运筹学】硕博申请指导、科研背景提升（限时特惠）

服务运营 | 医疗谣言在社交网络中的传播与控制：一种具有高度不对称网络结构的广义扩散模型

全奖｜年薪20W+，英国华威大学招收多智能体系统及其相关领域博士

架起工业界和学术界的桥梁！『运筹OR帷幄』商务合作指南

『运筹OR帷幄』创新学术成果宣传栏目，为论文插上翅膀

服务运营 | POMS论文精读：特征驱动的鲁棒手术调度

直播预告｜神户大学Yusuke Zennyo：零售竞争与商业模式的多产品视角「Ad OR Talk 11」

优化 | 整数规划预处理 Clique Merge 算法

全奖｜年薪30W+，维也纳技术大学招收人工智能博士

供应链 | 供应链中的后悔效应：解密买方势力下的战略博弈

供应链 | 经典文献解读：报童问题与库存管理中经典模型与优化策略解析

交通 | 基于自适应多图卷积和注意力机制的多模式交通系统短时客流预测模型

分类

时事

民生

政务

教育

文化

科技

财富

体娱

健康

情感

旅行

百科

职场

楼市

企业

乐活

学术

汽车

时尚

创业

美食

幽默

美体

文摘

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉