2

次の最適化問題をオクターブで解こうとしています

方式

最初の制約は、 A が半正定値であることです。S は、(xi,xj) が S にある場合に xi が xj に類似するようなデータ ポイントのセットであり、D は、(xi,xj) が D にある場合に xi と xj が類似しないようなデータ ポイントのセットです。上記の式は 2 つの個別の合計であり、2 番目の合計はネストされていないことに注意してください。また、xi と xj は長さ N の列ベクトルであると想定されます。

これは非線形最適化であるため、オクターブの非線形プログラム ソルバーである sqp を使用しようとしています。 問題は、最適化する関数を提供しただけでは、いくつかの小さなおもちゃのテストで、ヘッセ行列を見つけるための BFGS メソッド が失敗することです。このため、独自の Hessian 関数を提供しようとしましたが、この問題が発生しました

error: __qp__: operator *: nonconformant arguments (op1 is 2x2, op2 is 3x1)
error: called from:
error:   /usr/share/octave/3.6.3/m/optimization/qp.m at line 393, column 26
error:   /usr/share/octave/3.6.3/m/optimization/sqp.m at line 414, column 32

次の sqp 呼び出しを行うと、

[A, ~, Info] = sqp(initial_guess, {@toOpt, @CalculateGradient,@CalculateHessian},
[],[],0,[],maxiter);

対角要素のみを解き、すべての対角要素が >=0 になるように制約することで、A が正の半正定かつ対角であるという制約を単純化しました。initial_guess は、長さが N の 1 のベクトルです。

これは、ヘッセ行列であると私が信じているものを計算するための私のコードです

%Hessian = CalculateHessian(A)
%calculates the Hessian of the function we are optimizing as follows
%H(i,j) = (sumsq(D(:,i),1) * sumsq(D(:,j),1)) / (sum(A.*sumsq(D,1))^2)
%where D is a matrix of of differences between observations that are dissimilar, with one difference on each row
%and sumsq is the sum of the squares
%input A: the current guess for A
%output Hessian: The hessian of the function we are optimizing
function Hessian = CalculateHessian(A)
    global HessianNumerator; %this is a matrix with the numerator of H(i,j)
    global Dsum_of_squares; %the sum of the squares of the differences of each dimensions of the dissimilar observations

    if(iscolumn(A)) %if A is a column vector
        A = A'; %make it a row vector. necessary to prevent broadcasting
    endif

    if(~isempty(Dsum_of_squares)) %if disimilar constraints were provided   
        Hessian = HessianNumerator / (sum(A.*Dsum_of_squares)^2)
    else
        Hessian = HessianNumerator; %the hessian is a matrix of 0s
    endif

endfunction

Dsum_of_squares と HessianNumertor は

[dissimilarRow,dissimilarColumn] = find(D); %find which observations are dissimilar to each other
DissimilarDiffs = X(dissimilarRow,:) - X(dissimilarColumn,:); %take the difference between the dissimilar observations
Dsum_of_squares = sumsq(DissimilarDiffs,1);
HessianNumerator = Dsum_of_squares .* Dsum_of_squares'; %calculate the numerator of the Hessian. it is a constant value

X は、行ごとに 1 つの観測値を持つ M x N 行列です。

D は M x M の非類似度行列です。D(i,j) が 1 の場合、X の行 i は行 j とは異なります。それ以外の場合は 0。

エラーは次の領域のいずれかにあると思います (最も可能性が低いものから最も可能性が高いものへ)

  1. ヘッセ関数を導出するために使用した数学は間違っています。私が使用している式は、関数のコメントにあります。
  2. 数学の私の実装。
  3. sqp が必要とするヘッセ行列は、ウィキペディアのヘッセ行列ページで説明されているものとは異なります。

どんな助けでも大歓迎です。さらにコードを投稿する必要がある場合は、喜んで投稿します。現在、最適化を試行して解決するコードの量は約 160 行です。

コードが失敗する原因となる実行中のテスト ケースを次に示します。勾配関数を渡すだけで機能します。

X = [1 2 3; 
     4 5 6; 
     7 8 9; 
     10 11 12];
S = [0 1 1 0; 
     1 0 0 0; 
     1 0 0 0; 
     0 0 0 0]; %this means row 1 of X is similar to rows 2 and 3
D = [0 0 0 0; 
     0 0 0 0;
     0 0 0 1;
     0 0 1 0]; %this means row 3 of X is dissimilar to row 4
gml(X,S,D, 200); %200 is the maximum number of iterations for sqp to run
4

0 に答える 0