[TOC]

1. 最適化問題の基本用語

1.1. GAP

実行可能領域で目的関数が非負の値をとる最小化問題を考える.最適化アルゴリズムを実装している時にある時点でのGAPを以下で定義する.$\check{f}$を現在見つかっている下界の中で最大のものだとする.$f^{\ast }$を最適解の目的関数値とする(多くの場合,現時点では見つかっていない).$f$を現在見つかっている最良の解とする.この時,$\check{f}\le f^{\ast }\le f$, $0\le f^{\ast }$が成立しておりGAPは以下で表される. $$\frac{f-\check{f}}{f}$$

2. 最適化問題一覧

2.1. 混合整数二次錐計画MISOCP

MISOCP(Mixed Integer Second Order Cone Programming)

ある程度ソルバーでも解ける問題らしい

$$\begin{array}{ccccc}& \underset{x}{\text{minimize}}& & c^{T}x& \\ & \text{subject to}& & Ax=b& \\ & & & x⪰0& \\ & & & x_j\in [l_j,u_j]& (j\in J)\\ & & & x_j\in Z& (j\in J)\end{array}$$

where $c\in R^n,A\in R^{m,n},b\in R^m,l_j,u_j\in R$ and $x⪰0$ denotes that $x\in R^n$ consists of noc part vectors $\boldsymbol{x}_i \in \mathbb{R}^{k_i}$ lying in second order cones defines by $$K_i=\{x_i=(x_{i0},x_{i1}^T{)}^T\in R\times R^{k_i-1}\mid \parallel x_{i1}{\parallel }_2\le x_{i0}\}$$ つまり,$x=(x_1^T,x_2^T,\dots ,{)}^T$であり任意の$i$に対して,$x_i\in K_i$

2.2. 混合01二次錐計画

$$\begin{array}{ccccc}& \underset{x}{\text{minimize}}& & c^{T}x& \\ & \text{subject to}& & Ax=b& \\ & & & x⪰0& \\ & & & x_j\in \{0,1\}& (j\in J\subset \{1,\dots \left\}\right)\end{array}$$

3. 最適化問題における現在の研究潮流

線形$\subset$ニ次錐$\subset$半正定値$\subset$凸最適化

→現在は半正定値問題なら上手く解けることが知られているので, 研究テーマとしてはより一般的な凸最適化もしくは最新の研究成果を組み合わせながら実問題や別の問題に適応するなどが推奨される?

一方,非凸最適化は解きにくい

九大の脇先生→多項式最適化(最近の流行りの研究で目的関数と制約式が多項式)

4. 最適化問題の変形テクニック

4.1. 特定のパスを除く制約

$P$を除きたいパスの集合,$x_a$を枝$a$を通る時に1,通らない時に0をとる変数だとすると $$\sum _{a\in P}{x}_a\le |P|-1(\forall P\in P)$$

4.2. スイッチ制約

定数$v_{min},v_{max}$と変数$x\in \{0,1\},v\in R$が与えられたとする.この時 $$\begin{array}{ccc}{v}_{min}& \le v\le v_{max}& \text{if}x=1\\ & v=0& \text{if}x=0\end{array}$$ の制約式は$v_{min}x\le v\le v_{max}x$と等価

4.3. 目的関数に2乗を含む時に二次錐計画に変換

以下のように目的関数に$x^2$を含む時 $$\begin{array}{cccc}& \underset{x\ge 0}{\text{minimize}}& & x^2\\ & \text{subject to}& & x\in F\end{array}$$

以下のように二次錐計画に変形することができる.$t+1\ge 0$のとき $$t\ge x^2\iff (t+1{)}^2\ge (t-1{)}^2+(2x{)}^2\iff (t+1)\ge \sqrt{(t-1{)}^2+(2x{)}^2}$$ であるので,上記の最適化問題は以下のように書き表せる. $$\begin{array}{cccc}& \underset{t,x\in R}{\text{minimize}}& & t\\ & \text{subject to}& & x\in F\\ & & & \left(\begin{array}{c}t+1\\ t-1\\ 2x\end{array}\right)\in K\end{array}$$ ただし$K$は以下のように定義する. $$K\equiv \{x=(x_0,x_1)\in R\times R^{n-1}\mid x_0\ge \parallel x_1{\parallel }_2\}$$

4.4. 目的関数が分数の場合

4.4.1. 例1

$c>0$を定数として以下の最適化問題を考える $$\begin{array}{cccc}& \underset{x\ge 0,u\in R}{\text{minimize}}& & \frac{c}{x}\end{array}$$ この時上記は以下の最適化問題と同値 $$\begin{array}{cccc}& \underset{x\ge 0}{\text{minimize}}& & u\\ & \text{subject to}& & u\ge \frac{(\sqrt{c}{)}^2}{x}\end{array}$$ ここで制約式より$u\ge 0$であるので$u+x\ge 0$であることに注意すると $$u\ge \frac{(\sqrt{c}{)}^2}{x}\iff (u+x{)}^2\ge (u-x{)}^2+2(\sqrt{c}{)}^2\iff u+x\ge \sqrt{(u-x{)}^2+(s\sqrt{c}{)}^2}$$ であるので $$\begin{array}{cccc}& \underset{x\ge 0}{\text{minimize}}& & u\\ & \text{subject to}& & \left(\begin{array}{c}u+x\\ u-x\\ 2\sqrt{c}\end{array}\right)\in K\end{array}$$

4.4.2. 例2

$a,b,c\in R$は$a\ge 0,b>0,b+c>0$を満たしている定数として以下の最適化問題を考える $$\begin{array}{cccc}& \underset{x\in \{0,1\}}{\text{minimize}}& & \frac{ax}{b+cx}\end{array}$$ この時,$x^2=x$であることに注意すると $$\begin{array}{cccc}& \underset{x\in \{0,1\}}{\text{minimize}}& & au\\ & \text{subject to}& & u\ge \frac{x^2}{b+cx}\end{array}$$ 制約式を満たしてい流とき$u+(b+cx)\ge 0$であることに注意すると,上記と同様に $$u\ge \frac{x^2}{b+cx}\iff u(b+cx)\ge x^2\iff (u+b+cx{)}^2\ge (u-(b+cx){)}^2+(2x{)}^2$$ であるので, $$\begin{array}{cccc}& \underset{x\in \{0,1\}}{\text{minimize}}& & au\\ & \text{subject to}& & \left(\begin{array}{c}u+b+cx\\ u-(b+cx)\\ 2x\end{array}\right)\in K\end{array}$$