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

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

0 引 言

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

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

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

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

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

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

2.1 基礎算法模塊

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

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

圖1 共軛梯度法PAD圖

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

2.2 課程項目模塊

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

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

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

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

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

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

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

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

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

2.3 評價方式多元化

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

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

3 結 語

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