無料🆓【院試解答】 京都大学 情報学研究科 数理工学コース サンプル問題A 凸最適化

【院試解答】 京都大学 情報学研究科 数理工学コース サンプル問題A 凸最適化

問題は京都大学 大学院情報学研究科 数理工学コース 大学院入試サンプル問題にあります。
京都大学情報学研究科京都大学情報学研究科数理工学コースの筆記試験、専門科目「凸最適化」のサンプル問題Aの解答例です。もし誤字・脱字や、解答の誤りを見つけた場合には、連絡いただけると対応します。
解答一つ一つ、解説も含めて丁寧に作成しているので、全てを無料では書くことが難しいです。応援する気持ちも込めて、他の記事もワンコインで購入していただけると励みになります。
また、京都大学情報学研究科京都大学情報学研究科数理工学コース及び大阪大学大学院情報科学研究科（IST）情報数理学専攻に関してなら、他の科目・年度の解答・解説のリクエストも受け付けています。

総評

＜難易度評価＞ 易、やや易、標準、やや難、難の5段階評価。
(i)やや易、(ii)易、(iii)標準、(iv)標準〜やや難

＜解答のポイント＞
KKT条件、双対問題、線形計画問題についての知識と感覚が問われるオーソドックスな問題。これまでの過去問に比べて、比較的解きやすい。

以下、ベクトルであっても太字では書かないこととする。また、$${I}$$を単位行列、$${O}$$を零行列とする。

(i)

解説

関数$${f:\mathbb{R}^n\to\mathbb{R}}$$が$${C^1}$$-級である時、$${f}$$が凸関数であるための必要十分条件は、任意の$${x,y\in\mathbb{R}^n}$$に対して、

$$
f(y)\geq f(x)+\nabla f(x)^\top(y-x)
$$

が成り立つことである。（勾配不等式）
これは頻出なので、覚えておくと良い。これを知っていれば本問はすぐさま解ける。逆にそうでなかったら、凸関数の定義から勾配不等式を導出することになり、難易度が一気に上がってしまう。

解答

$${f}$$は連続的微分可能な凸関数なので、任意の$${x,y\in\mathbb{R}^n}$$に対して、

$$
\begin{align}
f(y)&\geq f(x)+\nabla f(x)^\top(y-x) \\
f(x)&\geq f(y)+\nabla f(y)^\top(x-y)
\end{align}
$$

が成り立つ。これらを辺々足し合わせると、

$$
f(x)+f(y)\geq f(x)+\nabla f(x)^\top(y-x)+f(y)+\nabla f(y)^\top(x-y)
$$

となる。これを整理すると、

$$
(\nabla f(x)-\nabla f(y))^\top(x-y)\geq 0
$$

を得る。

(ii)

解説

超頻出のKKT条件を書く問題。今、制約式はベクトルで表記されているが、実質的には制約が$${n+m}$$個あるので、$${n+m}$$個のラグランジュ乗数を用いてKKT条件を書くことになる。ベクトルで表記されている時は、常にベクトルの形を意識して式変形を行うこと。

解答

$${\lambda = (\lambda_1,\lambda_2,\cdots,\lambda_m)^\top \in \mathbb{R}^m}$$、$${\mu = (\mu_1,\mu_2,\cdots,\mu_n)^\top \in \mathbb{R}^n}$$をラグランジュ乗数として、ラグランジュ関数$${L}$$を次で定める。

$$
L(x,\lambda,\mu) = f(x) + \lambda^\top (b-Ax) + \mu^\top (-x)
$$

すると、問題(P)のカルーシュ・キューン・タッカー条件は次のように書ける。

$$
\begin{align}
\nabla_x L(x,\lambda,\mu) &= \nabla f(x) - A^\top \lambda - \mu = 0 \\
A x &= b \\
x &\geq 0 \\
\mu &\geq 0 \\
\mu^\top x &= 0
\end{align}
$$

(iii)

解説

線形計画問題が最適解を持つことを示すには、次の3通りの方法がある。

1. 主問題が最適解を持つことを示す。

2. 双対問題が最適解を持つことを示す。

3. 主問題、双対問題が共に実行可能解を持つことを示す。
   一般に、最適解を持つことを直接示すには、任意の実行可能解との目的関数値を比較しなければならず、難しい。一方、実行可能解を持つことを示すには、適当に実行可能解を構成すればよいので、比較的容易である。したがって、3.の方法が最も使いやすい。
   なお、なぜ上記の結果が成り立つかというと、

• 「有界な線形計画問題は、実行可能解をもてば最適解をもつ」

• 「主問題が最小化問題の時、(双対問題の目的関数値) $${\leq}$$ (主問題の目的関数値)」
  という結果があるからである。詳しくは、線形計画法や最適化の教科書を参照されたい。ちなみに、線形でない最適化問題では、有界かつ実行可能解を持っても、最適解を持たないことがある。例えば、$${f(x)=-1/x}$$の$${\mathbb{R}_+}$$上の最大化問題を考えると、上に有界かつ実行可能解をもつが、最適解を持たない。（どこまでも0に近づく。）

解答

$${\forall x^\ast \in X^\ast}$$をとる。問題(P)は凸計画問題なので、ある$${\lambda^\ast \in\mathbb{R}^m}$$、$${\mu^\ast \in\mathbb{R}^n}$$が存在して、$${(x^\ast,\lambda^\ast ,\mu^\ast )}$$がKKT条件を満たす。さて、問題(Q)の双対問題(D)は次のとおり。ただし、$${w\in\mathbb{R}^m}$$が決定変数である。

