目录

一、Lagrange对偶函数

1.1  Lagrange

1.2  Lagrange对偶函数

1.3最优值的下界

1.4通过线性逼近来理解

1.5例子（暂无）

1.6  Lagrange对偶函数和共轭函数

1.6.1共轭函数定义

1.6.2共轭函数和 Lagrange 对偶函数的关系

1.6.3例子（暂无）

二、Lagrange对偶问题

2.1显式表达对偶约束

2.1.1例1，标准形式线性规划的Language对偶

2.1.2例2，不等式形式线性规划的 Lagrange 对偶

2.2弱对偶性

2.3强对偶性和Slater约束准则

2.4例子（暂无）

2.5矩阵对策的混合策略（暂无）

三、几何解释

3.1通过函数值集合理解强弱对偶性（比较难理解）

3.2在约束准则下强对偶性成立的证明

3.3多准则解释

四、鞍点解释

4.1强弱对偶性的极大极小描述

4.2鞍点解释

4.3对策解释（暂无）

4.4价格或税解释（暂无）

五、最优性条件

5.1次优解认证和终止准则

5.2互补松弛性

5.3  KKT最优性条件

5.3.1非凸问题的KKT条件

5.3.2凸问题的KKT条件

5.4  KKT条件的力学解释（暂无）

5.5通过解对偶问题求解原问题

六、扰动及灵敏度分析

6.1扰动的问题

6.2一个全局不等式

6.3局部灵敏度分析

七、例子（暂无）

八、择一定理（暂无）

九、广义不等式（暂无）

一、Lagrange对偶函数

1.1  Lagrange

其Language函数定义为：

1.2  Lagrange对偶函数

Lagrange对偶函数定义为

1.3最优值的下界

对偶函数构成了原问题(5.1)最优值 p^{*}的下界:即对任意\lambda \succeq 0和\nu下式成立

解释：\lambda等0时，约束范围内的最小值p^{*}当然大于等于全局最小值g(\lambda ,\nu )

           \lambda大于0时，约束范围内的最小值会更小，所以约束范围内的最小值会比原\lambda等0时约束范围内的最小值更小，全局最小值又小于等于约束范围内的最小值，所以这种情况下全局最小值小于p^{*}

1.4通过线性逼近来理解

类似地，I_{0}是集合{0}的示性函数。即

                                                            I_{0}(u)=\begin{cases} 0 & \text{ } u=0 \\ + \infty & \text{ } u\neq 0 \end{cases}

I_{-}(u)和I_{0}(u)可以理解为对约束函数的愤怒或不满，且非常强硬。

将I_{-}(u)和I_{0}(u)用\lambda和\nu代替，就变成了Language函数，由“硬”约束变成了“软”约束。

由\lambda和\nu代替I_{-}(u)和I_{0}(u)而来的Language对偶问题为问题（5.3）提供了一个下界，因为\lambda _{i}u< I_{-}(u)、  \nu _{i}u< I_{0}(u)。

1.5例子（暂无）

1.5.1线性方程组的最小二乘解

1.5.2标准形式的线性规划

1.5.3双向划分问题

1.6  Lagrange对偶函数和共轭函数

1.6.1共轭函数定义

共轭函数和 Lagrange 对偶函数紧密相关。

1.6.2共轭函数和 Lagrange 对偶函数的关系

1.6.3例子（暂无）

1.6.3.1等式约束条件下的范数极小化

1.6.3.2熵的最大化

1.6.3.3最小体积覆盖椭球

二、Lagrange对偶问题

Lagrange 对偶函数给出了优化问题(5.1)的最优值 p*的一个下界。那么Lagrange 对偶函数的最大值就是原问题的最好下界。

所以Lagrange 对偶问题为：

2.1显式表达对偶约束

在Language对偶问题的例子中，Language函数求上界并不是在所有的\lambda \succeq 0都可以求出上界，只有在一定的\lambda和\nu的限制范围内才有上界，因此对于\lambda和\nu，也有约束。

2.1.1例1，标准形式线性规划的Language对偶

所以对偶问题为

该问题等式约束条件为隐式的，写成显示表达对偶约束为：

可进一步简化为

2.1.2例2，不等式形式线性规划的 Lagrange 对偶

Lagrange 函数为

对偶函数为

若线性函数不是恒值，则线性函数的下确界是-\infty，因此上述问题的对偶函数为

显式表达对偶可行的条件并作为约束来重新描述对偶问题：

我们注意到标准形式线性规划和不等式形式线性规划以及它们的对偶问题之间的有趣的对称性，标准形式线性规划的对偶问题是只含有不等式约束的线性规划问题。

2.2弱对偶性

2.3强对偶性和Slater约束准则

2.2和2.3见下文：

