SNOPT 求解器

SNOPT（Sparse Nonlinear OPTimizer）是GAMS内置的一款高性能大规模稀疏非线性规划（NLP）求解器，基于序列二次规划（SQP）算法。SNOPT采用先进稀疏矩阵技术，能够高效处理包含数千个变量和约束的大规模优化问题，特别适用于目标函数和约束条件为非线性但具有稀疏结构的大规模问题。SNOPT由Philip E. Gill、Walter Murray和Michael A. Saunders共同开发，是求解非线性约束丰富的优化问题的首选工具之一。

1. Introduction（介绍）

SNOPT（Sparse Nonlinear OPTimizer）是GAMS内置的一款大规模稀疏非线性规划求解器，专为求解以下形式的非线性规划问题而设计：

minimize f(x) subject to l ≤ { x, g(x), Ax } ≤ u

其中f(x)是目标函数，g(x)是非线性约束函数，Ax是线性约束，l和u分别是下界和上界。SNOPT假设f(x)和g(x)是连续可微的，且至少有一阶导数是稀疏的。

SNOPT的核心特点包括：

适合非线性约束多的模型：SNOPT在约束数量远多于变量数量的问题上表现尤为出色，能够高效处理高度约束的非线性优化问题。
大规模稀疏处理能力：利用稀疏矩阵技术，显著降低计算和内存开销，支持数千个变量和约束的大规模问题。
SQP算法稳健性：序列二次规划方法具有良好的全局收敛性和局部超线性收敛速度。
弹性模式：当问题不可行时自动进入弹性模式，通过松弛约束恢复可行性。
冷启动与热启动：支持从冷启动或热启动（利用高级基信息）开始求解。

SNOPT广泛应用于结构优化、过程系统优化、航空航天轨迹优化、可计算一般均衡（CGE）模型、宏观经济预测和资源配置优化等领域。

2. Description of the Method（方法描述）

SNOPT采用序列二次规划（Sequential Quadratic Programming, SQP）方法求解非线性规划问题。SQP方法的核心思想是在当前迭代点对原问题进行局部二次近似，然后求解该近似二次规划（QP）子问题以获得搜索方向，并通过线搜索确定步长以在每次迭代中逐步逼近最优解。

在每次主迭代中，SNOPT构造如下QP子问题：

minimize g^Td + ½ d^THd subject to l ≤ { x_k + d, g(x_k) + J_kd, A(x_k + d) } ≤ u

其中g是目标函数的梯度，H是拉格朗日函数的Hessian矩阵近似，J是非线性约束的Jacobi矩阵，A是线性约束矩阵，d是搜索方向。

SNOPT的SQP实现具有以下关键技术特性：

稀疏矩阵技术：充分利用问题的稀疏结构，大幅降低计算和存储需求，使SNOPT能够高效求解大规模稀疏问题。
增广拉格朗日价值函数：采用增广拉格朗日函数作为价值函数（merit function），用于衡量搜索方向的优劣和确定步长，平衡目标函数下降和可行性恢复。
有效集策略（Active Set）：通过维护有效约束集，高效处理不等式约束。在每个QP子问题求解中，有效集方法确定哪些约束在最优解处起主导作用。
BFGS拟牛顿更新：采用有限内存的BFGS公式更新Hessian矩阵近似，无需精确计算二阶导数，同时保证超线性收敛速度。
弹性模式（Elastic Mode）：当原始问题不可行时，SNOPT自动进入弹性模式，通过引入松弛变量和惩罚项来放宽约束，使问题恢复可行并继续求解。
线搜索（Line Search）：沿搜索方向使用回溯线搜索确定合适的步长，确保价值函数充分下降，保证全局收敛性。

SNOPT的全局收敛性通过线搜索技术和增广拉格朗日价值函数保证，局部超线性收敛速度则由BFGS拟牛顿更新实现。算法通常在几十到几百次主迭代内收敛到满足可行性和最优性容差的高精度解。

3. Starting Points（初始点与高级基）

SNOPT的收敛速度和最终解的质量在很大程度上依赖于初始点的选择。GAMS为SNOPT提供以下几种初始点设置方式：

默认初始点：如果用户未指定初始值，SNOPT会自动为变量生成初始点。默认情况下，连续变量取0值，但有下界时取下界值，有上界时取上界与下界的中间值。
用户指定初始点：通过在GAMS模型中使用variable.l属性为变量指定初始值。良好的初始点可以显著减少迭代次数并提高找到全局最优解的可能性。
高级基（Advanced Basis）：对于与已求解模型类似的新问题，可以使用GAMS的save和restart功能保存和恢复基（basis）信息，从而加速求解过程。高级基利用了先前求解的约束激活模式信息，能够大幅减少冷启动所需的迭代次数。

在设置初始点时，建议遵循以下原则：

尽可能提供接近真实最优解的初始值，特别是对非线性较强的约束变量。
避免使用使得约束函数或目标函数无定义的初始值（如分母为零、对数自变量为负、开平方自变量为负等）。
对于大规模问题，考虑先求解简化版本或松弛版本，然后将其最优解作为完整问题的初始点。
使用option NLP = SNOPT;后，GAMS会自动选择合适的求解器参数来处理初始点。
如果求解器在默认初始点下收敛困难，尝试使用Start = Warm选项配合先前保存的基信息进行热启动。

4. GAMS Options（GAMS选项）

在GAMS中使用SNOPT求解器，需要在模型中指定求解器选项。以下是与SNOPT相关的主要GAMS选项：

基本用法：

option NLP = SNOPT;       * 指定SNOPT作为NLP求解器
option QCP = SNOPT;       * 指定SNOPT作为QCP求解器
option LP = SNOPT;        * 指定SNOPT作为LP求解器
option RMINLP = SNOPT;    * 指定SNOPT作为RMINLP求解器

