Nonlinear rescaling vs. smoothing technique in convex optimization
Nonlinear rescaling vs. smoothing technique in convex optimization
复制标题
DOI：
10.1007/s101070100293
复制
发表时间：
2002-04
影响因子：
2.7
通讯作者：
R. Polyak
中科院分区：
文献类型：
--
作者：
R. Polyak
我们介绍了一种替代的平滑技术方法的约束优化。事实证明，对于任何给定的平滑函数，都存在具有特定性质的修改。我们使用非线性重标度（NR）的修改将给定约束优化问题的约束转换为等价的约束集。等价问题的拉格朗日量对应于相应的光滑罚函数，如经典罚函数的增广拉格朗日量或障碍函数的MBFs。此外，联合收割机结合了二次和非二次增广拉格朗日的最佳性质，同时又摆脱了它们的主要缺点。拉格朗日乘子和尺度参数更新导致一类新的NR乘子方法，其等效于对偶问题的内部二次Prox方法。¶我们在对输入数据非常温和的假设下证明了NR乘数方法的收敛性并估计了收敛速度。我们还估计了在输入数据上的各种假设下的收敛速度。特别地，在标准的二阶最优性条件下，NR方法以Q-线性速度收敛，而不需要无限增加对应于活动约束的尺度参数。我们还建立了具有唯一对偶解的线性规划的NR方法的全局二次收敛性。我们提供了数值结果，有力地支持了这个理论
We introduce an alternative to the smoothing technique approach for constrained optimization. As it turns out for any given smoothing function there exists a modification with particular properties. We use the modification for Nonlinear Rescaling (NR) the constraints of a given constrained optimization problem into an equivalent set of constraints.¶The constraints transformation is scaled by a vector of positive parameters. The Lagrangian for the equivalent problems is to the correspondent Smoothing Penalty functions as Augmented Lagrangian to the Classical Penalty function or MBFs to the Barrier Functions. Moreover the Lagrangians for the equivalent problems combine the best properties of Quadratic and Nonquadratic Augmented Lagrangians and at the same time are free from their main drawbacks.¶Sequential unconstrained minimization of the Lagrangian for the equivalent problem in primal space followed by both Lagrange multipliers and scaling parameters update leads to a new class of NR multipliers methods, which are equivalent to the Interior Quadratic Prox methods for the dual problem.¶We proved convergence and estimate the rate of convergence of the NR multipliers method under very mild assumptions on the input data. We also estimate the rate of convergence under various assumptions on the input data.¶In particular, under the standard second order optimality conditions the NR method converges with Q-linear rate without unbounded increase of the scaling parameters, which correspond to the active constraints.¶We also established global quadratic convergence of the NR methods for Linear Programming with unique dual solution.¶We provide numerical results, which strongly support the theory.