【凸优化】Language对偶函数，Language对偶问题，强对偶性，弱对偶性，Slater约束准则（本质剖析）-CSDN博客

2.4例子（暂无）

2.4.1线性方程组的最小二乘解

2.4.2线性规划的Language对偶

2.4.3二次约束二次规划的Language对偶

2.4.4熵的最大化

2.4.5最小体积覆盖椭球

2.4.6具有强对偶性的一个非凸二次规划问题

2.5矩阵对策的混合策略（暂无）

三、几何解释

3.1通过函数值集合理解强弱对偶性（比较难理解）

可以通过集合G

给出对偶函数的简单几何解释。这是一个(m+p+1)维空间点的集合。

       通过集合G可以给出优化问题（5.1）的最优解p^{*}

定义了集合g的一个支撑超平面。超平面的法向量为(\lambda ,\nu ,1)，切点(u_{0},v_{0},t_{0})与法向量的点积为g(\lambda ,\nu )。

以下两幅图可以说明p^{*}\geqslant g(\mu ,\nu )

通过集合G的上镜图来解释

3.2在约束准则下强对偶性成立的证明

下文中定性分析了在约束条件下强对偶性成立：

【凸优化】Language对偶函数，Language对偶问题，强对偶性，弱对偶性，Slater约束准则（本质剖析）-CSDN博客

课本中对提供了这个证明的解析过程。

3.3多准则解释

考虑没有等式约束的优化问题：

它的Language对偶问题与下面这个多准则优化问题的标量化问题有联系：

在标量化的过程中，选择一个正向量\lambda，极小化标量函数\tilde{\lambda }^{T}F(x)；任意最小点都是Pareto最优。由于可以将\tilde{\lambda }以任意正比例缩放而不影响极小化问题，所以不失一般性，可以选择\tilde{\lambda }=(\lambda ,1)。因此，在标量化中，我们极小化函数

而这正是问题(5.43)的 Lagrange 函数。

所以多准则凸优化问题的每个Pareto最优解都是给定某个非负权向量\tilde{\lambda }时函数\tilde{\lambda }^{T}F(x)的最小点，

我们考虑式(4.62)定义的集合A，

这和研究 Lagrange 对偶问题时式(5.37)中定义的集合A 一样。此时，和前面一样所需权向量也是集合在任意一个Pareto最优点处的支撑超平面。在多准则优化问题中，权向量的含义是目标函数的相对权重。当我们固定权向量的最后一个分量(和函数f_{0}对应)为一时，其他权向量分量的含义是相对f_{0}的成本，即相对于目标函数的成本。

四、鞍点解释

4.1强弱对偶性的极大极小描述

Language对偶问题是对原问题的极小极大描述，即：

原问题可等价于一种极大极小描述，

所以目标函数+约束函数可写成：

                                            \underset{\lambda \succeq 0}{sup}L(x,\lambda )=\begin{cases} f_{0}(x) & \text{ } f_{i}(x)\leqslant 0 \\ \infty & \text{ } others \end{cases}

即原问题等价于：

                                                  \underset{x}{inf}  \underset{\lambda \succeq 0}{sup}L(x,\lambda )

所以有

                                              p^{*}=  \underset{x}{inf}  \underset{\lambda \succeq 0}{sup}L(x,\lambda )

4.2鞍点解释

回到我们关于 Lagrange 对偶的讨论，如果 x^{*}和\lambda ^{*}分别是原问题和对偶问题的最优点，且强对偶性成立，则它们是Lagrange 函数的一个鞍点。反过来同样成立：如果(x,\lambda )是 Lagrange 函数的一个鞍点，那么x是原问题的最优解，\lambda是对偶问题的最优解，且最优对偶间隙为零。

4.3对策解释（暂无）

4.4价格或税解释（暂无）

五、最优性条件

5.1次优解认证和终止准则

5.2互补松弛性

即强对偶情况下在最优点处有

即

或

当f_{i}(x^{*})<0 时，对偶函数一定在\lambda _{i}=0时取最大值，即\lambda^{*}_{i}=0

当\lambda^{*}_{i}>0 时，显然f_{i}(x^{*})=0

5.3  KKT最优性条件

5.3.1非凸问题的KKT条件

原问题和对偶问题的最优解一定满足KKT条件。

5.3.2凸问题的KKT条件

对于凸问题，KKT条件同上，加一句：

满足KKT条件的点一定是原问题和对偶问题的最优解。

5.4  KKT条件的力学解释（暂无）

5.5通过解对偶问题求解原问题

如果强对偶性成立且存在一个对偶最优解(\lambda ^{*},\nu ^{*})那么任意原问题最优点也是L(x,\lambda ^{*},\nu ^{*})的最优解。

