2.6 约束优化问题的极值条件在线视频

接叙上节课内容 我们这节课来

学习约束优化问题的极值条件

那么对于有约束的优化问题的

极值条件怎么来求呢

在我们讲优化问题的几何意义的时候

我们给过大家一道题很简单的一道题

有约束大家好像就不太会求了那怎么办呢

我们看对于约束优化问题的极值条件

数学形式形回忆一下很简单

就是minf（x）Subject to

gux小于等于0 u等于1 2到m

hvx等于0 v等于1 2到p p小于n为什么p小于n

如果p等于n的话或p大于n的话可能就无解

因为受约束的影响

其最优解不仅与目标函数的性态有关

而且与约束函数的性状也密切相关

情况会比无约束优化问题复杂的多

我们来看一下几种情况

比如说这是我的一个带约束的

由于这几个约束面

使得我原来整个平面的解空间

变成了只有这个大D是可行的解可行域可行域

那好了那我如果给你这个函数f（x）的

函数是这样的等值线时候呢

那刚好这里面我们一看

这里边的f（x）无约束优化问题的最小值点x*

就落在了这个可行域内那意思说什么

约束的x*与无约束的x*是重合的

我们说约束条件不起作用那刚好什么

刚好这个约束面对这个整个问题求解

没有什么意义没有什么起作用

因为它刚好是这个x*无约束的极值点

和约束的极值点成一个点所以判断它不起作用

刚好在这里头没有问题没有问题在里头求解

那么再看一个问题

假如这是我的约束这是我的约束线和可行域D

我的极值无约束与约束优化问题

或者我的f（x）的等值线是这样子

等值线是这样那么这一点是我的极值点

无约束优化问题的极值点这一点

是这一点无约束优化问题极值点x*

那你说这一点在我对我的约束上给能取吗

肯定不能取对不对

你取完这一点你交给施工单位

你是要出问题的为什么

这一点是不可行解

你做一个大坝最后合拢围拢不上了

做一个电力系统的一个功率分配问题

分配完以后整个电力系统解裂了

那肯定不行对不对所以这是不可行解

你要找什么

必须找在可行域内的解

可行域内这些解都是可行的

在里边找最好的那个方案找最好方案

那这时候什么

是不是这可行域是起作用的

这边缘是起作用的对不对

那么这里边一看哪个解是你的

这是我们的无约束极小点

那哪个点是你的最后要真正求解那一点啊

是不这一点这一点对不对为什么这一点

因为给了你等值线吗给了你等值线是不是

这里头线你像这条线画的线

是不都比越来越来越大

在这个区域内哪个是最小

是不是这一点最小啊

往这边走也变大往这边走也变大都会小

你看哪个地方再往这边走都会变大

就这一点是最小的所以说这一点应该是你

约束优化问题所要想寻求的极值

所想寻求的极值

这是我们这里的约束优化问题的极值

约束优化问题的极值

那么因此说呢这是无约束约束那看可行域

或者是我这里面的约束面起作用

因此说呢x位于约束边界上

一个约束条件是起作用的一个约束条起作用

g1x*是等于0的g1x称为是起作用的约束

刚好你看这一点在这个约束线上约束面上

那一定是让g1x等于0

所以g1x为起作用的约束起作用的约束

再给一个这样的一个等值线这样一个等值线

这是我的约束面这是我的约束面或约束线

那这里边我们同样看这是g1x等于0

我们看对于一个没有约束来说的话

那么这一点实际上是你的

无约束优化问题最优点对不对

你现在这样打完斜线以后

应该是这一边是我的可行解对吧可行解

我现在问你这一点是不是我的极值点

对吧应该是我的极值点

对吧你看这个什么叫极值点

再回忆一下什么叫极值点

对于这一点来说

我这一点周围找一找我在我周围看一看

就像你们这个举例一样在你们班范围看一看

谁都比我大对不对

因为这等值线吗这等值线吗

我往这边来一点等值线就这条等值线比我高了

往这边来都比我高所以我这一点是我的极值点

是我的极值点

所以它是一个极值点它是一个极值点

x1*是极值点

但是x1*不一定是什么啊

最小值点为什么

我又找到这么一点

