Duaility | Hexo

Duality

概念和定义

拉格朗日函数

对于带约束优化问题(可能非凸)

$$\min f_0(x)\\ s.t\quad f_i(x)\leq 0,i=1,2,\cdots,n\\ h_i(x)=0,i=1,2,\cdots,p$$

目标函数最优值为$p^*$

定义Lagrange Function，定义为

$$L(x,\lambda,v) = f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p v_i h_i(x),\lambda\in \R^m,v\in\R^p$$

关于$\lambda,v$是线性函数

拉格朗日对偶函数

已知拉格朗日函数，定义对偶函数

$$g(\lambda,v) = \inf_{x\in D} L(x,\lambda,v)$$

D是问题的域，定义在所有函数的dom交集中

1. $\lambda$和不等式相关的拉格朗日乘子
2. $\mu$和等式相关的拉格朗日乘子

性质(与原问题无关，一定成立)

对偶函数一定是凹函数

$\forall \lambda_1,v_1,\lambda_2,v_2,\theta\in [0,1]$

$$\lambda = \theta \lambda_1+(1-\theta)\lambda_2\\ v=\theta v_1+(1-\theta)v_2\\ \begin{aligned} g(\lambda,v) &=\inf f_0(x) +\sum_{i=1}^n (\theta\lambda_1 +(1-\theta)\lambda_2)f_i(x) + \sum_{i=1}^p (\theta v_1 +(1-\theta)v_2)h_i(x)\\ &\geq \theta g(\lambda_1,v_1)+(1-\theta)g(\lambda_2,v_2)(\min(x+y)\geq \min x+\min y) \end{aligned}$$

被最优值约束

$$\forall \lambda\geq 0,\forall v,g(\lambda,v)\leq p^*$$

基于无约束的对偶函数求出的函数值一定是最优值的下界(被bound住)

任意在feasible set中的函数取值$L(x,\lambda,v)$一定被$p^*$ bound住

希望最大化$g(\lambda,\mu),\forall \lambda\geq 0$，实际上是凸问题

$$\min x^T x\\ s.t \quad Ax =b$$

Lagrange function

$$L(x,v) = x^T x+ v^T (Ax-b)$$

Dual function

$$g(v) =\inf_x L(x,v) \to 2 x= A^T v\to x^* = -\frac{A^T v}{2}\\ g(v) = -\frac{v^T A A^T v}{4}-v^T b$$

$g(v)$是凹函数(负定矩阵+线性函数)

$$\min c^T x\\ s.t Ax=b\\ x\geq 0\label{linear}$$

Lagrange function

$$f(x,\lambda,v) = c^T x +v^T (Ax-b) -\lambda^T x= (c^T +v^T A-\lambda^T) x -v^T b$$

Dual function

$$g(\lambda,v) = \begin{aligned} & -v^T b,c^T+v^TA-\lambda^T =0 \\ &-\infty,else \end{aligned}\tag{dual}\label{dual}$$

仅在超平面上为线性函数，在空间中其他位置取$-\infty$

$$\min x^T W x\\ s.t \quad x_i =-1/+1，i=1,\cdots,m$$

离散约束$x_i^2-1=0$

Lagrange Function

$$L(x,v) =x^T Wx+\sum_{i=1}^m v_i (x_i^2-1)=x^T (W+diag(v_i)) x-1^T v$$

Dual Function

$$g(v) =-1^T v\quad \forall W+diag(v) \succeq 0$$

满足$W+diag(v)\succeq 0$的v向量为凸集，因为两个正定矩阵相加还是正定的

函数的共轭和对偶函数

$f^*$是$f:\R^n\to \R$的共轭，若

$$f^*(y)=\sup_{x\in dom \ f} (y^T x - f(x))=\inf_{x\in dom\ f } (f(x) - y^T x)$$

考虑约束优化

$$\min f(x)\\ s.t \quad x= 0$$

的拉格朗日函数

$$L(x,v) = f(x) + v^T x,dom \ L = dom \ f\times \R^n\\ g(v) = -\sup_{x\in dom \ f} (-v^T x- f(x))=-f^*(-v)$$

