渐 令， 孙清滢， 邵红梅， 梁锡军， 高卫峰

(中国石油大学 理学院，山东 青岛 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 结 语

基于当前最优化理论、算法的发展现状，结合笔者近年来有关最优化方法课程的教学经验，针对高等院校最优化方法课程，设计了一套实验课程，包括基础算法和课程项目两大模块。通过本实验课程的建设有望实现最优化方法的理论分析、算法设计、实际应用的三位一体。有助于培养理论基础扎实、创新意识、工程实践能力强的高水平人才。