拉格朗日对偶

0.简介

在凸优化研究中，数学优化问题遵循以下形式：

    \bullet  x \in \mathbb{R}^n是一个称为优化变量的向量

    \bullet f:\mathbb{R}^n\rightarrow \mathbb{R} 是一个我们想要最小化的凸函数

    \bullet C\subseteq \mathbb{R}^n是一套凸集，描述了一组可行（能够完成或执行）的解决方案

x^* \in \mathbb{R}^n作为问题(1)的全局最优的充分必要条件是\bigtriangledown_xf(x^*) =0。

然而，在具有约束的凸优化问题的更一般设置中，这种简单的最优性条件不起作用。对偶理论的一个主要目标是以数学上严格的方式表征凸程序的最优点。

在这里，我们提出了一种通用可微凸优化问题的形式，如：

    \bullet x \in \mathbb{R}^n是优化变量

    \bullet f:\mathbb{R}^n\rightarrow \mathbb{R} 和g_i:\mathbb{R}^n\rightarrow \mathbb{R}是可微的凸函数

    \bullet h_i:\mathbb{R}^n\rightarrow \mathbb{R}是仿射函数

            \circ 对于a \in \mathbb{R}^n，b \in \mathbb{R}的仿射函数形式f(x)=a^Tx+b

1.拉格朗日

给定形式（OPT）的凸约束最小化问题，（广义）拉格朗日是一个函数L:\mathbb{R}^n\times \mathbb{R}^m\times \mathbb{R}^p\rightarrow \mathbb{R}，定义为

    \bullet x \in \mathbb{R}^n是拉格朗日的原始变量

    \bullet \alpha \in \mathbb{R}^m 和\beta \in \mathbb{R}^p是拉格朗日的对偶变量，也叫做拉格朗日乘子

直观地，拉格朗日可以被认为是原始凸优化问题（OPT）的目标函数的修改版本，其解释了每个约束。拉格朗日乘数\alpha_i和\beta _i可以被认为是违反约束的惩罚。拉格朗日对偶理论背后的关键直觉如下：

对于任何凸优化问题，总是存在对偶变量的设置，使得拉格朗日关于原始变量的无约束最小值（保持对偶变量固定）与原始约束最小化问题的解一致。

当我们在第6节中描述KKT条件时，我们将这种直觉形式化。

2.原始问题和对偶问题

为了显示拉格朗日和原始凸优化问题（OPT）之间的关系，我们引入了与拉格朗日相关的“原始问题”和“对偶问题”的概念：

原始问题

原始目标函数

然后是无约束的最小化问题

被称为原始问题。

    \bullet 一般来说，如果g_i(x)\leq 0和h_i(x)= 0成立，我们说x \in \mathbb{R}^n是原始可行的

    \bullet 我们通常使用向量x^* \in \mathbb{R}^n表示可以使（P）最小化的输入，我们让p^* = \theta p(x^*)表示原始目标的最优值

对偶问题

通过切换上面的最小化和最大化的顺序，我们获得了完全不同的优化问题。

然后是约束最大化问题

被称为对偶问题。

    \bullet 一般来说，如果\alpha_i(x)\geq 0成立，我们说(\alpha,\beta)是对偶可行的

3.解释原始问题

4.解释对偶问题

对偶目标，\theta_D(\alpha,\beta),是\alpha和\beta的凹函数。为了解释对偶问题，首先我们做出以下观察：

论点1：如果(\alpha,\beta)是对偶可行，那么\theta_D(\alpha,\beta) \leq p^*。

论点2（弱对偶性）：

论点3（强对偶性）：对于满足某些称为约束条件的技术条件的原始和对偶问题， d^*=p^*

5.互补松弛

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容