约束均为线性的优化问题

$$\min f_0(x)\\ s.t\quad Ax\leq b\\ Cx = d\\ L(x,\lambda,v) = f_0(x) +\lambda^T (Ax-b) +v^T(Cx-d)= f_0(x)+(\lambda^T A+v^T C)x-\lambda^T b -v^T d$$

对偶函数

$$g(\lambda,v) = \sup_{x\in dom \ f} L(x,\lambda,v) = -f_0^*(-(\lambda^TA+v^T C)^T )-\lambda^T b - v^T d$$

极大化$p^*$的下界$g(\lambda,v),\lambda \geq 0$

$$\max g(\lambda,v)\\ s.t \quad \lambda \geq 0$$

$，原问题最优解记作$p^，原问题最优解记作$p^*$，一定有

$$d^* \leq p^*$$

1. 何时对偶间距为0
2. ,v^,v^$(最优的拉格朗日乘子)，使得$g(\lambda6,v^) = d^*$

线性优化$\eqref{linear}$的对偶函数为$\eqref{dual}$，极大化

$$g(\lambda,v) = -b^T v\quad A^T v-\lambda ^T +c6^T=0$$

于是对偶问题最优变成

$$\max -b^T v\\ \lambda \geq 0\\ A^T v-\lambda +c =0$$

合并等式约束和不等式约束

$$A^T v+c\geq 0$$

等价的目标函数(最优解相同，最优值不同)

$$\max -b^T v\\ A^T v+c \geq 0 \label{dual1}$$

考虑

$$\min c^T x\\ s.t\quad Ax \leq b\label{linear2}$$

的对偶函数和对偶问题

$$L(x,\lambda ) = c^T x +\lambda^T (Ax-b) = (c^T +\lambda^T A) x - \lambda^T b$$

显然对偶函数满足

$$L(\lambda )= -\lambda^T b\quad c^T +\lambda^T A=0$$

对偶问题

$$\max -\lambda^T b\\ s.t\quad A^T \lambda +c =0\\ \lambda \geq 0\label{dual2}$$

考虑$\ref{dual1}$和$\ref{dual2}$,$\ref{dual1}$将$\ref{linear}$中$x\to \lambda$,​

$$\min c^T \lambda \\ s.t\quad A\lambda = b\\ \lambda \geq 0\tag{P1}\label{P1}$$

$\ref{dual2}$改写成

$$\min \lambda^T b\\ s.t\quad A^T \lambda =-c\\ \lambda \geq 0\tag{D2}\label{D2}$$

原问题$\ref{linear}$和对偶问题形式类似，原问题$\ref{linear}$的对偶问题$\ref{dual1}$，改写为

$$\min b^T x\\ s.t\quad A^T x+ c\geq 0\tag{D1}$$

考虑$\ref{linear2}$，令$-A=A^T$(做代换，并非等式)，写成

$$\min c^T x\\ -Ax+b \geq 0\tag{P2}\label{P2}$$

$P1,P2$代表原问题1，2，$D1,D2$代表对偶问题1，2

说明了$P1$对偶问题的对偶问题是它自身，现在从原始约束的角度考虑这个问题，对于原始问题$\ref{linear}$

$$\min c^T x\\ s.t\quad A^T x=b,c\in \R^n ,b\in \R^p，A\in \R^{n\times p}$$

优化变量是$\R^n$上的变量，拉格朗日函数和对偶函数在约束上添加变量，因此是一个p维约束

n个约束上$\R^p$的优化，p个约束上$\R^n$优化

对偶问题的对偶问题不一定是自身，以为对偶问题一定是凸问题

何时两者等价

关键词：拉格朗日函数，对偶函数，对偶问题

强/弱对偶

$与原问题最优解$p^$与原问题最优解$p^*$满足

$$d^*= p^*$$

则称为强对偶，定义

$$p^*-d^*$$

为对偶间隙

原问题的域

相对内部相对内部对内部**

$$Relint D = \{x\in D|B(x,r)\bigcap affine D\subseteq D,\exists r>0\}$$

仿射包和球交集在D内

