从约束优化问题的Lagrange对偶看《最优化方法》课程的驱动化教学

On the Driving Teaching of the Course of Optimizing Method from the Lagrange Duality of Constrained Optimizing Problem

摘要: 最优化理论，特别是约束优化问题的Lagrange对偶理论是《最优化方法》课程的重要内容，也是难点内容。对此，我们从约束优化问题的最优性条件入手，引出了约束优化问题的鞍点的定义，再由此引出与约束优化问题相关的两个双层极值问题，从而引出约束优化问题的Lagrange对偶规划。这样一层层驱动性地引入约束优化问题的Lagrange对偶，既降低了最优化对偶理论的教学难度，也提高了学生的学习兴趣。

Abstract: The optimization theory, especially the Lagrange duality theory of constrained optimization problems, is an important and difficult part of the course Optimizing Method. In this regard, based on the optimality conditions of constrained optimization problems, we first introduce the definition of saddle point of constrained optimization problems, and then derive two bilevel extreme value problems related to constrained optimization problems, which leads to Lagrange dual programming of constrained optimization problems. In this way, Lagrange duality of constrained optimization problem is introduced layer by layer, which not only reduces the teaching difficulty of optimization duality theory, but also arouses students’ interest in learning.

1. 引言

最优化就是从众多的可行方案中作出最优选择，使系统的目标函数在约束条件下达到最大或最小。它在计算机图像识别、工程技术、交通运输、经济管理、军事等方面有重要的应用，并已成为相关学科领域的重要研究工具。相应地，《最优化方法》成为运筹学专业及工程管理、金融管理、交通运输、生物医学、计算机技术等相关专业研究生的一门重要的专业课程。国内外也出版了不少这方面的研究生教材，中文版的如 [1] - [9] ，英文版的如 [10] [11] [12] 。相比运筹学专业研究生的《凸分析》《数值计算》《线性规划》等专业课程，《最优化方法》因最优化理论部分内容深奥、结论证明繁琐而使不少教师在主讲这门课时发愁，更使不少学生在学习这门课程时有畏难情绪。针对这种情况，我们从约束优化问题的Lagrange对偶规划入手，对《最优化方法》的最优性理论建立驱动化教学模式，通过挖掘最优化理论性质的关联性，将教学过程由浅入深、层层递进，驱动性地引入约束优化问题的Lagrange对偶，这既降低了最优化理论性质的教学难度，也提高了学生的学习兴趣。

2. Lagrange对偶规划问题的驱动化教学

约束优化问题的对偶问题源自对策论中的零和对策。它最早应用于线性规划，后被推广到非线性规划。现已成为包括组合优化问题在内的最优化理论研究的重要工具。利用对偶可将一个约束优化问题转化成另一个约束优化问题并建立两问题解之间的某种联系，进而揭示原规划问题最优解的存在性等理论性质，如对偶规划不但可以给出原规划问题最优值的一个下界，而且在特殊情况下可得到原规划问题的最优值。同时，基于对偶规划还可建立原规划问题的对偶类算法。可以说，原规划问题及其对偶如同太极图中的阴和阳，它们之间既互相对立又相互依赖，构成一个和谐、对称的辩证统一体。因此，掌握好约束优化问题的Lagrange对偶对《最优化方法》的课程学习至关重要。遗憾的是，多数《最优化方法》教材在引入Lagrange对偶时都是从线性规划问题的对偶规划简单推广而来，这使得很多初学者在初次接触Lagrange对偶时有摸不着头绪的感觉。在此，我们通过对约束优化问题的最优性理论和Lagrange对偶理论进行深刻剖析，抛开线性规划问题的对偶，利用约束优化问题的K-T条件引出约束优化问题Lagrange函数鞍点的定义，再借助定义中的两个不等式引出两个双层极值优化问题，最后通过证明其中一个为原问题引出约束优化问题的Lagrange对偶。这样就驱动性地引出了约束优化问题的Lagrange对偶规划。

定理1. 设x^*为等式约束优化问题

$\begin{array}{l}\text{min}f\left(x\right)\\ \text{s}\text{.}\text{t}\text{.}{c}_i\left(x\right)=0,i\in \mathcal{E}\end{array}$

的最优解，若向量组 $\nabla c_i\left(x^{*}\right),i\in \mathcal{E}$ 线性无关，则存在向量 ${\lambda }^{\text{*}}\in R^{\left|\mathcal{E}\right|}$ 使得

