《优化算法导论》课件

优化算法导论优化算法是计算机科学与应用数学的核心领域，解决从机器学习到运筹学的各类问题课程概述课程目标掌握优化算法理论基础重要性优化算法是现代计算基石课程结构理论结合实践的教学方法评估方式项目实践与理论考核并重第一部分优化基础理论基本概念分类方法优化问题定义确定性与随机优化1234标准形式复杂性分析约束与目标函数时间与收敛性评估什么是优化问题？数学定义寻找函数的最值点目标函数需要最大化或最小化的表达式约束条件解必须满足的限制最优解全局最优与局部最优优化问题的标准形式等式约束最大化问题不等式约束hx=0max fxgx≤0可行域最小化问题满足所有约束条件的区3域min fx2415优化算法的分类确定性算法随机算法连续优化离散优化局部搜索全局搜索单目标优化多目标优化优化问题的复杂性NP-难问题计算复杂性理论时间复杂度算法效率分析维数灾难高维空间搜索挑战计算挑战实际应用资源限制优化算法的收敛性12收敛速度收敛条件算法迭代接近最优解的快慢判断算法停止的准则34局部收敛全局收敛在初始点附近找到最优解无论起点都能找到全局最优第二部分经典优化算法从梯度下降到直接搜索，经典算法奠定了优化领域的基础梯度下降法原理梯度概念函数在各方向的变化率下降方向负梯度方向函数值减小最快学习率步长大小影响收敛性迭代过程沿负梯度方向不断更新梯度下降法变体批量梯度下降BGD随机梯度下降SGD小批量梯度下降使用所有样本计算梯度每次只用一个样本使用样本子集计算梯度精确但计算成本高快速但波动大平衡精度与速度进阶梯度方法动量法AdaGrad Adam累积历史梯度加速收敛自适应学习率针对稀疏特征结合动量与自适应学习率牛顿法与拟牛顿法Hessian矩阵牛顿迭代函数的二阶偏导数矩阵利用二阶信息加速收敛L-BFGS BFGS算法有限内存版本降低空间复杂度近似计算逆矩阵Hessian共轭梯度法90%On效率提升存储需求比标准梯度下降收敛更快只需线性空间复杂度n理论迭代维问题最多次迭代n n信赖域方法基本概念在小区域内使用模型近似区域限制防止过大步长导致发散半径调整根据预测准确度动态调整与线搜索比较更稳定但单步计算量大直接搜索方法单纯形法模式搜索坐标下降通过多面体在沿固定模式方每次只沿一个空间中移动搜向探索坐标方向优化索无导数优化适用于不可导或导数难计算情况第三部分进化与元启发式算法进化计算基础基于生物进化的计算模型经典算法遗传算法、差分进化、粒子群等搜索策略从自然界现象中获取灵感实际应用解决复杂优化与搜索问题进化计算基础遗传算法GA染色体编码二进制或实数表示选择机制轮盘赌或锦标赛选择交叉操作单点或多点交叉变异操作随机改变基因值差分进化算法DE基本原理通过向量差分生成候选解关键参数缩放因子与交叉率F CR变异策略多种向量组合方案性能优势高维问题中优于GA粒子群优化PSO位置更新速度更新参数设置基于当前速度移动粒子结合个体和全局最优影响惯性权重与学习因子平衡搜索蚁群优化算法ACO信息素路径构建模拟蚂蚁通信的间接方式基于概率选择下一步应用案例信息素更新解决旅行商问题全局与局部更新策略TSP模拟退火算法SA热力学类比模拟物质冷却结晶过程接受准则2以概率接受较差解温度调度缓慢降低系统温度探索与利用高温探索，低温利用禁忌搜索TS禁忌表记忆机制记录最近访问的解短期避免循环，长期多样化邻域搜索多样化策略在非禁忌邻域中选择最优解避免陷入局部最优第四部分特殊优化问题与方法针对不同类型优化问题的专门方法与技术约束优化问题惩罚函数法拉格朗日乘子法增广拉格朗日法将约束转化为目标函数惩罚项引入乘子构建拉格朗日函数结合惩罚项与乘子法优点外部惩罚函数仅处理等式约束更好的数值稳定性•••内部惩罚函数需满足正则条件广泛应用于实际问题•••多目标优化Pareto最优1无法同时改善所有目标的解支配关系解之间的优劣比较非支配排序核心机制NSGA-II分解策略4将多目标转为单目标MOEA/D整数规划与组合优化0-1整数规划决策变量仅取或01分支界定法系统枚举可行解空间割平面法添加约束收紧线性松弛混合方法精确算法与启发式结合凸优化问题凸集与凸函数KKT条件单纯形法局部最优即全局最优约束优化的最优性条件线性规划的经典求解算法动态规划问题分解将大问题拆分为子问题最优子结构大问题最优解包含子问题最优解状态转移定义递推关系求解问题备忘录法存储已解决子问题避免重复计算随机优化方法方法名称主要特点适用场景蒙特卡洛法随机采样估计高维积分计算随机梯度法随机近似梯度大规模学习问题方法马尔科夫链采样复杂概率分布推断MCMC随机模拟退火概率接受劣解复杂组合优化问题贝叶斯优化高斯过程对未知函数构建概率模型采集函数引导下一次评估位置探索-利用平衡未知区域探索与已知区域利用超参数优化机器学习模型参数调优第五部分深度学习中的优化算法1优化挑战非凸目标函数与梯度问题2反向传播神经网络梯度计算基础自适应方法针对深度模型的优化器4标准化技术改善训练稳定性与收敛速度5正则化方法防止过拟合的优化技术神经网络优化挑战反向传播算法链式法则复合函数求导基础计算图可视化梯度传播路径自动微分系统自动计算导数梯度计算优化提高计算效率的技术自适应学习率方法Adagrad RMSpropAdam累积历史梯度平方移动平均历史梯度平方结合动量与自适应学习率参数更新公式参数更新公式参数更新公式θt+1=θt-η/√Gt+ε*gtθt+1=θt-η/√Et+ε*gtθt+1=θt-η*mt/√vt+ε批标准化与层标准化内部协变量偏移标准化方法优化影响层输入分布变化影响训练不同维度上的归一化操作加速训练并提高模型泛化能力正则化优化技术权重正则化Dropout稀疏化，平滑化随机关闭神经元防止共适应L1L22数据增强早停法3扩充训练数据提高鲁棒性验证集性能不再提升时停止第二阶优化方法牛顿法自然梯度利用矩阵二阶信息基于参数空间黎曼度量HessianHessian-free K-FAC隐式计算矩阵近似信息矩阵Hessian Fisher分布式与并行优化数据并行模型并行异步SGD环形AllReduce多设备处理不同数据批模型不同部分分布于多无需等待所有工作器更高效通信梯度聚合方式次设备新第六部分优化算法前沿研究探索优化算法的最新研究方向与创新技术元学习优化学习优化器使用神经网络代替人工设计优化器自动调整动态适应问题特性调整学习率神经优化器端到端训练的优化算法快速适应4等方法优化初始化权重MAML非凸优化最新进展1理论突破对特定非凸问题的收敛性保证2全局收敛逃离局部最小值的新方法3鞍点逃逸利用噪声逃离高维鞍点4非光滑优化处理不可导函数的优化技术强化学习中的优化策略梯度直接优化策略参数价值函数近似学习状态或状态动作价值-Actor-Critic结合策略与价值学习置信域方法与限制策略更新PPO TRPO量子优化算法量子退火QAOA VQE利用量子隧穿效应可变深度量子电路变分量子特征求解器等量子退火机实现组合优化问题求解量子化学计算应用D-Wave神经架构搜索NAS10^20+1000x搜索空间性能提升可能的神经网络结构数量早期计算开销NASO1差分搜索等方法计算复杂度DARTS第七部分实际应用与案例研究机器学习应用金融应用超参数优化与模型选择投资组合优化与风险管理1234工程优化案例生物信息学能源系统与调度优化药物设计与蛋白质折叠机器学习中的应用超参数优化特征选择AutoML贝叶斯优化比网格搜索更高效遗传算法可选择最佳特征子集自动化端到端机器学习流程工程优化案例能源系统运筹学电网调度与可再生能源整合物流配送与生产调度优化投资组合网络设计风险收益平衡与资产配置通信网络路由与拓扑优化总结与展望发展趋势算法效率与可扩展性提升交叉学科与神经科学、量子计算融合关键问题高维非凸优化理论突破学习资源推荐书籍与后续课程方向。