0

cvx

自分で試したわけじゃないけど,cvxは画像処理みたいに大きな問題には適してないらしい.

くそ時間がかかって,イマイチな答えが返ってくると言ってる人がいた.
又聞きだけど.
Advertisements
0

L2ノルムとL1ノルムの違い

CVXを使って,L1ノルムとL2ノルムの違いをみてみる.
もっと正確に言うと,L1ノルムでスパースな解が求まっているのかを確かめる.

  1. >> m=16;n=8;
  2. >> A=randn(m,n); b=randn(m,1);
    % L2 norm
    % Minimize |A*x-b|_2
    % subject to |x|_2
  3. >> cvx_begin
  4. >> variable x_l2(n);
  5. >> minimize( norm(A*x_l2-b,2)+norm(x_l2,2));
  6. >> cvx_end
    % L1 norm
    % Minimize |A*x-b|_2
    subject to |x|_1
  7. >> cvx_begin
  8. >> variable x_l1(n);
  9. >> minimize( norm(A*x_l1-b,2)+norm(x_l1,1));
  10. >> cvx_end

x_l2, x_l1に,それぞれ正則化項をL2ノルム,L1ノルムにした解が格納されているので比較.
>> [x_l2 x_l1]
ans =
-0.1598 -0.1088
-0.0488 -0.0000
0.0380 0.0000
0.1336 0.0000
0.3207 0.2636
-0.0513 -0.0000
0.3794 0.2774
-0.0616 -0.0028

という事で,L1ノルムによってスパースな解が求まっている事が分かる.

0

CVX: quickstart 5 An optimal trade-off curve

CVX: quickstart 5 An optimal trade-off curve

Minimize |Ax-b|_2+gamma|x|_1
% gamma is 10^{-2} to 10^{2}
gamma = logspace( -2, 2, 20 );
l2norm = zeros(size(gamma)); l1norm = zeros(size(gamma));
for k = 1:length(gamma),
cvx_begin
variable x(n);
minimize( norm(A*x-b)+gamma(k)*norm(x,1) );
cvx_end
l1norm(k) = norm(x,1);
l2norm(k) = norm(A*x-b);
end
plot( l1norm, l2norm );
xlabel( ’norm(x,1)’ );
ylabel( ’norm(A*x-b)’ );
結果は以下のようになった.
gammaの値が大きくなるほど正則化項であるL1ノルムの重みが大きくなるため,L1ノルムの値が小さくなって行くのに対し,データ項であるL2ノルムは徐々に値が大きくなっている.
gamma norm(x,1) norm(A*x-b)
—————————————
1.0000e-002 3.3796e+000 2.0355e+000
1.6238e-002 3.3658e+000 2.0357e+000
2.6367e-002 3.3433e+000 2.0362e+000
4.2813e-002 3.3068e+000 2.0374e+000
6.9519e-002 3.2472e+000 2.0408e+000
1.1288e-001 3.1498e+000 2.0497e+000
1.8330e-001 2.9878e+000 2.0737e+000
2.9764e-001 2.7617e+000 2.1280e+000
4.8329e-001 2.3445e+000 2.2924e+000
7.8476e-001 1.4082e+000 2.8895e+000
1.2743e+000 3.7699e-001 3.9509e+000
2.0691e+000 2.4222e-010 4.4813e+000
3.3598e+000 6.0414e-012 4.4813e+000
5.4556e+000 4.3404e-010 4.4813e+000
8.8587e+000 1.8987e-010 4.4813e+000
1.4384e+001 1.0509e-011 4.4813e+000
2.3357e+001 3.5492e-012 4.4813e+000
3.7927e+001 5.2746e-010 4.4813e+000
6.1585e+001 1.8693e-012 4.4813e+000
1.0000e+002 1.4417e-010 4.4813e+000
0

CVX: quickstart 3 Other norms and functions

CVX: quickstart 3 Other norms and functions

Chebyshevノルム(L∞ノルム)やL1ノルムの計算をMatLabのOptimization toolboxで行うにはlinprog関数を使うのだが,関数の引数がややこしい.それに比べると,CVXはnorm関数の引数を変更するだけなので,記述が簡単.
  1. Chebyshevノルム
    >> cvx_begin
    >> variable x_inf(n);
    >> minimize(norm(A*x_inf-b,Inf));
    >> cvx_end
  2. L1ノルム
    >> cvx_begin
    >> variable x_1(n);
    >> minimize(norm(A*x_1-b,1));
    >> cvx_end
  3. k Largestノルム
    Ax-bの中で絶対値が大きいk個の値を考慮するノルム.
    |Ax-b|lgst,k = |Ax-b|1+|Ax-b|2+ ・・・ + +|Ax-b|k
    >> k=5;
    >> cvx_begin
    >> variable x_k(n);
    >> minimize(norm_largest(A*x_k-b,k));
    >> cvx_end
  4. Huber罰則項
    φ(z)=|z|^2 |z|1
    >> cvx_begin
    >> variable x_huber(n);
    >> minimize(sum(huber(A*x_huber-b)));
    >> cvx_end
と,こんな感じでObjective functionやconstraintが複雑になってもCVXを使えば簡単に…という話のようだ.
0

CVX: quickstart 2 Bound-constrained Least squares

CVX: quickstart2 Bound-constrained Least squares

Least squaresに制約条件を追加する.今回は上界と下界を

minimize ||Ax-b||2
subject to l<=x<=u

  1. m = 16; n = 8;
  2. A = randn(m,n); b = randn(m,1);
  3. bnds = randn(n,2);
  4. l = min( bnds, [], 2 ); u = max( bnds, [], 2 );
  5. cvx_begin
  6. variable x(n);
  7. minimize( norm(A*x-b) );
  8. subject to
  9. x >= l;
  10. x <= u;
  11. cvx_end
本当にl<=x<=uとなっているか確認.
>> [l x u]
ans =
-2.1237 -0.1904 0.4494
-0.5046 -0.5046 0.1006
-1.2706 0.4633 0.8261
-0.3826 -0.3826 0.5362
0.6487 0.6487 0.8979
-0.1319 -0.1319 0.8257
-1.0149 -0.1472 -0.1472
-0.4711 0.1281 1.0078
制約なしLeast squaresで求めた解は
>> x_ls
x_ls =
0.1768
-0.6757
-0.7052
-0.7581
-0.2865
-0.6379
0.0581
-0.4439
となっており,確かに制約通りの解が求まっている事が分かる.
0

CVX: quickstart 1 Least squares

とゆーわけで,実際にCVXを触ってみる.examplesフォルダのquickstartをユーザガイドを見ながら実行していく.
CVX: quickstart1 Least squares
単純なLeast squares.これならx=A\b;と解いてもいけちゃう.
minimize ||Ax-b||2

  1. m = 16; n = 8;
  2. A = randn(m,n);
  3. b = randn(m,1);
  4. cvx_begin
  5. variable x(n);
  6. minimize( norm(A*x-b) );
  7. cvx_end

cvx_beginとcvx_endの間にConvex optimizationの定義や宣言をする.
全ての変数はobjective functionやconstraintsを定義する前に宣言しなければならない.
CVXの計算が終わると,以下の変数ができる.

  • cvx_optval: Objective functionの値
  • cvx_status: 計算結果の状態(Solved, Unbounded, Infeasible).
  • cvx_slvtol: solverによって得られた許容値.
  • cvx_slvitr: 解くのにかかったiterationの回数.

まー初回はこんなもん.単なるHello Worldみたいなもん.

0

CVX; Matlab Software for Disciplined Convex Programming

CVXのインストール @ Windows XP 32bit
Convex optimizationを習得すべく,CVXのインストール.

以下のページに行く.
http://cvxr.com/cvx/download

CVXのパッケージはzip形式で提供されてる(unix用にはtar.gzファイル).
zipファイルの中にはプログラムファイル,ユーザガイド,サンプル等が入ってる.
http://cvxr.com/cvx/cvx.zip

zipファイル内,もしくは以下のユーザガイドのAppendixに詳しいインストール方法が書いてある.
http://cvxr.com/cvx/cvx_usrguide.pdf

  1. zipファイルを解凍するとcvxというフォルダができるので,任意の場所に移動.ただし,MatLabのtoolboxフォルダに移動させてはダメと注意書きされている(このルールを破るとどうなるのかは知らない).
    ユーザガイドに従って,C:\Matlab\personalというフォルダを作り,そこにcvxフォルダを移動.
  2. MatLabを起動.
  3. cvxフォルダへ移動.
    cd C:\Matlab\personal\cvx
  4. セットアップ
    cvx_setup
  5. setupを行えばcvxフォルダがパスに追加されるけど,MatLabを再起動するとパス設定が消えてしまう?ので,cvxを使い続けたい場合はスタートアップにpathを保存する.
    具体的には,startup.mというファイルに以下のコマンドを書いて保存すれば,毎回MatLab起動時にコマンドが自動的に実行される.
    addpath(genpath(‘C:\Program Files\MATLAB\personal\cvx’));