1 基本概念
1.1 最优化问题的定义
最优化问题是指在给定约束条件下，寻找使目标函数达到最大值或最小值的变量取值问题。这里的“目标”可以是成本、时间、误差、能量、收益等具体指标，因而最优化方法能够把抽象的数学分析与现实决策联系起来。按研究习惯，最优化既可讨论“最小化”形式，也可通过符号变换转化为等价的“最大化”形式。
1.2 目标函数
目标函数是用来衡量方案优劣的数学表达式，通常记为变量的函数。它刻画了决策变量变化时，系统性能或代价如何改变。不同应用中的目标函数形式差异很大，可以是线性的、二次的、分段的，也可以是高度非线性的。目标函数的可微性、凸性以及是否具有特殊结构，往往直接影响求解难度。
1.3 约束条件
约束条件是对变量取值范围和相互关系的限制，用于描述问题的现实边界。没有约束时，许多问题会退化为单纯的函数极值研究；而一旦加入约束，问题往往更贴近实际，也更具挑战性。约束条件通常包括等式约束和不等式约束两类。
1.3.1 等式约束
等式约束要求变量满足某种精确关系，例如资源平衡、守恒关系或几何条件。其一般形式可写为若干函数等于零。等式约束会把可行解限制在某个曲面、曲线或更低维的集合上，因此对求解方法提出了更强要求。
1.3.2 不等式约束
不等式约束用于描述上限、下限或安全边界，例如容量不能超出、成本不能低于某一阈值等。它们通常写成小于等于或大于等于的形式。与等式约束相比，不等式约束更常见，也更容易引出“活跃约束”这一重要概念，即在最优点处恰好达到边界的约束。
1.4 可行域
可行域是所有满足约束条件的变量集合，也称可行集合。只有位于可行域内的点才有资格参与最优化比较。可行域的形状可能非常简单，如一个区间，也可能十分复杂，如由多条非线性约束围成的不规则区域。可行域是否为空、是否有界，都会影响问题的可解性与解的性质。
1.5 最优解与局部最优
最优解是指在可行域内使目标函数取得最优值的变量点。根据比较范围不同，最优解可分为全局最优与局部最优。对于凸问题，两者通常一致；而在非凸问题中，局部最优并不一定是全局最优，这也是实际求解中常见的难点之一。
1.5.1 全局最优解
全局最优解是在整个可行域中都优于或不劣于其他可行点的解。它代表问题的真正最优结果。若目标函数和约束结构较为规整，例如满足凸性条件，则全局最优解往往更容易分析和证明存在。
1.5.2 局部最优解
局部最优解是在某个邻域内优于周围点的解。它在非凸优化中十分常见，可能表现为局部极小值、局部极大值或鞍点附近的稳定点。许多数值算法本质上都更容易收敛到局部最优，因此在实际应用中常需结合初值选择与全局搜索策略。
2 问题分类
2.1 按变量类型分类
最优化问题可依据决策变量的取值范围进行分类。变量是连续的、离散的，还是兼具两者特征，决定了模型结构和求解工具的差异。变量类型的划分，是理解优化问题复杂性的重要入口。
2.1.1 连续最优化
连续最优化中，变量可以在某个连续区间或连续空间内取值。此类问题广泛出现在物理建模、参数估计和控制设计中。由于变量连续，微积分、凸分析和数值迭代方法常成为主要工具。
2.1.2 离散最优化
离散最优化要求变量只能取有限个或可数个值，例如整数、0-1变量或排列。它常见于排程、路径选择、装配组合等问题。由于搜索空间通常呈组合爆炸式增长，离散优化往往比连续优化更难。
2.1.3 混合整数优化
混合整数优化同时包含连续变量和整数变量，既要处理连续调节，又要处理离散决策。它在生产计划、网络设计和选址问题中非常典型。此类问题兼具连续优化和组合优化的难点，建模和求解都较为复杂。
2.2 按目标与约束结构分类
依据目标函数和约束的数学形式，优化问题可分为线性、非线性、凸与非凸等类型。这一分类直接关联到是否能使用特定算法，以及问题是否容易获得全局最优。
2.2.1 线性规划
线性规划中，目标函数与约束条件都为线性形式。它是优化理论中最经典、应用最广的模型之一。由于结构清晰，线性规划在理论上具有较完整的对偶理论和算法体系。
2.2.2 非线性规划
非线性规划指目标函数或约束中至少有一项是非线性的。它能够描述更真实的系统关系，但求解通常更困难。许多实际问题都属于这一类，例如工程设计中的性能曲线优化。
2.2.3 凸优化
凸优化要求目标函数为凸函数、可行域为凸集，且通常是最小化问题。该类问题具有非常良好的理论性质：局部最优即全局最优，且数值求解相对稳定。因此，凸优化被视为现代优化理论的核心分支之一。
2.2.4 非凸优化
非凸优化是指不满足凸性条件的问题。它常出现多个局部极值、平坦区域或复杂约束结构，因此全局求解更具挑战。尽管如此，非凸优化在机器学习、控制和工程设计中极为常见。
2.3 按时间维度分类
从时间因素看，优化问题可分为静态和动态两种。前者只考虑单一时刻或单次决策，后者则关注多个时段之间的联动关系。
2.3.1 静态优化
静态优化处理的是在固定条件下的一次性决策问题。模型通常不显式包含时间演化，适合描述单次配置、单阶段分配等情形。其结构相对简洁，便于分析和求解。
2.3.2 动态优化
动态优化考虑状态随时间变化的过程，决策会影响未来可行性和收益。动态规划是这一类问题的重要代表。此类问题常见于库存管理、资源调度和控制系统中。
3 数学模型
3.1 建模步骤
优化建模通常从明确实际问题开始，依次完成目标识别、变量选择、约束整理与数学表达。之后还需检查模型是否合理、是否可解，以及是否过于复杂。一个好的模型既要足够贴近现实，又要便于分析和计算。
3.2 变量与参数的设定
变量是待决策的未知量，参数则是已知的环境量或固定常数。两者的区分十分重要，因为变量受优化过程控制，而参数决定问题背景。设定变量时，应尽量选取能够直接反映决策意义的量，以提高模型解释性。
3.3 目标函数构造
目标函数的构造通常围绕“希望最大化什么”或“希望最小化什么”展开。实践中，目标可能需要由多个指标综合而成，例如成本、效率、风险和稳定性之间的权衡。必要时还会引入加权方式，将多项性能统一到一个可优化的表达式中。
3.4 约束条件建模
约束条件建模的关键在于把现实规则转写为数学关系。它既包括硬性限制，也包括资源容量、技术规范和逻辑条件。合理的约束建模能够避免解脱离实际，但过多或过强的约束也可能导致不可行。
3.5 模型简化与等价变换
在不改变问题本质的前提下，模型常需要进行简化与变换。常见做法包括变量替换、约束合并、尺度调整和符号转换。等价变换的目的在于降低复杂性、突出结构特征，或使问题更适合特定算法处理。
4 理论基础
4.1 存在性与可解性
优化理论首先关注问题是否有解，以及是否能够在合理条件下求出该解。存在性与可解性分析为后续算法设计提供基础，也帮助判断一个模型是否具有现实意义。
4.1.1 最优解存在条件
最优解是否存在，通常与可行域的闭性、有界性以及目标函数的连续性有关。在一些经典情形下，可行域紧且目标函数连续，则最优解必然存在。若缺少这些条件，可能出现目标值趋于极限但解并不存在的情况。
4.1.2 可行性与不可行性
可行性指至少存在一个满足所有约束的解；不可行性则意味着约束彼此冲突，无法同时满足。可行性检查在实际建模中十分重要，因为错误设定的约束会使问题失去意义。对于大型模型，判断不可行性的原因往往比直接求解更复杂。
4.2 极值条件
极值条件用于判定候选点是否可能成为最优解，是微分型优化的核心理论工具之一。它通过导数、梯度和二阶信息来描述函数在局部的变化趋势。
4.2.1 一阶必要条件
在光滑无约束问题中，若某点是局部极值，则该点的一阶导数或梯度通常应为零。对于有约束问题，还需结合约束结构分析。由于一阶条件只提供必要性，因此满足该条件并不保证一定最优。
4.2.2 二阶条件
二阶条件利用 Hessian 矩阵或二阶导数信息判断候选点的局部性质。若二阶导数在某点附近表现出正定性或负定性，便可进一步区分极小值、极大值或鞍点。相比一阶条件，二阶条件能够提供更强的局部判别能力。
4.3 拉格朗日乘子法
拉格朗日乘子法是一种处理等式约束优化的重要方法。它通过把约束并入目标函数，构造一个新的辅助函数，从而将原问题转化为求导条件问题。该方法是约束优化理论中的基础工具。
4.3.1 约束最优化中的应用
在有约束情形下，拉格朗日乘子可解释为约束对最优值的影响强度。通过建立乘子方程组，可以同时刻画目标函数与约束的平衡关系。这种方法特别适合处理几何、力学和经济模型中的受限优化。
4.3.2 KKT条件
KKT条件是处理含不等式约束最优化问题的重要必要条件，由一系列互补关系、可行性条件与驻点条件组成。对于满足一定正则条件的凸优化问题，KKT条件不仅必要，而且往往也是充分条件。它在现代优化理论和算法设计中占据核心地位。
4.4 凸性理论
凸性理论为优化提供了简洁而强大的结构框架。许多复杂问题一旦被证明具有凸性，其理论分析和算法求解就会显著简化。
4.4.1 凸集
凸集是指任意两点之间的线段都完全包含在集合内部的集合。凸集在优化中十分重要，因为凸约束下的可行域更容易保持良好性质。许多线性约束和半空间交集都构成凸集。
4.4.2 凸函数
凸函数满足“线段上函数值不高于端点连线”的性质。对最小化问题而言，凸函数具有优良的局部—全局一致性。许多常见损失函数和正则项都利用了凸函数的稳定特征。
4.4.3 强对偶与弱对偶
对偶理论将原问题与一个伴随问题联系起来。弱对偶说明对偶问题的解通常不会优于原问题的最优值，而强对偶则在适当条件下表明两者最优值相等。对偶性不仅有助于理论分析，也常为算法提供更高效的求解途径。
5 求解方法
5.1 解析方法
解析方法依赖符号推导和公式变形，适用于结构较清晰或规模较小的问题。其优势在于结果明确、可解释性强，但对复杂模型的适用性有限。
5.1.1 微分法
微分法通过求导并分析导数零点来寻找极值点。对于单变量或低维光滑函数，这种方法尤其直观。若函数可导且结构简单，微分法往往能够直接给出解析解或候选解。
5.1.2 拉格朗日法
拉格朗日法通过引入乘子，把约束条件融入统一框架中。该方法适合处理等式约束下的极值问题，也常作为构建更一般条件的基础。它在理论推导和模型分析中都非常常见。
5.2 数值方法
数值方法通过迭代计算逼近最优解，是处理大规模和复杂优化问题的主要手段。与解析方法相比，数值方法更灵活，但需要关注收敛速度、稳定性和初值敏感性。
5.2.1 梯度下降法
梯度下降法沿目标函数下降最快的方向迭代更新变量，逐步减小目标值。它实现简单、应用广泛，尤其适合大规模连续优化。其效果通常依赖步长选择与函数光滑性。
5.2.2 牛顿法
牛顿法利用一阶和二阶导数信息构造局部二次近似，从而快速逼近极值点。相比梯度下降法，它通常收敛更快，但计算 Hessian 及其逆的代价较高。对于条件良好的问题，牛顿法具有很强的效率优势。
5.2.3 拟牛顿法
拟牛顿法在不直接计算 Hessian 的情况下，逐步构造其近似矩阵。它兼顾了牛顿法的快速性与较低的计算成本。常见方法包括通过迭代更新近似矩阵来提高收敛性能。
5.3 线性与整数规划算法
线性规划和整数规划各有一套成熟算法体系，其中不少方法兼具理论严谨性与工程实用性。对于组合结构明显的问题，这类算法尤为重要。
5.3.1 单纯形法
单纯形法沿可行域边界逐步移动，在多个顶点之间寻找更优解。它在实践中表现出很高的效率，尽管理论上最坏情况可能较慢。该方法是线性规划历史上最具代表性的算法之一。
5.3.2 分支定界法
分支定界法通过分解搜索空间并利用上下界剪枝，系统地求解整数规划问题。它能够保证在有限步骤内找到最优整数解，前提是计算资源足够。由于搜索树可能迅速膨胀，效率往往取决于界的质量与剪枝能力。
5.4 动态规划方法
动态规划将复杂问题分解为若干相互关联的子问题，并利用最优子结构和重叠子问题的特征进行递推求解。它特别适合多阶段决策问题。该方法的关键在于正确定义状态、决策和状态转移关系。
5.5 启发式与元启发式方法
当问题过于复杂、精确算法代价过高时，启发式与元启发式方法常被用于获得较优近似解。它们通常不保证全局最优，但在大规模场景中具有较强实用性。
5.5.1 模拟退火
模拟退火借鉴物理退火过程，通过允许一定概率接受较差解，帮助算法跳出局部最优。随着“温度”逐步降低，搜索趋向稳定。该方法适合复杂组合优化和非凸问题。
5.5.2 遗传算法
遗传算法模拟生物进化过程，通过选择、交叉和变异不断生成新解。它适合搜索空间巨大、结构不规则的问题。由于具有较强的全局探索能力，常用于难以解析建模的优化任务。
5.5.3 粒子群优化
粒子群优化以群体协同搜索为思想，每个“粒子”根据自身经验和群体经验更新位置。它实现简洁、参数较少，在连续优化中较为常用。该方法常用于函数优化和参数调优。
6 经典专题
6.1 线性规划
线性规划研究线性目标函数在一组线性约束下的最优值问题。它的理论结构完整，应用范围广泛，是现代优化的基础专题之一。
6.1.1 标准型与对偶问题
线性规划通常可以写成标准型，便于统一分析和算法实现。对偶问题则从另一个角度描述同一优化结构，两者之间存在紧密联系。对偶理论不仅能给出界，还能帮助解释资源价格与约束价值。
6.1.2 单纯形迭代过程
单纯形法在迭代过程中不断更新基变量与非基变量的组合，以移动到更优的顶点。每一步都依据改进方向和可行性规则进行。虽然过程看似简单，但其背后包含了对可行域几何结构的深刻利用。
6.2 非线性规划
非线性规划涵盖目标或约束含非线性项的问题，是最优化中最广泛的一类。它既包括平滑问题，也包括可能具有奇异结构的问题。
6.2.1 光滑优化
光滑优化要求目标函数和约束函数具有足够阶数的可导性。这样便可使用梯度、Hessian 和相关导数工具分析最优性。许多数值算法都建立在光滑性假设之上。
6.2.2 无约束优化
无约束优化不含显式约束，问题本质上是寻找函数的极值点。它是研究更复杂约束优化前的重要基础。很多算法首先在无约束场景中建立，再推广到约束问题。
6.2.3 约束优化
约束优化在现实问题中更常见，因为大多数决策都受到各种限制。与无约束优化相比，它需要同时处理可行性与最优性两个方面。KKT条件、罚函数法和投影法等都是常用工具。
6.3 整数规划
整数规划要求部分或全部变量取整数值，是离散优化的重要分支。由于变量的离散性，它常出现组合复杂性和计算困难。
6.3.1 0-1规划
0-1规划中，变量只能取 0 或 1，通常表示“选或不选”“开或关”等二元决策。它是许多离散模型的基础形式。尽管表达简单，但能够刻画大量实际选择问题。
6.3.2 背包问题
背包问题要求在容量限制下选择若干物品，使总价值最大。它是典型的组合优化模型，也常被用作算法教学和复杂性分析中的经典例题。不同变体对应不同的求解难度。
6.3.3 组合优化
组合优化研究从有限或离散结构中寻找最优组合的过程，例如路径、排列、匹配和覆盖等问题。它在图论、调度和网络设计中非常重要。由于搜索空间庞大，常需要专门算法或近似方法。
6.4 多目标优化
多目标优化同时考虑多个相互竞争的目标，无法像单目标问题那样直接给出唯一“最优”方案。它更强调平衡、偏好和折中。
6.4.1 帕累托最优
帕累托最优指在不损害某一目标的情况下，无法进一步改善另一个目标的状态。帕累托解集反映了不同目标间的权衡边界。它是多目标分析中最基本的概念之一。
6.4.2 目标权衡与折中解
目标权衡意味着提高一个指标往往会削弱另一个指标，因此需要根据偏好选择折中方案。折中解通常通过加权和、约束化处理或分层决策获得。实际应用中，折中解往往比单一极端解更具可实施性。
7 应用领域
7.1 工程设计
工程设计中的优化常围绕性能、成本、安全性与材料消耗展开。通过数学建模，可以在满足约束的前提下提升系统效率。
7.1.1 结构优化
结构优化关注构件形状、尺寸和材料分布的最优设计。其目标通常是在保证强度和稳定性的同时减轻重量或降低成本。该领域在机械、土木和航空设计中都很常见。
7.1.2 控制系统优化
控制系统优化主要研究如何选择控制参数，使系统响应更快、更稳或更省能。它常与动态系统理论结合，涉及稳定性、鲁棒性和跟踪性能等问题。现代控制工程中，优化方法已成为基础工具。
7.2 经济与金融
经济和金融问题天然包含资源有限、收益不确定和风险权衡等因素，因此最优化方法应用极为广泛。
7.2.1 资源配置
资源配置优化研究如何在有限资源下实现效益最大化或成本最小化。它可应用于生产、供应、预算分配等场景。合理配置资源往往决定系统整体效率。
7.2.2 投资组合优化
投资组合优化旨在在收益与风险之间寻找平衡。常见做法是构造收益最大、风险受控的模型，并根据偏好选择资产组合。该问题体现了优化理论在决策分析中的典型价值。
7.3 计算机科学
计算机科学中大量问题都可转化为优化形式，尤其是在学习算法、图像处理和系统调优方面。
7.3.1 机器学习中的优化
机器学习训练过程通常可表述为损失函数最小化问题。模型参数通过梯度下降及其变体不断更新，以提高预测性能。优化方法直接影响训练速度、收敛质量和最终效果。
7.3.2 图像处理中的优化
图像处理常涉及去噪、重建、分割和配准等任务，这些问题往往可写成最小化某种误差与正则项的形式。优化框架能够统一处理多种视觉任务。随着模型复杂化，数值优化的重要性也不断提升。
7.4 运筹与管理
运筹与管理中的优化主要服务于生产组织、库存控制和物流配送等问题。其目标通常是提升效率、降低成本并改善资源利用。
7.4.1 生产调度
生产调度优化研究任务在机器、工序和时间上的安排方式。它需要考虑设备能力、加工顺序和交期限制。合理调度能够显著提高生产系统的吞吐量与稳定性。
7.4.2 物流与路径规划
物流与路径规划关注如何选择运输路线和配送顺序，以减少时间、里程或费用。该类问题常与图模型和组合优化相关。实际应用中还需处理交通、容量和时窗等约束。
8 计算复杂性
8.1 问题难度分类
优化问题的计算复杂性用于衡量求解所需资源随规模增长的变化情况。按照难度不同，问题可分为易解、较难和极难等类别。复杂性分析有助于判断应采用精确算法还是近似策略。
8.2 多项式时间可解问题
若一个问题能在输入规模的多项式时间内求解，则通常被视为可有效处理的问题。线性规划在理论上就属于这类问题的典型代表。多项式时间可解性是算法设计中的重要目标。
8.3 NP难问题
NP难问题通常意味着不存在已知的高效精确算法，或者求解代价会随规模迅速膨胀。许多整数规划和组合优化问题都属于这一类。面对 NP难问题，常需借助剪枝、启发式或近似方法。
8.4 近似算法
近似算法不追求绝对最优，而是保证解与最优解之间存在可分析的误差界。它在大规模、复杂或 NP难问题中具有重要价值。近似算法的研究重点包括质量保证与计算效率之间的平衡。
8.4.1 近似比
近似比用于衡量近似解与最优解之间的性能差距。它提供了算法结果可控性的定量标准。对于最小化和最大化问题，近似比的定义形式略有不同。
8.4.2 误差界分析
误差界分析关注算法输出偏离最优值的上限或比例。通过建立误差界，可以更清楚地判断算法的适用范围。该分析在理论研究和工程实践中都很重要。
9 历史与发展
9.1 古典极值问题
最优化思想可追溯到古典数学中的极值研究，例如寻求面积、体积或路径的最优值。早期问题多依赖几何直观和解析技巧。随着微积分的发展，极值理论逐渐形成系统框架。
9.2 20世纪优化理论的发展
20世纪是优化理论快速成熟的阶段，线性规划、非线性规划和对偶理论相继发展。相关研究使优化从单纯的数学技巧演变为独立的学科体系。许多基础成果也在这一时期得到奠定。
9.3 现代优化方法的兴起
随着计算需求增大，现代优化更重视算法可扩展性和结构利用。凸优化、内点法以及大规模数值算法的发展，显著拓宽了优化的应用边界。优化理论与计算机科学的联系也因此更加紧密。
9.4 计算机时代的最优化研究
计算机的普及使复杂模型的数值求解成为可能，优化研究进入以算法和实现为核心的新阶段。大规模数据、并行计算和自动化建模推动了新方法不断涌现。如今，优化已成为数据科学、工程系统和智能决策的重要基础。
10 相关概念
10.1 对偶问题
对偶问题是由原优化问题导出的伴随问题，常用于提供界、验证最优性和改进求解效率。原问题与对偶问题之间存在深刻的数学联系。许多优化算法都隐含利用了对偶结构。
10.2 灵敏度分析
灵敏度分析研究模型参数发生变化时，最优解和最优值如何随之变化。它有助于评估模型的稳定性与可靠性。实际应用中，这类分析可为决策者提供“方案是否稳健”的参考。
10.3 约束松弛
约束松弛是指放宽部分约束，以便得到更易求解或更有分析价值的替代问题。松弛后的问题通常具有更大的可行域，因此可能给出原问题的下界或上界。它在近似算法和分解方法中十分常见。
10.4 鲁棒优化
鲁棒优化关注参数不确定条件下的最优决策，希望解在各种扰动下仍保持较好性能。它强调“最坏情形”下的稳定性，因此适合风险敏感型场景。该方法在工程设计和供应链管理中应用较多。
10.5 随机优化
随机优化处理目标函数、约束或环境参数具有随机性的情形。与确定性优化相比，它更能反映现实中的不确定因素。随机梯度、样本平均近似等方法，都是这一领域的重要工具。