数理最適化の難しさは谷の形が単調ではないこと
図2のようにして最短経路を見つけていく問題は「凸問題」と言われる。これは、「今の状態」よりも少しでも「より良い状態（滑らかな状態）」になるように変化すれば、いつかは最適な状態に近づくということが保証された問題である。
これを説明するには図3のような「評価関数」を書くとわかりやすい。
図3
この「評価関数」は、縦軸に「経路の長さ」横軸に「状態」を取ったもので、今の状態から、「滑らかになる方向（すなわち経路が短くなる方向）」に変化させていくと、「最適な状態」にたどり着くことが保証された問題である。こんな風に、谷の形が単調なら、いずれ問題が解けることは理解しやすいだろう。
しかしながら、実際の問題は、「非凸問題」と言われ、必ずしも、「今の状態」よりも少しでも「より良い状態（滑らかな状態）」になるように変化すれば、いつかは最適な状態に近づくということが保証された問題というわけにはいかない。
例えば、図4（a）のように、地点AからBまで、地形の状態が複雑に入り組んでいるとすれば、少し経路を滑らかにしたからといって、最適な状態（最適解）に近づく保証はないということは、理解に難くないだろう。
図4（a）
図4（a）のような場合、評価関数は図4（b）のようになり、「全部の経路をたどらないと、最短経路（最適解）が見つからない。
図4（b）
だからこそ、最適解を見つけることは容易ではなく、こうした非凸問題において、「最適解をどうやって見つけ出すか」に関する研究が歴史的になされてきた。囲碁や将棋などもこうした問題の1つであり、「最適な勝ち方（勝利までの最短の打ち方）」は未だわかっていないものの、どういった打ち方をすれば、より勝利への経路にたどり着きやすいかが分かって来た。これまでの棋譜を学習させることにより、「確率的に」問題を解けるようになり、人間を凌駕したロボット棋士が誕生するようになった、という背景がある。
あらゆる問題は「解ける」もの
このように、数理最適化の手法を用いることで、現実のさまざまな問題が、解決可能になってきた。囲碁や将棋といったゲームは、最も難しい問題の1つとされ、これらが解かれたことで、数理科学者への関心が高まり、今、「人工知能」の実現に向けた期待が一気に高まっている。
これらのように最も難しいとされている問題ですら、人間を凌駕する解を導き出せるようになったことは、「あらゆる問題はいつかは解かれる」ということの1つの証拠でもある。もはや、機械に解けない問題は、ないといってよい。
