【运筹学】对偶理论 : 最优性定理、强对偶性

简介: 【运筹学】对偶理论 : 最优性定理、强对偶性

文章目录

一、最优性定理

二、强对偶性





一、最优性定理


最优性定理 :


如果 X 0 \rm X^0X

0

 是 原问题的可行解 , Y 0 \rm Y^0Y

0

 是 对偶问题的可行解 ,


并且 两个可行解对应的目标函数值相等 , 即 C X 0 = B Y 0 \rm CX^0 = BY^0CX

0

=BY

0

 , 即 z = w \rm z = wz=w ,


则 X 0 \rm X^0X

0

 是原问题的最优解 , Y 0 \rm Y^0Y

0

 是对偶问题的最优解 ;



两个互为对偶的线性规划问题 , 只要有一个有最优解 , 另一个也有最优解 ;


最优解 首先是可行解 , 其次该可行解使目标函数达到最优 ( 最小值 / 最大值 ) ;



互为对偶的两个问题 :


原问题的目标函数求最大值 , 该值不断增大 , 处于一个界限值下方 ; 其最大值就是界限值 ;


对偶问题的目标函数求最小值 , 该值不断减小 , 处于一个界限值上方 ; 其最小值就是界限值 ;


当上述 X 0 \rm X^0X

0

 是 原问题的可行解 , Y 0 \rm Y^0Y

0

 是 对偶问题的可行解 ,


如果 C X 0 = B Y 0 \rm CX^0 = BY^0CX

0

=BY

0

 , 则说明 C X 0 = B Y 0 = 界 限 值 \rm CX^0 = BY^0 = 界限值CX

0

=BY

0

=界限值 , 当前的目标函数值就是界限值 ;


该界限值就是 原问题 目标函数的最大值 , 同时也是 对偶问题目标函数的最小值 ;






二、强对偶性


强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;


目录
相关文章
|
7月前
|
机器学习/深度学习 算法 搜索推荐
【机器学习】凸集、凸函数、凸优化、凸优化问题、非凸优化问题概念详解
本文解释了凸集、凸函数、凸优化以及非凸优化的概念,并探讨了它们在机器学习中的应用,包括如何将非凸问题转化为凸问题的方法和技术。
878 0
|
10月前
|
机器学习/深度学习 人工智能 算法
上升到人生法则的贝叶斯理论
贝叶斯定理在数据分析、机器学习和人工智能等领域有广泛的应用。贝叶斯定理(Bayes' theorem)是一种用于计算条件概率的重要定理,它基于条件概率的定义,描述了在已知某一条件下,另一个条件发生的概率。
|
10月前
|
机器学习/深度学习 存储 人工智能
一阶优化算法启发,北大林宙辰团队提出具有万有逼近性质的神经网络架构的设计方法
【4月更文挑战第19天】北京大学林宙辰团队在深度学习领域取得突破,提出基于一阶优化算法的神经网络设计方法,构建具有万有逼近性质的模型,提升训练速度和泛化能力。该方法利用一阶导数信息,高效处理大规模问题。虽然面临非光滑优化和收敛速度挑战,但团队通过正则化和自适应学习率等策略进行改进,相关研究在多个标准数据集上表现出色。
129 1
|
机器学习/深度学习 算法 决策智能
凸优化介绍
凸优化介绍。更多文章请关注我的微信公众号:Python学习杂记
248 0
|
算法 调度
融合多策略的萤火虫算法求解多目标优化问题(Matlab代码实现)
融合多策略的萤火虫算法求解多目标优化问题(Matlab代码实现)
190 0
凸优化理论基础3——凸集和凸锥重要例子
凸优化理论基础3——凸集和凸锥重要例子
984 0
凸优化理论基础3——凸集和凸锥重要例子
凸优化理论基础2——凸集和锥
凸优化理论基础2——凸集和锥
414 0
凸优化理论基础2——凸集和锥
【运筹学】对偶理论 : 互补松弛性 ( 定理内容 | 定理证明 )
【运筹学】对偶理论 : 互补松弛性 ( 定理内容 | 定理证明 )
1167 0
【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )
【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )
1101 0