快速收敛的可行方向算法.doc

 快速收敛的可行方向算法 唐燮黎 陆晓敏 赵 引 (河海大学土木工程学院 南京 210098) 要 用算例研究了尝试法计算中初始步长选取和收敛速度的关系 ,进而提出了一种新的步长 确定法 ———约束近似法 ,避免了人为给定初始步长的缺陷 . 对比计算表明 ,本文方法还可大幅度地 提高可行方向法的收敛速度. 优化 ;可行方向法 ;步长计算 O221 . 2 考虑一个有 n 个设计变量 x = [ x 1 x 2 x n ] T , p 个不等式约束的数学规划问题 : 极小化 满足 式中的目标函数 F ( x) gj ( x) ≤0 ( 1) j = 1 , 2 , , p F 和约束 gj 为 x 的线性或非线性函数 , 并假设它们对设计变量的偏导数 T 5 F 5 F 5 F AF = ( 2) 增加 5 x 1 5 x 2 5 gj 5 gj 5 x n T 5 gj 和 Agj = 5 x j = 1 , 2 , ?, p 城经 5 x 1 5 x 2 n 可求得. 从初始可行设计 x0 出发 , 可行方向法的迭代公式如下 : = xi + αS i i = 0 , 1 , 2 , xi +1 ( 3) 式中 : S i ———迭代方向 ;α———步长 . 记 = 0 , j = 1 , 2 , , p} J = { j | gj ( xi ) ( 4) 为 xi 点的有效约束指标集 , 方向矢量 Si 须满足 S T i AF 0 ( 5) ( 6) ( 7) S T i Agj 0 j J , 当约束曲面凸向可行域外 j J , 当约束曲面凸向可行域内或 gj 为线性约束 S T i Agj ≤0 条件式 ( 5) ～ ( 7) 保证了沿迭代方向 S i 至少可走一小步得到一个改善的可行解. 依据确定方向 S i 方法的不同 , 可行方向法还可进一步分类 . 其中 , Zo utendijk[ 1 ] 曾最早提出用如下线性 规划来确定 Si : 极小化 - β S T Ag +θβ≤0 满足 j J i j j S T i AF +β≤0 | S i k | ≤1 k = 1 , 2 , ?, n 由于可行方向法在每一迭代步将优化分解为求方向 S i 的线性规划问题和求步长α的单变量约束极小 化问题 , 所以适用于求解有众多设计变量的优化问题 . 对大规模的优化设计问题采用可行方向法的优点还在 于 : a . 每一迭代过程结束时都能获得一个可行设计 , 因此即使在接近最优解时停止迭代 , 一般也能得到满 足实际需要的优化设计 . b. 迭代过程中目标函数单调下降 , 即每走一迭代步都可得到一个更好的可行设计 . 与之相比 , 一些基于 约束和目标函数近似表达式的优化方法在收敛过程中有时会产生目标值突然增大的跳跃现象 , 甚至得不到 收敛的优化解 . 然而 , 常见的可行方向算法多数采用尝试法计算步长 , 也有其不足之处 : a . 为检验迭代点是否位于可行域内和是否到达约束边界 , 需反复计算约束函数值 . 对工程中提出的大 量优化问题 , 主要约束常不能用设计变量显式表达 , 约束值计算较费机时 . 因此 , 须要众多的约束计算次数是 影响现有可行方向类算法计算效率的一个主要问题. b. 用尝试法计算步长时必须先给出一初始迭代步长 , 但在实际使用中有时无法通过预测选取一个适宜 的初始步长 , 此外 , 在接近最优解的迭代步中 , 初始步长也应逐步减小 , 对其变化方式难以作出普遍适用的规 定 . 本文以 Zo utendijk 方法决定方向矢量 S i 为例 , 研究可行方向类算法中步长的最佳确定法 . 首先 , 通过算 例对常用尝试法的步长选取和收敛速度作一研究 , 其后提出一个基于约束函数一次和二次近似式的步长确 定法 , 该法可大幅度提高可行方向类算法的收敛速度 , 并消除了必须人为给定初始步长的缺陷. 实际计算中 , 为提高可行方向法的效率 , 在计算步长时一般不要求作精确的一维有哪些信誉好的足球投注网站 ; 在确定有效约束 时 , 采用约束容差法 , 即预先规定一个小的正数 εc , 凡满足 1 - εc ≤ gj ≤εc ( 10) 的约束为有效约束. 在算法实现时 , 计算步长 α的一维问题 ( 式 ( 9) ) 还可分成两步 :先求出 αb 使迭代沿 S i 方 向前进到可行域边界 , 再通过一维有哪些信誉好的足球投注网站计算 αi , 即要求 F ( xi + αi Si ) Kirsch[ 2 ]曾提出在求出 αb 后计算下例导数 = min f ( xi + αS i