数学优化

数学优化旨在从一组可行的备选方案中，根据某个目标，寻求最佳元素，并为此提供理论和算法。

Definition

优化问题要求在由约束定义的可行集上最小化或最大化目标函数；其解是一个可行点，在该点上目标函数达到其最佳值，并由最优性条件来表征。

Scope

该领域涵盖无约束和有约束优化、凸性和对偶性、线性、二次和非线性规划、拉格朗日和卡鲁什-库恩-塔克（Karush-Kuhn-Tucker）类型的最优性条件，以及计算最优值的算法，从单纯形法和内点法到梯度法和牛顿法。它通过最优控制扩展到时间上的优化。

Sub-topics

• convex optimization
• linear programming
• nonlinear programming
• optimal control

Core questions

• 是否存在最优解，它是唯一的还是全局的？
• 什么条件表征一个最优解？
• 凸性如何使问题变得易于处理？
• 哪些算法能够可靠且高效地计算出解？

Key theories

最优性条件

拉格朗日乘数和卡鲁什-库恩-塔克条件通过平稳性、可行性和互补性来表征约束最优解，推广了无约束情况下的梯度消失条件。

凸性和对偶性

对于凸问题，每个局部最优解都是全局最优解，而拉格朗日对偶性通过强对偶定理提供了最优性的界限和证明。

迭代算法

最优解通过迭代方案计算，例如用于线性规划的单纯形法和内点法，以及用于非线性问题的梯度法、牛顿法和拟牛顿法，其收敛性由问题结构决定。

Clinical relevance

优化是运筹学、经济学、机器学习、工程设计、控制和物流的基础，为资源分配、模型拟合和约束下的决策提供了标准框架。

History

优化起源于拉格朗日乘数法和变分法。线性规划在20世纪40年代随着坎托罗维奇（Kantorovich）和丹齐格（Dantzig）的工作以及单纯形法而出现，1951年的库恩-塔克（Kuhn-Tucker）条件统一了约束优化，而内点法从20世纪80年代开始改变了大规模计算。

Key figures

• Joseph-Louis Lagrange
• George Dantzig
• Leonid Kantorovich
• Harold Kuhn
• Albert Tucker

Seminal works

• nocedal2006
• boyd2004
• bertsekas1999

Frequently asked questions

为什么凸性在优化中如此重要？

在凸问题中，任何局部最小值自动是全局最小值，并且强大的对偶性和算法保证适用。这使得凸问题能够可靠地求解，而一般的非凸问题可能存在许多局部最优解，并且没有找到最佳解的有效保证。

什么是卡鲁什-库恩-塔克条件？

它们是约束优化问题解的一阶必要条件，将拉格朗日乘数推广到不等式约束。它们结合了拉格朗日函数的平稳性、可行性以及乘数与活跃约束之间的互补松弛关系。