MILES 求解器
求解混合互补问题（MCP）的高效求解器
MILES（Mixed Inequality and Linear Equation Solver，混合不等式与线性方程求解器）是 GAMS 中用于求解混合互补问题（MCP，Mixed Complementarity Problem）的专用求解器。MILES 采用推广的牛顿法（Newton's method）与 Lemke 算法的互补枢轴技术相结合，高效求解经济均衡、博弈论、能源市场、交通运输及工程优化等领域中的大规模互补性问题。
目录
1. 摘要
MILES 求解器专门用于求解混合互补问题（Mixed Complementarity Problem，MCP）。MCP 是数学规划中一类重要的问题形式，它统一了非线性方程组、变分不等式和互补问题等多种数学结构。MILES 的名称来源于"Mixed Inequality and Linear Equation Solver"（混合不等式与线性方程求解器），它利用广义牛顿法，在每次迭代中将原问题线性化为一个线性互补问题（LCP），然后调用 Lemke 算法对 LCP 进行求解。
MILES 的核心优势在于：
- 高效处理大规模稀疏 MCP 问题，充分利用问题结构的稀疏性；
- 鲁棒性强的求解策略，内置退化处理和奇异雅可比矩阵的应对机制；
- 作为 GAMS 的原生求解器，支持所有 GAMS MCP 模型语法；
- 提供灵活的选项控制，用户可精细调整求解参数以适应不同问题特性。
2. 引言
混合互补问题（MCP）是数学建模中一种强大的表述框架。给定一个函数 F: Rn → Rn，以及变量 z ∈ Rn 的上下界 l 和 u（允许取 -∞ 和 +∞），MCP 要求寻找 z 满足：
对每个分量 i，要么 li < zi < ui 且 Fi(z) = 0，
要么 zi = li 且 Fi(z) ≥ 0，
要么 zi = ui 且 Fi(z) ≤ 0。
当所有界均为 0 到 +∞（即 z ≥ 0）时，MCP 退化为标准的非线性互补问题（NCP）：F(z) ≥ 0，z ≥ 0，且 F(z)Tz = 0。当所有界均为 -∞ 到 +∞ 时，MCP 退化为非线性方程组 F(z) = 0。
MCP 在经济学中有着广泛的应用。一般经济均衡模型（CGE）、纳什均衡博弈模型、能源市场模型、交通网络均衡问题以及工程中的接触问题等，都可以自然地表述为 MCP 形式。GAMS 提供了声明 MCP 模型的完整语法，而 MILES 是求解这类模型的主要求解器之一。
3. 牛顿算法
MILES 的核心求解框架是推广的牛顿法。该方法将求解 MCP 问题转化为一系列线性互补问题（LCP）的求解。算法的主要步骤如下：
- 初始点选择：从用户提供的初始点 z0 开始，或由 GAMS 生成默认初始点。
- 线性化：在当前点 zk 处，计算函数值 F(zk) 和雅可比矩阵 J(zk)，构造线性近似：
LCP(q, M)：求 w，z 满足 w = q + M z，w ⟂ z，l ≤ z ≤ u
其中 q = F(zk) - J(zk)zk，M = J(zk)。
- 求解 LCP：调用 Lemke 算法求解上述线性互补问题，得到搜索方向 dk。
- 线搜索：沿搜索方向进行线搜索，确定步长 αk，使得新的迭代点 zk+1 = zk + αkdk 满足一定的下降条件。
- 收敛检查：如果残差 ||F(zk+1)|| 足够小，则算法终止；否则返回步骤 2。
MILES 在牛顿框架中加入了多种增强技术：
- 阻尼牛顿技术：当完全牛顿步导致残差增大时，采用阻尼策略缩小步长，提高全局收敛性。
- 稀疏矩阵处理：利用 GAMS 提供的稀疏雅可比矩阵结构，采用稀疏线性代数技术，显著减少计算量和存储需求。
- 退化处理：当 Lemke 算法遇到退化或几乎退化的枢轴时，MILES 采用微扰策略和重新启动机制绕开数值困难。
- 热启动：支持从上一个求解结果的热启动，加速序列求解场景中的收敛速度。
牛顿法的收敛速度通常是二阶（局部超线性收敛），这意味着在解的邻域内，迭代次数通常很少，即使对于大规模问题也是如此。然而，对于高度非线性的问题，初始点的选择对收敛性有显著影响。
4. Lemke 方法
Lemke 方法是一种求解线性互补问题（LCP）的著名算法。MILES 在每次牛顿迭代中调用 Lemke 算法求解线性化的 LCP 子问题。Lemke 方法的基本思想是通过引入一个人工变量（辅助变量），将原始 LCP 转化为一个增广系统，然后通过一系列互补枢轴操作逐步消除人工变量，最终得到原问题的解。
Lemke 方法的算法流程如下：
- 初始化：引入人工变量 z0，构造增广系统。选择初始基本可行解。
- 主枢轴：确定离开变量和进入变量，执行枢轴操作更新基矩阵。
- 互补条件维护：每次枢轴操作都保持互补条件（互补变量对不能同时为基变量），确保收敛到互补解。
- 终止判断：如果人工变量 z0 被驱赶出基（变为零），则算法成功且得到 LCP 的解。如果遇到射线解（无界），则 LCP 可能无解或需要进一步分析。
在 MILES 的上下文中，Lemke 方法的几个关键特性值得注意：
- 矩阵 M 的性质：Lemke 方法适用于任何矩阵 M，但当 M 是足够共正（copositive）矩阵时，算法保证有限步终止。在 MILES 的牛顿框架中，雅可比矩阵在解附近通常是正定的，这有利于 Lemke 方法的成功。
- 数值稳定性：MILES 实现了 Lemke 方法的数值稳定版本，包括迭代 refinement、枢轴容差控制和最小化舍入误差积累的策略。
- 处理失败情况：当 Lemke 方法遇到射线解（表明 LCP 可能无解或矩阵结构不良）时，MILES 会尝试调整参数并重新求解，或采用备选策略继续主算法。
- 效率优化：MILES 对 Lemke 方法进行了效率优化，包括稀疏矩阵存储格式、最小度排序（minimum degree ordering）等预处理技术，加速枢轴操作。
Lemke 方法被嵌入在牛顿迭代的内循环中，每次牛顿迭代需要求解一个 LCP。对于大规模问题，LCP 的求解是整个算法的主要计算开销，因此 MILES 特别关注 Lemke 方法的计算效率。
5. 选项文件
MILES 提供了丰富的求解选项，允许用户精细控制求解过程。选项可以通过 GAMS 的 option 语句直接设置，或者通过求解器选项文件（miles.opt）进行详细配置。
以下列出 MILES 的主要选项：
| 选项名称 |
默认值 |
描述 |
| iterlim |
1000 |
最大牛顿迭代次数。如果问题未能在此次数内收敛，求解器将终止并报告迭代限制到达。 |
| reslim |
1.0e-6 |
残差收敛容差。当最大互补残差（max(|min(F_i, z_i - l_i, u_i - z_i)|)）低于此值时，认为问题已收敛。 |
| domlim |
100 |
允许的最大退化步数。当算法连续多次只能走退化步时，超过此限制后将终止求解。 |
| workspace |
16 |
工作空间大小（兆字节）。MILES 使用此空间存储内部矩阵和临时数据，对于大规模问题可能需要增大此值。 |
| lcpiterlim |
10000 |
每次牛顿迭代中 Lemke 算法的最大迭代次数（枢轴次数）。 |
| lcpreslim |
1.0e-8 |
LCP 子问题求解的残差容差。通常应比主容差更严格。 |
| pivottol |
1.0e-8 |
枢轴容差，用于判断枢轴元素是否为零。过小的值可能导致数值不稳定性。 |
| lplin |
100 |
线搜索中的最大函数求值次数。 |
| lpdump |
0 |
控制详细输出（调试用）。值越大输出越详细，通常无需更改。 |
| haltonsamples |
0 |
使用 Halton 拟随机序列生成不同初始点的数量（当设为非零值时）。用于全局搜索策略。 |
| haltonskip |
0 |
Halton 序列的跳过点数。 |
在 GAMS 中设置选项的示例：
option mcp = miles;
option iterlim = 500;
option reslim = 1e-8;
$onecho > miles.opt
lcpiterlim 5000
workspace 64
$offecho
mymodel.optfile = 1;
solve mymodel using mcp;
关于选项的更多细节，可参考 GAMS 求解器手册中的 MILES 章节。
6. 日志文件
MILES 在求解过程中会输出日志信息，反映求解器的运行状态和进展。GAMS 将 MILES 的日志信息显示在屏幕输出（GAMS IDE 的日志窗口或命令行输出）以及 GAMS 的 LST 列表文件中。
典型的 MILES 日志输出格式如下：
MILES 版本 5.0 Build 12345
GAMS/MILES 求解器
模型统计
变量数: 1000
方程数: 1000
非零元素: 5000
非零雅可比: 5000
迭代 残差 步长 状态
1 2.45E+01 1.00
2 5.67E+00 1.00
3 1.23E-01 0.50
4 4.56E-04 1.00
5 7.89E-07 1.00 收敛
求解时间: 0.45 秒
牛顿迭代次数: 5
Lemke 枢轴总数: 47
日志中各列的含义：
- 迭代：牛顿迭代的次数编号。
- 残差：当前迭代点的互补残差（最大范数）。该值应随迭代逐渐下降。
- 步长：线搜索所确定的步长因子。步长为 1.0 表示采用了完全牛顿步；小于 1.0 表示采用了阻尼步。
- 状态：求解状态（如"收敛"、"迭代限制"、"退化"等）。
通过观察日志中的残差下降趋势，可以判断求解过程是否正常。如果残差反复震荡或下降极其缓慢，可能需要调整求解选项（如增大 iterlim、调整 reslim、或尝试不同的初始点）。
7. 状态文件
MILES 求解完成后，GAMS 会在模型实例中设置求解状态信息，这些信息可以通过 GAMS 的模型属性进行访问。主要的状态属性包括：
- mymodel.solvestat：求解器状态码，指示求解过程是否正常完成。
- mymodel.modelstat：模型状态码，指示求解结果的质量。
- mymodel.residual：求解结束时的最终互补残差。
- mymodel.number：求解过程中的牛顿迭代次数。
- mymodel.dominate：求解过程中遇到的退化步数。
常见求解状态码（solvestat）的含义：
| 代码 |
状态 |
说明 |
| 1 |
Normal |
正常完成，求解器退出。 |
| 4 |
Iteration Interrupt |
达到迭代限制（iterlim）而终止。 |
| 5 |
Resource Interrupt |
达到时间限制（reslim）而终止。 |
| 6 |
Terminated by Solver |
求解器因错误或无法继续而终止。 |
常见模型状态码（modelstat）的含义：
| 代码 |
状态 |
说明 |
| 1 |
Optimal |
问题已成功求解，残差在容差范围内。 |
| 2 |
Locally Optimal |
找到局部最优解（对于 MCP 即收敛到互补解）。 |
| 3 |
Unbounded |
问题无界（MCP 中通常意味着互补条件无法满足）。 |
| 4 |
Infeasible |
问题不可行（可能存在矛盾约束）。 |
| 6 |
Intermediate Infeasible |
求解过程中在某一步出现了不可行情况。 |
| 7 |
Intermediate Nonoptimal |
求解过程中在中途被中断，未达到收敛。 |
| 13 |
Error No Solution |
求解器遇到错误，未得到解。 |
在 GAMS 中，可以通过条件语句结合状态码来处理求解结果：
solve mymodel using mcp;
if (mymodel.solvestat = 1 and mymodel.modelstat = 1,
display "求解成功", mymodel.residual;
else
display "求解失败，状态：", mymodel.solvestat, mymodel.modelstat;
);
8. 终止信息
MILES 在求解终止时会产生一条终止信息（termination message），说明求解结束的原因。终止信息通过 GAMS 的模型属性 mymodel.solvestat 和 mymodel.modelstat 反映，并在 GAMS 输出中显示为文本。
以下是 MILES 常见的终止信息及其含义：
| 信息 |
说明 |
| 收敛（Converged） |
求解成功，残差已降低到指定的收敛容差（reslim）以下。这是期望的正常终止状态。 |
| 达到迭代限制（Iteration limit reached） |
牛顿迭代次数达到 iterlim 设置的上限但尚未收敛。可尝试增大 iterlim 或检查问题设定。 |
| 达到时间限制（Resource limit reached） |
求解时间超过 GAMS 的时间限制设定。可尝试增加时间资源。 |
| 退化步过多（Too many degenerate steps） |
求解器连续走了过多退化步（超过 domlim 设定），无法取得有效进展。这通常表明问题在当前位置附近存在奇异性。 |
| Lemke 方法失败（Lemke failed） |
内层 LCP 子问题的求解失败。可能的原因包括：雅可比矩阵奇异、数值不稳定、或线性化后的 LCP 无解。 |
| 奇异雅可比（Singular Jacobian） |
雅可比矩阵在当前点接近奇异，无法可靠地进行线性化。可尝试不同的初始点或调整问题设定。 |
| 工作空间不足（Insufficient workspace） |
设置的工作空间不足以完成求解。可通过增大 workspace 选项解决。 |
| 数值错误（Numerical error） |
求解过程中遇到了数值溢出、除零或其他数值异常。可尝试调整枢轴容差或检查问题缩放。 |
| 用户中断（User interrupt） |
用户手动中断了求解过程。 |
当遇到非收敛的终止信息时，建议的排查步骤：
- 检查模型是否正确地表述为 MCP 形式，特别是变量的上下界设置是否合理。
- 检查初始点是否合理，尝试提供更好的初始估计。
- 增大 iterlim 和/或调整 reslim 参数。
- 增大 workspace 选项确保有足够的内存。
- 检查问题是否存在内在的数值困难（如缩放不良、不连续性等）。
- 尝试使用 GAMS 的其他 MCP 求解器（如 PATH）进行对比。
9. 参考文献
- Rutherford, T. F. (1993). MILES: A Mixed Inequality and Linear Equation Solver. Working Paper, Department of Economics, University of Colorado.
- Dirkse, S. P. and Ferris, M. C. (1995). The PATH Solver: A Non-Monotone Stabilization Scheme for Mixed Complementarity Problems. Optimization Methods and Software, 5:123-156.
- Cottle, R. W., Pang, J. S. and Stone, R. E. (1992). The Linear Complementarity Problem. Academic Press.
- Lemke, C. E. (1965). Bimatrix Equilibrium Points and Mathematical Programming. Management Science, 11:681-689.
- Ferris, M. C. and Pang, J. S. (1997). Engineering and Economic Applications of Complementarity Problems. SIAM Review, 39(4):669-713.
- Brooke, A., Kendrick, D., Meeraus, A. and Raman, R. (1998). GAMS: A User's Guide. GAMS Development Corporation.
- Rutherford, T. F. (1995). Extension of GAMS for Complementarity Problems Arising in Applied Economic Analysis. Journal of Economic Dynamics and Control, 19(8):1299-1324.
在线留言
尊敬的客户朋友，如您有任何意见建议，请通过下表反馈给我们，我们会尽快与您联系。
|
400-621-1085
