资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,不等式约束最优化问题的最优性条件,不等式约束最优化问题,不等式约束最优化问题的最优性条件,定义,闭包,：,Closure,可行方向,：,可行方向锥,：,S,在点 处的可行方向锥,Feasible direction cone,注,:,当 时,S,在 处的可行方向锥是全空间,R,n,.,不等式约束最优化问题的最优性条件,定义,下降方向,(descent direction),：,下降方向锥,：,f,在点 处的下降方向锥,不等式约束最优化问题的最优性条件,可行方向锥与下降方向锥的几何解释,在极小点处，任何下降方向都不是可行方向，而任何可行方向也不是下降方向，即，不存在可行下降方向,.,S,F,0,D,有效约束,：,非有效约束,：,有效集,：,不等式约束最优化问题的最优性条件,定义,设,(3.3.1),中的一个可行点,满足,为在,处的有效约束或紧约束,则称约束,Active Constraint,若有,则,为,在,处的非有效约束或松约束,称,inactive Constraint,在可行点 处的有效约束的指标集：,有效约束与非有效约束,-,几何解释,不等式约束最优化问题的最优性条件,S,g,2,(x)=0,g,1,(x)=0,g,3,(x)=0,(1),在点 处,g,1,(x)0,和,g,2,(x)0,是有效约束；,g,3,(x)0,是非有效约束,.,(2),的非有效约束,g,3,(x)0,对 处的可行方向没有影响，,故非有效约束也称为,不起作用的约束,.,定理,3.3.1:,考虑约束最优化问题,几何最优性条件,一阶必要条件,不等式约束最优化问题的最优性条件,定理,3.3.2:,在问题,(3.3.1),中，假设：,(1),为局部最优解且,(2),与,在,点可微；,(3),在,点连续；,则,几何最优性条件,一阶必要条件,不等式约束最优化问题的最优性条件,仅考虑在某点起作用的约束,例,1,：,确定,：,在点,处的可行下降方向,.,解,：,不等式约束最优化问题的最优性条件,几何最优性条件,一阶必要条件,设,不等式约束最优化问题的最优性条件,几何最优性条件,一阶必要条件,不等式约束最优化问题的最优性条件,几何最优性条件直观,但难以在实际,计算中应用,.,将几何最优性条件转化为代数,最优性条件,.,?,几何最优性条件,一阶必要条件,(1)Fritz John,条件,(2)Kuhn-Tucker,条件,(1948),不等式约束最优化问题的最优性条件,Fritz John,最优性条件,一阶必要条件,定理,3.3.3:,设,为问题,(3.3.1),的局部最优解且,在,点可微，,则存在非零,使得：,则存在,非,零的向量,例,2,：,验证,处,Fritz-John,条件是否成立？,解,：,取,有,Fritz John,最优性条件,一阶必要条件,不等式约束最优化问题的最优性条件,即该问题在,x*,处,Fritz-John,条件成立,.,Fritz John,最优性条件,一阶必要条件,不等式约束最优化,问题的最优性条件,注,:,(1),上例说明在,Fritz John,条件中有可能,0,=0.,此时，目,标 函数的梯度就会从,Fritz John,中消失,即,Fritz,John,条件实际上不包含目标函数的任何信息，仅仅表明,起作用约束函数的梯度线性相关，而这对表述最优,点没有什么实际价值,.,(2),为了保证,0,0,还需要对约束再加上一些限制条件这种限,制条件通常称为,约束规格,(Constraint,Qualification,),一个,自然的想法是附加,线性无关的约束规格,(,当然还有许多其他的约束规格,),，这样就得到了著名的,KuhnTuker,条件,.,(1951),定理,3.3.4,设,为,(3.3.1),局部最优解,在,点可微，,对于,的,线性无关，,则存在非零向量,使得：,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶必要条件,K-T,条件,互补,松弛,条件,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶必要条件,式,(a),的几何意义,:,在局部,极小点,x,k,处,目标函数的梯度能表示成有效约束梯度的,非负组合,即目标函数的,梯度属于有效约束的梯度,所生成的凸锥内,.,例,3,：,验证,处,kuhn,-Tucker,条件是否成立？,解,：,对,所以,不是,K-T,点,原因是,线性相关,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶必要条件,定理,3.3.5,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶充分条件,设,在问题,(3.3.1),中,是凸函数,是可行点，,且,在 处可微,.,若 是,(3.3.1),的,K-T,点,则,是,(3.3.1),的全局极小点,.,K-T,条件对于约束问题的重要性在于：,1,）检验某点是否为约束最优点；,2,）检验一种搜索方法是否可行。,例,4,：,判断,x,(k,),=1 0,T,是否为下列约束优化问题最优点：,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶充分条件,解：,1,）判断,该点起作用约束,：,2,）,计算目标函数及,有效约束在,该点梯度：,不等式约束最优化问题的最优性条件,Kuhn-Tucker,最优性条件,一阶充分条件,5-1,约束最优解及其必要条件,3,）代入,K-T,条件，求乘子,：,解得,：,因此该点是最优点,.,又该问题为凸规划,即该点是,K-T,点,.,
展开阅读全文