簡単なSOCP例

このデモンストレーションは、nAG Library for Pythonに同梱されている例のセットから取られています。コマンドシェルで以下のコマンドを実行すると、すべての例を表示できます。

python -m naginterfaces.library.examples --locate

nAGのhandle_solve_socp_ipm関数（e04ptとしても知られる）は、大規模な二次錐計画問題（SOCP）のためのnAG最適化モデリングスイートのソルバーです。これは内点法（IPM）に基づいています。

\[ \begin{array}{ll} {\underset{x \in \mathbb{R}^{n}}{minimize}\ } & {c^{T}x} \\ \text{subject to} & {l_{A} \leq Ax \leq u_{A}\text{,}} \\ & {l_{x} \leq x \leq u_{x}\text{,}} \\ & {x \in \mathcal{K}\text{,}} \\ \end{array} \]

ここで、\(\mathcal{K} = \mathcal{K}^{n_{1}} \times \cdots \times \mathcal{K}^{n_{r}} \times \mathbb{R}^{n_{l}}\)は二次（二次錐型）錐と\(n_{l}\)次元実空間のデカルト積であり、\(n = \sum_{i = 1}^{r}n_{i} + n_{l}\)は決定変数の数です。ここで\(c\)、\(x\)、\(l_x\)、\(u_x\)は\(n\)次元ベクトルです。

\(A\)は\(m\)行\(n\)列の疎行列で、\(l_A\)と\(u_A\)は\(m\)次元ベクトルです。\(x \in \mathcal{K}\)は変数のサブセットを二次錐に分割し、各\(\mathcal{K}^{n_{i}}\)は二次錐または回転二次錐のいずれかであることに注意してください。これらは以下のように定義されます：

二次錐：

\[ \mathcal{K}_{q}^{n_{i}} := \left\{ {z = \left\{ {z_{1},z_{2},\ldots,z_{n_{i}}} \right\} \in {\mathbb{R}}^{n_{i}} \quad\quad : \quad\quad z_{1}^{2} \geq \sum\limits_{j = 2}^{n_{i}}z_{j}^{2},\quad\quad\quad z_{1} \geq 0} \right\}\text{.} \]

回転二次錐：

\[ \mathcal{K}_{r}^{n_{i}} := \left\{ {z = \left\{ {z_{1},z_{2},\ldots,z_{n_{i}}} \right\} \in {\mathbb{R}}^{n_{i}}\quad\quad:\quad \quad\quad 2z_{1}z_{2} \geq \sum\limits_{j = 3}^{n_{i}}z_{j}^{2}, \quad\quad z_{1} \geq 0, \quad\quad z_{2} \geq 0} \right\}\text{.} \]

このルーチンの完全な説明については、nAGライブラリマニュアルのe04ptcを参照してください。

この例は、handle_set_group関数のドキュメントから派生したもので、以下のSOCP問題を解きます：

minimize \[{10.0x_{1} + 20.0x_{2} + x_{3}}\]

from naginterfaces.base import utils
from naginterfaces.library import opt

# 問題のサイズ:
n = 3

# 問題ハンドルを作成する:
handle = opt.handle_init(nvar=n)

# 目的関数を設定する
opt.handle_set_linobj(handle, cvec=[10.0, 20.0, 1.0])

以下の制約条件に従う \[ \begin{array}{rllll} {- 2.0} & \leq & x_{1} & \leq & 2.0 \\ {- 2.0} & \leq & x_{2} & \leq & 2.0 \\ \end{array} \]

# 箱型制約を設定する
opt.handle_set_simplebounds(
    handle,
    bl=[-2.0, -2.0, -1.e20],
    bu=[2.0, 2.0, 1.e20]
)

一般線形制約

\[\begin{array}{lcrcrcrclcl} & & {- 0.1x_{1}} & - & {0.1x_{2}} & + & x_{3} & \leq & 1.5 & & \\ 1.0 & \leq & {- 0.06x_{1}} & + & x_{2} & + & x_{3} & & & & \\ \end{array}\]

# 線形制約を設定する
_ = opt.handle_set_linconstr(
    handle,
    bl=[-1.e20, 1.0],
    bu=[1.5, 1.e20],
    irowb=[1, 1, 1, 2, 2, 2],
    icolb=[1, 2, 3, 1, 2, 3],
    b=[-0.1, -0.1, 1.0, -0.06, 1.0, 1.0]
    )

そして円錐制約

\[\left( {x_{3},x_{1},x_{2}} \right) \in \mathcal{K}_{q}^{3}\text{.}\]

# 円錐制約を設定
_ = opt.handle_set_group(
    handle,
    gtype='Q',
    group=[ 3,1, 2],
    idgroup=0
)

アルゴリズムのオプションをいくつか設定します

# アルゴリズムのオプションをいくつか設定します。
for option in [
        'Print Options = NO',
        'Print Level = 1'
]:
    opt.handle_opt_set(handle, option)

# 省略された反復出力のために明示的なI/Oマネージャーを使用する：
iom = utils.FileObjManager(locus_in_output=False)

最後に、ソルバーを呼び出します

# SOCP内点法ソルバーを呼び出す
result = opt.handle_solve_socp_ipm(handle, io_manager=iom)

 E04PT, Interior point method for SOCP problems
 Status: converged, an optimal solution found
 Final primal objective value -1.951817E+01
 Final dual objective value   -1.951817E+01

最適解は以下の通りです

result.x

array([-1.26819151, -0.4084294 ,  1.3323379 ])

そして目的関数の値は

result.rinfo[0]

-19.51816515094211

最後に、ハンドルを破棄して後片付けをします

# ハンドルを破棄する:
opt.handle_free(handle)

簡単なSOCP例

nAG Library for Python Example集

簡単なSOCP例