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

MyEnigma

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

凸最適化(Convex Optimization)の基礎

凸解析と最適化理論 (数理情報科学シリーズ)

凸解析と最適化理論 (数理情報科学シリーズ)

目次

はじめに

先日、最適化技術の概要について説明しましたが、

myenigma.hatenablog.com

今回は、最適化技術の一つである凸最適化(Convex Optimization)の

基礎について説明したいと思います。

 

凸最適化とは?

凸最適化は下記のような式における最適化のことを指します。

f:id:meison_amsl:20161204043207p:plain

上記の式において、

コスト関数のfと不等式制約のgiはすべて凸関数である必要があります。

 

ちなみに、先日紹介した線形計画法や

myenigma.hatenablog.com

二次計画法も

myenigma.hatenablog.com

凸最適化の特殊系の一つです。

 

また、これら以外にも、

下記の図のような、状態量が連続値ではなく、

不連続値(整数値)などで与えられる

整数線形計画問題もあります。

f:id:meison_amsl:20161203093532p:plain

 

凸最適化の専門用語

unbounded

コスト関数を小さくしようとした時に、

無限にコスト関数を小さく出来る場合のこと

infeasible

与えられた制約条件を満たす解が一つも無いこと

active, inactive

不等式条件において、

fi(x)=ciとなるxが存在している場合、

その不等式条件はactiveとなり、

存在しない場合はinactiveとなる。

redundunt

ある制約条件が、別の制約条件を含んでいる状態のこと

 

凸集合と凸関数

前述の最適化の式において、

その最適化の問題が、

凸最適化問題であるためには、

下記の3つ条件が必要です。

  • 等式制約から得られる状態変数zが凸集合である

  • コスト関数fが凸関数である

  • 不等式制約giが凸関数である

 

凸集合と凸関数の概要を下記で説明します。

 

Convex Set (凸集合)

Convex Setは、

下記の図のように、ある集合の任意の二点を選び、

その弦がすべて集合に含まれるような、

集合のことを指します。

f:id:meison_amsl:20161101131437p:plain

 

一方、下記のような集合は

弦の一部が集合に含まれない二点を選ぶことができるので、

Convex Setではありません。

f:id:meison_amsl:20161101135546p:plain

 

代表的な凸集合としては、下記があります。

  • アフィン空間

  • 超平面(Hyperplanes)と、超平面で区切られた領域(halfspaces)

  • 多面体(Polyhedra)や多胞体(Polytopes)

  • ベクトルノルム

  • 楕円(Ellipsoid)

 

また、上記の凸集合に関して、

凸集合の交点を結んだ集合(Intersection)や、

f:id:meison_amsl:20161204044943p:plain

凸集合の外部を覆った集合(Convex Hull)は、

f:id:meison_amsl:20161204045128p:plain

凸集合になります。

しかし、一つ注意点として、

凸集合同士の和集合(Union)は凸集合ではなくります。

f:id:meison_amsl:20161204045337p:plain

 

Convex function(凸関数)

入力に対して、その出力が凸集合になる関数を、

凸関数といいます。

 

代表的な凸関数としては、

下記のようなものがあります。

  • 線形(アフィン) ax+b

  • Exponential eax

  • 乗数 xa

  • 絶対値の乗数 |x|^a

  • 対数関数 log x

  • エントロピー -xlogx

  • ベクトルノルム ||x||p

  • 行列ノルム

  • 正の重み付き足し算

  • アフィン関数の足し算

 

凸最適化の利点

上記の凸最適化には、通常の最適化とは異なる利点があります。

1. 大域的な最適値を得ることができる。

通常の最適化問題では、

一般的に初期値から勾配情報を使って最適化を実施しますが、

この方法の場合、局所最適値にとどまってしまうことがあります。

しかし、

凸最適化の場合、目的の評価関数の凸性が担保されているため、

大域的な最適値を得ることができます。

2. 最適化の計算が早い

凸最適化の場合、内分法やアクティブセット法といった、

凸最適化特有の最適化技術を使うことにより、

汎用的な最適化手法と比べて、大規模な問題に対しても、

高速に最適化を実行することができます。

 

関数の凸性の判定

一般的に、ある評価関数が凸関数であるかは、

評価関数のHessianの値がすべての値に対して、半正定である必要があります。

別の言い方をすると、評価関数V(θ)に対して、

0<λ<1を満たす任意のλに対して、下記が成り立てば、

V(θ)は凸関数であるといえます。

f:id:meison_amsl:20161117162311p:plain

 

二次計画法や線形計画法は、

制約条件が線形である場合、凸最適問題であるといえます。

 

制約付き最適化の判定法(KKT条件)

凸最適化のような、

制約付き最適化問題の最適化を判定する条件としては、

カルーシュ・クーン・タッカー条件(KKT条件)

がしばしば使われます。

このKKT条件は、

等式条件を入れたラグランジュの未定乗数法に、

不等式制約を入れたものだと考えることもできます。

myenigma.hatenablog.com

    

凸最適化用ツール

凸最適化には、

様々な環境で動作するツールがすでに提供されています。

最適化モデリングツール

凸最適化を実現したい場合、

