最 優 化 方 法 實 驗 課 程 創 新 設 計

漸 令， 孫清瀅， 邵紅梅， 梁錫軍， 高衛峰

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

0 引 言

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

1 最優化方法課程現狀分析

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

為保證最優化方法課程建設與當前優化理論與算法的發展保持同步，應在夯實學生理論分析能力的基礎上加強算法設計、編程實現的訓練，提高學生的動手能力[8-9]，激發學習興趣[10]，通過課程學習掌握基本的優化思想、能夠實現基本的算法、并能應用優化軟件編程解決小規模應用問題。

2 最優化方法課程實驗設計

最優化方法課程實驗主要由基礎算法模塊和課程項目模塊構成。其中，基礎算法模塊主要涉及最常用的幾個算法，要求學生會畫算法流程圖并在實驗課上編程實現；課程項目模塊由兩個小規模項目構成，主要涉及當前機器學習領域常用的感知機算法和支持向量機算法，要求學生在課下組隊完成相應的編程工作。

2.1 基礎算法模塊

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

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

圖1 共軛梯度法PAD圖

圖2 懲罰函數法PAD圖

2.2 課程項目模塊

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

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

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

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

LS-SVMs是標準SVMs(結構見圖3)的一種變形，其數學模型是一個等式約束的二次規劃問題[12-13]

圖3 支持向量機原理示意圖

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

進而得到LS-SVMs模型的決策函數

如圖4所示構造人工數據集，編程產生兩類點(雙螺旋結構)。并在雙螺旋結構數據集上訓練LS-SVMs模型，通過訓練學習得到決策函數，并利用決策函數對其他樣本點進行分類。

2.3 評價方式多元化

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

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

3 結 語

基于當前最優化理論、算法的發展現狀，結合筆者近年來有關最優化方法課程的教學經驗，針對高等院校最優化方法課程，設計了一套實驗課程，包括基礎算法和課程項目兩大模塊。通過本實驗課程的建設有望實現最優化方法的理論分析、算法設計、實際應用的三位一體。有助于培養理論基礎扎實、創新意識、工程實踐能力強的高水平人才。