D是一个开集，则$ReLint D=D$

Slater’s condition(满足对偶间隙为0的充分条件)

若有凸问题

$$\min f_0(x)\\ s.t \quad f_i(x)\leq 0,i=1,2,\cdots,m\\ Ax =b$$

当$\exists x\in relint D$，使得

$$f_i(x)< 0,i=1,2,\cdots,m,Ax=b$$

=d^=d^^*$

相对内点内点满足约束严格小，并且等式约束成立

A weaker Slater’s condition

=d^=d^=d^=d^=d^=d^*$

不等式约束写成

$$c_i x+ d_i\leq 0$$

表示一个半空间，原来问题域是

$$D=relint \{dom f_0 \}$$

$f_i$的域是全空间

1. $f_0$定义在全空间内，则必然满足weaker Slater’s condition(约束在空间中形成多面体)
   1. 不需要考虑$f_0(x)\leq 0和f_1(x)=-f_0(x)\leq 0$两个不等式同时在$f_i(x)$中的情况，此时转化为等式约束
2. 其它情况下，集合内部和多面体交集必然存在交集

目标函数、不等式约束，等式约束都是仿射(线性规划)，如果存在可行解，则一定是强对偶

=d^=d^=d^=d^=d^*$

原问题定义在全空间上，全空间和多面体一定有交点，满足所有约束严格小

$$\min x^T x\\\ s.t Ax = b$$

=d^=d^=d^=d^=d^*$，它的对偶问题是

$$\max -\frac{1}{4}t^T A^T A v- b^T v$$

两个问题最优值等价

QCQP

$$\min \frac{1}{2}x^T P_0x +q_0^T x+r_0\\ s.t\quad \frac{1}{2}x^T p_ix +q_ix+r_i\leq 0,i=1,2,\cdots,m\\ P_0\in S_{++}^n ,P_i\in S_+^n$$ $$L(x,\lambda) = \frac{1}{2}x^T P_0x +1_0^T x+r_0 +\sum_{i=1}^m (\frac{1}{2}\lambda _i x^T P_ix+\lambda_i q_i^Tb x+\lambda_i)\\ g(\lambda) =\inf_x L(x,\lambda) = \inf_x \frac{1}{2}x^T(P_0+\sum_{i=1}^m \lambda_i P_i)x+(q_0+\sum_{i=1}^m\lambda_i q_i)^T x+(r_0+\sum_{i=1}^m \lambda_i r_i)$$

当$\lambda>0$时，一定是凸问题，写成

$$g(\lambda) = \inf_x \frac{1}{2}x^T P(\lambda) x+q(\lambda)^T x+r$$

对x求微分

$$\frac{\partial L(x,\lambda)}{\partial x} = P(\lambda) x+ q(\lambda) = 0\\ x=-P^{-1}(\lambda) q(\lambda)\\ g(\lambda) = -\frac{1}{2}q^T(\lambda) P^{-1}(\lambda)q(\lambda) + r(\lambda)$$

$g(\lambda)$是凹函数，并且$P(\lambda)$是正定矩阵(前提是$\lambda>0$)，对偶问题

$$\max\ -\frac{1}{2}q^T(\lambda) P^{-1}(\lambda)q(\lambda) + r(\lambda)\\ s.t\quad \lambda \geq 0$$

若$\exist x\in \R^n,s.t$

$$\frac{1}{2}x^T P_i x+q_i^T x+r_i <0$$

=d^=d^=d^*$

没有线性和常数约束

此时约束退化为

$$\frac{1}{2}x^T P_i x<0$$

显然不可能，此时仅能让$x=0$才能满足所有约束，原问题最优值为

$$p^* = 0$$

此时对偶问题退化为

$$\max -\frac{1}{2}q^T(\lambda)P^{-1}(\lambda)q(\lambda)\\ s.t \lambda \geq 0$$

显然$d^*=0$，可见Slater条件只是充分条件

=d^=d^^*$

对于只包含一个不等式约束的优化问题

$$\min f_0(x)\\ f_1(x)\leq 0$$

定义

