目標函數只能被近似計算的優化

Question

我有一些圖算法依賴於中等數量的參數（比如說2-6），並且哪些並不總能成功找到他們想要的（他們想要「足夠好」 '解決已知困難的問題，如mincut/maxflow）。我還有一個非常大的圖表族，我想使用這些算法。

我目前的目標是找到給定算法最常成功的參數值。不幸的是，我知道如何計算'成功'的唯一方法就是從我的大家庭中獲取一張圖並實際運行算法。這有兩個問題：它在計算上很昂貴，它只給出了我的真實目標函數的近似值，算法成功的圖的真實百分比。

第一個不是世界的盡頭; Nelder-Mead或類似的東西可以工作。有沒有這種算法的變種可以在我的情況下工作？我期待成功的概率遠遠從0或1.

Answer 1

（對不起，切換電腦，並且沒有編輯的能力 - 這是原始海報，爲了迴應Shahbaz，我犯了一個錯誤，我的意思是說最稀疏這是NP完成的，我正在處理的實際問題往往是比較混亂，我只是想說乾淨的解決方案沒有希望，但最終卻意外地說出了相反的問題。