这一点在我的附近看看是不也是我最小的

我在这找找这一点变大了这一点我也变大了

附近都是我最小的所以我也是个极值点

但是你明显看这两点来比是不这点比这点要小

为什么

因为这点是在哪个是在这个等值线上嘛对吧

这一点呢是在这个等值线上

是不这点比这点明显要小

是不是我这里边有两个极小值点

这两个极小值点我要取一个最小值点对不对

就是我刚才说的极值问题和最值问题的区别

x2*这是我原问题的无约束优化问题的极值点

无约束优化问题极值点

无约束的最小极小值点这个问题

为什么会出来这种问题呢

分析原因是什么原因呢

是因为f（x）为非凸函数

导致了图示情况有两个极小值点为什么

是因为为什么它为非凸函数

我们刚刚讲了

如果x为凸函数的它的定义是什么

是不是这里边是成为大圆套小圆的情况

这是不不是圆了像个蚕豆一样的形状

它是一个非凸函数

正是因为它是这样的一个情况

导致了两个极值点

那你这里面就要找什么找最值点

那这个问题就很明显的问题了

如果说这是我能画出来的二维函数能画出来

如果你画不出来这个图形你看不到这个图形

你也不知道整个函数的性状的话

你比如说你就找这一点你求解了

只要你写的你的论文或你的方法找到这一点了

是什么你只能说是一个极值解

不能说这点是最小值或最优解了对吧

因为你不知道

你根本就不知道这个点的存在这个解的存在

你必须来证明要么你去证明我这个解

就是我这里边唯一解唯一的极小值解

或者说我找

我把所有的极小值解都找出来以后呢

我比较这个解是最小的

否则的话你不能说它是最小值解

因为你的所做出来的模型的函数

是一个非凸函数是个非凸函数

那这是什么因为f（x）是一个非凸函数

同样我们看另外一个f（x）是个凸函数

是个大圆套小圆的情况等值线是这样子的

我给了一个这样的一个约束面

给了一个这样的一个约束面

这边是我的可行域

这边是我的可行域是我的可行域

这边是我的可行域

那给了这样一个约束面以后呢

因为D为非凸集合

是吧这D肯定是非凸集合为什么非凸集合啊

因为什么

我随便取两点这两点连线是不是有一条线段

是在这个D之外的它是个非凸集那所以说什么

x1是极小值点吗

是对吧肯定是极小值点为什么

在x1附近我找一找都比我大么

我再随便取一点都是另外一条等值线都比我大

所以我是极小值点它是最小值点吗

不是因为什么x1这条线是在这呢

我还有这个点呢我还有这个点呢对不对

所以说x1是极小值点但它不是最小值点

x2是最小值点原因是什么

原因就因为D是非凸集合

这是我的无约束优化问题的x*

无约束优化问题的极小值x*

因为D为非凸集合

因此说什么我看到什么呢

可能由于目标函数是非凸函数

也有可能由于约束面

或者约束条件所造成的非凸集导致了什么

导致了我的约束优化问题

会有比无约束优化问题更复杂的情况在这里头

更复杂的情况在这里头

这里边的f(x)为凸函数约束集为非凸集

导致了更复杂的情况

因此说呢约束优化问题比无约束优化问题

要复杂的多要复杂的多

那同样呢我们说如果说f(x)也是个非凸函数

约束集也是个非凸集

那么这种情况就更加复杂了更加复杂

你都不知道这里面到底有几个极值点

然后怎么去判断这里面

或甚至而且你是二维的可以画出来

如果你是高维你连画也画不出来

你根本就看不到这函数的性状

你只能靠证明来证明你的解

是不是极小值还是最小值

因此说什么呢对于约束优化问题

对于多元函数的约束优化问题

它求极值是或求最小值是更复杂更难判断

那么下面呢我们就来讲一个

不等式约束的极值条件

我们称为是库恩塔克条件或简称K T条件

一个约束条件起作用的K T条件

我们首先看一下

对于一个约束条件起作用K T条件是什么

假如说我有一个g1x就这个约束条件

就这一个约束线约束面起作用

g1x等于0对于这一个约束线约束面起作用