$\nabla f\left(x^{*}\right)={\displaystyle \underset{i\in \mathcal{E}}{\sum }{\lambda }_i^{*}}\nabla c_i\left(x^{*}\right).$

引入Lagrange函数

$L\left(x,\lambda \right)=f\left(x\right)-{\displaystyle \underset{i\in \mathcal{E}}{\sum }{\lambda }_i}{c}_i\left(x\right).$

则上述结论中的最优性条件可表示为

${\nabla }_{x}L\left(x^{*},{\lambda }^{*}\right)=0.$

则根据上述结论，在正则性条件下，约束优化问题的最优解 $x^{*}$ 连同最优Lagrange乘子 ${\lambda }^{*}$ 构成Lagrange函数的稳定点，即

$\{\begin{array}{l}{\nabla }_{x}L\left(x^{*},{\lambda }^{*}\right)=0,\\ {\nabla }_{\lambda }L\left(x^{*},{\lambda }^{*}\right)=c\left(x^{*}\right)=0.\end{array}$

结合无约束优化问题的最优性条件，人们自然会想到如下问题：这些稳定点构成Lagrange函数关于 $\left(x,\lambda \right)$ 怎样的极值点？通过对带线性等式约束的凸规划问题分析发现， $x^{*}$ 为Lagrange函数在 $\lambda ={\lambda }^{*}$ 时关于x的极小值点，而 ${\lambda }^{*}$ 为Lagrange函数在 $x=x^{*}$ 时关于 $\lambda$ 的极大值点。由函数鞍点的定义，并结合下述不等式约束优化问题的最优性条件，可建立Lagrange函数鞍点的定义。

定理2 设约束优化问题

$\begin{array}{l}\text{min}f\left(x\right)\\ \text{s}\text{.t}\text{.}{c}_i\left(x\right)=0,i\in \mathcal{E}\\ c_i\left(x\right)\ge 0,i\in \mathcal{I}\end{array}$

在其最优解 $x^{*}$ 点满足 $\nabla c_i\left(x^{*}\right),i\in \mathcal{E}$ 线性无关，且存在非零向量 $s\in R^n$ 使得

$s^{\text{T}}\nabla c_i\left(x^{*}\right)=0,i\in \mathcal{E},s^{\text{T}}\nabla c_i\left(x^{*}\right)>0,i\in \mathcal{I}\left(x^{*}\right).$

则存在Lagrange乘子 ${\lambda }^{*}$ 使得

$\{\begin{array}{l}\nabla f\left(x^{*}\right)={\displaystyle \underset{i\in \mathcal{E}\cup \mathcal{I}}{\sum }{\lambda }_i^{*}\nabla c_i\left(x^{*}\right),}\\ c_i\left(x^{*}\right)\ge 0,{\lambda }_i^{*}\ge 0,{\lambda }_i^{*}{c}_i\left(x^{*}\right)=0,i\in \mathcal{I}.\end{array}$

定义1 对约束优化问题

$\min \left\{f\left(x\right)|c_i\left(x\right)=0,i\in \mathcal{E};c_i\left(x\right)\ge 0,i\in \mathcal{I}\right\},$

定义Lagrange函数

$\left(x,{\lambda }^{*}\right)=f\left(x\right)-{\displaystyle \underset{i\in \mathcal{E}\cup \mathcal{I}}{\sum }{\lambda }_i^{*}{c}_i\left(x\right).}$

若存在 $x^{*}\in R^n$ 和 ${\lambda }^{*}\left({\lambda }_i^{*}\ge 0,i\in \mathcal{I}\right)$ 使得

$L\left(x^{*},\lambda \right)\le L\left(x^{*},{\lambda }^{*}\right)\le L\left(x,{\lambda }^{*}\right),\forall {\lambda }_i\ge 0,i\in \mathcal{I},x\in R^n,$

则 $\left(x^{*},{\lambda }^{*}\right)$ 称为该约束优化问题Lagrange函数的鞍点。

容易证明，鞍点是约束优化问题的众多“最优”点中条件最强的点，如鞍点是约束优化问题的全局最优值点，鞍点是约束优化问题的K-T点等。尽管如此，鞍点不一定存在，而且即使存在也很难求。为此，我们从另一角度进行研究，由此引出了约束优化问题的对偶规划问题。

对约束优化问题

$\min \left\{f\left(x\right)|c_i\left(x\right)=0,i\in \mathcal{E};c_i\left(x\right)\ge 0,i\in \mathcal{I}\right\},$

记由不等式约束组成的向量值函数为 $G\left(x\right)$ ，由等式约束组成的向量值函数记为 $H\left(x\right)$ 。定义Lagrange函数

$L\left(x,u,v\right)=f\left(x\right)-G{\left(x\right)}^{\text{T}}u-H{\left(x\right)}^{\text{T}}v,x\in R^n,u\in R_{+}^{\left|\mathcal{I}\right|},v\in R^{\left|\mathcal{E}\right|}.$

根据定义，若 $\left(x^{*},u^{*},v^{*}\right)$ 为Lagrange函数的鞍点，其中 $u^{*}\ge 0$ ，则对任意的 $x\in R^n,u\ge 0$ 和v，有

$L\left(x^{*},u,v\right)\le L\left(x^{*},u^{*},v^{*}\right)\le L\left(x,u^{*},v^{*}\right).$

也就是说，鞍点是Lagrange函数在 $\left(u,v\right)=\left(u^{*},v^{*}\right)$ 时关于 $x\in R^n$ 的全局极小值点，又是其在 $x=x^{*}$ 时关于 $u\ge 0$ 和v的全局极大值点。由此得到如下两双层极值问题

$\underset{u\ge 0,v}{\max }\underset{x\in R^n}{\min }L\left(x,u,v\right)\underset{x\in R^n}{\min }\underset{u\ge 0,v}{\max }L\left(x,u,v\right)$

对于后者，容易验证

$\underset{u\ge 0,v}{\sup }L\left(x,u,v\right)=\{\begin{array}{l}\infty ,若x\notin \Omega ,\\ f\left(x\right),若x\in \Omega ,\end{array}$

故后一个极值问题就是原优化问题，即

$\underset{x\in R^n}{\min }\underset{u\ge 0,v}{\max }L\left(x,u,v\right)=\min \left\{f\left(x\right)|G\left(x\right)\ge 0,H\left(x\right)=0\right\}.$

对于前者，引入极值函数

$\theta \left(u,v\right)=\min \left\{L\left(x,u,v\right)|x\in R^n\right\}$

得到下面的优化问题

$\begin{array}{l}\max \theta \left(u,v\right)\\ \text{s}\text{.t}\text{.}u\in R_{+}^{\left|\mathcal{I}\right|},v\in R^{\left|\mathcal{E}\right|}\end{array}$

这就是约束优化问题的Lagrange对偶问题。

与原规划问题相比，对偶问题的可行域结构简单，而且在原规划问题约束个数较少时，问题规模也较小。

对原规划问题及其对偶，它们最优值之间的关系是建立对偶规划问题的关键所在。对此，有如下两个常识性的结论。

定理3 (弱对偶定理) 设 $x_0,\left(u_0,v_0\right)$ 分别是约束优化问题和其对偶问题的可行解，则 $f\left(x_0\right)\ge \theta \left(u_0,v_0\right)$ 。

原规划问题和对偶规划问题的最优值之间的差称为对偶间隙。若对偶间隙为零，则称完全对偶定理成立。若两规划问题的最优解都存在，且对偶间隙为零，则称强对偶定理成立。下面的结论说明Lagrange函数存在鞍点和零对偶间隙是等价的，也就是说，Lagrange函数存在鞍点恰好保证对偶规划问题中对Lagrange函数的min和max两个极值过程可以交换。

定理4 (强对偶定理) 约束优化问题的Lagrange函数存在鞍点，记为 $\left(x^{*},u^{*},v^{*}\right)$ ，的充分必要条件是 $x^{*}$ 和 $\left(u^{*},v^{*}\right)$ 分别是原规划问题及其对偶规划问题的最优解且对偶间隙为零。

3. 结论

本文借助约束优化问题的Lagrange对偶，建立了《最优化方法》的驱动化教学法。该教学法以问题驱动为导向，引出相关概念和要研究的问题。这样通过挖掘课堂教学内容的逻辑关联，找出教学课堂内容的驱动点，层层推进，这样不但降低了课堂教学内容的教学难度，也提高了学生的学习兴趣，更有助于加强学生对最优化理论的理解和掌握。当然，主讲教师要做到这一点，必须对《最优化方法》的最优化理论内容彻底吃透，归纳出有关概念和方法引出的背景及其与相关内容的关联度。