文档介绍：凸规划的新算法
张敏洪 杨德庄 杨庆芝
(华罗庚应用数学与信息科学研究中心)
(中国科学技术大学研究生院数学部, 北京 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 , 由基准