一种非精确非光滑信赖域算法

An Inexact Trust Region Algorithm for Nonsmooth Optimization

Aravkin等人提出了求解非光滑优化问题min_(x∈R^(d))f(x)+h(x)的非光滑信赖域算法(采用f的精确梯度),其中f是连续可微函数,h是邻近有界且下半连续的真函数。文章研究当该问题中f:=1/n ∑_(i=1)^(n)f_(i)(n很大且每个分量函数fi是连续可微)时,求解这类大规模可分离非光滑优化问题的有效算法。结合非精确算法和非光滑信赖域算法的思想,提出了用非精确梯度代替精确梯度的非精确非光滑信赖域算法。与非光滑信赖域算法(采用精确梯度)相比,该算法降低了每次迭代的计算量。在一定的假设条件下,证明了算法的迭代复杂度。

Aravkin et al proposed the trust region algorithm(employing exact gradients of f)for solving the nonsmooth optimization problem min_(x∈R^(d))f(x)+h(x),where f is a continuously differentiable function and h is a lower semicontinuous and prox-bounded proper function.In the case when f:=1/n ∑_(i=1)^(n)f_(i)(n is quite big,and each component fi is continuously differentiable),the efficient algorithm for solving such kind of large-scale separable nonsmooth optimization problem is studied.Combining the concepts of the inexact algorithm and the above trust-region algorithm,it is proposed that the inexact trust-region algorithm replaces the exact gradients with the inexact gradients for solving this nonsmooth problem.Comparing with the trust-region algorithm(employing the exact gradients of f),the new algorithm can reduce the computational cost at each iteration.Under certain assumptions,the iteration complexity of this algorithm is established.