最 優(yōu) 化 方 法 實 驗 課 程 創(chuàng) 新 設(shè) 計

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

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

0 引 言

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

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

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

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

2 最優(yōu)化方法課程實驗設(shè)計

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

2.1 基礎(chǔ)算法模塊

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

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

圖1 共軛梯度法PAD圖

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

2.2 課程項目模塊

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

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

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

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

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

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

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

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

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

2.3 評價方式多元化

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

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

3 結(jié) 語

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