無導數優化方法及應用

高靜 曹健

摘 要：信息時代的優化問題多以大數據為研究基礎，其模型通常規模龐大且函數不具有典型性。傳統最優化方法已無法省時高效的求解此類問題，于是無導數優化方法脫穎而出。本文介紹了無導數優化的概念、國內外研究現狀以及其在圖像配準、動態定價和網絡優化等領域的應用。

關鍵詞：最優化理論；無導數優化方法

1 概述

最優化理論與方法在軍事、金融和工業生產等領域都具有巨大的指導意義。在我國，最優化理論與方法在經濟計劃、工程設計、生產管理、交通運輸等方面得到了廣泛應用，成為一門十分活躍的學科。最優化問題的一般數學模型為

min f（x）

s.t.x∈Ω，

其中x∈Rn是決策變量，f（x）為目標函數，ΩRn為優化問題的可行域。最優化問題隨目標函數、決策變量和約束條件的不同，可作為不同分支的優化問題來研究，如線性規劃、非線性規劃以及隨機規劃等，解決方法不斷推陳出新，應用效果日漸完美。隨現代信息技術的革新，海量數據得到廣泛應用，致使最優化問題呈現出規模巨大，目標函數性狀不光滑、不穩定或者導函數信息不可用等特點。眾所周知，在優化問題中許多經典的最優化方法框架均基于導函數信息，一旦導函數信息缺失，傳統最優化方法運算起來就會十分費力耗時，甚至有一部分問題難以求解，為此需要新的優化思想有針對性的適應此類問題。于是，無導數優化思想受到學者們的廣泛關注。

2 國內外研究現狀

無導數優化思想是在有效避免使用目標函數或約束條件的導函數信息的前提下，獲得最優化問題的近似最優解。在當前的研究領域中，求解帶有不完整導數信息或者解決成本極高的目標函數的優化問題的實用性日益增長。日益復雜的數學建模，更加復雜的科學計算等都使得無導數優化算法的需求量逐漸增大。

關于無導數優化算法的研究，目前已有許多卓有成效的算法指導實踐，如無導數優化算法應用在調整非線性優化方法的參數[1]時，根據目標問題集的特點，確定出適合該問題集的參數取值。使用這種取值方案，可以使目標問題集的求解總用時縮短15%。為了減少在優化過程中所需的詳細分析，J.E.Booker[2]等人在帶有直升機旋翼設計問題的測試問題中利用無導數優化思想開發了一個嚴格有效的管理方案。其中，在優化和預定進度檢查中使用替代函數，它與繁雜的分析之間相互作用，使得該過程收斂于原始的解決方案。而且此方案給出的結果支持在DACE模型上使用ANOVA分解來識別最優設計問題中最重要的優化變量。此外，無導數優化思想還用于空氣聲學的形狀設計和水動力設計等。這些無導數優化方法都是為解決特定的優化問題而設計的，缺點在于其局限性，無法廣泛應用于各行各業。所以，還有另一種框架式的無導數優化方法，如J.Cao[3]等人提出的無導數優化算法是以信賴域方法為框架提出的。相比之下，這些算法的優勢在于能夠廣泛應用到一類優化問題上。

3 無導數優化方法的應用

在大數據蓬勃發展的今天，無導數優化問題有著廣泛的應用空間。在診斷病情和制定治療方案時，為了給醫生提供更全面，更直觀的圖像依據，往往需要將不同模態的圖像信息在空間上達到一致，這一步驟稱為配準。但由于配準的計算涉及到大量的浮點運算且數據量過大，配準過程復雜、費時，于是無導數優化方法在這里便有了用武之地。無導數優化問題中的模型搜索法是解決配準問題比較有效的一種方法，該算法輪流對變換參數進行優化，因為無需計算梯度，所以可以加快搜索變量與變量之間的統計相關性的速度，在局部范圍內有很高效的尋優性。

網絡銷售渠道的出現使得動態定價策略日益重要。所謂動態定價，是指企業根據市場需求和自身供應能力，以不同的價格將同一產品適時地銷售給不同的消費者或不同的細分市場，以實現收益最大化的一種策略。為實現客戶與企業資產回報最大化，動態定價決策過程需要管理層投入大量寶貴的時間和精力，定價策略應與企業品牌戰略同時進行而不相抵觸。然而具體定價與企業品牌之間的函數關系，與市場價格浮動產生的影響之間的函數關系并沒有具體的形態，所以性能價格比的評估值函數不確定。因此根據市場環境，應用無導數優化方法構造函數關系，計算出性能價格比的評估值，用戶便可以根據評估值來選擇適合自己的業務類型，自然而然的性能價格比高的業務類就會選擇頻率高，這樣下來能給互聯網服務提供商帶來更多的商業利益。

無導數優化方法還可以運用到網絡運營管理及優化中。通過分析網絡流量、流向趨勢變換，無導數優化算法能夠及時調整資源配置進行網絡優化使網絡質量得分和利用率不斷提升。它還可以根據網絡信令數據，實時監控網絡狀況，識別分析出價值小區和業務熱點小區，更精準的實施網絡優化，使網絡應用和用戶可以實時智能匹配。

4 總結

日益發展的信息技術時代，為無導數優化方法提供了廣闊的發展空間。以無導數優化方法獲得的決策方案更為信息技術時代的最優化問題提供指導依據。無導數優化算法以其避免導函數信息、化繁為簡為優勢，為信息技術時代的革新發揮著重要的作用，未來前景值得期待。

參考文獻：

[1]C.Audet，D.Orban，Finding optimal algorithmic parameters using derivative-free optimization，SIAM J.Optim，2006，17：642-664.

[2]A.J.Booker，J.E.Dennis，P.D.Frank，D.W.Moore，D.B.Serafini，Managing surrogate objectives to optimize a helicopter rotor design-further experiments，in AIAA Paper 1998-4717，8th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization，St.Louis，MO，1998.

[3]J.Gao，J.Cao，A class of derivative-free trust-region methods with interior backtracking technique for nonlinear optimization problems subject to linear inequality constraints，Journal of Inequalities & Applications，2018，2018（1）：108.

項目基金：國家自然科學基金（11626037）；吉林省教育廳“十三五”科學技術項目（JJKH20170036KJ）；北華大學青年培育計劃項目（2017QNJJL10）

作者簡介：高靜，女，講師，研究方向：最優化理論與方法。

通訊作者：曹健，男，講師，研究方向：網絡優化算法。