- 線形不等式制約付きの最適化は「constrOptim()」を使用してできますが、制約条件も非線型の最適化を実行する必要が生じましたので、情報を求めたいと考えています（byどうむ）。
- 参考：数理計画法
- 問題は株式ポートフォリオの最適化（リバランス）です。
- すでに市販の「Generalized Reduced Gradient」手法を使用したDLLでSPlus6上では実現した実績はあります（前の会社でです、今はSPlusも当該DLLもありません）。
- 銘柄数は最大3500銘柄までできればかなりハッピー（できればというのはメモリーなどのハード条件をクリアし、かつスピードも耐えられるもの。まぁ、問題によりますが...）。
- 非線型の制約条件というのはポートフォリオのリスクです（たとえばトラッキングエラー(TE)3.00%以下とか）。
- ポートフォリオのリバランスを想定しています。目的関数はポートフォリオの期待リターンでリバランスに伴うコスト控除後のリターンです。コストはリバランスに伴う個別銘柄の取引量の非線型関数です。なので目的関数も非線型となります。
- 現在私が認識しているRにおける最適化の関数は以下のとおりです（説明に温度差があって申し訳ございません）。追記・修正など、どしどしお願いいたします。
- optimize()／optimise()
- １変数関数の最小化・最大化
- 変数のレンジを指定可能
- 微係数の関数（グラディエント）はあたえられない
- optim()
- ２変数以上の関数の最適化
- 変数のレンジを指定可能
- 微係数の関数（グラディエント）を与えることができる
- nlm()
- simplex()
- solve.QP()
- 二次計画法
- 目的関数が二次形式、線型不等式制約条件を指定可能(二次計画法の定義なので、あたりまえですが。。。)
- constrOptim()
- ちょっと違いますが「gnls()」とか
- Ｓでは「nlreg(b)」なんてのもありましたが。。。（Ｒでは→）
- もしＲで制約条件に非線形の関数を与えられるようなものが存在しないのであれば「donlp2」というSQP(逐次二次計画法(と認識してますが...))のコードを見つけましたので、これを使用して（いえ、わざわざこれを使用してなくてもいいのですが）Ｒで動く最適化のコードを作成しようと考えております。
- もっとも、スピードを求めるので、今回のポートフォリオのリバランスという要件に関しては、目的関数などは最終的にＣ言語で書いてしまうつもりです。が、その前段階として「solve.QP()」や「constrOptim()」のように、汎用的に使える関数を作成しておき、検証用に使いたいというのが目的です。
- ＳＱＰにするとスピードも改善するのでは？という、期待もあったりします（GRG methodと比べて）。
- あるいはもっとほかの使用できるFrotranやCのコードがあればご紹介をお願いいたします。
（コメントなどはこちらにお願いいたします）
- 先日学生とゼミ中に次のような汎用的方法のことを知りました。f(x1,...,xn) を目的関数, g(x1,...,xn)>=0 が (非線形)不等式制約条件とします。G(x1,...,xn,y)=g(x1,...,xn,y)+y^2 と置けば、制約条件は等式 G=0 に形式的に変換できます。あとは定番の Lagrange 未定乗数法を使う、というものです。つまり、
F(x1,...,xn,y,c)=f(x1,...,xn)+cG(x1,...,xn,y)
を(制約なしの)目的関数にとり最適化を行なう、というものです。(非線形)不等式制約条件が複数でも同じように処理できます。感心しましたが、実際の有用性は分かりません。あまり知られていない(?)ようなので、それほどのことはない？
- おそらく先刻御承知とは思いますが、netlib やそこからたどれる
NEOS にはそれらしいソフトがたくさんありますね。使い勝手は？
- 早速のRESありがとうございます。このNEOSは存在は知っておりましたが、ちらっとみてみたところ、使えそうなルーティーンは有料であったような先入観があって、今回の件で深くはチェックしなかったのですが、可能性を求めて行けるところまで行ってみました。（byどうむ）
- 上記ウエブサイトのTREEのうちContinuous＞Constrainted＞Nonlinearly Constraintedをたどりました。
- その下にA.Sequential Quadratic Programming/B.Augmented Lagrangian Methods/C.Reduced-Gradient Methods/D.Feasible Sequential Quadratic Programming/E.Notes and References、がありました。
- Sequential Quadratic Programming：で、ここをみると代表的なものとして1.NPSOL、2.NLPQL、3.OPSYC、4.OPTIMA、5.MATLAB、6.SQP、というパッケージがあるとのことでした。
- NPSOLはLSSOLというルーティーンとあわせて$4,000(涙)。問題が大きくなればMINOSを使うべきとのことでこのMINOSも有料-$5,000(涙涙)
- NLPQLはここにリンクされ、これらはIMSLに実装されているとのこと。明らかに有料。
- OPSYCはリンクなし（Googleで調べてみましょう）
- OPTIMAリンク先からたどれません。Googleでもヒットしませんね。
- MATLABはあきらかに有料
- ハアハア、疲れてきました。SQPに望みを。。。
- SQPはPowellの逐次二次計画法を使用しているとのこと。おお、望みが。。。で、ここにリンクされProduct Priceとか、ありますね。
- まだ未確認のものもたくさんあります、が、私の↑この理解間違っておりますでしょうか？ちゃんとしたRESになっておりますでしょうか？ご指導よろしくお願いいたしますm(__)m
- 「donlp2」はたしかこの「netlib」からたどりました。でIMSLのJAVA版（JMSL）はこの「donlp2」をベースにしているとマニュアルに書いてありました。もちろん修正はされているのでしょうが。で、このJMSLを評価用で使用したのですが遅い。JVM上で動いているからでしょうか。いえ、そうにちがいありません。そうでなければ「donlp2」自体が遅いということになってしまいます...
- r-help 記事にあった、非線形不等式制約を形式的に線形不等式制約に変える方法(これもアイデアはともかく実用性は？) --
問題 f(x) を 制約 g(x) >= 0 下で最適化
方法 "slack (たるみ)変数" z 、ラグランジュ未定乗数 y を用い
F(x,y,z) = f(x) - y * (g(x) - z) を制約 z >= 0 下で最適化
- NEOS に紹介されているソフトが有料ソフトとは知りませんでした。有料でも使えれば価値はあるものの、実際購入して使ってみないと、様子が分からないところが困る点。私が R や linux を使い続けている理由も、ただだからという消極的な理由ではなく、購入してみたものの結局使えない、使い勝手が悪い、情報もお粗末ということが多かったからです。 --
- こちらの情報も貴重な情報だと思います。後でこのページを見られた方の、参考になるかもしれませんから。（byどうむ）
- constrOptim 関数で使われている(らしい？)アルゴリズムも汎用性があります(?constrOptim で参考文献)。つまり領域外や、領域境界に近付くに従い、増加する関数 g を目的関数 f に加えておいて、f+g を最小化する。繰返しにつれて g を適応的に変更するというもの(らしい？)です。非線形不等式制約の形によっては使える可能性あり。 --
- 調査してみます。で、少し調べてみました。（byどうむ）--
- 制約つき問題の最適化法（非線型）として以下のようなものがあるようです。（出典／藤田・今野・田邊：最適化法・岩波講座・応用数学：方法７／坂和：数理計画法の基礎：森北出版）
- 障壁関数法
不等式制約のみの場合で障壁関数を
Bk≡f(x)-ρk(Σlog(gi(x)))
と定義して、制約なし問題として最適化する方法。
xが許容範囲内の内側から境界に近づくと第２項が大きくなって、障壁の役割を果たしている。
許容範囲の内側から近づくので内点法とも呼ぶそうです。
- 罰金関数法
罰金関数を
Pk(x)=f(x)+ρ（Σ(gi(x))^2+Σ(hi(x))^2）
と、定義。外点法とも。
- 乗数法
上記二つはρの選択の善し悪しによって収束範囲と収束速度が左右される。
反復が進行するにつれ最適化するべき拡大関数が悪条件になり数値的に解きにくくなる。
これらの欠点を修正した方法として乗数法。
拡大Lagrange関数を
Lρ(x,λ)≡L(x,λ)+ρΣ(gi(x))^2
と定義。不等式制約がある場合は「slack」変数を導入
- 厳密罰金関数法
えと、も〜省略。
- 上記の方法は制約つき最適化問題を、制約なし問題に帰着させて解く方法で、拡大関数法と、呼ばれているそうです。「constrOptim」はまさに「障壁関数法」ですね（違いますか？）。
- で、「最適化法（岩波講座・応用数学）」によると、これら拡大関数法には
- 罰金パラメータρの値に客観的設定方法がなく収束範囲と収束速度がこのパラメータに左右される。
- 収束が一般に遅い。
- その他
- などの欠点があると、散々な、言われようです。で、制約を直接的に取り扱う方法として
- Newton法
- 修正Newton法
- 逐次二次計画法
- というのが、あるそうです。--とても勉強になりました(^ー^)ノ。
- GDR (Generalized Reduced Gradient) 法は Excel に組み込まれているらしいですね。r-help でもこれで解けた問題が otpim で解けないと文句(?)を言っている人がいました。手法的には optim の矩形制約問題が扱える L-BFGS-B 法に近いとのコメントがありました。こうしたソフトには原理だけではない、実際的な工夫が凝らされているのでしょうね。商用の GDR2 では一般的な形の非線形不等式制約が使えるのでしょうか。 --
- 上のGDRはGRGのことでしょうね。エクセルに組み込まれているソルバーは確かにGRGだったと記憶しています。MSDNのサポート技術情報検索（英語版）でSOLVERで検索すると「How to Find Resources on Microsoft Excel Solver(146606)」というページがみつかるはずです。そちらに'Solver Uses Generalized Reduced Gradient Algorithm'とありました。また、そこから「Frontline Systems, Inc.」という会社のウエブサイトへリンクされますがそちらに詳しく書いてあるようです。こちらにはWIN版のいろいろなソルバーがあります（もちろんライセンス料取られます）。評価版もダウンロードできますし、ドキュメントもそろっていますね。（byどうむ）--
- それと、エクセルのソルバーはGRGですので目的関数・制約条件（不等式含む）とも滑らかな非線型関数であれば解けるはず（言い過ぎか。解けるかどうかはわかりませんね。問題の設定ができるということです。）ですが、「optim()」は制約条件にChanging Variablesの短形制約しか指定できませんので、「r-help」に書かれた方がそういう意味で書かれているかどうかわかりませんが、エクセルのソルバーでは設定できる問題が「optim()」では設定できないということはあると思います。ただエクセルのソルバーは変数を200までしか設定できませんし、おそい！（←あっ、わたくしの業務では使えないってことですね）（byどうむ）--
- <<補足>>上の”おそい！”ですがエクセルではセル上の値の読み書きがとても遅いのでそれが原因では？と推測しています。GRG2の評価をしたわけではありませぬ（byどうむ）--
- donlp2のライセンスはどんなものでしょうか？LGPLで、OPT++ というものがありますよ(solverではなくライブラリですが)。 -- さとう
- 情報ありがとうございます！さっそくOPT++でGoogleしました。最初にヒットしたのが「Opt++ is a tool for Database Query Optimization that uses the Object-Oriented ･･･」ときたので、どきっ、としましたが、ありました！「An Object-Oriented Nonlinear Optimization Library」ですね。（byどうむ）--
- 「donlp2」のライセンスはダウンロードしてきたドキュメントを探してみたのですが明示的なものはみつからず。このページに"DONLP2 can be used freely for any kind of research purposes. For-profit-use requires licensing from P. Spellucci."とありました。（byどうむ）--
- 確認が大変遅くなりましたが、OPT++あっさりLINUXでコンパイルできました。OPT++についていたサンプルも問題なく動いているようです。サンプルを見た限りではライブラリへのインターフェースもシンプルそうです。WINDOWS版で動かすことを目標にしてますが、とりあえずはLINUXのＲ用のOPT++のインターフェースを作って、このページにさらしてみようと思います。（byどうむ）--
- donlp2のANSI CバージョンをRに組み込んでみました。まだパッケージの体を成していないので公開はできませんが(来週あたりには完成予定)、動作状況に関心のある方は http://arumat.net/blog/programming/r/ をご覧ください。 -- tam
- http://arumat.net/Rdonlp2/ にパッケージを置きました。ここはあまり覗かないのでご意見ご要望がありましたらメールなどで頂けたら幸いです -- tam
- おや、数年ぶりにここを覗いてみたら、Rdonlp2なるものを作られた方が．そして公開までされている！すばらしい！！私はといえば、作ってRに実装したものの、別にプログラミング？の専門家でもないので、恥ずかしくて紹介することもなく・・・、普通にリサーチとしての業務で使っておりました・・・．というか「donlp2」でぐぐるとここがTOPになってたのでクリックしてみただけなんですが・・・．【Rdonlp2】の発展を祈っております．そしてｔａｍさまのサイトは大変参考になりますね． -- どうむ
![[RjpWiki]](image/../Rlogo.png "[RjpWiki]")
