漸 令， 孫清瀅， 邵紅梅， 梁錫軍， 高衛(wèi)峰

(中國(guó)石油大學(xué) 理學(xué)院，山東 青島 266580)

0 引 言

最優(yōu)化方法涉及理論分析、算法設(shè)計(jì)和實(shí)際應(yīng)用，是一門(mén)兼顧理論與實(shí)踐的綜合性課程[1]。由于最優(yōu)化算法在工程科學(xué)計(jì)算、數(shù)據(jù)挖掘、計(jì)算機(jī)視覺(jué)、機(jī)器學(xué)習(xí)、經(jīng)濟(jì)、金融、管理等各領(lǐng)域的廣泛應(yīng)用，許多高校的理、工、管、經(jīng)濟(jì)與金融等學(xué)科都將最優(yōu)化方法設(shè)置為專(zhuān)業(yè)必修或選修課程[2]。近幾十年來(lái)，伴隨計(jì)算機(jī)科學(xué)的飛速發(fā)展[3]，人工智能、機(jī)器學(xué)習(xí)等眾多應(yīng)用領(lǐng)域的優(yōu)化問(wèn)題層出不窮[4]，這些優(yōu)化問(wèn)題的出現(xiàn)極大地推動(dòng)了最優(yōu)化理論、算法和優(yōu)化軟件的發(fā)展[5-6]。然而，“傳授型”的基本理論教學(xué)模式依然主導(dǎo)著當(dāng)前的高校優(yōu)化課堂，學(xué)生鮮有機(jī)會(huì)接觸到前沿優(yōu)化算法。最優(yōu)化方法的課程教學(xué)方式和內(nèi)容均有待改進(jìn)，以緊追當(dāng)前學(xué)科發(fā)展前沿，培養(yǎng)高素質(zhì)人才。結(jié)合當(dāng)前優(yōu)化理論與算法的發(fā)展現(xiàn)狀，設(shè)計(jì)了最優(yōu)化方法的實(shí)驗(yàn)課程，包括基礎(chǔ)算法和課程項(xiàng)目?jī)纱竽K。該實(shí)驗(yàn)課程的設(shè)計(jì)有助于學(xué)生在夯實(shí)基本優(yōu)化理論和思想的基礎(chǔ)上，熟練掌握算法設(shè)計(jì)技巧，靈活運(yùn)用優(yōu)化軟件包進(jìn)行編程解決小規(guī)模應(yīng)用問(wèn)題。能夠激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)、提高其創(chuàng)新能力和分析解決實(shí)際工程問(wèn)題的能力。

1 最優(yōu)化方法課程現(xiàn)狀分析

當(dāng)前最優(yōu)化方法課程側(cè)重于講授經(jīng)典最優(yōu)化理論與算法,包括：凸函數(shù)理論基礎(chǔ)；線性規(guī)劃理論、單純形算法與對(duì)偶單純形算法；無(wú)約束優(yōu)化問(wèn)題的最優(yōu)性條件、梯度下降算法、Newton算法、擬Newton算法、共軛梯度算法；約束優(yōu)化問(wèn)題的最優(yōu)性條件、懲罰函數(shù)法、Lagrange乘子法、序列二次規(guī)劃算法等[7]。主要是理論授課，關(guān)注的是知識(shí)系統(tǒng)性以及對(duì)優(yōu)化思想和原理的深刻理解。而在實(shí)驗(yàn)教學(xué)方面投入的力度不夠，相關(guān)算法的講授比較欠缺，甚至無(wú)暇顧及優(yōu)化軟件的應(yīng)用以及算法的編程實(shí)現(xiàn)。導(dǎo)致許多學(xué)生在課程結(jié)束之后仍不具備運(yùn)用最優(yōu)化理論與方法分析、解決實(shí)際問(wèn)題的基本能力。此外，由于課時(shí)緊張，近年來(lái)新出現(xiàn)的算法如核感知機(jī)算法、支持向量機(jī)算法等優(yōu)秀算法在課堂上均無(wú)法涉及。使得最優(yōu)化方法的課程教學(xué)無(wú)法與當(dāng)前優(yōu)化理論與算法的快速發(fā)展保持同步。

為保證最優(yōu)化方法課程建設(shè)與當(dāng)前優(yōu)化理論與算法的發(fā)展保持同步，應(yīng)在夯實(shí)學(xué)生理論分析能力的基礎(chǔ)上加強(qiáng)算法設(shè)計(jì)、編程實(shí)現(xiàn)的訓(xùn)練，提高學(xué)生的動(dòng)手能力[8-9]，激發(fā)學(xué)習(xí)興趣[10]，通過(guò)課程學(xué)習(xí)掌握基本的優(yōu)化思想、能夠?qū)崿F(xiàn)基本的算法、并能應(yīng)用優(yōu)化軟件編程解決小規(guī)模應(yīng)用問(wèn)題。

