均衡约束规划的新型松弛算法及其应用研究

Mathematical programs with complementarity constraints are receiving more and more attention now in operations research. This project will design numerical algorithms for solving mathematical programs with complementarity constraints. .This project will mainly focus on the following issues: (1) Using the penalty method that separates complementarity constraints, we introduce a new relaxed scheme to solve mathematical programs with complementarity constraints. We will study the first-order optimality conditions for the relaxed problem by virtue of the advanced tools of the variational analysis, and build the connection between optimality conditions of the relaxed problem and that of mathematical programs with complementarity constraints. (2) It follows from the separable property of the relaxed problem and the nonconvexness of its feasible set that we use the idea of the proximal alternating minimization method to design new algorithms for solving the relaxed problem and we establish their global convergence under mild assumptions. Under different constraint qualifications, we prove that the stationary point generated by proposed algorithms converges to different stationary points of mathematical programs with complementarity constraints. (3) We will test the performance of the proposed algorithms by use of the test problems set MacMPEC written by Leyffer. Moreover, we will use the proposed algorithms to solve problems from game theory and the large-scale problems from support vector machines and portfolios..This project will further enrich numerical algorithms of mathematical programs with complementarity constraints, and will provide effective numerical methods for solving mathematical programs with large-scale complementarity constraints.

均衡约束规划是运筹学研究的热点之一。本项目将围绕均衡约束规划的算法设计和应用展开研究。本项目主要研究内容包括：（1）基于分离均衡约束项的罚方法，提出新型松弛格式来求解均衡约束规划问题。运用变分分析工具来研究松弛格式的一阶最优性条件，在合适约束规格下，建立松弛格式最优性条件与均衡约束规划最优性条件之间的对应关系。（2）根据松弛问题可分离的特性以及其可行集非凸的特点，借鉴临近点交替极小化方法的思想来设计新型的算法求解该松弛问题，在合适的假设下，建立算法的全局收敛性。在不同的约束规格下，建立算法生成迭代序列的稳定点与原问题稳定点之间的对应关系。（3）用Leyffer的MacMPEC测试问题集来测试提出算法的数值性能。进一步，应用提出的算法求解博弈模型、大规模的支持向量机模型和投资组合风险模型。本项目的研究将进一步丰富均衡约束规划的数值算法，同时为大规模均衡约束规划问题的求解提供算法支持。

均衡约束规划一直是运筹学和管理科学研究的热点问题。本项目研究的主要内容一方面设计有效的算法对互补约束进行分离化处理，从而为设计高效的新型算法求解均衡约束规划提供理论基础。另一方面，本项目对供应链和量化投资中的实际问题建立相应均衡规划模型和实证分析。在本项目的资助下，主要取得以下三个方面的成果：.（1）提出加权线性罚函数方法求解非线性互补问题。该新型的方法不但具有传统低阶罚函数方法的指数收敛速度，而且具有线性罚函数建立局部超线性收敛性的优点。在一致P-函数的假设下，我们建立迭代点序列收敛子列的指数收敛性。进一步，我们运用semismooth Newton法求解加权的线性罚方程，并且证明了迭代点序列的Q-超线性收敛性。最后，我们运用MCPLIB测试问题集对提出方法的数值性能进行分析。数值结果显示，新提出的方法能够更加高效精确地求解测试问题集。.（2）提出非线性Jacobian迭代的加权线性罚函数方法求解美式期权定价模型在有限体积法离散后的线性互补问题。对任意给定的低阶指数因子，加权线性罚方程的非线性Jacobian迭代格式均具有唯一的解析解。进一步，我们证明了迭代序列的全局收敛性和指数阶收敛速度。最后，运用有限体积离散的美式看跌期权模型对提出方法的数值性能进行对比分析。数值结果显示，新型方法能够更加高效精确地得到美式期权定价模型的近似解。.（3）提出一个由3PL(第三方物流平台)和制造商通过3PL代付货款的担保率共同承担零售商破产风险的风险分摊方式，研究在该模式下由3PL、供应商和资金受限零售商组成的供应链系统的最优运作策略。得到主要结论：(1)3PL的融资及采购服务能够弱化零售商资金受限对供应链的不利影响；(2)3PL和制造商进行适当的风险分摊可刺激零售商采取更积极的订货策略；(3)当3PL代付货款的担保率满足一定的条件，该供应链系统可以达到协调。最后，我们将分散决策与集中决策下的最优订货量进行比较，给出能够使该供应链达到协调策略的条件。