線形計画法や二次計画法の標準形で表される問題に関しては、

後述するソルバーをそのまま利用することで凸最適化問題を解くことができます。

(それぞれの標準形に関しては上記のリンク先を参照下さい)

 

しかし、自分が解きたい問題が標準形とは違う形式の場合、

自分でなんとか標準形の形にできるように

最適化問題を変形する必要があるのですが、

この変換を自動的に実行してくれるのが最適化モデリングツールです。

つまり、標準形ではない形の評価関数や制約条件を記述すると、

自動的にソルバーで解けるように式変換をし、最適化を実行してくれるのです。

(もちろんどんな問題でもとけるわけではありませんが)

 

代表的な最適化モデリングツールは下記の通りです。

CVXPY

CVXPYはPython製の最適化モデリングツールです。

Welcome to CVXPY — CVXPY 0.4.8 documentation

オープンソースで開発されており、フリーで利用することができます。

 

詳しいCVXPYの使い方に関しては、下記の使用を参照下さい。

myenigma.hatenablog.com

 

CVX

CVXはMATLAB上で動作する凸最適化モデリングツールです。

CVX: Matlab Software for Disciplined Convex Programming | CVX Research, Inc.

フリーのソルバーを使う場合はCVXも無料で利用できます。

 

詳しいCVXの使い方に関しては、下記を参照下さい。

myenigma.hatenablog.com

 

YALMIP

YALMIPもMATLAB上で動作するフリーの最適化モデリングツールです。

YALMIP

 

先程のCVXは凸最適化のみ利用できますが、

YALMIPの場合はその他の汎用的な最適化問題にも利用可能です。

 

AMPL

AMPLは商用の最適化モデリングツールです。

 

非常に広い範囲の最適化問題や、ソルバーに対応しています。

GAMS

GAMSも商用の最適化モデリングツールです。

非常に多くのソルバーや、最適化問題に対応しています。

 

PC向け凸最適化ソルバー

下記は凸最適化ソルバーです。

自分の解きたい問題が、

線形計画法や二次計画法の標準形で簡単に表すことが出来る場合は、

下記のソルバーを単体で使うと便利です。

 

ちなみに、前述のモデリングツールも、

下記のソルバーを内部で使っています。

 

cvxopt

cvxoptはPython製のフリーの凸最適化ソルバーです。

 

cvxoptの詳しい使い方は下記を参照下さい。

myenigma.hatenablog.com

 

Ipopt

IpoptはC++で書かれた大規模システム用の最適化ソルバーです。

 

IpoptはC++だけでなく、MATLABやJava, R, Fortran, Python, C#などの

インターフェイスが準備されており、それらの言語からも利用可能です。

 

SeDuMi

SeDuMiはMATLABやOctaveから利用可能なフリーなソルバーです。

SDPT3

SDPT3もMATLAB上で利用可能なフリーのソルバーです。

GPLライセンスで公開されています。

 

IBM CPLEX

CPLEXはIBMが開発、販売している商用ソルバーです。

オペレーションズ・リサーチなどの分野ではかなり広く利用されているようです。

 

Gurobi

Gurobiも商用ソルバーの一つです。

www.gurobi.com

前述のAMPLとの連携や、Pythonインターフェイスの充実などの特徴があります。

 

MOSEK

MOSELも商用ソルバーの一つです。

二次凸問題を非常に高速に解くことができる特徴ががあります。

 

組み込み用凸最適化ソルバー

前述のソルバーは、ほとんどPC上で動くことを仮定しており、

組み込みシステムや、高速で最適化問題を解きたい場合には、

あまり適していません。

 

そこで下記は、組み込みに利用できるソルバーや、

組み込み用のコードを自動生成できるツールになります。

qpOASES

qpOASESはフリーのC++ソルバーです。

qpOASES

モデル予測制御のような用途において、

高速に計算可能な最適化を実現することができます。

ライセンスはLGPLです。

 

OOQP

OOQPは二次計画法を解くための

オブジェクト指向で書かれたC++ライブラリです。

 

ECOS

ECOSはCで書かれたオープンソースのソルバーです。

github.com

PythonやMATLABのインターフェイスも準備されています。

 

CVXGEN

CVXGENは比較的小規模の二次形式問題を解くための、

Cコードを自動生成することができるモデリングツールです。

CVXGEN: Code Generation for Convex Optimization

最適化問題を非常に高速に解くことが可能になります。

 

FiOrdOs

FiOrdOsは、二次計画法を解くためのCコードを生成することができる

MATLABライブラリです。

 

FORCES or (FORCES PRO)

FORCESは内分法による最適化のコードを生成することができるMATLABライブラリです。

モデル予測制御などにおいて、高速に問題を解くことができるコードを生成してくれます。

FORCES PROという商用ライセンスも販売しています。

 

より詳しく凸最適化を学びたい人は

こちらの資料がおすすめです。

Convex Optimization

Convex Optimization

英語の書籍ですが、

世界的に凸最適化のデファクトスタンダードの教科書として扱われています。

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

凸解析と最適化理論 (数理情報科学シリーズ)

凸解析と最適化理論 (数理情報科学シリーズ)

Convex Optimization

Convex Optimization