最优化问题（英语：Optimization problem）在数学与计算机科学领域中，是从所有可行解中寻找最优良的解的问题。根据变数是连续的或离散的，最佳化问题可分为两类：连续最佳化问题与组合优化。
相对于决策问题(Decision problem)、功能性问题(Function problem)，最优化问题是：从问题的多个解中，求出最佳解。例子：背包问题
- 连续最优化问题
连续最优化问题的标准的形式化是（变量是连续的）：
这里f(x)是目标函数,通过n个x来最小化f
g(x)是不等式约束条件
h(x)是等式约束条件并且m>=0,p>=0.
如果 m和p = 0，则问题是一个无约束的优化问题。按照惯例，标准表单定义了最小化问题。最大化问题可以通过否定目标函数来处理。
经典的算法：
- 牛顿法
- 随机梯度下降
- 共轭法
- 组合最优化问题
形式上（变量是离散的），一个组合优化问题A包含四个要素(I,f,m,g)，其中：
I是一组实例;给定一个实例I，f(x)是一组可行的解决方案;给定一个实例x和一个可行的解决方案f(x)，m(x,y)表示了y的度量，这通常是一个正实数。g是目标函数，并且是min或max。
它的目标是找到一些实例x一个最优的解决方案，即一个可行的解决方案y。
对于每一个组合优化问题，都有一个相应的决策问题，询问是否有一个可行的解决方案m0。例如，如果有一个图 G，其中包含点u和v，一个优化问题可能是“从u到v找到消耗最少边的一条路径”。这个问题可能有一个答案，比如说，4。一个相应的决策问题是“是否有一条从u到v的路径，它使用了边数目是否小于10?”这个问题可以用简单的“是”或“不是”来回答。
在近似算法的领域，算法的设计是为了寻找解决难题的近似最优解。通常的决策版本对问题的定义不充分，因为它只指定可接受的解决方案。虽然我们可以引入合适的决策问题，但问题更自然地被描述为优化问题。
经典的算法：
- 搜索算法：深度优先，广度优先，A*，贪婪算法
- 进化优化算法：遗传算法GA，蚁群算法PSO,和谐搜索算法HSA
- 神经网络：Hopfield神经网络
- 模拟退火
- NP优化问题
一个np优化问题(NPO)是一个具有以下附加条件的组合优化问题。
在f(x)中，每一个可行的解决方案y∈ f(x)的大小被给定的实例x的大小中的多项式所限制。
m是多项式可计算的时间
在计算机科学中，有趣的优化问题通常具有上述特性，因此是NPO问题。如果存在一个在多项式时间内找到最优解的算法，那么问题就被称为P-optimization (PO)问题。通常，NP-complete是NPO非常经典的问题。NP完全问题(NP-C问题)，是世界七大数学难题之一。
NPO根据其可逼近性分为以下子类:
- NPO(I):完全多项式时间近似方案EPTAS，例子：背包问题
- NPO(II):多项式时间的近似模式PTAS，例子：Makespan scheduling problem.
- NPO(III):它计算解决方案的成本是最优成本(最小化问题)或成本至少是最优成本(为了最大化问题)的最优成本(最小化问题)。例如：TSP问题
- NPO(IV):通过输入大小的比例近似逼近最优值用多项式对输入的对数的一个对数来逼近最优解。集合覆盖问题。
- NPO(V):通过几个n的函数的界限的比例来逼近最优值，并且不包含NPO(IV)问题，如Max Clique problems.
【描述来源：wikipedia，URL：https://en.wikipedia.org/wiki/Optimization_problem】
发展历史
最优化算法已经有很悠远的历史了。
古代
希腊数学家解决了一些与几何研究相关的最优化问题。
公元前300年欧几里得考虑到直线之间的最小距离，并证明了一个正方形在给定的总长度的矩形中有最大的面积。公元前100年，Heron在卡布里卡证明，光通过镜子反射的最短路径.
17和18世纪
在微积分的发明之前，只有一些单独的优化问题正在被研究。牛顿(1660年代)和g·w·冯·莱布尼茨(1670年代)建立了数学分析，形成了变化的微积分基础 calculus of variations(CoV)。还考虑了一些单独的有限优化问题。
19世纪
K.T.W. Weierstrass, J. Steiner, W.R. Hamilton and C.G.J. Jacobi 提出了第一个优化算法。.
1806 A.-M. Legendre 提出了最小二乘法。1826年j·b·傅里叶(J.B.J.傅里叶)为解决力学和prob中出现的问题提出了lp问题。
1847年，柯西A.L. Cauchy提出了梯度法。
19世纪70年代的边际主义革命，例如L. Walras和A. Cournot将经济学家的注意力转移到效用最大化的个体上——优化成为经济理论的一个组成部分。
二十世纪
1917年，汉考克出版了第一本关于优化的教科书，《最小和最大的理论》
1932 K。门格尔提出了旅行推销员问题的一般构想。
1939年，Kantorovich提出了lp模型和求解的算法。
二战后的优化与运筹学同时发展。冯·诺依曼是行动研究发展的重要人物。算法研究领域随着电子计算的发展而扩展。
1944年，von Neuman和O. Morgenstern用动态规划的思想解决了顺序决策问题。
1947年，为美国空军工作的G. Dantzig提出了解决lp问题的简单方法，冯·诺依曼建立了lp问题的对偶理论。
1950年代
1951年H.W. Kuhn和A.W. Tucker重新创造了非线性问题的最优性条件。约翰在1948年和W. Karush在1939年曾提出过类似的条件。1954年，L.R. Ford和D.R. Fulkerson对网络问题的研究是组合优化c研究的起点。提出了拟牛顿法和共轭梯度法等无界问题的算法。1957年，贝尔曼提出了最优性原则。
1960年代，Zoutendijk(1960)提出了一种可行的方法来推广非线性规划的单纯形法。罗森、沃尔夫和鲍威尔也有类似的想法。
序列二次规划法是威尔逊1963年首次提出的。1975年的韩寒和1977年的鲍威尔再次展示了它。
1973年，数学编程协会成立。1984年，Karmarkar的lp问题多项式时间算法开始了内部点方法的兴起。第一个多项式时间算法，即椭球面法，已于1979年由Khachiyan提出。60年代和70年代发展起来的复杂性分析开始影响到优化理论。随着计算机变得更加高效，启发式算法的全局优化和大规模问题开始流行。90年代，内点方法的使用扩展到半正定优化。
首先，在机器学习中使用了数学优化的地方有很多。如，最小化分类算法中的测试误差，所以，许多分类方法都需要解决优化问题。其次，在某些情况下，最优化算法可以应用于对过度拟合的惩罚上。优化算法是机器学习非常重要的组成部分。
优化算法在神经网络中的应用，优化算法帮助我们最小化(或最大化)一个目标函数(也叫Error函数)E(x)，它仅仅是一个依赖于模型内部可学习参数的数学函数，该函数用于计算模型中使用的预测数据集合(X)中的目标值(Y)。例如，我们将神经网络的权值(W)，Weights(W) 和偏置Bias(b)值称为其内部可学参数，这些参数用于计算输出值，并在最优解i的方向上学习和更新。通过网络的训练过程来减少损失Loss。如Adam, Adamax,Adagrad等等优化算法应用于神经网络中来最小化Error，使得训练的模型达到最佳。
主要事件
| 年份 | 事件 | 相关论文 |
| 1981 | 提出粒子优化算法 | Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical optimization. |
| 2001 | Geem, Z. W.提出谐搜索算法HSA | Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. simulation, 76(2), 60-68. |
| 2003 | Trelea, I. C.基于PSO算法分析 | Trelea, I. C. (2003). The particle swarm optimization algorithm: convergence analysis and parameter selection. Information processing letters, 85(6), 317-325. |
| 2009 | 通过凸优化的精确矩阵实现 | Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6), 717. |
发展分析
瓶颈
2000年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题。其中P与NP问题被列为这七大世界难题之首，从而大大激发了对这一问题的研究热情。它计算的时间是它的致命的问题。对于TSP问题，它的复杂度是按照指数的增长形式的，那是如何的可怕。
未来发展方向
NP问题排在世界七大数学难题之首，七个问题都是经过美国克雷数学研究所的科学顾问委员会精心挑选出来的，这些问题的获解上哪怕是获得了些许的进展，就将对数学理论的发展和应用产生极其巨大的推动作用。研究这些“千年大奖问题”已经成为世界数学界的热点，不少国家的数学家正在组织联合攻关，同时它们也是任何一个数学工作者都梦寐以求予以摘取的数学皇冠上的耀眼明珠。可以预期，这些“千年大奖问题”将会改变新世纪数学发展的历史进程。因此NP问题的求解将会不断地被注视着，当然如果有一天它被人求解出来，那么我们身边的许多问题将会被解决。