§2罚函数法与乘子法,,,基本思想：,根据约束的特点(等式、不等式)构造某种“罚”函数，然后把它加到目标函数约,中去，使得,束问题的求解转化为一系列无约束问题的求解惩罚”的目的：对于无约束问题求解过程中企图违反约束条件的迭代点给予很大,的目标值，,迫使迭代点在可行集内或向可行集靠近，直到收敛于约束问题的,极小点外罚函数法(外点法)：迭代点不在可行集内,(2)内罚函数法(内点法)：迭代点在可行集内,(3)乘子法：外罚函数的一种推广和发展,二 罚函数法：,1.外罚函数法：(适用于一般函数约束),(引例) 求解：,s.t:,解：根据约束条件，及“惩罚”的目的，构造如下罚函数,,，其中,是很大的正数显然：当,是可行点时：,当,不是可行点时：,的值很大( 因,很大),因此，求解无约束问题，,得极小点,（不是原问,题的可行点），我们取迭代点：,，显然随,的增大，,必向原问题的可行域靠近如：求解：,得极小点,,显然：,即,不是原问题的可行解，但,是可行解，且为最优解1) (外罚函数法)：,,,(1) 根据约束条件给出“惩罚”项(罚函数),,，其中：,(通常,显然若,为可行点，则,(2)对于给定的罚因子,，求解无约束问题，,增广目标函数。
得：,(例1)求解：,称,解：(1)构造新目标函数,,,“惩罚”项：,因此,(2)求解无约束问题，,,,,(3),(例2)求解：,,解：(1)构造(罚函数)“惩罚”项,,(2)令,①当,时：,,,由,解得：,当,时：,②当,时：,,,内，∴不考虑此种情况,,,(2)算法：,,构造罚函数：,-终止限，,-罚因子放大系数,①给定初始点,可以是不可行解)，初始罚因子,②以,为初始点，求解无约束问题：,，得极小点,③若,则,停止；否则,，转②,已充分小)，,,2.内罚函数法(适用于不等式约束),(1)思想方法：,①对企图离开可行或的迭代点给予“惩罚”，使目标值很大，（彻一道“高墙”）,问题的可行域有内点(因此，约束条件中不能有等式),②当迭代点,靠近可行域的边界时，有一个,很小,因此，罚函数应为：,③罚函数(惩罚项),④增广目标函数：,，(,很小)例1)，求解：,解：增广目标函数：,,,(负根不合舍去),,(例2)，求解：,,s.t:,,,解：增广目标函数：,,,,,,(2)算法：,---终止限，,-罚因子缩小系数,①给定初始点,(可行域的内点)，初始罚因子,②以,为初始点，求解无约束问题，,得最优解：,③若,，则输出,停止；否则,，转②,② 内罚函数法：,且要求初,始点为可行域的内点。
外点法适用于一般约束，但迭代点(近似最优解)不是可行点③混合罚函数法：,3.备注：,① 外罚函数法、内罚函数法简单易懂，是常用求解约束问题的方法,迭代点是可行点(近似最优解是可行解)，但仅应用于不等式约束，,对于给定的初始点,，记：,作增广目标函数：,,④在罚函数法中，由于增广目标函数的Hesse矩阵，,(或,)的条件,数随,的增大(和,从而造成在求解相应的无约束问题的困难的减小)而变大，,三、乘子法：将Lagrange函数与罚函数结合起来,1.等式约束问题的乘子法：,,,①记：,则Lagrange函数为：,,②增广Lagrage函数为：,,(外罚函数法的罚函数),,③求解无约束问题：,,(例1)求解约束问题：,,(拉格朗日函数无极小点),解：作增广Lagrange函数：,,,再由条件,，此时,为原问题的最优解④算法：,,分析：,,,(a)∴已知迭代点：,，令,则有：,,从而当,时，有：,这即是K-T条件：,(b)又,，而,(收敛)，从而有：,,(c)在实际中，用比值,来度量,的收敛快慢(太慢时，应增大,的值),,算法：(Powell和Hestenes几乎同时各自独立地提出)-PH算法(P170),,①给定初始点,，初始乘子向量,始罚因子,及其放大系数,，控制误差,，与常,数,②以,为初始点求解无约束问题,,得其最优解,。
③若,则输出,停止；；否则,④若,，(收敛较快)，则转⑤；否则：,转⑤,⑤,转②,四、乘子法：,考虑问题：,,利用多无微积分极值的思想：作Lagrange函数,,其中：,设,为,的极小点，且相应的Lagange乘子向量为,则有：,(可行域)都有：,,(1)从而原问题等价于：,,(2)利用外罚函数法求解上问题：其增广目标函数为：,①当,适当大时(,)：(不必趋于无穷大)：无约束问题,,的最优解是原问题的最优解②但如何确定,呢？(在,未知时，,是无法知道),采用迭代法，求得点列,，使,对已得迭代点,，求解无约束问题：,得极小点：,，然后修正,为,,,然后，再求解无约束问题：,得极小点：,,……,如此，重复进行，得两个点列,，满足,,（例1）用PH算法求解：,,,解：增广Lagrange函数为：,,,即,由,的递推公式：,得：,,令,有，,将,代入,得，,（一般取,较大即可）,2.不等式约束问题的乘子法,先引进辅助变量化为等式约束的问题，然后先求等式约束问题关于辅助变量,的极小化问,题，得原问题的增广目标函数1）关于（＊）的增广Lagrange函数为：,,①,（2）记：,（对所有变量求极小）,,,即有：,（要求,）,因此：,②,（3）,中化去,：,将②代入①得：,,,,（配方）,,,,,,Lagrange乘子的迭代公式：,,,,终止准则：,,而：,,,3.一般约束问题的乘子法:,,,（1）增广Lagrange函数为：,,(2)乘子（修正）迭代公式：,,,（3）终止准则：,令：,,（4）算法－PHR算法：,①给定初始点,，初始乘子向量,，初始罚因子,及其放大系数,，控制误差,，，,常数,，令,。
②以,为初始点，求解无约束问题：,得最优解：,③若,停止；否则,④若,，则转⑤；否则，,转⑤,⑤,,,，转②,（例2）用PHR算法求解：,,,解：增广Lagrange函数为：,,,（1）当,时：,,显然，当,充分大时，（,），故,不满足,，即,不是,的,极小点2）当,时：,,,,显然：,因此：,乘子的迭代公式：,,取,，则,令,时，,此时：,。