無導(dǎo)數(shù)優(yōu)化方法及應(yīng)用

高靜 曹健

摘 要：信息時(shí)代的優(yōu)化問題多以大數(shù)據(jù)為研究基礎(chǔ)，其模型通常規(guī)模龐大且函數(shù)不具有典型性。傳統(tǒng)最優(yōu)化方法已無法省時(shí)高效的求解此類問題，于是無導(dǎo)數(shù)優(yōu)化方法脫穎而出。本文介紹了無導(dǎo)數(shù)優(yōu)化的概念、國內(nèi)外研究現(xiàn)狀以及其在圖像配準(zhǔn)、動(dòng)態(tài)定價(jià)和網(wǎng)絡(luò)優(yōu)化等領(lǐng)域的應(yīng)用。

關(guān)鍵詞：最優(yōu)化理論；無導(dǎo)數(shù)優(yōu)化方法

1 概述

最優(yōu)化理論與方法在軍事、金融和工業(yè)生產(chǎn)等領(lǐng)域都具有巨大的指導(dǎo)意義。在我國，最優(yōu)化理論與方法在經(jīng)濟(jì)計(jì)劃、工程設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸?shù)确矫娴玫搅藦V泛應(yīng)用，成為一門十分活躍的學(xué)科。最優(yōu)化問題的一般數(shù)學(xué)模型為

min f（x）

s.t.x∈Ω，

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

2 國內(nèi)外研究現(xiàn)狀

無導(dǎo)數(shù)優(yōu)化思想是在有效避免使用目標(biāo)函數(shù)或約束條件的導(dǎo)函數(shù)信息的前提下，獲得最優(yōu)化問題的近似最優(yōu)解。在當(dāng)前的研究領(lǐng)域中，求解帶有不完整導(dǎo)數(shù)信息或者解決成本極高的目標(biāo)函數(shù)的優(yōu)化問題的實(shí)用性日益增長。日益復(fù)雜的數(shù)學(xué)建模，更加復(fù)雜的科學(xué)計(jì)算等都使得無導(dǎo)數(shù)優(yōu)化算法的需求量逐漸增大。

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

3 無導(dǎo)數(shù)優(yōu)化方法的應(yīng)用

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

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

無導(dǎo)數(shù)優(yōu)化方法還可以運(yùn)用到網(wǎng)絡(luò)運(yùn)營管理及優(yōu)化中。通過分析網(wǎng)絡(luò)流量、流向趨勢變換，無導(dǎo)數(shù)優(yōu)化算法能夠及時(shí)調(diào)整資源配置進(jìn)行網(wǎng)絡(luò)優(yōu)化使網(wǎng)絡(luò)質(zhì)量得分和利用率不斷提升。它還可以根據(jù)網(wǎng)絡(luò)信令數(shù)據(jù)，實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)狀況，識(shí)別分析出價(jià)值小區(qū)和業(yè)務(wù)熱點(diǎn)小區(qū)，更精準(zhǔn)的實(shí)施網(wǎng)絡(luò)優(yōu)化，使網(wǎng)絡(luò)應(yīng)用和用戶可以實(shí)時(shí)智能匹配。

4 總結(jié)

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

參考文獻(xiàn)：

[1]C.Audet，D.Orban，F(xiàn)inding 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.

項(xiàng)目基金：國家自然科學(xué)基金（11626037）；吉林省教育廳“十三五”科學(xué)技術(shù)項(xiàng)目（JJKH20170036KJ）；北華大學(xué)青年培育計(jì)劃項(xiàng)目（2017QNJJL10）

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

通訊作者：曹健，男，講師，研究方向：網(wǎng)絡(luò)優(yōu)化算法。