2 最優(yōu)化方法課程實(shí)驗(yàn)設(shè)計(jì)

最優(yōu)化方法課程實(shí)驗(yàn)主要由基礎(chǔ)算法模塊和課程項(xiàng)目模塊構(gòu)成。其中，基礎(chǔ)算法模塊主要涉及最常用的幾個(gè)算法，要求學(xué)生會(huì)畫(huà)算法流程圖并在實(shí)驗(yàn)課上編程實(shí)現(xiàn)；課程項(xiàng)目模塊由兩個(gè)小規(guī)模項(xiàng)目構(gòu)成，主要涉及當(dāng)前機(jī)器學(xué)習(xí)領(lǐng)域常用的感知機(jī)算法和支持向量機(jī)算法，要求學(xué)生在課下組隊(duì)完成相應(yīng)的編程工作。

2.1 基礎(chǔ)算法模塊

基礎(chǔ)算法模塊主要包括5個(gè)最為常用的優(yōu)化算法：最速下降法、Newton法、擬Newton法、共軛梯度法、懲罰函數(shù)法、Lagrange乘子法。在最優(yōu)化方法的實(shí)驗(yàn)課上，先簡(jiǎn)單回顧算法思想；再引導(dǎo)學(xué)生一起畫(huà)出算法的問(wèn)題分析圖(PAD圖)，見(jiàn)圖1、2；最后，給出具體優(yōu)化問(wèn)題，學(xué)生自主編程并求解問(wèn)題。

例1為無(wú)約束優(yōu)化問(wèn)題，可讓學(xué)生分別嘗試使用最速下降法、Newton法、擬Newton法、共軛梯度法進(jìn)行編程求解，編程語(yǔ)言如Matlab、Lingo、Fortran、R、Java、Python、C++等由學(xué)生自由選擇。例2為約束優(yōu)化問(wèn)題，可讓學(xué)生分別嘗試使用懲罰函數(shù)法和Lagrange乘子法進(jìn)行編程求解。此部分在實(shí)驗(yàn)課上完成，下課時(shí)學(xué)生提交程序用于本模塊的考核評(píng)價(jià)。

圖1 共軛梯度法PAD圖

圖2 懲罰函數(shù)法PAD圖

2.2 課程項(xiàng)目模塊

本模塊由兩個(gè)小規(guī)模課程項(xiàng)目組成，要求學(xué)生在課下自由組隊(duì)(2或3人1組)完成。兩個(gè)項(xiàng)目分別為：①利用隨機(jī)梯度下降法實(shí)現(xiàn)感知機(jī)(Perceptron)程序，并應(yīng)用感知機(jī)對(duì)UCI上的某個(gè)中等規(guī)模基準(zhǔn)分類(lèi)數(shù)據(jù)進(jìn)行分類(lèi)；②編程實(shí)現(xiàn)最小二乘支持向量機(jī)算法(LS-SVMs)，并用LS-SVMs對(duì)雙螺旋樣本進(jìn)行分類(lèi)。兩個(gè)項(xiàng)目的設(shè)計(jì)目標(biāo)和具體操作簡(jiǎn)介如下：

(1) Perceptron：理論課程介紹完最速下降法之后，可將其思想進(jìn)行推廣引出隨機(jī)梯度下降法。而Perceptron是使用隨機(jī)梯度下降法的眾多機(jī)器學(xué)習(xí)方法中形式最為簡(jiǎn)單、思想最為直觀的智能算法。講完梯度下降法后可將該項(xiàng)目布置給學(xué)生。通過(guò)本項(xiàng)目的實(shí)現(xiàn)，可使學(xué)生深入理解梯度下降法，包括最速下降法、坐標(biāo)輪換法、隨機(jī)梯度下降法的基本思想。在此基礎(chǔ)上靈活應(yīng)用梯度、隨機(jī)梯度信息處理實(shí)際應(yīng)用問(wèn)題。Perceptron模型的目標(biāo)函數(shù)是一個(gè)無(wú)約束優(yōu)化問(wèn)題[11]：

