3

Math SE でこの質問をしましたが、回答はあまり満足のいくものではありません。だから私はここでもう一度尋ねました：

線形不等式と等式の制約に関する最適化の問題があります。

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 ツールボックスにありますか?

4

3 に答える 3

2

この問題は、混合整数計画法ソルバーを使用して正確に解くことができます。Math SE の投稿への回答で詳細を説明します。要約すると、ヘヴィサイド ステップ関数を含む目的関数の各項に対してバイナリ変数と線形不等式を導入する必要があります。

于 2011-01-10T16:15:36.330 に答える
1

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

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

何を最適化したいのか完全にはわかりませんが (申し訳ありませんが、少し早いです)、例として、x 値xdataを持つベクトルと 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);

この関数をobjFun.mMatlab パスに保存します。次に、定義xdataして(またはファイルから読み込み)、 (k 行 1 列の配列)ydataの初期推定を行い、( 3 つのステップがある場合は です) のような線形等式制約の配列を作成し、次のように記述します。locAeqAeq*loc==beqAeq[1 1 1]

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

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

于 2011-01-10T12:36:15.487 に答える
0

X の任意の 1 つの次元に沿った絶対最小化は、O(i) 時間で見られる単純なタスクです。

1) 変更する Xj を選択します (他のすべては固定されています)。

2) Xj に沿った各方程式の切り替え位置を含む長さ i のリストを作成し、+inf に近づくにつれて減少するか増加するかに応じて、1 または -1 にマッピングします。

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

4) このリストをステップごとに最小合計を追跡し、切り替え位置をスコアに最適なマップとして維持します。

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

ここから、X の各次元に沿って共役最小化を実行し、結果の改善が止まるまで繰り返します。それは少なくとも極小値を見つけるでしょう。

または、勾配を必要としない缶詰のローカル最適化コードを使用することもできます...たとえば、Nelder Mead ダウンヒル シンプレックスメソッドです。そのタスクに利用できる Matlab ライブラリがあります。

これらのアプローチは両方とも、局所的な最適値を提供します。よりグローバルなソリューションが本当に必要な場合は、シミュレーテッド アニーリングまたは遺伝的アルゴリズム ソリューションを調べることができます。これは、おそらくこの種の問題で非常にうまく機能します。

最後に、使うお金が山ほどある場合 (これが無料かどうかわからない場合)、Matlab Global Optimizationツールボックスを確認します。

于 2011-01-10T08:33:57.000 に答える