3

我在 Math SE 上问过这个问题，但回答不是很令人满意。于是我又在这里问：

我有一个线性不等式和等式约束的优化问题：

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 工具箱中有什么东西可以让我在不进行平滑函数转换的情况下解决这个问题吗？

4

3 回答 3

2

这个问题可以使用混合整数规划求解器精确求解。我在对您的 Math SE 帖子的回答中解释了详细信息；总而言之，您需要为涉及 Heaviside 阶跃函数的目标函数中的每个项引入一个二元变量和一个线性不等式。

于 2011-01-10T16:15:36.330 回答
1

在 Matlab 中，您进行数值优化。这意味着您不必担心目标函数的分析形式。相反，您需要编写一个目标函数，该函数使用优化参数为x数据的每个值创建一个y-value，然后您可以将其与输入数据进行比较。

通过线性和非线性约束，您可以使用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和（或从文件中加载它），对（k×1数组）和线性等式约束的数组进行ydata初始猜测，这样（如果你有3个步骤），然后写locAeqAeq*loc==beqAeq[1 1 1]

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

这将估计步骤的位置。您可以添加不等式约束，而不是两个空括号，而 5 是因为我假设等式约束的计算结果为 5。

于 2011-01-10T12:36:15.487 回答
0

沿 X 的任何一个维度进行绝对最小化是一项简单的任务，可以在 O(i) 时间内找到。

1）选择一个Xj来修改（其他都是固定的）

2) 创建一个长度为 i 的列表，其中包含沿 Xj 的每个方程的切换位置，映射到 1 或 -1，具体取决于它在接近 +inf 时是减小还是增大。

3）按切换位置排序...从最小切换位置的0开始，加上或减去映射值。

4) 在您逐步浏览此列表时跟踪最小总和，将切换位置保持为映射到分数的最佳位置。

5) 在列表的最后，您的最佳切换位置成为您对 Xj 的新值。

从这里，您可以沿 X 的每个维度进行共轭最小化，重复直到您停止改进结果。这至少会找到一个局部最小值。

或者，您可以使用不需要渐变的罐装本地优化代码......例如Nelder Mead 下坡单纯形法。有可用于该任务的Matlab 库。

这两种方法都会给你局部最优。如果您真的需要更全局的解决方案，您可以研究模拟退火或遗传算法解决方案，它可能非常适合此类问题。

最后，如果你有一大笔钱要花（不确定这是免费的），我会查看Matlab 全局优化工具箱。

于 2011-01-10T08:33:57.000 回答