A Sequential Bundle Method for Solving a MPEC Problem

本文主要探讨了一类凸数学规划问题，即带有不可微凸目标函数和约束条件分离为两个变量向量的数学规划问题，其中第二个变量向量属于约束子问题的最优解集。文章介绍了一种序列束方法来解决这类问题，并对其进行了收敛性分析，证明了在一定条件下，该算法可以在有限步骤内终止于一个近似解。 在学术领域，MPEC（带有均衡约束的数学规划问题）是指含有均衡约束的优化问题，这类问题在理论和应用中都有重要价值。MPEC问题通常很难求解，因为它们结合了非线性规划、非光滑优化等复杂性质。MPEC问题的一般形式可以表示为寻找最优解以最小化目标函数，同时满足一组均衡条件。 对于这类问题，本文提出了一种新的求解方法，即序列束方法。这种方法是通过结合Hintermüller在2001年提出的近邻束方法和Brännlund、Kiwiel和Lindberg在1995年提出的下降近邻水平束方法构建的。具体来说，序列束方法的每个迭代步骤包括两个主要阶段：首先使用第一个束方法为每次迭代过程提供初始点，然后利用第二个束方法在每次迭代过程中找到约束子问题的（近似）最优解。 为了更清楚地解释这种方法的工作原理，让我们看看具体的数学表达形式。考虑一个MPEC问题，形式如下： min f(x,y) s.t. y ∈ Ω2 ⊂ R^n, x ∈ Ω1 ⊂ R^m ∧ x,y ∈ Ω1 × Ω2 ⊂ R^m × R^n 其中f: R^(m+n) → R是凸函数（一般情况下不可微），Ω1是闭凸集，而Ω2由下式定义： Ω2 = Arginf_{y ∈ R^n} ϕ(y) = {y | ϕ(y) = inf_{y' ∈ R^n} ϕ(y')} 这里，函数ϕ: R^n → R也是凸函数（一般情况下不可微）。在问题设定中，目标函数f是两个变量x和y的函数，而约束条件被分成了两个部分，分别与x和y相关。 本文提出的序列束方法在迭代过程中，首先用近邻束方法产生每个迭代的初始点，然后用下降近邻水平束方法在每个迭代中找到约束子问题的近似最优解。文章在最后一节提供了该算法的收敛性分析，指出在某些条件下，算法可以在有限步骤内按照给定的容忍误差终止于一个近似解。 关键词包括非线性规划、非光滑优化、MPEC问题、束方法、水平束方法、近邻束方法。主题分类方面，属于2000年的AMR Subject Classification中的90C30、90C25、49M37、90C59等。 文章的这部分内容给出了数学模型和方法论的基本介绍，为后续的具体算法实现和理论分析奠定了基础。文章所提出的序列束方法是针对一类特定MPEC问题的求解，其创新之处在于将不同束方法的优势结合起来，解决了目标函数和约束条件具有特定结构的优化问题。 值得一提的是，该研究得到了“博士点专项科研基金”（Grant***）和国家自然科学基金（Grant***）的支持。这表明该研究课题得到了相关科研基金的资助，说明了其研究价值和潜在的应用前景。 研究团队由夏尊铨、沈洁和李平庞组成，他们在优化理论和算法开发领域有着丰富的经验和深入的研究。他们在本研究中将理论研究与实际应用相结合，提出了有创新性的解决方案，为解决这类复杂优化问题提供了新的思路。 本研究在理论探索和实际应用方面都有重要的贡献。对于那些对非光滑优化、非线性规划和MPEC问题感兴趣的研究者和实践者来说，该文具有重要的参考价值。通过详细的研究和分析，本文不仅为我们解决这类问题提供了工具，也为相关领域的进一步研究奠定了基础。