目次
- 目次
- はじめに
- CVX: MATLAB Software for Disciplined Convex Programming
- インストール
- シンプルな凸最適化を解く
- 変数がベクトルの場合の凸最適化
- 参考資料
- MyEnigma Supporters
はじめに
先日、最適化技術の一つである凸最適化の基礎に関する
記事を書きましたが、
この凸最適化を実際に解くライブラリの中で最も有名なのが、
CVXというライブラリです。
今回はこのライブラリの概要と実際に凸最適化を解くための
サンプルコードについて説明したいと思います。
CVX: MATLAB Software for Disciplined Convex Programming
CVXはMATLAB上で動く凸最適化のためのモデリングツールです。
このCVXを使えば、線形計画法(LPs)から、
二次計画法(QPs)、
二次凸関数問題(Second-order cone programs:SOCPS)
Semidefinite Programs(SDPs)
などの様々な最適化問題を解くことができます。
Stanford大学の凸最適化の有名な教授である、
Stephen P. Boyd氏が所属しているCVX Research Inc.という
企業が開発をしています。
このBoyd教授は凸最適化の著名教科書である
『Convex Optimization』の著者でもあります。
CVXは基本的に学術用途でも商用用途でも無料ですが、
商用ソルバであるGurobiやMosekという有償ライブラリを利用するには、
Professional Licenseを購入する必要があるようです。
加えて、もしCVSのモデリングなどに関して、
質問がある場合は、下記の掲示板で質問することもできます。
インストール
インストール方法は下記の通りです。
1. ソフトをzipで落としてきて、解凍
こちらからDLできます。
2. CVXを起動する
MATLABを立ち上げて、先程の解凍したソフトの場所まで移動します。
そして、
cvx_setup
とコマンドを入力します。
このコマンドでライブラリなどのパスが追加されます。
(パスを自分で追加したらいけないようです)
ちなみに毎回MATLABを立ち上げる度に、この作業が必要になります。
シンプルな凸最適化を解く
では、実際にCVXを使って、
簡単な凸最適化を解いてみたいと思います。
例題として、変数x,yにおいて、
(x+y+3)2という式を最小化するx,yを見つけたいとします。
しかし、制約としてyは正であるとします。
この問題を解きたい場合は、
下記のようにMATLABでコマンドするだけです。
% cvx model cvx_begin variables x y minimize((x+y+3)^2) y>=0 cvx_end % answer x y % optimization status cvx_status % final cost value cvx_optval
cvx_beginとcvx_endで囲まれたコードは、
CVXのモデリングコードとして認識されます。
それ以外は普通のMATLABコードです。
モデリングとしては、非常にシンプルで、
variablesの後に変数を記述し、
最小化するコスト関数をminimize()の中に書きます。
そして、各変数の制約条件を数式のように記述するだけです。
cvx_endと記述した時点で、凸最適化計算が実行されます。
その後、最適化後の変数はそのままモデリングした名前と
同じ変数に格納されます。
cvx_statusは最適化の結果を表す変数です。
上記のコードを実行すると、下記のような出力が得られます。
x=-7.531,y=4.51でコスト関数がほぼ0の最小値が得られました。
モデリング言語が数式のように書けるのが非常に便利だと思います。
変数がベクトルの場合の凸最適化
続いて、先程は変数がx,yの2つだけでしたが、
変数がベクトルとして複数個ある場合の最適化を解いてみたいと思います。
これも非常に簡単です。
まず問題として、Ax=bの線形方程式を考えます。
xのサイズは30個で、方程式の数は100個としましょう。
続いて、変数xはすべて正、そして総和は1であるという制約もあるとします。
上記の問題を解く場合は下記のようにMATLABスクリプトを書けばOKです。
A=randn(100,30); b=randn(100,1); cvx_begin variable x(30) x>=0 sum(x)==1 minimize(norm(A*x-b)) cvx_end x
今回はAとbの係数はrandnで与えました。
そしてAx=bを解く代わりに、Ax-bを最小化するようにしています。
ちなみに上記のコードのように制約条件はminimiziの前に書いてもOKのようです。
上記のコードを実行すると、下記のように最適値のxベクトルが得られます。
参考資料
MyEnigma Supporters
もしこの記事が参考になり、
ブログをサポートしたいと思われた方は、
こちらからよろしくお願いします。