ステップ関数を使用した目的関数の最適化

Question

数学SEではthis questionに質問しましたが、応答はそれほど満足できるものではありません。だから私はここで再び尋ねた：私は線形不等式で最適化問題を持っている

をし、等式制約：

A*x<=b 
Aeq*x=beq 

問題は、目的関数はヘビサイドのステップ関数の級数の和で構成されていることである、

ここでの目的関数のための擬似コードです：私が得た

function f(k, c, x) 
    ffunction =0; 
    for i=0;i<k.row.length;i++ 
    smallF=0 
    for j=0; j<k.column.length; j++ 
     smallF+= k.row[i]*k.column[j]*x[j]+c[j] 
    end 
    ffunction += u(smallF) 
    end 
f=ffunction 
end 


function u(x) 
    if(x>0) 
    return 1 
    else 
    return 0 
    end 
end 

提案は、ステップ関数を近似することですこの目的のために非線形最適化を使用する。しかし、MATLABツールボックスには、円滑な関数変換を行わずにこれを解決できるものがありますか？

Answer 1

Xの任意の1つの次元に沿った絶対最小化は、O（i）時間で見出すことができる単純なタスクです。

1）場合に応じて1または-1のいずれかにマッピングされたiはXjの沿った各方程式のスイッチング位置を含んだ長さのリストを作成する）（他のすべてが固定されている）

2を変更するXjのピック+ infに近づくにつれて増加または減少します。

3）最小スイッチング位置で0から始まり、マッピングされた値を加算または減算します。

4）このリストをステップ実行する際に最小の合計を追跡し、最適なスイッチング位置をスコアにマッピングします。

5）リストの最後に、最適なスイッチング位置がXjの新しい値になります。

ここから、Xの各次元に沿ってコンジュゲート最小化を行い、結果の改善を止めるまで繰り返すことができます。それは少なくとも地方の最小値を見つけるだろう。また

---

、インスタンスのために... Nelder Mead downhill simplex方法をグラデーションを必要としない缶詰局所最適化コードを使用することができます。そのタスクにはMatlab libraries availableがあります。

---

どちらの方法でもローカル最適化が得られます。よりグローバルなソリューションが本当に必要な場合は、Simulated AnnealingまたはGenetic Algorithmソリューションを調べることができます。これはおそらくこのタイプの問題ではうまくいくでしょう。あなたは（これは自由であることを確認していない）を過ごすためにお金の山を持っている場合

---

最後に、私はMatlab Global Optimizationツールボックスにチェックインしたいです。

Answer 2

Matlabでは、数値の最適化を行います。つまり、目的関数の分析形式について心配する必要はありません。代わりに、最適化パラメータを使用して、データのすべての値xに対してy値を作成する目的関数を作成し、入力データと比較する必要があります。

線形制約と非線形制約を使用すると、FMINCONを使用して問題を解決できます。

私はあなたが最適化したいことを理解していません（申し訳ありませんが、少し早いですが）。例のために、x値がxdataのvectory 「階段関数」に適合させるy値がydataである。そこにはいくつのステップがあるのか​​分かっていますが、どこに配置されているのか分かりません。また、ステップ位置の合計は5（線形等価制約）でなければならないことがわかります。

目的関数を書くことから始めましょう。出力はできるだけ0に近づけたいと考えています。これは、残差の二乗和（すなわち、実y値と推定y値との間の差）であり得る。私の便宜のために、ステップの位置は線形方程式で定義しませんが、代わりに直接設定します。

function out = objFun(loc,xdata,ydata) 
%#OBJFUN calculates the squared sum of residuals for a stair-step approximation to ydata 
%# The stair-step locations are defined in the vector loc 

%# create the stairs. Make sure xdata is n-by-1, and loc is 1-by-k 
%# bsxfun creates an n-by-k array with 1's in column k wherever x>loc(k) 
%# sum sums up the rows 
yhat = sum(bsxfun(@gt,xdata(:),loc(:)'),2); %'# SO formatting 

%# sum of squares of the residuals 
out = sum((ydata(:)-yhat).^2); 

MatlabパスにobjFun.mという名前で保存してください。次に、loc（k行1列）の初期推測を行い、（Aeqは3の場合は[1 1 1]）のような線形等価制約のための配列Aeqをxdataとydataと定義する（またはファイルからロードする）ステップ）、および書き込み

locEst = fmincon(@(u)objFun(u,xdata,ydata),locInitialGuess,[],[],Aeq,5); 

これは、ステップの位置を推定します。 2つの空白のかっこの代わりに不等式制約を追加することができます。平等制約が5と評価されたためです。

Answer 3

この問題は、整数混合プログラミングソルバーを使用してと正確に一致します。あなたの数学SEの投稿に私のanswerの詳細を説明します。要約すると、Heavisideステップ関数を含む目的関数内の各項に対して、2項変数と1次の不等式を導入する必要があります。