京都大学 情報学研究科 数理工学専攻 2021年8月実施 オペレーションズ・リサーチ

Author

Casablanca

Description

日本語版

とする。 パラメータ をもつ次の非線形計画問題を考える。

ここで、 の決定変数は である。 また、 は転置記号を表す。さらに、任意の に対して、問題 の最適値が定義されているとし、その最適値を と表す。

以下の問いに答えよ。

(i) 問題 のカルーシュ・キューン・タッカー条件 (Karush-Kuhn-Tucker 条件) を書け。

(ii) 問題 の目的関数が、 に対して凸であることを示せ。

(iii) を正定値対称行列と仮定し、次の最適化問題を考える。

を問題 P1 の大域的最適解とするとき、以下の不等式が成り立つことを示せ。

ただし、 は の最小固有値を表す。

(iv) を 零行列、 を 次元零ベクトルと仮定する。以下の最適化問題を考える。

ここで、 は正の実数である。 が共に問題 P2 のカルーシュ・キューン・タッカー条件を満たすとき、 が成り立つことを示せ。

English Version

Kai

(i)

Lagrangian:

and we get:

(ii)

is convex, is convex, then the objective function is convex.

(iii)

By (i) we have

and

since is symmetric positive difinete, can be decomposited as , and

Thus

(iv)

Lagrangian:

If , then .

If , then .