nAG数値計算ライブラリ
> 最適化アルゴリズムExample集
> 双線形制約を含む半正定値計画問題の解法
半正定値計画問題-SDP（双線形制約）
このExampleでは、Pennonを用いて双線形行列不等式制約を含む半正定値計画問題を解いています。目的は双線形行列不等式制約を含む半正定値計画問題の定式化と解法を示すことです。
目的関数:
| タスク | 式 |
|---|---|
| Minimize | \(x_1 + x_3\) |
決定変数:
| 変数 | 範囲 |
|---|---|
| \(x_1\) | \((-\infty, \infty)\) |
| \(x_2\) | \((-\infty, \infty)\) |
| \(x_3\) | \((-\infty, \infty)\) |
| \(x_4\) | \((-\infty, \infty)\) |
| \(x_5\) | \((-\infty, \infty)\) |
制約条件:
| 制約 | 式 |
|---|---|
| 線形行列不等式制約1 | \(\begin{bmatrix} x_1 + 2x_2 + 6x_3 + 5x_4 & x_1 - 2x_2 + 3x_5 \\ x_1 - 2x_2 + 3x_5 & x_2 + 8x_5 \end{bmatrix} \succeq 0\) |
| 双線形行列不等式制約 | \(\begin{bmatrix} 2x_1x_4 + x_2x_4 + x_3x_4 & x_1x_5 + x_2x_5 + x_3x_5 \\ x_1x_5 + x_2x_5 + x_3x_5 & 2x_2x_5 \end{bmatrix} \succeq 0\) |
| 線形行列不等式制約2 | \(\begin{bmatrix} x_1 + x_3 & x_2 \\ x_2 & x_5 \end{bmatrix} \succeq 0\) |
- \(\succeq 0\)は半正定値を表す
- 線形行列不等式制約1は\(2\times 2\)の対称行列で、\(x_1, x_2, x_3, x_4, x_5\)の線形式で表現されています
- 双線形行列不等式制約は\(2\times 2\)の対称行列で、\(x_1, x_2, x_3, x_4, x_5\)の2次式（双線形項）で表現されています
- 線形行列不等式制約2は\(2\times 2\)の対称行列で、\(x_1, x_2, x_3, x_5\)の線形式で表現されています
Exampleの実行コマンド:
python -m naginterfaces.library.examples.opt.handle_solve_pennon_bmi_exソースコード表示コマンド:
python -c "import inspect; from naginterfaces.library.examples.opt import handle_solve_pennon_bmi_ex; print(''.join(inspect.getsourcelines(handle_solve_pennon_bmi_ex)[0]))"出力結果例:
naginterfaces.library.opt.handle_solve_pennon Python Example Results.
BMI-SDP.
Final objective value is 2.000000
at the point:
(1.000e+00, 1.029e-15, 1.000e+00, 1.314e+03, 1.311e+03).
マニュアル:
ソース:
#!/usr/bin/env python3
"""
``naginterfaces.library.opt.handle_solve_pennon`` Python Example,
with bilinear matrix inequality constraints.
"""
# nAG Copyright 2018-2019.
# pylint: disable=invalid-name,too-many-arguments,too-many-locals,too-many-statements
from naginterfaces.library import opt
def main():
"""
Example for :func:`naginterfaces.library.opt.handle_solve_pennon`,
with bilinear matrix inequality constraints.
Semidefinite programming using Pennon.
>>> main()
naginterfaces.library.opt.handle_solve_pennon Python Example Results.
BMI-SDP.
Final objective value is 2.000000
at the point:
(1.000e+00, 1.029e-15, 1.000e+00, 1.314e+03, 1.311e+03).
"""
print(
'naginterfaces.library.opt.handle_solve_pennon Python Example Results.'
)
print('BMI-SDP.')
# The number of decision variables:
nvar = 5
# Create a handle for the problem:
handle = opt.handle_init(nvar)
# Define the linear objective function:
opt.handle_set_linobj(
handle,
cvec=[1., 0., 1., 0., 0.],
)
# Define the first linear matrix constraint:
opt.handle_set_linmatineq(
handle,
dima=2, nnza=[2, 2, 3, 2, 0, 0],
irowa=[1, 2, 1, 1, 1, 1, 2, 1, 2], icola=[1, 2, 1, 2, 1, 2, 2, 2, 2],
a=[1.0, 1.0, 2.0, -2.0, 6.0, 5.0, -4.0, 3.0, 8.0],
)
# Define the bilinear matrix constraint:
opt.handle_set_quadmatineq(
handle,
qi=[1, 2, 3, 1, 2, 3], qj=[4, 4, 4, 5, 5, 5],
dimq=2, nnzq=[1, 2, 1, 1, 2, 1],
irowq=[1, 1, 1, 1, 1, 1, 2, 2], icolq=[1, 1, 2, 2, 2, 2, 2, 2],
q=[2.0, 2.0, 1.0, 1.0, 1.0, 1.0, 2.0, 2.0], idblk=1,
)
# Define the second linear matrix constraint:
opt.handle_set_linmatineq(
handle,
dima=2, nnza=[2, 1, 1, 1, 0, 0],
irowa=[1, 2, 1, 1, 2], icola=[1, 2, 1, 2, 2],
a=[1.0, 1.0, 1.0, 1.0, 1.0],
)
# Initial estimate of the solution:
x = [0.]*nvar
opt.handle_opt_set(
handle, 'Print Level = 0',
)
opt.handle_opt_set(
handle, 'Print Options = No',
)
# Solve the problem:
pennon_sol = opt.handle_solve_pennon(handle, x, inform=0)
print('Final objective value is {:f}'.format(pennon_sol.rinfo[0]))
print('at the point:')
print('(' + ', '.join(['{:.3e}']*nvar).format(*pennon_sol.x) + ').')
# Destroy the handle:
opt.handle_free(handle)
if __name__ == '__main__':
import doctest
import sys
sys.exit(
doctest.testmod(
None, verbose=True, report=False,
optionflags=doctest.ELLIPSIS | doctest.REPORT_NDIFF,
).failed
)