二次錐制約のベンチマーク問題

論文 :
K. Kobayashi, S. Kim and M. Kojima, "Sparse Second Order Cone Programming Formulations for Convex Optimization Problems", Journal of the Operations Research Society of Japan., Vol. 51 (3), 241-264, 2008
で用いたSOCPのベンチマーク問題の置き場です.

二次錐計画

二次錐は以下で定義される.

ここで、"|"記号以下の不等式のことを, 二次錐制約とよぶ。 二次錐計画では、複数の二次錐のCartesian productの要素を変数とする場合も扱う. すなわち、n次元のベクトルxがm個の要素に分けられて、分けられた部分ベクトルがそれぞれ二次錐の制約を満す場合である:

二次錐制約をベクトルxが満たすことを,

とも書く.

Restricted hyperbolic constraint

多項式に関する不等式の中には、二次錐制約で表すことができるものがある。二次錐制約で表すために、以下の"restricted hyperbolid constraint"とよばれる関係を用いる

以下は、\vec{z} = (y_1,y_2), u=1, v=xの場合のrestricted hyperbolic constraintの例である.

一番目の不等式は、他の書き方をすると、y_1^2+y_2^2<=xである。 このタイプの不等式は、矢印下の二次錐不等式と同値であることを表している. 多項式の不等式の中には、この関係をつかって二次錐制約で表現することができるものがあることがわかる.

二次錐制約で表現可能な多項式最適化問題

次の形の多項式最適化問題を二次錐計画問題として表現する.

ただし、ここでf_jは二次錐制約で表現可能な多項式とする. 一般に、二次錐計画として定式化可能な多項式計画問題は、その定式化は複数存在する.

例:the Chained singular function

the Chained singular functionの最小化問題は、以下のとおり制約をもたない最小化問題です.

ただし、

で、nは4の倍数です. この最小化問題は、補助変数sを導入すると,以下のとおりに表現できます.

これを二次錐計画問題として表すと、

となります。

様々な多項式から生成する二次錐計画問題

ここまでで述べた原理を用いて、様々な多項式計画問題から二次錐計画問題をしました。

Unconstrainted problems

CUTEr http://cuter.rl.ac.uk/cuter-www/ で用いられているいくつかの関数から導出しました.

• The arwhead function

  

  Download, arwhead.tar.gz(651KB) SOCP problem in SeDuMi format
• The engval1 function

  

• The nondquar function

  

• The vardim function

  

http://keizai.xrea.jp/latex/tutorial/mathkigou.html