はじめに
この記事は，数理最適化 Advent Calendar 2022の21日目の記事になります．
数理最適化 Advent Calendar 2022 - Qiita Advent Calendar
機械工学専攻な著者が，研究の中でDC最適化について勉強したので，アウトプットしようとしたサムシングです．
かなり抽象化しているので，詳細な内容については参考文献を見ていただけるといいと幸いです．
なお，数学が苦手＆数理最適化初学者というステータスを持っています．
クリティカルな間違いがありましたら，コメントかTwitter: @santana_hammerまで教えていただけると幸いです．
（追記：2023/02/18）
内容を修正しました．
無知無知の無知から，無知にレベルアップしました．
簡単に凸最適化を知ろう
関数 $f : \mathbb{R}^n \to \mathbb{R} \cup { \infty }$ がプロパーな凸関数，かつ集合 $C \subset \mathbb{R}^n$ が閉凸集合であるとき， $x \subset C$ の中で $f(x)$ を最小にする $x$ を求める問題を凸最適化問題（凸計画問題）と呼びます．
プロパー
$f(x)<\infty$ となるような $x$ が一つでも存在する（$\text{dom} f \neq \varnothing$）とき，関数 $f$ はプロパーであると言います．
dom（実効定義域）
関数 $f$ の定義域のうち， $f(x)$ が実数値を取るような $x$ の集合を $f$ の実効定義域と呼びます．
\begin{align*}
\text{dom} f \triangleq \{ x \in \mathbb{R} : f(x) < \infty \}
\end{align*}
凸最適化の何が嬉しいのか
さてさて，凸最適化ってよく聞きますよね．え，聞かない？
ネットワークトポロジーとか最適制御ではよく聞くんですが...そうですか...
凸最適化問題になると，実は何かとうれしいことがあります．
大域的な最適値を得ることができる
一般に，勾配情報を利用した最適化手法では局所的な最適値に収束することが多いです．
イメージで行くと，あれですかね．極小値は極小値でも，絶対にそこが最小値になるとは限らない的な．
凸最適化では評価関数の凸性が担保されているため，大域的な最適値を得ることができます．
これはうれしいですね，泣いて喜んじゃいます．
最適化問題を解く計算の高速化ができる
凸最適化特有の最適化手法を用いることで，汎用の最適化手法よりも計算時間を短縮することができたりします．
何か，最近では更に高速化を目指した手法があったりしたりラジバンダリ．
私が知っているのは，内点法，近接勾配法(Proximal Gradient Method)，交互方向乗数法(ADMM)あたりですね．
DC最適化
さぁ，上記では簡単にですが凸最適化問題について触れました．ほんとにざっくりですが．
凸最適化問題に全部なってくれたらうれしいんですが，現実はそうはいきません．
それでは，いよいよ非凸最適化問題であるDC最適化についてやっていこうと思います．
DC最適化とは
DC(Difference of Convex function)最適化とは，目的関数が2つの凸関数の差で表現される非凸最適化問題について，最小化を行う際に使う手法です．
2つの凸関数 $g, h:\mathbb{R}^n\to\mathbb{R} \cup {\infty}$ を使って以下のように表現される非凸最適化問題を扱います．
\begin{align}
& && \underset{x} {\text{minimize}} && g(x) - h(x) &&
\end{align}
問題(1)は一般的に非凸最適化問題であるため，局所的な最小値が大域的な最小値と一致せず，大域的最適解を求めるのが困難です．
ここで，関数 $f: \mathbb{R}^n\to\mathbb{R}$ に対して，2つの閉凸関数 $g, h: \mathbb{R}^n\to\mathbb{R}$ について
\begin{align}
f(x)=g(x)-h(x), \forall x \in \mathbb{R}^n
\end{align}
が成り立つとき， $f$ をDC関数といい，この式記述を $f$ のDC表現と呼んだりします．
なお，2階微分が可能な任意の関数など，多くの関数がDC関数となっています．
そのため，様々なクラスの最適化問題がDC最適化問題によって表現できることが知られています．
なぜ非凸最適化問題になるのか
これは，凸関数どうしの差は凸関数にならない場合があるためです．
凸関数どうしの和は必ず凸関数になります．証明についてはGoogle大先生に聞いたり，最適化問題について書いてある参考書を読んだりすると書いてあると思います．
（私は，永原先生の「スパースモデリング」で知りました．）
しかし，凸関数どうしの差は一概に凸関数になるとは言えず，一般的には非凸関数として扱われます．
このため，今まで使っていた凸最適化問題の手法が使えなくなってしまいます．
さて，どうしましょうか...
え，どうすることもできないって？
そらもう自爆するしか...（なんでやねん）
DCアルゴリズム
さぁ，DC最適化は非凸最適化問題であり，従来の凸最適化問題の手法では解けないことがわかりました．
そこで登場するのが， DC Algorithm(DCA) です．
DCAを用いることで，非凸最適化問題から凸最適化問題に変換することができ，従来の凸最適化の手法によって最適解を求めることができるようになります．
以下に，DCアルゴリズムの疑似コードを示します．
$\partial h(x[k])$ はステップ $k$ における $x[k]$ まわりの劣微分を表しており，劣微分は以下のように定義されます．
\begin{align}
\partial h(x[k]) \triangleq \{ s \in \mathbb{R}^n : h(x) \geq h(x[k])+s^{\top} (x - x[k]) \}
\end{align}
ざっくり言うと，微分を微分不可能関数（絶対値関数とか）にも使えるように一般化したものです．
微分可能な関数の場合は勾配，微分不可能な関数の場合は劣勾配（取りうる勾配）の集合を表します．
アルゴリズムの中を見てみると，各反復点で子問題として凸最適化問題が含まれており，それをどんどん解いて更新することで最適解を得ることができる仕組みになっています．
誰だこんなの思いついたの，絶対変態だろ（誉め言葉）．
DCアルゴリズムの問題点
以上までで，DCAについて紹介しました．
「すっげぇアルゴリズム！！万能そう！！最高だぜぇ！！」と思った方いらっしゃるかもしれません．
実はこのアルゴリズム，ちょっと問題を抱えています．
それは，各反復点において子問題の凸最適化問題を解いていることです．
大規模な問題だったり子問題が複雑な場合，計算コストが莫大になる可能性があるわけです．
とても簡単に言うと，コンピュータに優しくないアルゴリズムになる可能性があります．
こんな感じですね．
そのため，現在では近接作用素やNesterovの加速法を組み合わせた研究が盛んに行われています．
一例として，PDCAとPDCAeを紹介します．
PDCA(Proximal Difference-of-Convex function Algorithm)
出典：PDCA（Plan-Do-Check-Action）の重要性 - 農林水産省
これじゃないですよ？
そういえば，「Panic（混乱）」，「Doom（破滅）」，「Chaos（混沌）」，「Apocalypse（終焉）」って書いてるパチンコ屋がありましたね...
PDCAは，DCアルゴリズムに近接勾配法を組み合わせたアルゴリズムになります．
目的関数が以下のように表される場合に用いることが可能です．
\begin{align}
& && \underset{x} {\text{minimize}} && f(x) + g(x) - h(x) &&
\end{align}
$f$ が $L$ 平滑な凸関数，かつ $g$ が近接写像を利用できるような凸関数である場合，各反復で最適化問題を解く必要性がなくなることがあります．
ここで， $L$ 平滑とは以下で示すような等式を満たすことを指します．
\begin{align}
\|\nabla f(x) - \nabla f(y)\| \leq L \|x - y\|
\end{align}
これは，勾配 $\nabla f$ がリプシッツ定数 $L$ でリプシッツ連続（Lipschitz continuity）であることを表しています．
さらに $g$ の近接写像は，
\begin{align}
\text{prox}_g (z) \triangleq \underset{x}{\text{argmin}}\{g(x) + \frac{1}{2}\|x - z\|^2_2\}
\end{align}
で定義されます．
これの評価が簡単な演算で行える場合，そんなに計算コストが重くならないことがわかっています．
最近では $h$ が凸関数でない場合や，そもそもリプシッツ定数 $L$ が得られない（計算が困難な）場合に対する研究が行われています．
（リプシッツ定数 $L$ の獲得が困難な場合は，Backtracking法と組み合わせることで解決するみたいです．）
PDCAe(PDCA with extrapolation)
PDCAに対して，更にNesterovの外挿を施した改良版アルゴリズムです．
以下のアルゴリズムに，PDCAeの疑似アルゴリズムを示します．
$\beta[k]=0$ とすると，PDCAに一致するようになっています．
このアルゴリズムでは，ステップ4に「外挿」と呼ばれるステップが入っており，主問題が凸最適化（$h=0$）である場合，加速化が理論的に保証されています．
以下の論文に，PDCAeについてより詳しい説明が載っています．
Wen, Bo, Xiaojun Chen, and Ting Kei Pong. "A proximal difference-of-convex algorithm with extrapolation." Computational optimization and applications 69.2 (2018): 297-324.
最後に
すごく雑になりましたが，DC最適化の概要とDCAの問題点でした．
基本的に，数理最適化を勉強していると凸最適化がよく出てきますが，あるクラスについては凸最適化が適用できないというパターンもあるんですね．
また，加速法の研究についても割と最近行われている印象です．
$L$ 平滑性の解析って結構難しいので，それをBacktracking法などの組み合わせで賄えるのは，私としてもうれしいです．
このクラスの最適化は，スパース最適化や疎構造学習と相性が良かったりするので，勉強しといて損は...ない...と思います（全部スパースやないかい）．
そういえば，他学科（情報系じゃない）の研究室でもDC計画問題を扱うとか聞いたりしたなぁ...
私の感想の密度もスパースなのがばれたところで，ではでは．
参考文献
田中未来, 奥野貴之 - DC 最適化の理論と応用
後藤 順哉, 武田 朗子 - DC アプローチに基づくスパース最適化
小野 峻佑 - 近接分離アルゴリズムとその応用 : 信号処理・画像処理的観点から