对于它来说如果是它起作用g1x是什么呢

这个是无约束优化问题的极值点

我们要找现在找它的约束优化问题的极值点

我们首先给一点这一点是它极小值吗

肯定不是显然不是对吧为什么

我往这边走我是不会更小啊

往这边走更小就肯定不是这

那么对于这点我们分析一下对于xk来说

那对xk我做等值线的切线做它的法线

或做g1x的我做约束面的

我做这个约束面的约束线的切线

然后呢做它的法线做它的法线

做它切线做它法线这样子

那既然做它切线做它法线那条法线一定是什么

就是它的什么▽gxk嘛就是它的梯度

同样呢那我做什么我做f（x）的切线

做f（x）的切线做f（x）的法线

那就应该是什么负的▽f（xk）因为什么

因为是变小了所以负的▽f（xk）

通过感性的认识判断我们可以知道

xk点一定不是极值点不是稳定点或者不是极值

因为它还可以往里面走

那么这里面呢我给大家一个概念形式里面呢

这条切线和这条切线之间不重合

会有一个这么样一个夹角会有这么样一个夹角

我把这个角呢称为是可用角

为什么是可用角呢一会我会讲为什么可用角

我们先成为是可用角什么呢先记住什么

这个约束线的切线和等直线的切线的夹角

我们称为是可用角我们称为可用角

那么这里边的这个角里边的随意一个方向

我们都称为可用方向

什么叫可用方向

你看刚好如果我按照这个方向

去搜索去寻找的话我往下一步走的话

是不是我的大致方向是对的

我们说这一点既然不是极小值点

哪一点是极小值点

是不往这边走的好像这个区域内的

都可以是极小值点对不对

所以我这个方向这么来画一个方向

我下一步我从这一步开始搜索搜索找一找

这里面呢好像的值都比这个值要小

所以说是一个什么

给了我一个明确的方向我到底往哪边去走

给了我一个明确的方向

这是我的可用角和可用方向

按照这个方向去来搜索的话

应该能找到更好的解能找到更好的解

那这里边什么啊

为什么会有可用角可用方向呢

通过图究其原因是什么

是因为负的▽f（x）跟▽g（x）之间不共线

因为有了这个角所以我这个角

这俩角是一样的嘛对吧

因为是都是垂直关系吗

因为它俩不共线所以说有可用角和可用方向

再做一个情况同样是这样的一个等值线

无约束优化问题的极值点这是g1x

如果说我在这里边呢我找到是这个点

这个点找这个点

那这个点现在大家通过图形来判断话

通过几何意义来判断这个点是不是极值点

应该是极值点对不对为什么

这个点的附近你往这边走一走是不比它大了

往这边走是不比它大了

往这边走是不也比它大了这点应该是在极值点

那么对于这个极值点我们好了我们先看看

这个点就是我的极值点的话

那我看这一点有什么特点

我们看看它的特点同样做约束线的x*

做g1x*的切线做它的法线

做它切线做它的法线

然后呢这是我们的▽gx*那同样做这个什么

这个等值线的切线做它的法线呢

是不是负的▽f(x)啊

是不是这两条线是重合的

两个切线是重合两个法线是不也重合的

两个切线重合两个法线也重合的

如果说x*是一个极值点的话通过图像我们看

好像是说我的约束线

和我的这个等值线的切线重和法线重合

这一重合怎么办

是不没有这个可用角了

没有可用角了

没有可用角是不也没有可用方向了

告诉你的你没有可用的方向也没有可用角

告你没有可用的方向表示什么意思

你就最好了你没有下一步的机会了

你都没有下一步机会那你就是最好的了

你就是最好的了

没有可用角没有可用方向它俩重合的

所以说呢是极值点的就表示

负的▽f(x)与▽g（x）是共线的

是共线它俩是共线的

我们通过一个例子看了一下

它俩是共线但并不代表什么

大小也相等对不对

只能说方向相等并不能代表大小相等

所以说什么我这里乘了一个λ

只是方向相等不代表大小相等

因为首先这是一个失量有大小有方向

它俩相等表示方向肯定相等的

但是不表示大小相等

所以说我乘以λ是个标量

是表示是方向是相等的大小可能是有大有小

这里的λ大于0是任意常数

大于0任意常数为什么

小于0是不反方向了小于0是反方向了

大于0任意常数

那好了我们看

两个约束条件起作用的K T条件更复杂一点了

两个g1x等于0 g2x等于0g1x等于0 g2x等于0

如果取这一点的话呢

首先你告诉我这一点xk这一个点是极值点吗

通过图能判断出来吧

讲这么多了应该能有一些清晰的认识

这点是极值点吗

应该不是的吧应该不是因为什么

是不这个地方还可以有更小的对不对

这条线肯定会这样这个这条线肯定还更小

做g1x的切线做它的法线▽g1x

做g2x的切线做g2x的法线▽g2x

做等值线的切线做它的法线f(x)

负的▽f(x)看看什么情况

是不是我这里边的负的▽f(x)

和g1x和g2x是不不在它的夹角里头

是不是在它外头啊

xk不是极值点xk不是极值点

是不会存在什么

同样会存在这么一个夹角会存在这么一个夹角

这个夹角呢我们称为是可用角

负的▽f(xk)与▽g1xk和▽g2xk是线性无关的

是线性无关的什么意思什么是线性无关

所谓的线性无关不就是说

你用▽g1xk和▽g2xk

没有办法去表示▽f(xk)么对不对因为什么啊

说的更通俗一点因为什么

因为-▽f(xk)这个向量这个矢量

没有在这两个之间对不对

就线性无关的因为这个两个之间是线性无关的

它们线性无关的

同样我们再同样画一个

这样的一个情况

那如果说我们分析下这一点

这一点显然我们看肯定是我们这里面的极值解

是我们极值解因为什么这一点是极小值对吧

往这边走走都比我大往这边走走都比我大

你往这边走走也都比我大

都比我大这些都比我大

它是一个极值点

那我们同样做切线做g1x切线做法线

做g2x切线做法线▽g1x ▽g2x

然后做什么

做等直线的切线做它的法线f(x)负的▽f(x)

那么x*是极值点的条件是什么是什么

刚好这个负的▽f（x）加在了▽g1x和▽g2x之间

加在之间什么表示

我们用一个数学方法表示什么

负的▽f（x）与▽g1x和▽g2x*是线性相关的

什么是线性相关

所谓的线性相关不就说是

负的▽f（x）可以由什么

可以由▽g1x和▽g2x的线性组合来表示对不对

可以由它线性组合来表示

那什么意思啊什么叫线性组合表示

说再通俗一点就是什么

是不是你们之前所学的什么

三角形或平行四边形法则呀

它能够这个向量能够用这两个向量表示

是不这个向量等于这个向量

和这个向量三角形表示

或者平行四边形表示啊对吧

就是这样子一个线性相关线性相关性对吧

可以用它来平行四边形来表示线性相关

所以说我们看到什么

x*的极值点如果是极值点一个条件是什么

是函数值的梯度的负方向

与两个约束线的梯度是线性相关的

数学表达是什么我要放大变什么了

就是负的▽f（x*）等于λ1▽g1x*加λ▽g2x*

就这两个式子就这两个式子

然后呢这里边呢要保证

λ1 λ2是大于0的对吧大于0的

否则的话又反方向了大于0的

那因此说对于一个求极小值的

minf(x)Subject to gux如果只有不等式约束

没有等式约束的时候的话呢

不等式约束的极值条件的K T条件的是什么呢

▽f（x）我把这个负号移过去了

好写一点负号移过去了

▽f（x）等于负的Σ求和u等于1到q

有q个u等于1到q

λu▽gu(x*)等于它能够表示

这里面保证λu是大于0的

q着重说下q

q是起作用的约束个数

这里我要着重说q起作用的约束个数

这里面的q你看到没有u是等于1到q的

而不是所有的什么

不是所有的u是1到m的是一个u等于1到q的

意思是什么

是起作用的约束

不起作用约束是不要记录在这里边的

不要写在这里边的

q是起作用的约束

那么这里边λ呢我们又称为是非负乘子

或称为拉格朗日乘子

那么同样如果把它放大了

我把这个式子写的放大了

我不要这个q

