簡単そうに見えて、実は難しい、最適化問題

最小自乗問題
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n $$
は、A の行が一次独立なら簡単に解ける問題。

次に、
$$ \min \frac{1}{2} || x - x^0 ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$

と各変数が非負に制限されるときも簡単に解けて、解としては

$$ x^* = \max\{x,0\} $$
である。

ところが、この２つが組み合わさると
$$ \min \frac{1}{2} || Ax - b ||^2 \quad \mbox{s.t.} \quad x \in R^n,\ x \ge 0$$

とたんに、簡単には解けなくなる。

http://math.uni-graz.at/mobis/publications/SFB-Report-2012-016.pdf

のように内点法ベースなら解けるのであるが、もっと簡単に解けそうにも見えて、そういった解法が見当たらない。

この「簡単そうなのに、より適した解法が案外見当たらない」というところが、面白い。