目标函数只能被近似计算的优化

Question

我有一些图算法依赖于中等数量的参数（比如说2-6），并且哪些并不总能成功找到他们想要的（他们想要“足够好” '解决已知困难的问题，如mincut/maxflow）。我还有一个非常大的图表族，我想使用这些算法。

我目前的目标是找到给定算法最常成功的参数值。不幸的是，我知道如何计算'成功'的唯一方法就是从我的大家庭中获取一张图并实际运行算法。这有两个问题：它在计算上很昂贵，它只给出了我的真实目标函数的近似值，算法成功的图的真实百分比。

第一个不是世界的尽头; Nelder-Mead或类似的东西可以工作。有没有这种算法的变种可以在我的情况下工作？我期待成功的概率远远从0或1.

Answer 1

（对不起，切换电脑，并且没有编辑的能力 - 这是原始海报，为了回应Shahbaz，我犯了一个错误，我的意思是说最稀疏这是NP完成的，我正在处理的实际问题往往是比较混乱，我只是想说干净的解决方案没有希望，但最终却意外地说出了相反的问题。