非凸・整数の問題の双対ギャップ

有限集合 $X=\{0,1,3\}\subset \mathbb{R}$ 上の次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}{x}^2\text{subject to}2-x\le 0,x\in X$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。不等式制約 $2-x\le 0$ だけを乗数 $\mu \ge 0$ で緩和したラグランジュ関数を $L(x,\mu )=x^2+\mu (2-x)$ とし、双対関数を $q(\mu )={\min }_{x\in X}L(x,\mu )$、双対問題の最適値を $d^{\ast }={\sup }_{\mu \ge 0}q(\mu )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

頂点集合 $V=\{s,a,b,c,t\}$ の有向グラフ $G$ を考える。各有向辺 $e$ には費用 $c_e$ と所要時間 $d_e$ が次のように与えられている（$(c_e,d_e)$ の順に記す）。
$$s\to a:(2,3),s\to b:(5,1),a\to b:(1,1),a\to c:(3,1),$$
$$b\to c:(1,2),a\to t:(1,7),b\to t:(4,2),c\to t:(2,1).$$
グラフにはこれ以外の辺はない。$\mathcal{P}$ を $s$ から $t$ への有向道全体とし、有向道 $P$ の費用と所要時間を $c(P)={\sum }_{e\in P}{c}_e$、$d(P)={\sum }_{e\in P}{d}_e$ と定める。次の制約付き最短路問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}c(P)\text{subject to}d(P)\le 6,P\in \mathcal{P}.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。時間制約 $d(P)\le 6$ のみを乗数 $\lambda \ge 0$ で緩和したラグランジュ双対関数を
$$\phi (\lambda )=\underset{P\in \mathcal{P}}{\min }\{c(P)+\lambda (d(P)-6)\}(\lambda \ge 0)$$
と定め、双対問題の最適値を $d^{\ast }={\sup }_{\lambda \ge 0}\phi (\lambda )$ とする。$p^{\ast }$ と $d^{\ast }$ をこの順に組 $(p^{\ast },d^{\ast })$ で求めよ。

$X=\{0,1{\}}^3$ 上の次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}3x_1+4x_2+5x_3\text{subject to}2x_1+3x_2+4x_3\ge 5,x=(x_1,x_2,x_3)\in X.$$
不等式制約 $2x_1+3x_2+4x_3\ge 5$ だけを乗数 $\mu \ge 0$ で緩和したラグランジュ関数
$$L(x,\mu )=3x_1+4x_2+5x_3+\mu (5-2x_1-3x_2-4x_3)$$
により双対関数 $q(\mu )={\min }_{x\in X}L(x,\mu )$ を定め、双対問題の最適値を $d^{\ast }={\sup }_{\mu \ge 0}q(\mu )$、$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

閉区間 $X=[0,4]\subset \mathbb{R}$ 上の次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}f(x)=-x^2+5x\text{subject to}g(x)=1-x\le 0,x\in X.$$
不等式制約 $g(x)\le 0$ だけに乗数 $\lambda \ge 0$ を付けてラグランジュ関数 $L(x,\lambda )=f(x)+\lambda g(x)$ を作り（$x\in X$ という制約は双対化しない）、双対関数を
$$q(\lambda )=\underset{x\in X}{\min }L(x,\lambda )(\lambda \ge 0)$$
と定める。$(\mathrm{P})$ の最適値を $p^{\ast }$、双対問題 $\underset{\lambda \ge 0}{\max }q(\lambda )$ の最適値を $d^{\ast }$ とする。組 $(p^{\ast },d^{\ast })$ をこの順に求めよ。

$X=[0,2]\times [0,2]\subset {\mathbb{R}}^2$ とし、次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}-x_1{x}_2\text{subject to}{x}_1+2x_2\le 2,x=(x_1,x_2)\in X.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。制約 $x_1+2x_2\le 2$ だけを乗数 $\lambda \ge 0$ で緩和したラグランジュ双対関数
$$g(\lambda )=\underset{x\in X}{\min }\{-x_1{x}_2+\lambda (x_1+2x_2-2)\}$$
を用い、双対問題の最適値を $d^{\ast }={\sup }_{\lambda \ge 0}g(\lambda )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

