円錐双対性について少し

機械学習の理論コース（数学、経済学、最適化、財務など）を勉強するとき、「二重問題」の概念がよく見られます。



デュアルタスクは、最適化問題のターゲット関数の低い（または高い）推定値を取得するためによく使用されます。 さらに、最適化問題のほとんどすべての意味のあるステートメントについて、二重問題には意味のある解釈があります。 つまり、重要な最適化の問題に直面している場合、その二重の問題もおそらく最も重要です。



この記事では、円錐双対性について説明します。 私の意見では、デュアルタスクを構築するこの方法は、当然のことながら注目を奪われています...



次のマット...

通常、デュアルタスクはどのように構築されますか？

いくつかの最適化問題を与えましょう：

$$

$$\ min_ {x \ in R ^ n} f（x）\\ f_i（x）\ leq 0、\ quad 1 \ leq i \ leq k \\ h_i（x）= 0、1 \ leq i \ leq m$$

デュアルタスクは、次のスキームに従って構築されます。

• ラグランジアンを構築

$$

$$L（x、\ lambda、\ mu）= f（x）+ \ sum_ {i = 1} ^ k \ lambda_i f_i（x）+ \ sum_ {i = 1} ^ m \ mu_i h_i（x）$$

• 二重機能を構築する

$$

$$g（\ lambda、\ mu）= \ inf_x L（x、\ lambda、\ mu）$$

• デュアルタスクを取得する

$$

$$\ max _ {\ lambda、\ mu} g（\ lambda、\ mu）\\ \ lambda \ geq 0$$

このスキームの主な難点は、検索ステップで配線されています $$$\ inf_x L（x、\ lambda、\ mu）$ 。



問題が凸でない場合、これはcoです-一般に、多項式時間で解決することはできません（ $$$P \ neq NP$ ）およびこの記事のこのような問題については、今後触れません。



問題が凸であると仮定します、それでは何ですか？



問題が滑らかな場合、1次の最適条件を使用できます $$$\ nabla_x L（x、\ lambda、\ mu）= 0$ 。 この条件から、すべてが正常であれば、推測または $$$x（\ lambda、\ mu）= \ arg \ min_x L（x、\ lambda、\ mu）$ そして $$$g（\ lambda、\ mu）= L（x（\ lambda、\ mu）、\ lambda、\ mu）$ または直接機能する $$$g（\ラムダ、\ mu）$ 。



問題がスムーズでない場合は、1次条件のアナログを使用できます $$$0 \ in \ partial_x L（x、\ lambda、\ mu）$ （こちら $$$\ partial_x L（x、\ lambda、\ mu）$ 関数の微微分を示します $$$L（x、\ lambda、\ mu）$ ）ただし、この手順は通常はるかに複雑です。



場合によっては、同等の「滑らかな」最適化問題があり、それに対して二重の問題を構築できます。 ただし、構造を改善するために（非滑らかから滑らかに）、原則として、常に次元の増加を支払う必要があります。

円錐双対性

次の表現を可能にする最適化タスク（以下の例）がかなりあります。

$$

$$\ min_ {R ^ nのx \} c ^ Tx \\ Ax + b \ in K$$

どこで $$$A$ -マトリックス $$$b$ -ベクトル $$$K$ -非縮退凸コーン。



この場合、デュアルタスクは次のスキームに従って構築できます。



デュアルタスクは、次のスキームに従って構築されます。

• ラグランジアンを構築

$$

$$L（x、\ lambda）= c ^ Tx + \ lambda ^ T（Ax + b）$$

• 二重機能を構築する

$$

$$g（\ lambda）= \ inf_x L（x、\ lambda）= \ begin {cases} \ lambda ^ T b、\ quad c + A ^ T \ lambda = 0 \\-\ infty、\ quad c + A ^ T \ lambda \ neq 0 \ end {cases}$$

• デュアルタスクを取得する

$$

$$\ max _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\-\ lambda \ in K ^ *$$

共役円錐はどこですか $$$K ^ *$ コーン用 $$$K$ として定義される $$$K ^ * = \左\ {y \ in R ^ k | z ^ T y \ geq 0、\ quad \ forall z \ in K \ right \}$ 。



ご覧のように、二重問題の構築の複雑さ全体が二重円錐の構築に移されました。 しかし、喜びは、デュアルコーンを構築するための優れた計算法があり、非常に頻繁にデュアルコーンをすぐに書き出すことができることです。

例

問題の二重最適化問題を構築する必要があると仮定します。

$$

$$\ min_ {x \ in R ^ n} \ | x \ | _2 + \ | x \ | _1 \\ Ax \ geq b$$

ここに $$$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ 、 $$$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$



最初に気づくことができます：目的関数は常に線形にすることができます！



むしろ、線形目的関数には常に同等の問題があります。

$$

$$\ min_ {Rのn \ ^ n、Rのy \、Rのz \} y + z \\ \ | x \ | _2 \ leq y \\ \ | x \ | _1 \ leq z \\ Ax \ geq b$$

今、あなたは少し秘密の知識を使用する必要があります：多くの

$$

$$K_1 = \ {（x、t）\ in R ^ n \ times R | \ quad \ | x \ | _1 \ leq t \}$$

そして

$$

$$K_2 = \ {（x、t）\ in R ^ n \ times R | \ quad \ | x \ | _2 \ leq t \}$$

凸コーンです。



したがって、問題の同等の表記法に到達します。

$$

$$\ min_ {R ^ nのx \、Rのy \、Rのz \} y + z \\ I_ {n + 1} \ begin {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ K_2 \\ I_ {n + 1} \ begin {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ K_1 \\ Ax-b \ in R _ + ^ k$$

これで、二重の問題をすぐに書き出すことができます。

$$

$$\ max _ {\ lambda、\ mu、\ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0、\ quad 1 \ leq i \ leq n \\ \ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\-\ lambda \ in K_2 ^ *（= K_2）\\-\ mu \ in K_1 ^ *（= K _ {\ infty}）\\-\ nu \ in R ^ k _ +$$

または、少し簡単にするために、

$$

$$\ max _ {\ lambda、\ mu、\ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\-\ nu \ in R ^ k _ +$$

どこで $$$\ | \ mu \ | _ {\ infty} = \ max_ {i} | \ mu_i |$ 。



さらなる研究のためのリンク：

• S.ボイド＆L.ヴァンダーバーグ、Convex Optimization、2.6（p。51）
• A.ベン・トール＆L.エル・ガウイ＆A.ネミロフスキー、ロバスト最適化、App。 A