维普资讯 http://www.cqvip.com
第１６卷第５期 运 筹 与 管 理 ０ＰＥＲＡＴ１０ＮＳ ＲＥＳＥＡＲＣＨ ＡＮＤ ＭＡＮＡＧＥＭＥＮＴ ＳＣＩＥＮＣＥ Ｖｏ１．１６．Ｎｏ．５ Ｏｃｔ．２００７ ２００７年１Ｏ月 解决大规模信赖域子问题的一种新算法 吕立波 （中国科学技术大学数学系，安徽合肥２３００２６） 摘要：信赖域方法是解决无约束优化问题的一类有效的方法，而求解信赖域子问题又是信赖域方法的一个重 要的组成部分。在本文中，我们首先介绍Ｈａｇｅｒ［．３的序列子空间方法，并分析了对于不同的子空间序列，该算法 所具有的性质。随后我们在以上分析的启发下，给出ｓｓＭ算法的一种改进算法，改进后的算法不仅是全局收敛 的，而且进一步减少了矩阵运算量。最后我们给出一些初步的数值试验报告。 关键词：非线性优化；信赖域子问题；序列子空间方法；全局收敛 中图分类号：０２２４ 文章标识码：Ａ 文章编号：１００７—３２２１（２００７）０５—００４８—０５ Ａ Ｎｅｗ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｓｏｌｖｉｎｇ Ｌａｒｇｅ Ｓｃａｌｅ Ｔｒｕｓｔ Ｒｅｇｉｏｎ Ｓｕｂｐｒｏｂｌｅｍ ＬＵ Ｌｉ—ｂｏ （Ｄｅｐｔ ｏｆ Ｍａｔｈ，Ｕｎｉｖ．ｏｆ Ｓｃｉ．ａｎｄ Ｔｅｃｈ．ｏｆ Ｃｈｉｎａ．Ｈｅｆｅｉ ２３００２６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ．Ｓｏｌｖｉｎｇ ｔｒｕｓｔ ｒｅｇｉｏｎ ｓｕｂｐｒｏｂｌｅｍ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｃｏｍｐｏｎｅｎｔ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｒｕｓｔ ｒｅ－ ｇｉｏｎ ｍｅｔｈｏｄ，ｗｈｉｃｈ ｈａｓ ｂｅｅｎ ｓｈｏｗｎ ｔＯ ｂｅ ｖｅｒｙ ｅｆｆｅｃｔｉｖｅ ｆｏｒ ｕｎｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｈｅ Ｓｅｑｕｅｎｔｉａｌ Ｓｕｂｓｐａｃｅ Ｍｅｔｈｏｄ（ＳＳＭ）ｏｆ Ｈａｇｅｒａｔ ｆｉｒｓｔ．Ｔｈｅｎ ｗｅ ａｎａｌｙｚｅ ｔｈｅ ｒｅ－ ｓｕｉｔｓ ｏｆ ｔｈｅ ｍｅｔｈｏｄｓ ｂａｓｅｄ ｏｎ ａｎ ａｌｔｅｒｎａｔｉｖｅ ｃｈｏｉｃｅ ｏｆ ｔｈｅ ｓｕｂｓｐａｃｅｓ．Ｉｎｓｐｉｒｅｄ ｂｙ ａｂｏｖｅ ａｎａｌｙｓｉｓ，ｆｌ ｍｏｄｉ— ｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ ＳＳＭ ｉｓ ｇｉｖｅｎ，ｗｈｉｃｈ ｎｏｔ ｏｎｌｙ ｐｒｏｖｉｄｅｓ ｔｈｅ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ，ｂｕｔ ｄｅｃｒｅａｓｅｓ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｍａｔｒｉｘ－ｖｅｃｔｏｒ ｐｒｏｄｕｃｔｓ．Ｆｉｎａｌｌｙ，ｗｅ ｓｈｏｗ ｓｏｍｅ ｎｕｍｅｒｉｃａｌ ｒｅｓｕｌｔｓ ｗｉｔｈ ｃｏｍｐａｒｉｓｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｎｏｎｌｉｎｅａｒ ｏｐｔｉｍｉｚａｔｉｏｎ；ｔｒｕｓｔ ｒｅｇｉｏｎ ｓｕｂｐｒｏｂｌｅｍ；ｓｅｑｕｅｎｔｉａｌ ｓｕｂｓｐａｅｅ ｍｅｔｈｏｄ；ｇｌｏｂａｌ ｃｏｎｖｅｒ－ ｇｅｎｃｅ ０引言 将光滑多变量函数极小化是各类数学模型中经常出现的问题。信赖域算法是解决此类最优化问题的 一种有效的迭代算法。在每一步迭代中，我们都要求解一个信赖域子问题 ｍｉｎ １ （ ）＝去 ∈ ＋ｇ （１） Ｓ．ｔ． １ｌ ｌｌ≤△ 其中，对称矩阵ＢＥＲ 是对函数，（ ）的Ｈｅｓｓｅ阵的逼进，ｇＥＲ”是函数，（ ）的梯度，Ｉｌ ＩＩ三ｌ ｌ△＞Ｏ是信赖域边界。我们通常称该问题为信赖域子问题。 ２， 对于中小规模问题（１），Ｇａｙ 以及Ｍｏｒ６和Ｓｏｒｅｎｓｅｎ［ 已经给出了非常有效的算法。他们的算法需 要对Ｂ进行Ｃｈｏｌｅｓｋｙ分解，所以对于大规模问题而言，他们算法所需要的计算量将非常庞大。Ｇｏｕｌｄ， Ｌｕｃｉｄｉ，Ｒｏｍａ，Ｒｏｍａ和Ｔｏｉｎｔ 。 选择在对Ｂ进行Ｃｈｏｌｅｓｋｙ分解之前，利用ＬａｎｅｚＯＳ方法将Ｂ三对角化。 收稿日期：２００４—１０－２４ 作者简介：吕Ａ￣（１９８２一），男，浙江宁波人，硕士研究生，主要从事最优化理论与算法研究。 维普资讯 http://www.cqvip.com
第５期 吕立波：解决大规模信赖域子问题的一种新算法 ４９ 这种技巧降低了Ｃｈｏｌｅｓｋｙ分解的运算量，但是当Ｂ是退化矩阵时，他们没有给出相应的算法分析。Ｒｏ— ｊａｓ，Ｓａｎｔｏｓ和ＳｏｒｅｎｓｅｎＬ９］以及Ｒｅｎｄｌ和Ｗｏｌｋｗｉｃｚ ］贝４将信赖域子问题转化成一个参数特征值问题。他 们的算法能够处理退化的Ｂ，但是试验表明当问题规模较大时，算法所需要的存储空间和运算规模非常庞 大。 为了解决算法执行过程中运算规模过大的问题，Ｈａｇｅｒ［ 对信赖域子问题增加了一个子空间序列 ｛Ｓｔ）作为新的约束条件，并以这个子问题序列的解为基础建立对问题（１）的ＳＳＭ算法。以下，我们首先分 析ＳＳＭ算法中子空间Ｓｔ的结构对算法收敛性质和计算结果的影响。随后，基于分析的结果，我们提出一 种不同的求解（１）的策略，给出一个实施方案，并讨论算法和整体收敛性和计算特点。最后我们给出一些 数值试验结果。 １全局收敛性 Ｈａｇｅｒ在Ｅ４］中提出的序列子空间方法（ＳＳＭ）是一个解决问题（１）的迭代算法。在算法的第忌步，需 要选取相关的Ｓ。以解决问题 ｍｉｎ （ｚ）一￣ｘＴＳｘ＋ｇ （２） ｚ∈ Ｓ．ｔ． １ ｌｚ ｌｌ≤△ｚ∈Ｓ＾ Ｈａｇｅｒ在Ｅ４］中利用Ｎｅｗｔｏｎ法对问题（２）的一阶最优条件求解得到ｚ ，并证明如果Ｓ。￣ｓｐａｎ｛ｘ。，ｓ９。Ｐ）， 则算法具有局部二阶收敛性。以下我们讨论Ｓ。的结构对ＳＳＭ算法整体收敛的影响。首先我们证明若 Ｓｔ￣ｓｐａｎ｛ｘｔ，Ｂｘｔ＋ｇ），则算法收敛到问题（１）的ＫＫＴ点。问题（１）的Ｌａｇｒａｎｇｅ函数是： Ｌ（ｘ， ）一寺ｚ Ｂｘ＋ｇＴｘ＋ （１ ｌｚ ｌｌ－ｚＳ） 我们称ｘｉ是稳定点（局部极大点、鞍点或局部极小点），如果存在ｌｌ兹ｌｌ≤△， ∈ 满足 （Ｂ＋ Ｄ蕊一一ｇ，ｌｌ蕊ｌｌ≤Ａ （３） 引理１．１蕊是问题（１）的稳定点当且仅当蕊对Ｂｚｉ＋ｇ的投影为零向量，且ｌｌ蕊ｌｌ≤△。 证明蕊对Ｂｘｚ＋ｇ的投影可表示为 ：一（Ｊ一凳）山＾山＾ （Ｂ蕊＋ｇ）一Ｂ蕊＋ｇ．一苎 苎 山＾上＾ （４） 若蕊是稳定点，则 满足（３），于是Ｂｘｚ＋ｇ一－－￣ｉｘｉ，由（４）可得 一Ｏ。 另一方面，若 ＝Ｏ，则由（４）可得 ＩＳ一 Ｊｋ一一ｇ （５） 令 一盔 王 ，则（３）成立。 定理１．２若ＳＳＭ算法每次迭代所选取的子空间Ｓ。都包括Ｂｘ。＋ｇ，ｚ 和，则该算法收敛到问题（１） 的一个稳定点。 证明 记ＳＳＭ算法所产生的点列为｛ｚ。），由于ｚ。∈Ｓ。，且ｚ抖 是 在｛ｚｌｚ∈Ｓ。，ｌ ｌｚ ｌｌ≤△）上的极 小点，我们有 （ｚ抖 ）≤ （ｚ。）。由｛ｚ…ｚ ｌｌ≤△）的紧性，可知其必有子序列收敛到蕊。不失一般性，我 们仍将该序列记为｛ｚ ）。由于 的连续性，显然有 （ｚ ）收敛到ｇ＇（ｘＤ。 若 不是（１）的稳定点，我们分别考察一下两个向量 ； ｘｚ（ 其中Ｐ。和， 由（４）定义。显然，若｛ｚ。）收敛到 ，则｛Ｐ。）收敛到 。又由于 与ｘｉ，（Ｂｘｚ－ｔ－ｇ）一 都 正交，于是有 维普资讯 http://www.cqvip.com
５Ｏ 运 筹 与 管 理 ２００７年第１６卷 （ （ｒ）） 。一（Ｂ ＋ 一。 ）一 ） （６） （Ｂ ＋ｇ） （趣（ｐ 一一（Ｂ ＋ｇ）／ｎ 一一ｌ ｌＩ Ｉ因为我们假设．ｚ＇／－不是（１）的稳定点，由引理１．１可知ｐ 不是零向量。 于是存在ｃ＞Ｏ使得对充分大的ｋ， 有ｌｌ Ｐ ＩＩ≥ｃ。所以，由（６）可知，存在ＫＥＮ，使得 （ｚｔ（ｒ）） ：一 （ｚｔ（ｒ））Ｉ ｒ＝Ｏ￣Ｄ ｌ ｌＰ Ｉ ≤一ｃＩ Ｖ忌＞忌 （７） 由于ｇＳ（ｘ）是二次函数，所以 （ｚ （ｒ））是由ｒ和１／ｌ ｌＸ －－ｒｐ ＩＩ决定的多项式，且最高阶数不大于６次。 于是 （ｚ （ｒ））在ｒ＝Ｏ附近的闭区间上的有界性成立，即：了Ｍ＞０，￡＞０使得 Ｉ （ｚ （ｒ））Ｉ≤Ｍ Ｖ Ｉ ｒＩ≤￡忌＞忌 （８） 我们将ｇＳ（ｘ （ｒ））在ｒ一０点二阶Ｔａｙｌｏｒ展开，结合（７），（８）可得 ｇＳ（ｘ＾（ｒ））＝ｇＳ（ｘ＾）＋ ／（ｚ＾）ｒ＋｛ ｌ／，（ｚ＾（ ）） ０≤ ≤ ｒ ≤ （ｚ＾）一ｃ ｒ＋÷Ｍ ≤ｇＳ（ｘ＾）＋（÷Ｍｒ—ｃ ）ｒ Ｖ ｋ＞Ｋ 特取ｒ＝ｍｉｎ｛￣，Ｃ ／ｍ），可得 ｇＳ（ｘ＾＋１）≤ｇＳ（ｘ＾（Ｔ））ｇｔ（ｘ＾）一÷ｃ Ｔ Ｖ ｋ＞Ｋ （９）显然与ｇＳ（ｘ ）收敛到ｇＳ（ｘ￣）矛盾。所以 是（１）的稳定点。 （９） 由于每个Ｘ 都是相应的（２）的全局极小点，所以｛Ｘ ）的极限点ｘ－／不可能是问题（１）的局部极大点或 鞍点。于是以上定理实际上证明了由ＳＳＭ算法得到的点列最终收敛到问题（１）的ＫＫＴ点。 定理１．３［１。 设Ｘ。∈Ｒ”是问题（１）的全局极小点，当且仅当存在 ≥０使得 （Ｂ＋ Ｉ）ｘ ：一ｇ （１０） 且Ｂ＋ Ｉ半正定，ｌ ｌＸ。ＩＩ≤△， （１ ｌＸ ｌｌ－－ａ）一０。 不难发现，Ｂ＋ Ｉ不是半正定阵当且尽当Ｘｉ只是ＫＫＴ点，而非全局极小点。对此类ＫＫＴ点， Ｍａｒｔｉｎｅｚ给出了以下刻画。 定理１．４ 问题（１）至多存在一个非全局极小的ＫＫＴ点ｘｉ，并且我们有ｘｉ一△， ∈（一口 ，一口 ）。其 中 满足ＫＫＴ必要条件，ａ ，ａ 分别是Ｂ最小的两个特征值。 以上定理证明了若ｘｉ是一个非全局极小的ＫＫＴ点，则Ｂ＋ｋＩ不是半正定的。设Ｂ＋ Ｉ的最小特 征值所对应的特征向量是 。Ｌｕｃｉｄｉ，Ｐａｌａｇｉ和ＲｏｍａＥ５］对ＫＫＴ点的进一步刻画给出了一个让目标函数 进一步下降的方法。 定理１．５如果（ ， ）是问题（１）非全局极小的ＫＫＴ点，那么只可能属于以下两种情况： （ａ）若ｇｒｘ ＞０，记 Ｘｉ一一∞ （ｂ）若ｇｒｘｉ≤０，且］ ∈Ｒ”使得ＺＴ（Ｂ＋２Ａ￣Ｉ）ｚ（Ｏ，则 （ｉ）若ｌ ｌＩｌ＜△＜记 Ｘｌ一一 ＋ａｚ 其中 ≤ （ｉｉ）若ｌｌ趣ｌｌ一△且ｘｌｚ≠０，记 一趣 维普资讯 http://www.cqvip.com
第５期 吕立波：解决大规模信赖域子问题的一种新算法 ５１ （ｉｉｉ）ｌＩ ｌｌ一△且ｚｉｚ一０，记 Ａ２ ｚ ｘｉｚ 一２一 蔷 其中 Ｘｉ ＋ａ十 ｚ）、＞竖：兰二［ 竖： ± 竖二兰 ： 皇± ｚ （Ｂ＋２ ｉｊ） 则我们有ＸＦ（ｘ￣）＜ （ ），ＩＩ ｚ Ｉｌ≤△ 。 如果 是一个非全局极小的ＫＫＴ点，则 只可能满足情况ａ或ｂ（ｉｉ）。 如果Ｓｉ ｓｐａｎ｛ ，ｚ）由以上定理我们知道相应问题（２）的解ｚ蚪 必满足 （ｚ抖 ）＜ （ ）。我们以 ｚ ＋ 为初始点，再次按照定理（１．２）对子空间的选取执行ＳＳＭ算法，求得问题（１）的新的ＫＫＴ点ｚ 。由 定理１．３可得，ｚ 必为问题（１）非全局极小点。于是我们证明了以下结论。 定理１．６设ｘ－／是问题（１）非全局极小的ＫＫＴ点 。则按照定理１．５选取，ｚ川，并继续按照定理 （１．２）选取子空间，则ＳＳＭ算法必收敛到问题（１）的全局极小点。 ２ ＳＳＭ算法的改进 我们知道，当问题（１）的规模相当大时，直接利用Ｃｈｏｌｅｓｋｙ分解计算求解是非常困难的。ＳＳＭ算法 将一个大规模问题的求解转化成对一系列中小规模问题的求解，再通过对解序列的讨论而得到问题解，从 而成功的降低了计算量。 以下我们讨论算法的具体实现过程。设ｄｉｍＳ 一ｚ，首先利用Ｋｒｙｌｏｖ子空间方法，将我们所选定的向 量扩充成ｚ维线性无关向量组，并令其为Ｓ 中的一组基。再利用Ｈｏｕｓｅｈｏｌｄｅｒ方法将其单位正交化以构 成一个矩阵ＶＥＲ 。预校正之后得到下面这个等价问题 ｍｉｎ ｚ∈Ｒ』 （ｚ）一百１ １’亩 ＋ １’Ｙ ６ （１１） Ｓ．ｔ． １ ｌＹ ＩＩ≤△ 其中豆一 ＢＶ， 一 ｇ，ｚ—ｖｙ。如果ｚ较大，则采用Ｌａｎｃｚｏｓ方法对豆三对角化，接着利用Ｍｏｒｅ，Ｓｏ— ｒｅｎｓｅｎ中的方法求解问题（１１），得到Ｙ ＋ ，ｚ抖 ， …。注意到在处理大规模问题时，对于矩阵 的计算量 和存储量将会随着ｚ的增长而快速增长。所以，在Ｈａｇｅｒ的实际计算中，作者只令ｚ一４，Ｓ —ｓｐａｎ｛ｘ ， ｘｓＱ ，Ｂ ｚ＋ｇ，岛），其中￡是Ｂ对应于ａ 的特征向量。具体计算方法和技巧，请参照Ｈａｇｅｒ。 结合上一节的证明过程不难发现，Ｈａｇｅｒ对Ｓ 的选取可以保证算法收敛到ＫＫＴ点。而我们的求解 策略使得如果算法迭代到非全局极小的ＫＫＴ点，我们可以依然通过选取适当的子空间，使得算法可以进 一步迭代下去，最终得到全局极小点。我们称该算法为改进ＳＳＭ算法，记做ＭＳＳＭ算法。为了减少问题 （２）的计算量，我们将ＭＳＳＭ算法中Ｓ 的维数定为３。算法的具体表述如下： 算法２ 步１ 给定初值ｋ：一０； 一０，ｚ 一（１，０，…，０） ∈Ｒ ，￡＞０，Ｓ ＝ｓｐａｎ｛ｘＩ，Ａｘ ，Ａ ），将相应的问题 （２）转化成（２）的形式，求解得到ｚ ＋ ， ＋ ，令ｋ：一五十１； 步２若ｌｌ（Ｂ＋ Ｄｚ ＋ｇ ＩＩ＜￡，则转入步５； 步３计算ｚ Ｐ，令Ｓ 一ｓｐａｎ｛ｘ ，ｚ Ｐ，Ｂｘ ＋ｇ）； 步４ 将相应的问题（２）转化成（１１）的形式，求解得到ｚ抖 ， ＋ ，令ｋ：一五十１，转入步２； 步５按照定理１．５的方法给出ｚ ； 步６令ｚ 一ｚｉ，Ｓ 一ｓｐａｎ｛ｘ ，ｚ）转入步４。 对以上ＭＳＳＭ算法的一些细节，比如预校正子的选取和求解ｚ ， 的技巧感兴趣的读者，请参阅 Ｈａｇｅｒ中相关的介绍。以下我们结合数值试验的结果，对算法进行讨论。 ４数值试验和讨论 在这一节中，我们将ＭＳＳＭ算法与［８］中的ＲＷ算法、［９］中的ＬＳＴＲＳ算法和Ｅ４］中的ＳＳＭ算法进 维普资讯 http://www.cqvip.com
５２ 运 筹 与 管 理 ２００７年第１６卷 行比较。令Ｂ＝Ｂｏ－－５１，其中，Ｂｏ是具有５点等距网格的单位正方形空格样板上的标准２维Ｌａｐｌａｃｅ算 子。我们随机地取２Ｏ个不同的ｇ，其中ｇ的元素一致分布在区间［Ｏ，１］上。对于不同的容许误差、信赖域 半径，我们有以下平均运算结果。 表Ｉ 不同容许误差条件下的矩阵向量乘积平均次数 表２不同信赖域半径条件下的矩阵向量的乘积平均次数 从上面的计算结果中我们可以看到，对于相同的容许误差和信赖域半径，ＳＳＭ算法和ＭＳＳＭ算法所 需要的向量乘积次数比ＲＭ算法和ＬＳＴＲＳ算法明显减少。而且由于ＭＳＳＭ算法中我们选定的维数比 ［－４］ＳＳＭ算法中的维数至少小一维，所以，ＭＳＳＭ算法所需的向量乘积次数比［４］ＳＳＭ算法更少。这一改 进在处理工程技术中出现的规模日益庞大的优化问题时，显示出其重要意义。同时，我们发现不同的容许 误差和信赖域半径对运算量起着关键性的作用。我们希望读者在利用ＭＳＳＭ算法构建信赖域算法的时 候，能够利用以上两份计算结果中的信息对信赖域算法进行一些调整。比如适当放宽容许误差和控制信 赖域半径，这样既不会对计算结果产生本质影响，又可以有交减少运算量，提高运算效率。 综上所述不难发现，序列子空间算法收敛性分析的关键所在就是关于Ｓｋ的选取。经过上面的讨论， 我们已经得到了可以保证全局收敛性的子空间选取办法，接下来对算法进一步的研究应该主要集中在如 何选取Ｓ 以达到满意的整体收敛速度，同时尽可能保持ＭＳＳＭ算法在节省运算量方面的优势。此外， ＭＳＳＭ算法在信赖域算法中的应用也是值得探讨的。 参考文献： ［１］Ｇａｙ Ｄ Ｍ．Ｃｏｍｐｕｔｉｎｇ ｏｐｔｉｍａｌ ｌｏｃａｌｌｙ ｃｏｎｓｔｒａｉｎｅｄ ｓｔｅｐｓ［Ｊ］．ＳＩＡＭ Ｊ．ｓｃｉ．Ｓｔａｔｉｓｔ．Ｃｏｍｐｕｔ．，１９８１，（２）：１８６—１９７． ［２］Ｇｏｌｕｂ Ｇ Ｈ，Ｖｏｎ Ｍａｔｔ Ｕ．Ｑｕａｄｒａｔｉｃａｌｌｙ ｃｏｎｓｔｒａｉｎｅｄ ｌｅａｓｔ ｓｑｕａｒｅｓ ａｎｄ ｑｕａｄｒａｔｉｃ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｎｕｍ．Ｍａｔｈ．．１９９１。 （５９）：５６１－５８０． ［３３ Ｇｏｕｌｄ Ｎ Ｉ Ｍ，Ｌｕｃｉｄｉ Ｓ，Ｒｏｍａ Ｍ，Ｔｏｉｎｔ Ｐ Ｌ．Ｓｏｌｖｉｎｇ ｔｈｅ ｔｒｕｓｔ－ｒｅｇｉｏｎ ｓｕｂｐｒｏｂｌｅｍ ｕｓｉｎｇ ｔｈｅ Ｌａｎｃｚｏｓ ｍｅｔｈｏｄＥＪ３．ＳＩＡＭ Ｊ．Ｏｐｔｉｍ．，１９９９，（９）：５０４－５２５． ［４３ Ｈａｇｅｒ Ｗ Ｗ．Ｍｉｎｉｍｉｚｉｎｇ ａ ｑｕａｄｒａｔｉｃ ｏｖｅｒ ａ ｓｐｈｅｒｅＥＪ］．ＳＩＡＭ Ｊ．Ｏｐｔｉｍ．，２００１，（１２）：１８８—２０８． ［５３ Ｌｕｃｉｄｉ Ｓ，Ｐａｌａｇｉ Ｌ，Ｒｏｍａ Ｍ．Ｏｎ ｓｏｍｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｓ ｗｉｔｈ ａ ｃｏｎｖｅｘ ｑｕａｄｒａｔｉｃ ｃｏｎｓｔｒａｉｎｔ［Ｊ］．ＳＩＡＭ Ｊ．Ｏｐｔｉｍ．，１９９８，（８）：１０５－１２２． ［６３ Ｍａｒｔｉｎｅｚ Ｊ．Ｌｏｃａｌ ｍｉｎｉｍｉｚｅｒｓ ｏｆ ｑｕａｄｒａｔｉｃ ｆｕｎｃｔｉｏｎｓ ｏｎ Ｅｕｃｌｉｄｅａｎ ｂａｌｌｓ ａｎｄ ｓｐｈｅｒｅｓ［Ｊ］．ＳＩＡＭ Ｊ．Ｏｐｔｉｍ．，１９９４，（４）： １５９—１７６． ［７３ Ｍｏｒｅ Ｊ Ｊ，Ｓｏｒｅｎｓｅｎ Ｄ Ｃ．Ｃｏｍｐｕｔｉｎｇ ａ ｔｒｕｓｔ ｒｅｇｉｏｎ ｓｔｅｐＥＪ］．ＳＩＡＭ Ｊ．Ｓｃｉ．Ｓｔａｔ．Ｃｏｍｐｕｔ．，１９８３，（４）：５５３—５７２． ［８３ Ｒｅｎｄｉ Ｆ，Ｗｏｌｋｏｗｉｃｚ Ｈ．Ａ ｓｅｍｉｄｅｆｉｎｉｔｅ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｔｒｕｓｔ ｒｅｇｉｏｎ ｓｕｂｐｒｏｂｌｅｍｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｌａｒｇｅ ｓｃａｌｅ ｍｉｎｉｍｉ— ｚａｔｉｏｎ［Ｊ３．Ｍａｔｈ．Ｐｒｏｇ．１９９７，（７７）：２７３—２９９． ［９３ Ｒｏｊａｓ Ｍ，Ａａｎｔｏｓ Ｓ Ａ，Ｓｏｒｅｎｓｅｎ Ｄ Ｃ．Ａ ｎｅｗ ｍａｔｒｉｘ－ｆｒｅｅ ａｌｇｏｒｉｔｈｍ ｏｒｆ ｔｈｅ ｌａｒｇｅ－ｓｃａｌｅ ｔｒｕｓｔ－ｒｅｇｉｏｎ ｓｕｂｐｒｏｂｌｅｍ［Ｊ］．ＳＩ— ＡＭ Ｊ．Ｏｐｔｉｍ．，２０００，（１１）：６１１－６４６． ［１Ｏ３ Ｓｏｒｅｎｓｅｎ Ｄ Ｃ．Ｎｅｗｔｏｆｆｓ ｍｅｔｈｏｄ ｗｉｔｈ ａ ｍｏｄｅｌ ｔｒｕｓｔ ｒｅｇｉｏｎ ｍｏｄｉｉｆｃａｔｉｏｎ［Ｊ］．ＳＩＡＭ Ｊ．Ｎｕｍｃｒ．Ａｎａ１．，１９８２，（１９）：４０９— ４２６． ［１１］Ｓｏｒｅｎｓｅｎ Ｄ Ｃ．Ｍｉｎｉｍｉｚａｔｉｏｎ ｏｆ ａ ｌａｒｇｅ－ｓｃａｌｅ ｑｕａｄｒａｔｉｃ ｆｕｎｃｔｉｏｎ ｓｕｂｊｅｃｔ ｔｏ ａ ｓｐｈｅｒｉｃａｌ ｃｏｎｓｔｒａｉｎｔ［Ｊ－］．ＳＩＡＭ Ｊ．Ｏｐｔｉｍ．。 １９９７．（７） １４１．１６１．