$$
\begin{aligned}
\max &\quad b^\top w \\
\text{s.t.} &\quad A^\top w \leq \nabla f(x^\ast) \\
\end{aligned}
$$

今、$${x^\ast}$$は問題(P)の最適解なので、特に問題(P)の制約、$${Ax^\ast =b, x^\ast \geq 0}$$を満たす。よって、$${y=x^\ast}$$は問題(Q)の実行可能解。また、KKT条件(3)、(6)より、

$$
\begin{aligned}
\nabla f(x^\ast) =A^\top \lambda^\ast + \mu^\ast \geq A^\top \lambda^\ast
\end{aligned}
$$

よって、$${w=\lambda^\ast}$$は、問題(Q)の実行可能解。
主問題、双対問題が共に実行可能解を持つので、双対定理により、主問題、双対問題の最適解が存在する。よって特に、問題(Q)は最適解を持つ。

(iv)

解説

本問題の中では最も難しい問題。まず、等式の形が(i)の不等式とほとんど同じであることから、等式を示すために、反対向きの不等式さえ示せれば良いと気づく。実際、最適解であることが効いてきて、反対向きの不等号も成り立つのだろう、と予想できる。また(iii)で、$${x^\ast}$$を用いた線形計画問題(Q)やその双対問題について問われていたので、それが誘導ではないか、と疑うことができる。線形計画問題は当然凸計画問題であり、KKT点は最適解を与える。（ちなみに加えて、その時のラグランジュ乗数は双対問題の最適解を与える。）もし$${x^\ast}$$が問題(Q)の最適解であるならば$${\nabla f(x^\ast)^\top x^\ast \leq \nabla f(x^\ast)^\top y^\ast}$$が成り立ち、$${y^\ast}$$も同様に考えて辺々足せば、逆向きの不等式が示せることに気づく。そこで、$${x^\ast}$$が問題(Q)の最適解であることを示しにいく。実は、(iv)の解答の流れは、凸計画問題において、KKT条件が最適解を与えることの証明とほとんど同じであり、それは過去の問題でも多少の式変形の違いはあれど同様である。過去問を演習すれば、同じ流れが繰り返されることがわかる。

解答

$${\forall x^\ast,y^\ast \in X^\ast}$$をとる。
まず、(i)の結果より、

$$
\begin{align}
(\nabla f(x^\ast)-\nabla f(y^\ast))^\top(x^\ast-y^\ast)\geq 0
\end{align}
$$

次に逆向きの不等式を示す。(iii)同様に、ある$${\lambda^\ast \in\mathbb{R}^m}$$、$${\mu^\ast \in\mathbb{R}^n}$$が存在して、$${(x^\ast,\lambda^\ast,\mu^\ast)}$$がKKT条件を満たす。(iii)の議論より、$${x^\ast, \lambda^\ast}$$はそれぞれ問題(Q)、問題(D)の実行可能解である。
問題(Q)における$${x^\ast}$$の目的関数値は、

$$
\begin{aligned}
\nabla f(x^\ast)^\top x^\ast
&= (A^\top \lambda^\ast + \mu^\ast)^\top x^\ast
\quad (\because \nabla f(x^\ast) = A^\top \lambda^\ast + \mu^\ast) \\
&= \lambda^{\ast \top} A x^\ast + \mu^{\ast \top} x^\ast \\
&= \lambda^{\ast \top} b\quad (\because Ax^\ast=b, \mu^{\ast \top} x^\ast=0) \\
&= b^\top \lambda^\ast
\end{aligned}
$$

最右辺は問題(D)における、$${\lambda^\ast}$$の目的関数値である。よって、双対定理により$${x^\ast}$$、$${\lambda^\ast}$$はそれぞれ問題(Q)、問題(D)の最適解である。今、$${y^\ast}$$は問題(Q)の実行可能解なので、$${x^\ast}$$の最適性より、

$$
\nabla f(x^\ast)^\top x^\ast \leq \nabla f(x^\ast)^\top y^\ast
$$

（問題(Q)は$${x^\ast}$$を用いて定義されていることに注意する。）

全く同様に、$${y^\ast}$$についても、

$$
\nabla f(y^\ast)^\top y^\ast \leq \nabla f(y^\ast)^\top x^\ast
$$

が成り立つ。これらを足し合わせると、

$$
\nabla f(x^\ast)^\top x^\ast + \nabla f(y^\ast)^\top y^\ast \leq \nabla f(x^\ast)^\top y^\ast + \nabla f(y^\ast)^\top x^\ast
$$

これを整理して、

$$
\begin{align}
(\nabla f(x^\ast)-\nabla f(y^\ast))^\top(x^\ast-y^\ast)\leq 0
\end{align}
$$

となる。(8),(9)より、

$$
\begin{align}
(\nabla f(x^\ast)-\nabla f(y^\ast))^\top(x^\ast-y^\ast)=0
\end{align}
$$

が成り立つ。

#京大 #京都大学 #京大院試 #京大情報学研究科数理工学コース #京都大学大学院
#凸最適化
#数学 #大学数学 #外部院試 #院試過去問 #院試対策 #院試解答 #大学院入試 #大学院試験 #理系大学院 #情報系