MyEnigma

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

凸最適化(Convex Optimization)の基礎

Convex Optimization

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. 最適化の計算が早い

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

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

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

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

 

例えば、内分法の場合、

大抵の凸最適化問題は、10-50回の繰り返し計算で

解けることが知られています。

 

関数の凸性の判定

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

評価関数の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は商用の最適化モデリングツールです。

 

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

 

cvxgen

cvxgenは、あるモデリング言語で記述した

凸最適化問題を高速に解くことができる

C言語のコードを生成できるWebツールです。

myenigma.hatenablog.com

 

JuMP

プログラミング言語Julia製のフリーの最適化モデリングツールです。

Juliaが高速な計算が可能な言語なので、

JuMPを使うと高速に最適化計算をすることができます。

また、非線形最適化にも対応しているのも便利です。

 

詳細は下記を参照ください。

myenigma.hatenablog.com

 

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

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

myenigma.hatenablog.com

 

FiOrdOs

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

MATLABライブラリです。

 

FORCES or (FORCES PRO)

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

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

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

 

凸最適化の応用例

線形計画法の応用例

下記の記事を参照ください。

myenigma.hatenablog.com

 

画像復元

下記のプレゼン資料にある通り、

ある画像の一部が欠けている時に、

凸最適化を使って隣接ピクセルの分散を最小化するようにすると、

欠けている画像部分を復元することができます。

H2O World - Consensus Optimization and Machine Learning - Stephen Boyd

 

例えば、下記のように一部の写真が文字で欠けている画像でも、

f:id:meison_amsl:20171022014112p:plain

下記のように、非常に美しく画像が復元できたり、

f:id:meison_amsl:20171022014153p:plain

下記のように80%の画像データが失われてる状態でも、

f:id:meison_amsl:20171022014400p:plain

下記のように復元できます。

f:id:meison_amsl:20171022014555p:plain

 

サポートベクターマシン

機械学習の技術で有名なサポートベクターマシンは、

凸最適化を使って、分類を実施します。

詳細は下記の記事を参照ください。

myenigma.hatenablog.com

 

線形MPC(モデル予測制御)

制御技術の一つである線形MPC(モデル予測制御)は

リアルタイムに凸最適化を解くことで、

制御を実施するアルゴリズムです。

詳細は下記を参照ください。

myenigma.hatenablog.com

 

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

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

Convex Optimization

Convex Optimization

英語の書籍ですが、

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

 

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

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

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

Convex Optimization

Convex Optimization

 

MyEnigma Supporters

もしこの記事が参考になり、

ブログをサポートしたいと思われた方は、

こちらからよろしくお願いします。

myenigma.hatenablog.com