求解器选项设置：

可以通过$option编译时指令或option运行时语句设置SNOPT的具体选项：

$option SNOPT <option_name> = <value>
option SNOPT = "<option_name> <value>";

示例：

$option SNOPT iterations = 10000
option SNOPT = "major_iterations 500";
option SNOPT = "major_optimality_tolerance 1e-8";

常用GAMS控制选项：

reslim：求解时间限制（秒），如 option reslim = 3600;
iterlim：迭代次数限制，如 option iterlim = 5000;
optcr：最优性容差（相对），如 option optcr = 1e-6;
optca：最优性容差（绝对），如 option optca = 1e-9;
domlim：允许的域错误次数，如 option domlim = 10;

5. Options（选项列表）

SNOPT提供了丰富的求解器选项，用于控制算法各个方面的行为。以下列出了最常用的选项及其说明：

选项名称	默认值	说明
`Major iterations`	500	主迭代（SQP迭代）的最大次数。当问题规模较大或非线性较强时，可能需要增加此值。
`Minor iterations`	500	每个主迭代中QP子问题的最大迭代次数。
`Major feasibility tolerance`	1.0e-6	主迭代的可行性容差，控制约束违反的允许程度。
`Major optimality tolerance`	1.0e-6	主迭代的最优性容差，控制KKT条件的满足精度。
`Minor feasibility tolerance`	1.0e-6	QP子问题的可行性容差。
`Minor optimality tolerance`	1.0e-6	QP子问题的最优性容差。
`Hessian`	Limited memory	Hessian矩阵更新方式：`Limited memory`（有限内存，适合大规模问题）或`Full memory`（完全内存）。
`Hessian dimension`	30	有限内存Hessian的存储维度，决定拟牛顿更新的存储量。
`Elastic mode`	NO	是否启用弹性模式处理不可行问题：`YES`或`NO`。启用后自动松弛不可行约束。
`Unconstrained`	NO	是否假定问题为无约束优化。设为YES可跳过约束处理步骤。
`Scale`	YES	是否对问题进行自动缩放，改善数值稳定性。
`Derivative option`	1	导数计算方式：0=用户提供解析导数，1=自动有限差分。
`Verify level`	0	导数验证级别：0=不验证，1=梯度验证，2=梯度+Hessian验证。
`Start`	Cold	启动方式：`Cold`（冷启动）或`Warm`（热启动，利用高级基）。
`Print level`	1	输出详细程度：0=最小输出，1=正常输出，2+=详细调试输出。
`Solution`	YES	是否输出解文件。
`Timing level`	0	计时详细程度：0=不计时，1=基本计时，2=详细计时。
`Superbasics`	500	允许的最大超基变量（superbasic）数量。增加此值可处理更复杂的有效集。

选项可以通过多种方式传递给SNOPT：

在GAMS中使用option SNOPT = "option_name value";语句。
使用$option SNOPT option_name = value编译时指令。
通过SNOPT选项文件（通常命名为snopt.opt）。

当使用选项文件时，需要在GAMS模型中添加：

option SNOPT = "options_file snopt.opt";

6. The SNOPT Log（日志文件说明）

SNOPT在求解过程中会生成详细的日志输出到GAMS列表文件（.lst），包含迭代信息和求解状态。理解日志内容是诊断求解问题、优化求解器性能和判断求解质量的关键。

日志文件各列说明：

列标题	说明
Itns	主迭代（SQP迭代）的累计次数。
Major	当前主迭代步序号。
Minor	当前主迭代中QP子问题的迭代次数。
Penalty	惩罚参数值，用于平衡目标函数和约束违反。
Feasible	当前点是否可行（Yes/No）。显示为Yes表示所有约束在容差范围内满足。
Optimal	当前点是否满足最优性条件（Yes/No）。
Objective	当前目标函数值。
Merit Function	价值函数值，用于线搜索决策。价值函数综合了目标函数和约束违反信息。
Max Primal Inf	最大原始不可行度（约束违反量）。该值应随着迭代逐渐减小至低于可行性容差。
Max Dual Inf	最大对偶不可行度。该值应逐渐减小至低于最优性容差。
Step	步长（线搜索的步长因子），取值范围通常为(0,1]。

求解终止状态说明：

退出信息（Exit Information）	说明
Finished successfully	求解成功，找到满足可行性和最优性容差的最优解。
Optimal solution found	找到最优解，KKT条件在容差范围内满足。
The problem is infeasible	问题不可行，约束条件无法同时满足。可检查约束定义是否正确，或启用弹性模式分析不可行原因。
The problem is unbounded	问题无界，目标函数可无限优化。可检查是否遗漏了必要的约束或边界。
Major iteration limit reached	达到主迭代次数上限，求解未完成。可增加`Major iterations`选项值。
Minor iteration limit reached	达到次要迭代次数上限，QP子问题未收敛。
User requested termination	用户终止求解（如达到时间限制或用户中断）。
Resource limit reached	达到求解时间限制（`reslim`）。可增加时间限制值。

通过分析日志文件，用户可以：

监控求解进度，判断算法是否正常收敛。
识别问题难点，如可行性或最优性难以满足时可及时调整策略。
调整求解器选项（如容差、迭代限制、Hessian更新方式等），提高求解效率和稳健性。
对比不同初始点或选项设置下的求解性能，选择最优配置。
诊断不可行或无界问题的根本原因。

在线留言

尊敬的客户朋友，如您有任何意见建议，请通过下表反馈给我们，我们会尽快与您联系。

联系我们
	微信公众号	咨询微信	企业店铺
400-621-1085
（节假日期间办公室座机如无人接听，请选择其他联系方式，感谢理解！祝您节日快乐！）