京都大学 情報学研究科 数理工学専攻 2015年8月実施 線形計画

Author

Casablanca

Description

日本語版

関数 を連続的微分可能な凸関数とする。 さらに、 を次式で定義される関数 の における勾配とする。

ただし、 は転置記号を表す。

次の線形計画問題 P を考える。

ただし、 は 定数行列、 は 次元定数ベクトル、 は 次元定数ベクトル、 は 次元変数ベクトルである。 問題 P は最適解を持つとする。

以下の問いに答えよ。

(i) である任意の に対して となることを示せ。

(ii) 問題 P の双対問題を書け。

(iii) とする。このとき、 である任意の に対して、 であることを示せ。

English Version

Kai

(i)

Since , from first order condition we have

(ii)

Lagrangian:

Lagrange dual function

Dual problem:

(iii)

Since and is in domain of P, let denote P's optimal value, then

Since

thus

therefore