$$G =\{(f_1(x),f_0(x))|x\in D \}$$

G是$\R^2$的子集，原问题的最优值$p^*$定义为

$$p^* = \inf\{t|(u,t)\in G,u\leq 0 \}(满足约束的最小值)$$

对偶函数定义为

$$g(\lambda) =\inf\{\lambda u+t|(u,t)\in G \}$$

对偶函数是目标和优化的线性组合，并且存在$x^*$使得函数值最小

如果在$\R^2$上画出G组成的集合，则$p^*$为在全空间左边部分中G中最矮的点，对于特定$g(\lambda)$

$$g(\lambda) = \inf_x f_0(x)+\lambda f_1(x)=\inf \{\lambda u + t,(u,t)\in G\}$$

考虑$\lambda u + t = m$，是$\R^2$上的一条斜率为$-\lambda$的直线，m是在t轴上的截距

1. 直线和G没有交集
2. 直线和G有交集，则意味着m可以取到

平移斜率为$-\lambda$的直线，直到与G有交集并在t轴上截距最小(相切)

$的几何意义，$d^，$d^*$就是在上述直线的基础上调整$\lambda>0$，使得相切直线在t轴的截距最高

鞍点解释

拉格朗日函数的鞍点，如果有

$$\inf_{x\in D}\sup_{\lambda\geq 0}L(x,\lambda) =\sup_{\lambda \geq 0}\inf_{x\in D}L(x,\lambda)$$

,\lambda^ambda^*)$处取到

RHS对应$d^*$

LHS拉格朗日函数写成

$$f_0(x) +\sum_{i} \lambda_i f_i(x)$$

1. 如果满足约束，即$f_i(x)\leq 0,\forall i=1,2,\cdots$，则显然取$\lambda_i =0$使得对于任意给定x，$L(x,\lambda)$尽量大
   1. 描述原问题的最优值
2. 存在一个约束不被满足$f_i(x)$，则$\sup_\lambda L(x,\lambda)=\infty$

对偶间距为0的一个等价条件是对于新的优化问题

$$target:L(x,\lambda)\\ \lambda \geq 0$$

,\lambda^mbda^*)$为该问题的鞍点

多目标优化解释

考虑多目标优化

$$\min \{f_0(x),f_1(x),\cdots,f_m(x) \}$$

给定一组系数$\lambda_i\geq 0$得到一组帕累托面，求解下列优化问题

$$\min f_0(x)+\sum_{i} \lambda_i f_i(x) = L(x,\lambda)$$

对于给定的$\lambda$，找到x使得$L$极小，得到$\overline x$，得到$g(\lambda)$的值，在所有$g(\lambda)$中找到最大化$g$对应的$\overline \lambda$

反之，带入$\overline \lambda$到$L(x,\lambda)$中，记作$L(x,\overline \lambda)$，随后对于x求解极小化问题得到$\overline x$，是系数取$\overline \lambda$对应的帕累托面上的顶点

Economy

$$\min f_0(x)\\ s.t f_i(x)\leq 0,i=1,2,\cdots,m$$

1. x 生产商品量
2. $f_0(x)$生产x的损失
3. $f_i(x)$原材料的约束

给定原材料上限生产利润$-f_0(x)$最大化

假设原材料i单价为$\lambda_i$，购买原材料多余的部分$f_i(x)>0$表示多出的原材料，则拉格朗日函数

$$\min _x f_0(x)+\sum_{i=1}^m \lambda_i f_i(x)$$

$f_i(x)<0$表示第i类原材料不足，购买第i类原材料还需要花费$-\lambda_i f_i(x)$，总的目标是让生产损失和购买原材料损失之和尽量小

$g(\lambda )=\min_x f_0(x) +\sum_{i=1}^m \lambda_i f_i(x)$表示在不同市场价格下，最低生产成本有所不同$\max g(\lambda)$意味着找到最大损失

\leq p^eq p^*$表示在可交换原材料的情况下，最大损失必然小于原材料不可买卖的最大损失(买卖可以不浪费资源)

$\lambda ^*$称为影子价格，商品价格取到影子价格可以让资源配置最优