具有階梯函數的目標函數的優化

我在Math SE上問過this question，但答案並不令人滿意。於是我又在這裏問：具有階梯函數的目標函數的優化

我有線性不等式的優化問題和平等約束：

A*x<=b 
Aeq*x=beq

的問題是目標函數是由一系列的Heaviside階梯函數的總和，

這裏的目標函數的僞代碼：

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工具箱中有沒有什麼可以讓我解決這個問題而不做順利的功能轉換？

來源

2011-01-10 Graviton

* *優化工具箱* fmincon * http://www.mathworks.com/help/toolbox/optim/ug/fmincon.html可能會爲您的任務提供一些幫助。 – zellus 2011-01-10 07:51:31

絕對最小化沿X的任何一個維度是一個簡單的任務，可以在O（i）時間找到。

1）挑XJ修改（所有其他被固定）

2）創建長度包含I用於沿着XJ每個方程的切換位置，映射到1或-1取決於如果它的列表隨着你接近+ inf而減少或增加。

3）按切換位置進行排序...在最小切換位置以0開始，並添加或減去映射值。

4）當您逐步瀏覽此列表時，追蹤最小總和，將切換位置保持爲最佳映射到分數。 5）在列表末尾，最佳切換位置將成爲Xj的新值。

從這裏，你可以沿X的每個維度做共軛最小化，重複直到你停止改進結果。那至少會找到當地的最低限度。

或者，您可以使用罐裝局部優化的代碼，不需要梯度...例如在Nelder Mead downhill simplex方法。該任務有Matlab libraries available。

這兩種方法都會給你當地的最佳狀態。如果你真的需要更全面的解決方案，你可以看看Simulated Annealing或遺傳算法解決方案，這可能會很好地解決這類問題。

最後，如果你有一堆的錢，花（不知道這是免費的），我檢查到Matlab Global Optimization工具箱。

來源

2011-01-10 08:33:57 tbischel

在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.m保存在Matlab路徑中。然後，您定義xdata和ydata（或從文件加載它），對loc（k乘1陣列）做出初始猜測，並且對於線性相等約束使用數組Aeq，使得Aeq*loc==beq（Aeq爲[1 1 1]，如果您有3步驟），並寫入

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

這將估計步驟的位置。而不是兩個空括號可以添加不等式約束，而5是因爲我認爲等於約束條件的計算結果爲5.

來源

2011-01-10 12:36:15 Jonas

使用混合整數規劃解算器可以解決正確。我將我的answer中的詳細信息解釋給您的Math SE文章;總結一下，您需要爲涉及Heaviside階躍函數的目標函數中的每個項引入二元變量和線性不等式。

來源

2011-01-10 16:15:36 Fanfan

具有階梯函數的目標函數的優化

回答

相關問題