注意目標(biāo)函數(shù)是n項(xiàng)相加的和，使用最速下降法對(duì)變量w進(jìn)行迭代求解時(shí)，每一步迭代需要計(jì)算n項(xiàng)的加和，這將嚴(yán)重影響算法的收斂速度，尤其不適合處理大規(guī)模問(wèn)題(n較大的情況)。Perceptron模型采用隨機(jī)梯度下降法實(shí)現(xiàn)對(duì)變量w的迭代，格式如w∶=w+yixi, ifyi(wTxi)≤0,進(jìn)而求解上述優(yōu)化問(wèn)題。Perceptron的決策函數(shù)f(x)=wTx,在迭代過(guò)程中不斷在線更新。從美國(guó)加州大學(xué)爾灣分校的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中下載中等規(guī)?；鶞?zhǔn)分類(lèi)數(shù)據(jù)集(要求n>20 000)，應(yīng)用Perceptron模型對(duì)該數(shù)據(jù)集進(jìn)行分類(lèi)。

(2) LS-SVMs：理論課講授約束優(yōu)化問(wèn)題的最優(yōu)性條件(KKT條件)之后，將該項(xiàng)目布置給學(xué)生。目標(biāo)是通過(guò)本項(xiàng)目的實(shí)現(xiàn)使學(xué)生深刻理解最優(yōu)性條件，并靈活使用KKT條件求解約束優(yōu)化問(wèn)題。此外，LS-SVMs模型是當(dāng)前流行的機(jī)器學(xué)習(xí)算法，學(xué)生掌握該算法可直接利用其處理一些實(shí)際應(yīng)用問(wèn)題。

LS-SVMs是標(biāo)準(zhǔn)SVMs(結(jié)構(gòu)見(jiàn)圖3)的一種變形，其數(shù)學(xué)模型是一個(gè)等式約束的二次規(guī)劃問(wèn)題[12-13]

圖3 支持向量機(jī)原理示意圖

學(xué)生可以借助Lagrange函數(shù)直接寫(xiě)出LS-SVMs模型的最優(yōu)性條件，并通過(guò)引入核函數(shù)K(xi,xj)=φ(xi)Tφ(xi)得到如下鞍點(diǎn)系統(tǒng)

進(jìn)而得到LS-SVMs模型的決策函數(shù)

如圖4所示構(gòu)造人工數(shù)據(jù)集，編程產(chǎn)生兩類(lèi)點(diǎn)(雙螺旋結(jié)構(gòu))。并在雙螺旋結(jié)構(gòu)數(shù)據(jù)集上訓(xùn)練LS-SVMs模型，通過(guò)訓(xùn)練學(xué)習(xí)得到?jīng)Q策函數(shù)，并利用決策函數(shù)對(duì)其他樣本點(diǎn)進(jìn)行分類(lèi)。

2.3 評(píng)價(jià)方式多元化

對(duì)于最優(yōu)化方法這門(mén)具有工具性、應(yīng)用性特征的課程而言，考核不僅要反映出學(xué)生對(duì)基礎(chǔ)理論知識(shí)和優(yōu)化思想的掌握情況，更應(yīng)體現(xiàn)出學(xué)生靈活運(yùn)用所學(xué)優(yōu)化理論、算法分析解決實(shí)際問(wèn)題的能力。

為此，最優(yōu)化方法的課程考核包括3個(gè)方面：①基礎(chǔ)理論考核，采取閉卷考試的形式進(jìn)行評(píng)價(jià)，比重占總成績(jī)的50%；②基礎(chǔ)算法考核，通過(guò)實(shí)驗(yàn)課上基礎(chǔ)算法的編程實(shí)現(xiàn)情況進(jìn)行評(píng)價(jià)，比重占總成績(jī)的20%；③課程項(xiàng)目考核，通過(guò)實(shí)驗(yàn)課課程項(xiàng)目的完成情況進(jìn)行評(píng)價(jià)，比重占總成績(jī)的30%。

3 結(jié) 語(yǔ)

基于當(dāng)前最優(yōu)化理論、算法的發(fā)展現(xiàn)狀，結(jié)合筆者近年來(lái)有關(guān)最優(yōu)化方法課程的教學(xué)經(jīng)驗(yàn)，針對(duì)高等院校最優(yōu)化方法課程，設(shè)計(jì)了一套實(shí)驗(yàn)課程，包括基礎(chǔ)算法和課程項(xiàng)目?jī)纱竽K。通過(guò)本實(shí)驗(yàn)課程的建設(shè)有望實(shí)現(xiàn)最優(yōu)化方法的理論分析、算法設(shè)計(jì)、實(shí)際應(yīng)用的三位一體。有助于培養(yǎng)理論基礎(chǔ)扎實(shí)、創(chuàng)新意識(shí)、工程實(shí)踐能力強(qiáng)的高水平人才。