更精确地，假设强对偶性成立，对偶最优解(\lambda ^{*},\nu ^{*})已知。L(x,\lambda ^{*},\nu ^{*})的最小点（即下列问题的解）唯一，且等于原问题的最优解。

在满足强对偶条件（例如 Slater 条件）的情况下，原问题的最优解可以通过对偶问题的解间接获得。此时原问题和对偶问题的最优值相等，解对偶问题即可获得原问题的最优值。当我们通过对偶问题优化拉格朗日对偶函数，得到的对偶变量将帮助我们在原问题的约束边界处逼近最优解。

六、扰动及灵敏度分析

6.1扰动的问题

其中，变量 x\epsilon R^{n} 。当 u=0 以及 v=0 时，上述问题即为原问题(5.1)。若 u_{i} 大于零，则我们放松了第 i 个不等式约束；当 u_{i} 小于零时，则意味着我们加强此约束。因此扰动的问题(5.56)是在原问题(5.1)的基础上通过将不等式约束加强或放松 u_{i}，并将等式约束的右端变为 v_{i} 得到。

定义 p^{*}(u,v) 为扰动的问题(5.56)的最优值：

有可能 p^{*}(u,v)=\infty，这时对约束的扰动使得扰动后的问题不可行。注意到 p^{*}(0,0)=p^{*},而 p^{*} 是没有被扰动的问题(5.1)的最优解。

当原问题是凸问题时，函数p^{*}是u和v的凸函数;事实上，其上境图恰恰就是式(5.37)定义的集合A的闭包。

6.2一个全局不等式

假设强对偶性成立且对偶问题最优值可以达到。(当原问题是凸问题目Slater条件满足时这种情形将会发生。)设(\lambda ^{*},\nu ^{*})是未被扰动的问题的对偶问题(5.16)的最优解则对所有的 u和v，我们有

不等式（5.57）的推导：

通俗解释不等式（5.57）：

1、先对不等式约束的扰动进行讨论

（1）如果x^{*}是约束的内点（即不包含边界）时，\lambda ^{*}=0，且u和v在0附近时，p^{*}(u,v)=p^{*}，所以不等式成立。

（2）当x^{*}是约束的边界点时，

当约束放松，即u_{i}>0时，p^{*}将会减小，即p^{*}(u_{i})<p^{*}，\lambda _{i}> 0，如图

\lambda _{i} 是约束函数相较于目标函数在最优点时的权重（斜率之比的绝对值），由凸问题的性质在最优点左侧，权重就会减小，即有p^{*}(u_{i})\geqslant p^{*}-\lambda ^{*}u_{i}

2、再对等式约束的扰动进行讨论

还没想好

灵敏度解释

6.3局部灵敏度分析

七、例子（暂无）

7.1引入新的变量以及相应的等式约束

7.2变换目标函数

7.3隐式约束

八、择一定理（暂无）

8.1通过对偶函数建立弱择一性

8.2强择一

8.3例子

九、广义不等式（暂无）

9.1  Lagrange对偶

9.2最优性条件

9.3扰动及灵敏度分析

9.4择一定理

# 机器学习
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

Handy 离线语音转写教程：免费开源，本地跑不连网

你肯定遇到过：语音输入 5 分钟，云转写服务要登录、要付费；或者出差没网，想口述一段会议纪要，发现全都没法用。Handy 离线语音转写工具就是为解决这个问题做的，声音全程不出你的电脑。## 🎯 这个工具是什么Handy 是一款免费、开源、跨平台（Windows / macOS / Linux）的离线语音转写应用。按住快捷键说话，松手后文字直接粘贴进任意输入框，全程不联网。核心能力就三条：

avatar 天工造物局

Supabase Edge Functions 编写与部署完整指南：Deno 运行时上的无服务器利器

Supabase Edge Functions 是基于 Deno 运行时编写、面向 Web 的无服务器函数服务，帮你把后端逻辑部署到全球边缘节点。作为 Postgres 开发平台的核心能力之一，它让你用 TypeScript 就能快速搭建低延迟的 API 端点、Webhook 接收器和 AI 集成服务，无需管理任何服务器。本文将从零带你完成一个 Edge Function 的创建、本地调试与全球部

avatar 天工造物局

celld从v0.1.0到v0.2.0为何不能滚动升级：两个破坏性变更详解

celld 是一个自托管、分布式的 Durable Objects 开源守护进程，它在你自己的机器上运行 Cloudflare Workers，每个对象对应一个独立的 SQLite 数据库，并持续复制到你自己拥有的 S3 兼容存储桶中。如果你正准备把 v0.1.0 的集群（fleet）升级到 v0.2.0，这篇文章必须先读：这次升级**不能滚动升级**，必须采用"先停光、再启动"的一次性发布方式。

avatar 天工造物局