技能一覧 › 大学院数学 凸最適化・組合せ最適化

凸共役(ルジャンドル・フェンシェル変換)

を、上限を与える ()を求めて計算できる。定義域の制限( をとる部分)や の範囲による場合分け、ノルムの共役が双対ノルムの単位球の指示関数になることを使える

前提

この技能までの道筋(44 技能)
算数中学高校大学大学院

読み込み中…

右端(太枠)がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る(前提が先)
  1. 分数のたし算・ひき算 (算数 計算と数のきまり)
  2. 小数の四則計算 (算数 計算と数のきまり)
  3. 正負の数の加法・減法 (中学数学 数と式)
  4. 分数のかけ算・わり算 (算数 計算と数のきまり)
  5. 四則の混じった計算の順序 (算数 計算と数のきまり)
  6. 正負の数の乗除・累乗と四則混合 (中学数学 数と式)
  7. 分配法則を使った計算のくふう (算数 計算と数のきまり)
  8. 文字式の計算(同類項・分配法則) (中学数学 数と式)
  9. 乗法公式による展開 (中学数学 数と式)
  10. 因数分解 (中学数学 数と式)
  11. 3 次式までの展開と因数分解 (数学I 数と式)
  12. 微分係数と導関数の定義 (数学II 微分法と積分法)
  13. 多項式の微分 (数学II 微分法と積分法)
  14. 等間隔にならんだ数の和 (算数 計算と数のきまり)
  15. 等差・等比数列の和と Σ (数学B 数列)
  16. 数列の極限 (数学III 極限)
  17. 関数の極限 (数学III 極限)
  18. 積と商の微分 (数学III 微分法)
  19. 合成関数の微分 (数学III 微分法)
  20. 偏微分と全微分 (大学数学 微分積分)
  21. 三角形の角の大きさ (算数 平面図形)
  22. 対頂角と平行線の同位角・錯角 (中学数学 平面図形)
  23. 三角形の外角と角の組み合わせ (中学数学 平面図形)
  24. 小数と分数のまじった計算 (算数 計算と数のきまり)
  25. 逆算(□ を求める) (算数 計算と数のきまり)
  26. 1 次方程式の解き方 (中学数学 方程式)
  27. 二等辺三角形の角 (中学数学 平面図形)
  28. 平行四辺形と特別な四角形の性質 (中学数学 平面図形)
  29. 三角形・四角形の面積 (算数 平面図形)
  30. 約数の見つけ方 (算数 整数の性質)
  31. 素因数分解と約数の個数 (算数 整数の性質)
  32. 平方根の意味と根号の簡単化 (中学数学 数と式)
  33. 三平方の定理 (中学数学 相似と三平方の定理)
  34. 折り返した図形の角と長さ (中学数学 平面図形)
  35. 三平方の定理と平面図形 (中学数学 相似と三平方の定理)
  36. ベクトルの演算と成分 (数学C ベクトル)
  37. 特別な直角三角形の辺の比 (中学数学 相似と三平方の定理)
  38. 最大公約数と最小公倍数 (算数 整数の性質)
  39. 比の性質と簡単な比 (算数 割合と比)
  40. 相似な三角形と長さの比 (算数 平面図形)
  41. 三角形の相似条件と対応する辺の長さ (中学数学 相似と三平方の定理)
  42. 三角比の定義と値 (数学I 図形と計量)
  43. 内積となす角 (数学C ベクトル)
  44. 劣勾配と劣微分 (大学院数学 凸最適化・組合せ最適化)

説明

関数 に対し、凸共役(ルジャンドル・フェンシェル変換)を で定めます。この技能では、 が凸関数( でない値を少なくとも 1 点でとり、 をとらないもの)であると仮定して、上限を与える点 を条件 から見つけ、 を具体的に計算します。 が をとる部分(定義域の制限)があるときや、 の範囲で上限のとり方が変わるときの場合分けも扱います。凸共役は双対問題を作るとき、最適化の下界を求めるとき、ノルムと双対ノルムを結びつけるときなどに使います。

なぜそうしてよいのか

以下、 は凸関数とします。 を固定すると、 を について最大化することは、 を最小化することと同じです()。 は凸関数から 1 次関数を引いたものなので凸で、劣微分の定義から がすぐわかります。凸関数では が最小点であるための条件なので、これは と書けます。つまり「 を劣勾配にもつ点 」を見つければ、そこが最大点で、 です。図形的には、傾き の 1 次関数 が のグラフを下から支えるときの最小の が です。

となる が存在しない では、上限は達成されず、 を無限遠に飛ばすと になったり、ある有限値に近づいたりします。そのときは などの極限を直接調べます。また が をとる点は上限に寄与しないので、 は定義域 だけを動くと考えます。定義域の端点では劣微分が広がる(例: の端点 では負の傾きをすべて含む)ため、多くの がその端点に対応します。なお、 は の 1 次関数の族の上限なので、定義そのものは が凸でなくても意味をもち、 は常に凸関数になります。ただし、この技能の手順(劣微分を使って最大点を探す方法)は が凸のときに使うものです。凸でない では が空になる点があり、また を満たさない最大点の候補もありうるので、この方法はそのままでは使えません。

ノルム (凸関数)の場合、双対ノルムを で定めると が成り立ちます。 なら で、 で が達成されるので 。 なら となる があり、()で です。よって は双対ノルムの単位球の指示関数(球上で 、外で )になります。たとえば の双対は 、 の双対は です。

手順

  1. が凸関数であることを確かめ、定義域( となる の集合)を確認する。 はその中だけを動くものとする。

  2. 各点 での劣微分 を求める(凸な が定義域の内部の点で微分可能なら 、定義域の端点では広がった集合になる)。

  3. 与えられた に対し を満たす を求める。 の範囲によって の求め方が変わるなら場合分けする。

  4. 見つかった で を計算する。

  5. となる がない では、 などの極限で を調べ、上限( もありうる)を求める。

例題

を、 のとき 、 のとき と定める。凸共役 について、 と の値を順に求めよ。

例題の解答

【手順 1】 は凸関数 を凸集合 に制限し、外を としたものなので凸である。定義域は なので、 の範囲だけで の上限を考える。

【手順 2】 では は微分可能で 。端点 では、 は「すべての で 」と同値で( では左辺が なので常に成り立つ)、 で割ると がすべての で成り立つ、つまり 。よって 。

【手順 3】 のとき、 となるのは 、すなわち 。 のとき、 を満たす はないが、 なので 。

【手順 4】、。

(一般には で 、 で となる。)

答え:

よくある誤り

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること