具有线性收敛率的极小化r个最大函数和的光滑化方法

The Smoothing Method with the Linear Rate of Convergence for Minimizing the Sum of the r-Largest Functions

在已给q个定义于n维欧几里徳空间的函数中求r个最大值函数和的最小值,其中1≤r≤q。该问题是非光滑最优化问题,不能直接用一阶最优化方法或梯度法求解。利用对偶理论将该问题转化为只包含最大值函数max{0,t}的非光滑问题。运用对数-指数光滑函数,对该非光滑问题建立具有全局收敛的光滑化算法。该算法的收敛率是线性的。

Abstract. Given a collection of q functions defined on R^n , we minimize the sum of the r largest functions of the collection, where 1≤r≤q. It is obvious that this is a non-smooth optimization problem. It cannot be solved by using any first-order or gradient unconstrained minimization algorithms. In this paper, the problem is reformulated as a non-smooth problem that only involves the maximum function max {0, t} using the duality theory. A new globally convergent smoothing method is then developed with the log-exponential smoothing function. The convergence rate of the smoothing method is linear.