带球(椭球)约束的不定二次规划问题.pdf

维普资讯 第9畚 第2期 应用散学与计算数学学报 V l_9 No．2 1995年l2月 COM IVI．ON A．PPL．MATH．AND CoMPUT Dec．，1995 带球 (椭球)约束 的不定二次规划 问题 ～ 兰兰 ：2／ ． ． ’ ’ {上jI大学数学幕，上海，201800} 厂、)) ■要 本文证明了带璋(椭球)约柬的不定二次规划问题具有强Lagr4nge对疽性，设舟 关量词 ：：班规划，珏时锅 ． 霞 税划 ． ． 《优 二次规划是连续优化理论的基本 问题， 同时也被认为是最有挑战性 的组合优化 问题 Z-(1z]lo])．如下带球约束(椭球约束可作线性变换化为球约束)的不定二次规划问题： Q(P)f窖 近来得到特别的重视，其 中口 ∈R “是对称不定矩阵，c，z∈月 “．在非线性规划的 Levenberg-Marquardt信赖域方法(如 1【】5【】)中，每次迭代都要求解IQP)类型的子问题． 特异9地，4【II7I把求解问题(QP)作为子过程试图求解带线性约束的非凸二次规划问题． 显见，(QP)的一阶最优性必要条件为： 2(口+ )z=一c， (1．1) I】￡ll墨 0，p(r—l14)=0 (1．2) 二阶充分条件是： ^(口+ ，) 0，即口+ ，的特征值非负． (1_3) I~ (QPl的解的特点在 l【】I4l5【】等文中有所讨论．1992年7【】首次’正刚了如下结论： 定理 若(l，x1)(2，2：2)满足(1．1)(1．2)(1．3)，则 1= 2，且 g(z1)；g(￡2) 即满足(QP)的一、二阶最优性条件的解是列题(QP)的总体最优解．利用该性质， 7【】给 出了如下算法： l ：=0， = +n- I 2．2：：；(l-I-3) 3．令p； 2，解 (1_1) 4．若№一 1e，停机；否则若0+ ，不是正定阵，或者若 (11)无解或 (1．1)的范数极 小解的范数大于r，则令 1=批．转2：否则若(1．1)的范数极小解的范数小于r令 3= 2。 转2． 本 文1995年3月30 日收到 维普资讯 一 48一 应用数学与计算数学学报 9卷 该算法的迭代步数为0(1lI)，每选代一次要做0( )次算术运算 · 与文7【】不同．本文从对偶的角度出发讨论问题(QP)及 解的特点 证州了问题(QP) 具有强Lagrange对偶性，从而得到比文7【】强的结论．本文第三节设计了解问题 (QP)的 一 个算法．该算法迭代0(1n )次，每迭代一次的计算量约为0fn)-但算法需先把问题化 为可分离变量形式的 问题后再进行求解． 2．强对偶性