制約に最小化を含む最小化問題

仕事で「制約に最小化を含む最小化問題」みたいなのを考える必要が出てて、これが思った以上に難しくて「むむむっ」ってなってる。というか、頭から離れない。。。

例えば、次のような最小化問題：

$\left| \begin{align} &\mathrm{min.} & & x + q(x) + r(y) \\ &\mathrm{sub. to} & & q(x) = \mathrm{min.}\{2y\;|\; x + y \ge 3\} \\ & & & r(y) = \mathrm{min.}\{3z\;|\; y + z \ge 4\} \\ & & & x \ge 0, y \ge 0, z \ge 0 \\ \end{align} \right.$

パッと見、 $q(x)$ も $r(y)$ もそれぞれ $2y$ と $3z$ を最小化するんだから、目的関数の部分を置き換えてしまえばいいように思う：

$\left| \begin{align} &\mathrm{min.} & & x + 2y + 3z \\ &\mathrm{sub. to} & & x + y \ge 3 \\ & & & y + z \ge 4 \\ & & & x \ge 0, y \ge 0, z \ge 0\\ \end{align} \right.$

でも、これではダメだったり。

実際、後者の最適解は $(x, y, z) = (0, 4, 0)$ で、最適値は8となるんだけど、これを前者に入れて考えてみると、 $q(x) = \mathrm{min.}\{2y\;|\; x + y \ge 3\}$ の制約が守られてない。 $x$ を0とするなら、この制約を守るために $y$ は自動的に3となる。

つまり、前者では $x$ が決まると自動的に $y$ が決まり、同様に $z$ も決まるので、実際に自由に値を取れるのは $x$ となる。一方、後者は $x, y, z$ のいずれも制約を守る限りで自由に動けるので、等価になっていない（緩和にはなってる）。

ただ、これくらい簡単な例なら、 $q(x)$ と $r(y)$ を具体的に $x$ の式にできるので、解くことはできる：

$\begin{align} q(x) &= \begin{cases} 6 - 2x & (0 \le x \le 3) \\ 0 & (\mathrm{otherwise}) \\ \end{cases}\\ r(y) &= \begin{cases} 12 - 3y & (0 \le y \le 4) \\ 12 & (\mathrm{otherwise}) \\ \end{cases}\\ &= \begin{cases} 3x + 3 & (0 \le x \le 3) \\ 12 & (\mathrm{otherwise}) \\ \end{cases} \end{align}$

なので、

$\begin{align} x + q(x) + r(y) = \begin{cases} 2x + 9 & (0 \le x \le 3) \\ x + 12 & (\mathrm{otherwise}) \\ \end{cases} \end{align}$

となり、 $(x, y, z) = (0, 3, 1)$ で最小値9をとると分かる。

けど、これが

$\left| \begin{align} &\mathrm{min.} & & \boldsymbol{c}^\top \boldsymbol{x} + q(\boldsymbol{x}) + r(\boldsymbol{y}) \\ &\mathrm{sub. to} & & q(\boldsymbol{x}) = \mathrm{min.}\{\boldsymbol{d}^\top \boldsymbol{y}\;|\; A\boldsymbol{x} + B\boldsymbol{y} \ge \boldsymbol{a}\} \\ & & & r(\boldsymbol{y}) = \mathrm{min.}\{\boldsymbol{e}^\top\boldsymbol{z}\;|\; C\boldsymbol{y} + D\boldsymbol{z} \ge \boldsymbol{b}\} \\ & & & \boldsymbol{x} \ge \boldsymbol{0}, \boldsymbol{y} \ge \boldsymbol{0}, \boldsymbol{z} \ge \boldsymbol{0} \\ \end{align} \right.$