読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

凸二次計画法を高速に解くc言語ソルバーを自動生成できるCVXGENの使い方

optimization

離散凸解析と最適化アルゴリズム (数理工学ライブラリー)

離散凸解析と最適化アルゴリズム (数理工学ライブラリー)

 

目次

はじめに

先日、凸最適化のモデリングツールとして、

MATLAB製のCVXや

myenigma.hatenablog.com

Python製のCVXPYを紹介しましたが、

myenigma.hatenablog.com

実際にロボットの制御などで凸最適化を利用したい場合、

高速に実行できるように、

C++などに最適化のコードを移植する必要があります。

しかし、モデリングの過程や、

ソルバーの中身はかなりブラックボックスなので、

移植は大変です。

 

そこで、モデリングツールでありながら、

モデリングした対象を実行するc言語ソフトを自動生成する

CVXGENというツールを使ってみたので

その時の使い方をメモしておきたいと思います。

 

CVXGENとは?

CVXGENは凸二次計画問題を解くための、

高速で、コード量の小さいCコードを生成するWebツールです。

コーディングの労力をできるだけ減らしつつ、

数式から直接高速なソルバーを生成することを目的としています。

 

CVXGENの特徴1: ライブラリフリーのcソルバーを自動生成できる

CVXGENが生成するCコードは、

ライブラリに依存していないため、

コンパイラでコンパイルすれば、

すぐに利用することができます。

また、ソルバーだけでなく、

MATLABのmexファイルからソルバーを利用できる

MATLAB関数のファイルも生成することができます。

 

CVXGENの特徴2: 非常に高速なソルバーを生成できる

CVXGENは凸最適化問題を解くための

数式の変換やコードの最適化をコード生成時に自動で実施するため、

オンラインでの計算の高速化を実現しています。

コードの生成は数秒から数分かかることがありますが、

実際の最適化の計算は数ミリ秒で終わることが多いです。

MATLABの最適化ツールであるCVXと比べると、

myenigma.hatenablog.com

標準的な問題で20倍、

小さな最適化問題の場合は10000倍速度が高速化されます。

 

CVXGENの制約事項

CVXGENは凸二次計画形式の問題しか解くことができません。

 

また、比較的に小規模の問題しか解くことができません。

制約条件とコスト関数のパラメータが

約2000個以下の問題しか対応できないようです。

 

CVXGENのライセンス

残念ながら、CVXGENはオープンソースではなく、

アカデミックライセンスと、商用ライセンスしかありません。

 

学生の場合は、下記のHPからライセンス依頼を出すことで

無料で利用できます。

商用ライセンスの場合は、直接作者にコンタクトする必要があるそうです

 

CVXGENの使い方

CVXGENはCVXGEN特有のモデリング言語で問題を記述すると、

その問題を解くソルバーコードを生成してくれます。

基本的には下記のドキュメントを読めば、

モデリング言語の記述の仕方はわかると思いますが、

下記に注意点をまとめておきます。

コメント

コメントはpythonと同じで、#から始まる行がコメントになります。

各タグの意味

  • Dimensions: コード生成される時の定数 (ハードコードされるので変更できない)

  • Parameters: ソルバーに渡すことができる定数

  • Variable: 最適化に使用する変数

Dimensionでの定数をVariableの変数の定義に使うことが可能

Parametersで使うことができる属性

Parametersタグで宣言した行列やベクトルには、

下記の属性を付けることができます。

正しく属性を付けることで、ソルバーの動きが安定化したり、

計算が高速化されます。

  • nonnegative: 非負

  • nonpositive: 非正

  • psd: Positive semi definite: 半正定値

  • nsd: Negative semi definite: 半負定値

  • symmetric: 対称行列

  • diagonal: 対角行列 (ちゃんとこれを設定すると速度が高速化される)

 

C言語ソルバーの使い方

使い方のメモを書いておきます。

コードの実行方法

ダウンロードしてきたcのコードを、

$ make

$ ./test_solver

とすればソルバーが実行されます。

 

test_solver.cの各パラメータの設定部分を変更すると、

任意のシステムでの最適化を実現できます。

 

最適化のデータ

ソルバーのコードでは、

下記の4つの構造体のデータをメモリに格納して、

最適化が実施されます。

下記の構造体はすべてsolver.hに定義されています。

  • Vars vars 最適化変数

  • Params params パラメータのデータ

  • Workspace work 最適化処理の中間変数

  • Settings settings 最適化設定変数

CVXGEN: Code Generation for Convex Optimization

 

ZERO_LIBRARY_MODE

CVXGENはprintfとsqrtを使うために、

stdio.hとmath.hをインクルードしていますが、

solver.hのZERO_LIBRARY_MODEのdefineをONにすると、

stdio.hとmath.hを利用しない状態で、

コンパイルすることができます。

しかし、printfが使えなくなるので、

処理結果などは表示されません。

最適化の収束判定

最適化の収束判定は、

work.converged == 1

で判定できます。

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

離散凸解析と最適化アルゴリズム (数理工学ライブラリー)

離散凸解析と最適化アルゴリズム (数理工学ライブラリー)