凸规划的新算法.doc

凸规划的新算法 张敏洪 杨德庄 杨庆芝 (华罗庚应用数学与信息科学研究中心) (中国科学技术大学研究生院数学部, 北京 100039) 摘 要 对一般凸目标函数和一般凸集约束的凸规划问题新解法进行探讨, 它是线性规划一种新算法的扩展和改进. 此算法的基本思想是在规划问题的可行 域中由所建的一个切割面到另一个切割面的不断推进来求取最优的. 文章对目标 函数是二次的且约束是一般凸集和二次目标函数且约束是线性的情形, 给出了更 简单的算法. 关键词 支撑超平面; 基准线 (段) ; 切割面 分类号 (中图) O 22112; (1991M R ) 90C 30. 文献标识码 A 文章编号 100024424 (2000) 0220235206 §1 引 言 凸规划是一类目标函数为凸函数, 约束集为凸集的规划问题. 由于其可行域中局部最优 解必是全局最优解这一性质, 因此它是非线性规划中比较特殊的一类规划问题, 但至今针对 其特性解决大规模变量有界的凸规划求解的有效算法还不是很多, 且算法较复杂1 . 2 提 出了一种求解线性规划的新算法, 此算法是按照算法与模型一体化思想构思的, 主要求优计 算是在一切割平面上进行的, 所用的基本方法简单初等. 本文主要针对凸规划目标函数与约 束集的凸性, 讨论如何扩展和改进这一线性规划的新算法, 生成一种求解带约束凸规划的有 效算法. 文中也对凸规划中的一些特例二次目标函数或线性约束集给出了一些简单的计算 方法. §2 算 法 考虑带约束的凸规划问题  m in f (x ) s. t. ci (x ) ≥ 0, i = 1, , m . 其中 f (x ) 为凸函数, P = {x | ci (x ) ≥0, i= 1, , m }为凸集. 首先引入一些概念: 假定有一已知点 x k , 过点 x k 可生成一切线 ( 面) , 使凸函数 f (x ) 的图形位于点 x k 的切 线(面) 上, 则称此切线 (面) 为过点 x k 的凸函数 f (x ) 的一个支撑超平面. 记为 Z (x k ) = f (x k ) + f (x k ) T (x - x k ). 在支撑超平面 Z (x k ) 上, 称过点 x k 的切线L (x k ) = {x ∈Rn | x = x k + tΒk ,  f (x k ) T Βk = 0, - ∞ t ∞}为基准线; 称 P ∩L (x k ) 的直线段为基准线段 l (x k ) = P ∩L (x k ) = {x ∈Rn | x = x k + tΒk , f (x k ) T Βk = 0, t1 ≤t≤t2 }; 显然 l (x k ) L (x k ) Z (x k ) , 其中 Βk 为 n 维非???列向量,  x k (1) = x k + t1 Βk , x k (2) = x k + t2 Βk 为基准线段的两个端点. 若点 x k ∈{ci (x ) 0, i= 1, , m }, 即为可行解集 P 的一内点解. 若有 x k + qΑk ∈P 且 f (x k + qΑk ) f (x k ) , q≥0, 则称 Αk 为一使目标函数值 f (x ) 在点 x k 有改进的好方向. 给定一好方向 Αk , 由基准线L (x k ) 上的点沿 Αk 方向发射形成一超平面 0 k , 称 0 k 为切割 面, 0 k = L (x k ). 算法的基本思想: 步骤1 从初始可行解 x k 出发; 步 骤2 确定基准线: 在 Z (x k ) 上确定一条过 x k 的直线 L (x k ) = {x ∈Rn | x = x k + tΒk , f (x k ) T Βk = 0, - ∞ t + ∞}, 对确定的 Βk , 求 t1 , t2 , 使得 l (x k ) = P ∩L (x k ) = {x ∈Rn | x = x k + tΒk , f (x k ) T Β= 0, t1 ≤t≤t2 };  步骤3 形成切割面: 求出一好方向 Αk , 由好方向与基准线确定一超平面 0 k , 使得 0 k = L (x k ) ; 步骤4 切割面 0 k 上求优:  得到在 P ∩0 k 上的最优解 x k + 1. m in f (x ) s. t. x ∈ P ∩ 0 k , 步骤5 决定继续迭代或停止: 若满足停机条件, | f (x k ) T ( tΒk + qΑk ) | Φ, 则停止, 其中  f (x k )