$x=(x_1,x_2,x_3,x_4)\in \{0,1{\}}^4$ を変数とする次の 0-1 ナップサック問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{maximize}7x_1+5x_2+4x_3+3x_4\text{subject to}5x_1+4x_2+3x_3+2x_4\le 9,x\in \{0,1{\}}^4.$$
$(\mathrm{P})$ の最適値を $p^{\ast }$ とする。不等式制約だけに乗数 $\lambda \ge 0$ を導入してラグランジュ関数
$$L(x,\lambda )=7x_1+5x_2+4x_3+3x_4+\lambda (9-5x_1-4x_2-3x_3-2x_4)$$
を定め、双対関数を $g(\lambda )={\max }_{x\in \{0,1{\}}^4}L(x,\lambda )$、双対問題の最適値を $d^{\ast }={\min }_{\lambda \ge 0}g(\lambda )$ とする。双対ギャップ $d^{\ast }-p^{\ast }$ を求めよ。

$B=[-1,2]\times [-1,2]\subset {\mathbb{R}}^2$ とし、次の最適化問題 $(\mathrm{P})$ を考える。
$$(\mathrm{P})\text{minimize}f(x)=-x_1{x}_2\text{subject to}{x}_1+x_2=1,x=(x_1,x_2)\in B$$
等式制約 $x_1+x_2=1$ だけを乗数 $\mu \in \mathbb{R}$ で緩和し、集合制約 $x\in B$ は残したラグランジュ関数
$$L(x,\mu )=-x_1{x}_2+\mu (x_1+x_2-1)$$
から双対関数 $q(\mu )=\underset{x\in B}{\min }L(x,\mu )$ を定め、双対問題 $(\mathrm{D})$: $\underset{\mu \in \mathbb{R}}{\max }q(\mu )$ を考える。$(\mathrm{P})$ の最適値を $p^{\ast }$、$(\mathrm{D})$ の最適値を $d^{\ast }$ とするとき、双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

$x=(x_1,\dots ,x_5)\in {\mathbb{R}}^5$ を変数とする次の最適化問題 $(\mathrm{P})$ を考える（添字は $\mathrm{mod}5$ で考え、$x_6=x_1$ とする）。
$$(\mathrm{P})\text{minimize}f(x)=2\sum _{i=1}^5{x}_i{x}_{i+1}\text{subject to}{x}_i^2-1=0(i=1,\dots ,5).$$
その最適値を $p^{\ast }$ とする。等式制約に乗数 $\nu =({\nu }_1,\dots ,{\nu }_5)\in {\mathbb{R}}^5$ を対応させたラグランジュ関数
$$L(x,\nu )=f(x)+\sum _{i=1}^5{\nu }_i(x_i^2-1)$$
に対し、双対関数を $q(\nu )={\inf }_{x\in {\mathbb{R}}^5}L(x,\nu )$（値 $-\infty$ を許す）、ラグランジュ双対問題の最適値を $d^{\ast }={\sup }_{\nu \in {\mathbb{R}}^5}q(\nu )$ とする。双対ギャップ $p^{\ast }-d^{\ast }$ を求めよ。

$n\ge 2$ を整数とし、$J$ を成分がすべて $1$ の $n$ 次正方行列、$I$ を $n$ 次単位行列、$W=J-I$ とする。$x\in {\mathbb{R}}^n$ を変数とする最適化問題
$$(\mathrm{P})\text{minimize}{x}^{\top }Wx\text{subject to}{x}_i^2-1=0(i=1,\dots ,n)$$
を考え、その最適値を $p^{\ast }$ とする。$\nu \in {\mathbb{R}}^n$ に対しラグランジュ関数を
$$L(x,\nu )=x^{\top }Wx+\sum _{i=1}^n{\nu }_i(x_i^2-1)$$
と定め、双対関数を $g(\nu )={\inf }_{x\in {\mathbb{R}}^n}L(x,\nu )\in [-\infty ,\infty )$、双対問題の最適値を $d^{\ast }={\sup }_{\nu \in {\mathbb{R}}^n}g(\nu )$ とする。

双対ギャップ $p^{\ast }-d^{\ast }$ が、$n$ が奇数のとき $1$、$n$ が偶数のとき $0$ であることを証明せよ。