PATH 求解器
PATH 求解器是 GAMS 中用于求解混合互补问题（Mixed Complementarity Problem, MCP）的高性能求解器。由 Michael C. Ferris 和 Todd S. Munson 开发，采用基于非光滑牛顿法的路径搜索算法，能够高效处理大规模互补性问题，广泛应用于经济均衡建模、交通网络分析、能源市场仿真和博弈论等领域。
作为 GAMS 生态系统中处理 MCP 问题的首选求解器，PATH 以其收敛速度快、数值稳定性高而著称。本文档系统介绍互补性问题的基础理论、PATH 算法的核心原理、求解器选项配置、高级主题以及完整的案例分析。
目录
1. 互补性问题概述
互补性问题（Complementarity Problem）是数学规划领域的一个重要分支，它描述了两组变量之间满足"互补"关系的系统。在最基本的非线性互补问题（NCP）中，给定函数 F: Rn → Rn，求向量 z ∈ Rn，使得 z ≥ 0，F(z) ≥ 0，且 zTF(z) = 0。这一条件意味着对于每个分量 i，要么 zi = 0，要么 Fi(z) = 0，或两者同时成立。
混合互补问题（MCP）对 NCP 进行了推广，允许变量具有更一般的上下界约束。给定函数 F(z) : Rn → Rn 以及上下界 l, u ∈ Rn（其中 l ≤ u），MCP 要求找到 z ∈ [l, u] 使得 F(z) 与 z 满足互补关系。具体而言，对于每个分量 i：当 li < zi < ui 时，Fi(z) = 0；当 zi = li 时，Fi(z) ≥ 0；当 zi = ui 时，Fi(z) ≤ 0。
MCP 在经济学中有着天然的应用场景。例如，在竞争性市场均衡中，价格与超额需求之间存在互补关系：如果价格为正，超额需求必须为零；如果存在超额需求，价格必须处于上界。类似地，在交通网络建模中，路径流量与旅行成本之间也满足互补条件。这些实际应用使得 MCP 成为经济建模和工程优化中的重要工具。
2. PATH 算法原理
PATH 求解器的核心算法基于非光滑牛顿法（Non-smooth Newton Method）与路径搜索（Path Search）策略的结合。该算法通过将互补条件转化为非光滑方程组，然后沿特定路径追踪问题的解。
2.1 算法框架
PATH 算法的基本思路是将 MCP 问题重新表述为寻找一个满足特定条件的点，使得该点位于由问题的可行域和互补条件所定义的"路径"上。算法从初始点出发，通过求解一系列线性互补问题（LCP）来产生搜索方向，并沿该方向进行步长控制，最终收敛到问题的解。
2.2 互补条件的转化
为了实现非光滑牛顿法的应用，PATH 首先将互补条件转化为等价的形式。常用的转化方法包括：
- Fischer-Burmeister 函数：φ(a,b) = √(a² + b²) - a - b，该函数满足 φ(a,b) = 0 ⇔ a ≥ 0, b ≥ 0, ab = 0
- 最小值函数：min(a,b) = 0 ⇔ a ≥ 0, b ≥ 0, ab = 0
通过引入这些函数，MCP 的互补条件被转化为一个非光滑方程组，从而可以使用牛顿类方法进行求解。
2.3 路径搜索策略
在每次迭代中，PATH 求解器执行以下步骤：
- 线性化：在当前点构造问题的线性化近似，计算广义雅可比矩阵
- 求解 LCP：求解一个线性互补问题（LCP）来确定搜索方向
- 线搜索：沿搜索方向执行非精确线搜索，确保充分的函数值下降
- 更新与检查：更新当前迭代点，检查收敛条件是否满足
2.4 关键技术特性
- 全局化策略：采用非单调线搜索技术，在保证收敛性的同时提高求解效率
- 稀疏矩阵处理：充分利用雅可比矩阵的稀疏结构，降低计算和存储开销
- 重启机制：当算法陷入困难区域时，自动从新的初始点重新开始搜索
- 热启动支持：可以利用先前求解的结果作为初始点，加速收敛过程
3. 求解器选项
PATH 求解器提供了丰富的选项参数，用户可以通过 GAMS 的 option 语句或在命令行中设置这些选项来调整求解行为。下表列出了常用的求解器选项：
| 选项名称 |
默认值 |
类型 |
说明 |
| convr |
1e-6 |
实数 |
相对收敛容差，控制残差的相对减少量 |
| conva |
1e-6 |
实数 |
绝对收敛容差，控制残差的绝对大小 |
| ftol |
1e-6 |
实数 |
函数值容差，判定函数值为零的阈值 |
| limiter |
10000 |
整数 |
最大牛顿迭代次数 |
| time_limit |
无限制 |
实数 |
求解时间限制（秒） |
| crash |
0 |
整数 |
起始点策略：0=使用用户提供初值，1=自动选择初值 |
| output |
1 |
整数 |
输出详细程度：0=最小输出，1=标准输出，2=详细调试输出 |
| scaling |
1 |
整数 |
是否启用自动缩放：0=禁用，1=启用 |
| preprocess |
1 |
整数 |
预处理级别：0=无，1=标准，2=完全 |
| basis_resolve |
0 |
整数 |
遇到奇异基时是否自动重新求解 |
| major_iterations |
100 |
整数 |
主迭代（路径搜索）的最大次数 |
| lcp_iterations |
1000 |
整数 |
每次主迭代中LCP子问题的最大迭代次数 |
在 GAMS 中设置选项的示例：
option path = "convr=1e-8 limiter=5000 output=0";
option mcp = path;
4. 高级主题
对于复杂的大规模 MCP 问题，合理使用高级技术可以显著提升求解效率和成功率。本节介绍预处理、缩放和其他高级优化技术。
4.1 预处理技术
PATH 求解器在求解之前会对问题进行预处理，以提高求解的数值稳定性：
- 变量重排序：通过对变量和方程进行重新排序，改善雅可比矩阵的对角占优特性
- 结构化简：检测并移除冗余的方程和变量，缩小问题规模
- 三角分解：对问题进行前向三角分解，加速后续迭代计算
4.2 缩放技术
当问题中各变量的量级相差较大时，缩放技术至关重要：
- 自动缩放：PATH 内置的自动缩放模块会根据变量的取值范围自动计算缩放因子
- 手动缩放：用户可以通过修改模型中的参数单位来手动调整变量量级
- 动态缩放：在求解过程中根据迭代进度动态调整缩放因子
4.3 初始点选择
初始点的选择对 PATH 求解器的收敛性有重要影响。良好的初始点可以显著减少迭代次数，而较差的初始点可能导致算法收敛到非期望的解甚至发散。建议：
- 尽量利用问题领域的先验知识设置初始点
- 对于经济均衡模型，可以从上一期的均衡解开始搜索
- 当模型求解困难时，尝试多次使用不同的随机初始点
4.4 诊断与调试
当求解失败时，可以通过以下方法进行诊断：
- 设置 output=2 获取详细的调试输出信息
- 检查残差在各分量上的分布，定位问题来源
- 分析雅可比矩阵的奇异性，检查模型是否存在结构性缺陷
- 使用热启动从部分解开始逐步调试
5. 案例分析
本节通过一个完整的空间价格均衡模型（Spatial Price Equilibrium Model, SPEM）展示 PATH 求解器在实际问题中的应用。该模型描述多个地理区域之间商品流动的市场均衡状态。
5.1 问题描述
假设有多个市场，每个市场具有线性供给和需求函数。商品可以在不同市场之间运输，运输成本与贸易量成正比。市场均衡的条件是：每个市场的本地供给加上从其他市场的流入等于本地需求加上流向其他市场的流出，且价格差不超过运输成本。
5.2 GAMS 模型实现
* 空间价格均衡模型 - 使用PATH求解器
sets
i 市场 / m1*m4 /
;
alias(i,j);
parameters
a(i) 需求截距
/ m1 100, m2 80, m3 120, m4 90 /
b(i) 需求斜率
/ m1 0.5, m2 0.6, m3 0.4, m4 0.55 /
c(i) 供给截距
/ m1 10, m2 15, m3 8, m4 12 /
d(i) 供给斜率
/ m1 0.3, m2 0.4, m3 0.2, m4 0.35 /
t(i,j) 运输成本
/ m1.m2 5, m1.m3 8, m1.m4 6
m2.m1 5, m2.m3 6, m2.m4 7
m3.m1 8, m3.m2 6, m3.m4 4
m4.m1 6, m4.m2 7, m4.m3 4 /
;
positive variables
p(i) 市场价格
s(i) 供给量
q(i,j) 从i到j的运量
;
free variables
dem(i) 需求量
;
equations
supply_eq(i) 供给函数
demand_eq(i) 需求函数
balance_eq(i) 市场出清条件
price_diff(i,j) 价格差约束
;
supply_eq(i).. s(i) =e= c(i) + d(i)*p(i);
demand_eq(i).. dem(i) =e= a(i) - b(i)*p(i);
balance_eq(i).. s(i) + sum(j, q(j,i)) =e= dem(i) + sum(j, q(i,j));
price_diff(i,j)$(not sameas(i,j)).. p(j) - p(i) =l= t(i,j);
model spem / supply_eq.s, demand_eq.dem, balance_eq.p, price_diff.q /;
option mcp = path;
solve spem using mcp;
display p.l, s.l, dem.l, q.l;
5.3 结果分析
求解完成后，PATH 会输出各市场的均衡价格 p.l、供给量 s.l、需求量 dem.l 和市场间的贸易流量 q.l。通过分析这些结果，可以得出以下结论：
- 各市场的价格差反映了运输成本和套利行为的影响
- 贸易流量方向从低价市场流向高价市场，验证了套利均衡条件
- 当价格差小于运输成本时，对应路径上的贸易量为零，体现了互补条件
PATH 求解器能够在数秒内完成求解，即使扩展到数十个市场也能保持高效的求解性能。这充分展示了 PATH 在处理大规模 MCP 问题方面的优势。
在线留言
尊敬的客户朋友，如您有任何意见建议，请通过下表反馈给我们，我们会尽快与您联系。
|
400-621-1085
