拉格朗日对偶的实例计算

一、Lagrange 对偶函数1.1 拉格朗日函数1.2 拉格朗日对偶函数二、标准形式线性规划拉格朗日对偶minCTxs.t.Ax=bx≥0minC^Tx\\s.t. Ax=b\\x\ge0minCTxs.t.Ax=bx≥0构建拉格朗日表达式在标准优化形式中，f(x)≤0f(x)\le0f(x)≤0，因此将满足条件的第二条转换为−x≤0-x\le0−x≤0,那么函数表达式如下：L(x,λ,μ)=C

蛋总的快乐生活

9647人浏览 · 2020-12-05 11:00:57

蛋总的快乐生活 · 2020-12-05 11:00:57 发布

该书为凸优化教材

一、Lagrange 对偶函数

1.1 拉格朗日函数

在这里插入图片描述

1.2 拉格朗日对偶函数

在这里插入图片描述

二、标准形式线性规划拉格朗日对偶

$C^Tx\\s.t. Ax=b\\x\ge0$

构建拉格朗日表达式

在标准优化形式中， $f(x)≤0f(x)\le0$ ，因此将满足条件的第二条转换为 $−x≤0-x\le0$ ,那么函数表达式如下：
$\begin{aligned} L(x,\lambda,\mu)&=C^Tx+\sum\lambda_i(-x_i)+\sum \mu_i(Ax_i-b)\\&=C^Tx-\lambda^Tx+u^T(Ax-b)\\&=(C^T-\lambda^T+\mu^TA)x-\mu^Tb \end{aligned}$
因此令 $∂L(x,λ,μ)∂x=0\frac{\partial L(x,\lambda,\mu)}{\partial x}=0$ ,那么 $L(x,λ,μ)=−uTbL(x,\lambda,\mu)=-u^Tb$

因此其对偶函数如下：
在这里插入图片描述

三、三个实例

3.1 线性方程的最小二乘解

$minx^Tx\\s.t. Ax=b$
第一步构造拉格朗日方程：
$L(x,\mu)=x^Tx+u^T(Ax-b)\\ \frac{\partial L(x,\mu)}{\partial x}=0,\frac{\partial L(x,\mu)}{\partial \mu}=0$
由于忘记矩阵的求导法则了，翻看一下矩阵分析，有如下两个公式
$\frac{\partial x^TAx}{\partial x}=2Ax [注：A为对称阵]\\$
$\frac{\partial b^Tx}{\partial x}=b [注：转置了一下]$
因此求解计算如下
$\begin{aligned} \frac{\partial L(x,\mu)}{\partial x}=2x+A^T\mu=0 \\ x=-\frac{1}{2}A^T\mu \end{aligned}$
那么代回原方程有
$\begin{aligned} L(x,\mu)&=x^Tx+u^T(Ax-b)\\&=(-\frac{1}{2}A^T\mu)^T(-\frac{1}{2}A^T\mu)+\mu^T(A(-\frac{1}{2}A^T\mu)-b)\\ &=\frac{1}{4}\mu^TAA^T\mu-\frac{1}{2}\mu^TAA^T\mu-\mu^Tb\\&=-\frac{1}{4}\mu^TAA^T\mu-\mu^Tb \end{aligned}$
在这里插入图片描述