约束优化常见算法.docxVIP

第五章约束优化常见算法定义5.1设∈ ??为一可行点, ?? ∈，若存在?? 0, 使对??? ∈ [0, ??]均有?? + ???? ∈ ??, 则称??是可行域??在可行解??处的可行方向, 可行域??在可行解ˉ??处的所有可行方向记为FD(??, ??), 简记为FD(??)定理5.1设??是问题(5.1)的可行解，在点??处有?? =,?? ，其中，则非零向量??为??处的可行方向的充要条件是?? ≥ 0,???? = 0。Zoutendijk方法：如果非零向量??同时满足? ?? 0,?? ≥ 0,???? = 0，则??是在??处的下降可行方向。因此，Zoutendijk法把确定有哪些信誉好的足球投注网站方向归结为求解线性规划问题:min ? ??s.t?? ≥ 0???? = 0‖??‖≤ 1.(5.2)其中增加约束条件‖??‖≤ 1是为了获得一个有限解。在(5.2)中，显然?? = 0是可行解, 因此最优目标值小于或等于零．如果? ?? 0，则得到下降可行方向??；如果最优值为零,则有如下结果.定理5.2考虑问题(5.1)，设??是可行解，在点??处有?? = ,?? ，其中，则??为Kuhn-Tucker点的充要条件是问题(5.2)的最优目标值为零。Rosen投影梯度法定义5.2设??为??阶矩阵，若?? =且= ??，则称??为投影矩阵。定理5.3设??是问题(5.1)的可行解，在点??处，有??1?? = ??1,??2?? ??2，其中，又设为行满秩矩阵，则?? = ?? ??? 是一个投影矩阵, 且若?????(??) 0，则?? = ??????(??)是下降可行方向.定理5.4设??是问题(5.1)的一个可行解, ,,??的定义同定理5.3, 且??为行满秩矩阵，令?? = ?????(??) =其中??和??分别对应于和??. 若?????(??) = 0，则1 如果?? ≥ 0，那么??是K-T点；2 如果??中含有负分量，不妨设 0，这时从??1中去掉对应的行，得到,令,?? = ????(??)那么??为下降可行方向。梯度投影法计算步骤给定给定初始可行点, 置?? = 1。在点处，将??和??分别分解成,和,, 使得?? = ,?? .3.令如果??是空的，令?? = ??（单位矩阵）, 否则令?? = ?? ???.4.令= ??????(). 若??(??) 0, 则转步6; 若??(??) = 0，则进行步5.若??是空的，则停止计算，得到；否则，令?? = ?????(??) =如果?? ≥ 0，则停止计算，为K-T点；如果??中包含负分量，则选择一个负分量，比如，修正，去掉中对应的行，返回步3。根据式(5.4)计算, 然后解下列问题,min ??(+ ??)??.?? 0 ≤ ?? ≤得步长，令 = + ,置?? := ?? + 1，返回步2DuZhang的修改1.给定给定初始可行点和一个正常数?? 0, 置?? = 1。2.在点处，将??和??分别分解成,和, , 使得?? = ,?? .3 令?? =如果??是空的，令?? = ??（单位矩阵）, 否则令?? = ?? ???.4 计算?? = ?????(??) =和??(??) = ??????().5. 定义 , min{ | ?? = 1, . . . ,??}. 如果‖‖ = 0且≥ 0(或??是空的)，则停止计算，为K-T点；若‖‖≥???，不变, 转下步; 若‖‖ ???，修正??1，去掉中对应的行, 令←, 转下步.6. 根据式(5.4)计算, 然后用Amijo线有哪些信誉好的足球投注网站近似求解下列问题,min ??( + ??)??.?? 0 ≤ ?? ≤得步长，令 = + ,置?? := ?? + 1，返回步2罚函数法对于等式约束问题min ??(??)s.t.(??) = 0, ?? = 1, ...,(5.6)可定义辅助函数 (??, ??) = (??) + ??(5.7)参数??是很大的正数。这样就能把(5.6)转化为无约束问题min (??, ??) = ??(??) + ?? (5.8)显然，(5.8)的最优解必使得 (??)接近零，因为如若不然，(5.7)的第2项将是很大的正数，现行点必不是极小点。由此可见，求解问题(5.8)能够得到问题(5.6)的近似解。罚函数的理论分析考虑min ??(??)s.t.(??) = 0, ?? ∈ ?? (??) ≥ 0, ?? ∈ ???? ∈ ??其中??是非空闭集, ?? = {1, ..., }, ?? = { + 1, ...,??}. 定义?? = {?? ∈| (??) = 0, ?? ∈ ??; (??) ≥ 0, ?? ∈ ??}该问题对应的罚函数优化