不要这个起作用这个约束起作用变成什么了

变成了u又从1到m

那么这里面λu是要大于等于0的

注意这里边的不是随意的大于等于0

只要是不起作用的约束条件λu都取0

只有起作用的约束条件λ是大于0

不起作用λ都等于0

那么这是对于我们这里边的不等式约束

那么优化问题建模变形是

minf（x）Subject to

gux小于0 hvx等于0对吧有了等式约束呢

那么对于这个标准形式的K T条件是什么呢

等式和不等式约束的极值条件

我们说K T是什么呢

负的▽u等于1到q

λu▽gux*加上v等于1到j λv▽hvx*

这里边λu和λv都是大于0的

q和j都是起作用的不等式约束

或者是等式约束的个数

要强调的是

起作用的不等式约束或等式约束的个数

那么几何意义目标函数负梯度向量负的▽f（x）

应落在起作用约束梯度向量

▽gu（x）和 hv（x）

在设计空间中组成的锥角的范围内

就是正过去说倒过来说

用数学形式表达说就是什么啊

就是说负的▽f（x）是可以被什么

是可以被 ▽gu（x）和 ▽ hv（x）

线性表示或者是线性相关的

那么几何意义就是什么落在它的锥角范围内

刚刚那个是落在它那个两个夹角之内

现在是落在它的锥角范围内因为什么

空间的多个变量多个向量

所以说呢它要落在夹角内

画一个图如果说这一点是极值点的话

那么它应该是落在起作用的

▽g1（x*）▽g2（x*）▽g3（x*）▽g4（x*）

这样所围成的空间

注意这是个空间不是个平面

你看我画的这是个空间

要想象这是个什么啊

这是一个棱锥对吧一个棱锥这是个空间

然后呢什么你要想象一下

这是那个尖这是那个底面

这是那个底面那个空间底面

然后呢如果这一点是极值点的话

目标函数的负梯度应该是就在这个锥体里头

所以说我怎么画

从这个锥体里头一直穿出来对吧一直穿出来

穿出来是实线在椎体里头看不见是虚线

想象这是一个这是个底面这是个尖

然后穿出来在这个椎体里头

这是它的几何意义

第一个K T条件为判定约束优化问题

局部极小值点的必要条件不是充分条件

可能这句话提出来大家心里又凉了半截

我们讲了半天这是一个必要条件

什么是必要条件

它是它的极值条件以后所具备的性质对不对

不是充分条件不是在判断是不极值条件

我要做解题时候我哪知道那个点是极值条件

哪个点是极值点呀

所以它是必要条件不是充分条件

你是必要条件了

我可以用这东西来看它的性质是什么

这是它的必要条件

第二对于凸规划问题

K T条件上升为充分必要条件是不就有希望了

如果说你所做出来这个问题工程问题

到了数学模型你能证明这个模型

是一个凸规划问题什么是凸规划问题

f（x）目标函数是一个凸函数

约束条件是个什么

也是凸函数都是凸函数的话

我是个凸规划问题如果是凸规划问题好了

K T条件就很重要了变成什么了

充分必要条件什么意思

你可以用K T条件来求解问题了

它是充分必要条件

所以说判断一个函数的凸性

判断一个规划问题的凸性

是非常重要的是非常重要的

例子看一个例题

minf(x)等于x1减3平方加上x2的平方

然后呢有一些不等式约束

g1x等于x1平方加x2减4小于等于0

g2x等于负的x2小于等于0

g3x等于等于负的x小于等于0

用K T条件验证x*2 0点

是否为该问题的极小值点呢是不它的极小值点

让你们验证怎么去验证

就是我们刚刚讲的一套代进去验证就行了

看看看看什么

看看负的▽f（x）是不是这些

那个起作用它的线性表示

能不能线性表示或线性相关就可以了对不对

那看看第一个计算x*处各函数约束值

判定是不是起作用对不对什么叫起作用

我们看这个图什么叫起作用

无非是那个点刚好落在了约束线或约束面上

那落在约束线约束面什么意思

不就是那个点让那个不等约束面变成相等

就是这样子那代进去看就行了

代进去g1x*等于x1平方加上x2减4

2 0代进去2的平方加0减4等于0

