簡単に見えて、どのソフトでも解けない問題

今やっている問題が解けないので、基本的な制約だけを残して定式化してみた。
それでもsparsePOP では解けなかった。
 NEOS に載っているほかのソフトでも試してみたが (GAMSを受け付けるものを試してみた）
BARON, LINDO, Gurobi, MOSEK, XpressMP, CONOPT, Ipopt, KNITRO, SNOPT, Bonnin, Conenne, PATHNLP
でも解けなかった。

問題は x \in R^5 が変数であって、
min c^T x : subject to e^T x = 1, x_i^2 = 1 (i=1,..,5)
というものである。
実行可能解としては、x_1=x_4=-1, x_2=x_3=x_5=1 があるので、実行不可能ではない。
しかし、NEOS のソフトの場合、たいていは Locally Infeasible あるいは Infeasible で終了してしまう。
sparsePOP の場合は、relaxOrder = 1 (通常の SDP 緩和）だと解くには解くが、x_1=x_4=0 などとなってしまい緩和が弱く、relaxOrder >= 2 だと SDP infeasible となる。

実際に使った GAMS のファイルは以下の通りである。
========


Variables x1,x2,x3,x4,x5,objvar;
Positive Variables x1,x2,x3,x4,x5;
Equations e1,e2,e3,e4,e5,e6,e7;
* e1.. 0.2*x1 +0.7*x2 +0.1*x3 +0.9*x4 +0.4*x5 + objvar =E= 0;
e1.. objvar =E= 0.8*x1 +0.7*x2 +0.1*x3 +0.9*x4 +0.4*x5;
e2.. x1 + x2 + x3 + x4 + x5 =E= 1;
e3.. x1*x1 =E= 1;
e4.. x2*x2 =E= 1;
e5.. x3*x3 =E= 1;
e6.. x4*x4 =E= 1;
e7.. x5*x5 =E= 1;
Model m / all /;
m.limrow=0; m.limcol=0;
$if NOT '%gams.u1%' == '' $include '%gams.u1%'
Solve m using NLP minimizing objvar;

==

おそらくGAMSファイルは間違っていないはずで e2 の =E= 1 を =E= 5 にすると、最適解x_1=x_2=x_3=x_4=x_5 = 1 が得られる。

しかし、=E= 1 のままでは解くことができない。

もちろん、x_i^2 = 1 を x_i = {-1,1} にして Mixed Integer にすれば CPLEX などで簡単に解けるのであるが、本来解こうとしている問題にするために条件を追加する時点でうまくできなくなってしまう。

数理最適化の分野はいろいろなソフトが開発されているが、まだ完全とは言えないようで、だからこそ研究余地が大きく残っているともいえる。

今日の作業内容：SparsePOP, NEOS 確認 5h

今日のランチ：シッダルータ キーマカレー

明日の予測作業時間：2h