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

Author

Casablanca

Description

日本語版

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

ただし, 問題 の決定変数は であり, は転置記号を表す。また, と を満たすベクトル が存在するとする。

以下の問いに答えよ。

(i) 問題 の双対問題を とする。 が問題 の最適解であり, ある実数 に対して, を満たす問題 の実行可能解 が存在すると仮定する。そのとき,

が成立することを示せ。

(ii) は第 成分を とする　対角行列と定義し, は正則行列と仮定する。さらに, 以下の最適化問題を考える。

ここで, 問題 の決定変数は であり, はユークリッドノルマ表す (すなわち, 任意のベクトル に対して, ). また, と定義し, と仮定する。さらに, 以下のベクトルを定義する。

以下の問 (a) , (b) , に答えよ。

(a) であることを示せ。

(b) が問題 の最適解であることを示せ。

とする。そのとき, が問題 の実行可能解であることと, を満たすことを示せ。

English Version

Kai

(i)

Lagrangian:

Lagrange dual function:

dual problem

thus

since

and from duality we know

thus

then

(ii)

(a)

thus

(b)

Write Q as:

Lagrangian:

We get KKT_conditions:

satisfies KKT-conditions for

and easy to see:

thus

thus is feasible, and we get: