<p>We are concerned with minimizing a composite objective function, which can be decomposed into a differentiable but not necessarily convex part and a convex but possibly nonsmooth function. To efficiently exploit the decomposable structure, in this paper, we propose a Multi-step inertial ExtraGradient Algorithm (MEGA), which consists of two inertial steps involving the combination of finite historical iterates and two proximal gradient steps evaluating the proximal operators of a convex function at some points. With the help of Kurdyka-Łojasiewicz property, we theoretically prove that the sequence generated by our MEGA is globally convergent to a stationary point of the problem under consideration. A series of numerical experiments on Lasso and nonconvex quadratic optimization problems show that the proposed MEGA works well in practice. Particularly exciting is the illustration by some computational results that our MEGA can escape local minima points (at least with high probability) to reach a global solution. This strongly supports the idea that utilizing more historical information in extragradient methods is beneficial for solving nonconvex optimization problems.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A multi-step inertial extragradient algorithm for nonsmooth and nonconvex composite optimization problems

  • Zhixue Wang,
  • Hongjin He

摘要

We are concerned with minimizing a composite objective function, which can be decomposed into a differentiable but not necessarily convex part and a convex but possibly nonsmooth function. To efficiently exploit the decomposable structure, in this paper, we propose a Multi-step inertial ExtraGradient Algorithm (MEGA), which consists of two inertial steps involving the combination of finite historical iterates and two proximal gradient steps evaluating the proximal operators of a convex function at some points. With the help of Kurdyka-Łojasiewicz property, we theoretically prove that the sequence generated by our MEGA is globally convergent to a stationary point of the problem under consideration. A series of numerical experiments on Lasso and nonconvex quadratic optimization problems show that the proposed MEGA works well in practice. Particularly exciting is the illustration by some computational results that our MEGA can escape local minima points (at least with high probability) to reach a global solution. This strongly supports the idea that utilizing more historical information in extragradient methods is beneficial for solving nonconvex optimization problems.