它等于0是不起作用啊

然后g2x0 0代进去等于了起作用

g3x x1平方小于0肯定是满足条件的

但是它什么不等于0是吧

不等于0都不是它的可行解

你还谈它什么极小值没有意义判断极小值

是可行的但是呢它不起作用所以说呢

起作用约束起作用约束

不等于0所以是不起作用约束

g1x和g2x起作用约束g3x是不起作用的约束

第二计算在x*点处的

起作用的约束函数和目标函数的梯度

判断它们的梯度

那就把梯度求出来梯度我们刚才会求了

▽g（x）等于2倍的x1减3 2倍x2

把x等于x*代进去求出来就行了

▽g1（x）求出来▽g2（x）求出来

你要判断什么那就是看这个东西

能不能用这两个来线性表示么

它能不能用它俩来线性表示就可以了

第三步代入K T条件求拉格朗日乘子λ

并且你要看λ能不能求出来

再去看λ是不是大于0的对吧

λ是不是大于0的K T条件代进去

▽f（x）等于负的λ1▽g1（x*）

加上λ2▽g2（x*）

把数值都代进去λ1λ2写出来这个式子是什么

不就是个二元一次方程组吗

解这个方程就行了

解出来记这个就行了对不对

负2加上4倍的x1等于0 λ1减去λ2等于0

解得λ1等于λ2等于0.5

那么λ1 λ2均为非负乘子

所以说呢满足K T条件x为极值点x为极值点

那就这样就判断出来了

这个题里边的2 0这一点是不它的极值点

做一图我们看一看刚好这个题是一个二元的

所以我们做一个图看看

到底是个什么样的几何意义x1 x2

到底这三个是什么东西呢

x1平方加x2平方减4小于等于0是个什么东西

是个抛物线对不对是个抛物线

是不这样一个抛物线

那么取哪个呢

把这个0 0点代进去看看就行了对不对

取这里头呢还取外头呢看一看

肯定是取里头的

然后呢第二个呢负x小于等于0x大于等于0

是不取上面的对吧取上面的

g2x等于0取上面的

然后呢x1大于等于0取那半边的

所以说这样子的

可行域这是我们的可行域D

这是我们的等值线

f（x）等值线

是不是应该是一个圆呢正圆的因为什么

是因为x1的平方项系数

x2的平方项系数是相等的所以是个正圆

圆心在3 0点对吧3 0点

然后呢我们的2 0这一点在哪呢

是不在这这一点那么这一点2 0这一点一看

x*这一点是不就是什么谁对它起作用了

是不这个约束面和这个约束线起作用呢

是不这条线不起作用

没管住它不起作用所以说呢这个是不起作用的

这两个是起作用的

我们通过一个画图更清楚的看出来了

看到了这里边的问题

谁起作用谁不起作用起作用就是什么

就是在这条线上让什么

让g1x等于0g2x等于0起作用

那好了这一点

那么这点完了以后呢我们来看一下什么

这几条矢量到底是什么样的东西这几条矢量

在这一点处呢

约束优化条件最优解这点处呢我们看一看

这是我们的g1x*

这是我们的g2x*那我呢f（x*）在哪呢

▽f（x）在哪呢

在这呢▽f（x）在这

因为它是一个正圆

刚好它的梯度什么就指向圆心为什么啊

是不对这个等值线做一条切线做法线

你说一个圆做切线法线是不就指向圆心了

所以是刚好是指向圆心的

你看我的负的▽f（x）

就夹在▽g1（x）和▽g2（x）夹角之内

它可以由它们两个

通过乘以λ系数线性表示对不对

所谓的线性表示不就是我们的什么

三角形或者是平行四边形法则么

三角形平行四边形法则线性表示

它是约束优化问题的最优解

满足我们的K T条件

这是我们的这个几何意义

那意思是说什么

意思就说如果说你的函数的

或者你的模型的形式是个标准形式

什么是标准形式

minf（x）并且呢不等式约束都是小于等于0

还包括等式约束也可以

如果是个标准形式的话

那么你K T条件是它的一个极值条件

是否极值条件的一个必要条件

如果是凸规划问题它是一个充分必要条件