提出随机优化新算法,可同时找到一阶和二阶驻点。
Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models
- 用随机模型逼近目标函数,满足自适应精度条件
- 结合信赖域与二次规划,实现几乎必然收敛
- 适合处理带约束的随机优化问题,尤其在鞍点附近表现好
本文研究具有随机目标函数和确定性等式约束的优化问题。提出一种信赖域序列二次规划方法,用于寻找一阶和二阶驻点。该方法利用随机观测构建目标函数的随机模型,并在高但固定的概率下满足适当的自适应精度条件。为收敛至一阶驻点,每轮迭代通过最小化目标函数的二次近似(受限于约束的线性松弛和信赖域约束)计算梯度步。为收敛至二阶驻点,额外引入特征值步以探测约化海森矩阵的负曲率,并加入二阶修正步以缓解由约束非线性引发的马拉托斯效应(可能阻碍算法脱离鞍点)。梯度步与特征值步均采用新颖的无参数分解机制,综合考虑可行性残差、最优性残差与负曲率的比例关系。本文建立了该方法全局几乎必然的一阶与二阶收敛性保证,并在CUTEst测试问题、回归问题及鞍点问题上展示了其对现有基于线搜索的随机方法的优越性。
原文摘要 · Abstract (English)
In this work, we consider solving optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Sequential Quadratic Programming method to find both first- and second-order stationary points. Our method utilizes a random model to represent the objective function, which is constructed from stochastic observations of the objective and is designed to satisfy proper adaptive accuracy conditions with a high but fixed probability. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a quadratic approximation of the objective subject to a (relaxed) linear approximation of the problem constraints and a trust-region constraint. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature of the reduced Hessian matrix, as well as a second-order correction step to address the potential Maratos effect, which arises due to the nonlinearity of the problem constraints. Such an effect may impede the method from moving away from saddle points. Both gradient and eigen step computations leverage a novel parameter-free decomposition of the step and the trust-region radius, accounting for the proportions among the feasibility residual, optimality residual, and negative curvature. We establish global almost sure first- and second-order convergence guarantees for our method, and present computational results on CUTEst problems, regression problems, and saddle-point problems to demonstrate its superiority over existing line-search-based stochastic methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。