正のスパニングセットを使用して、ブーステッドDCアルゴリズムでd-定常性を達成する

Using Positive Spanning Sets to Achieve d-Stationarity with the Boosted DC Algorithm.

• F J Aragón Artacho
• R Campoy
• P T Vuong

抄録

凸関数差分アルゴリズム(DCA)は、2つの凸関数の差分を最小化するために広く使用されています。最近提案された高速化バージョンは、Boosted DC AlgorithmのBDCAと呼ばれ、各反復で目的値をより大きく減少させるための線探索ステップが組み込まれています。このステップのおかげで、BDCAは実際にはDCAよりもはるかに速く収束します。DCAで得られた解は、問題の臨界点であることが保証されていますが、局所的な最小値ではない可能性があります。BDCAは見つけた解の目的値を向上させる傾向があるが、その解が単なる臨界点であることも多い。本論文では、BDCAと単純なDFO（D Derivative-Free Optimization）アルゴリズムを組み合わせて、得られた点にd-定常性（下降方向の欠如）を強制的に与えます。このアプローチの可能性を、最小二乗和クラスタリング問題の計算実験を通して示す。我々の数値結果は、この新しい手法がより良い解を提供する一方で、大多数のテストケースにおいてDCAよりも高速であることを示している。

The Difference of Convex functions Algorithm (DCA) is widely used for minimizing the difference of two convex functions. A recently proposed accelerated version, termed BDCA for Boosted DC Algorithm, incorporates a line search step to achieve a larger decrease of the objective value at each iteration. Thanks to this step, BDCA usually converges much faster than DCA in practice. The solutions found by DCA are guaranteed to be critical points of the problem, but these may not be local minima. Although BDCA tends to improve the objective value of the solutions it finds, these are frequently just critical points as well. In this paper we combine BDCA with a simple Derivative-Free Optimization (DFO) algorithm to force the d-stationarity (lack of descent direction) at the point obtained. The potential of this approach is illustrated through some computational experiments on a Minimum-Sum-of-Squares clustering problem. Our numerical results demonstrate that the new method provides better solutions while still remains faster than DCA in the majority of test cases.

© The Author(s) 2020.