最优化问题简介

，为约束函数，。满⾜最优化数学模型中的所有约束条件就称为可⾏点(FeasiblePoint)，所有可⾏点的全体称为可⾏域(Feasible表⽰。在⼀个可⾏点的边界；如果有，就称不等式约束在点，如果没有⼀个不等式约束是有效的，就称是可⾏域的内点，不满⾜，如果存在⼀个邻域成⽴，则称为最优化问题的局部最优解，其中，如果存在⼀个邻域和和为等式约束，和考虑不等式约束，则称为最优化问题的全局最优解（或总体最优解）；如果可⾏点是⼀个⼩的正数；对于可使得则是局部极⼩解，其中为连续函数，通常还要求连续可微。称为决策变量，为不等式约束，并记等式约束的指标集为分别是英⽂单词minimize(极⼩化)和subjectto(受约束)的缩写。，如果有满⾜成⽴，则称为最优化问题的严格局部最优解。如下图所是严格局部极⼩解，⽽为⽬标函，就称不等式约束是⾮严格局部极⼩解。（注：在点附近有⼀段线考虑不等式约束是

最优化问题简介，为约束函数，。满⾜最优化数学模型中的所有约束条件就称为可⾏点(FeasiblePoint)，所有可⾏点的全体称为可⾏域(Feasible表⽰。在⼀个可⾏点的边界；如果有，就称不等式约束在点，如果没有⼀个不等式约束是有效的，就称是可⾏域的内点，不满⾜，如果存在⼀个邻域成⽴，则称为最优化问题的局部最优解，其中，如果存在⼀个邻域和和为等式约束，和考虑不等式约束，则称为最优化问题的全局最优解（或总体最优解）；如果可⾏点是⼀个⼩的正数；对于可使得则是局部极⼩解，其中为连续函数，通常还要求连续可微。称为决策变量，为不等式约束，并记等式约束的指标集为分别是英⽂单词minimize(极⼩化)和subjectto(受约束)的缩写。，如果有满⾜成⽴，则称为最优化问题的严格局部最优解。如下图所是严格局部极⼩解，⽽为⽬标函，就称不等式约束是⾮严格局部极⼩解。（注：在点附近有⼀段线考虑不等式约束是

题⽬：最优化问题简介

⼀年多学习以来，⽆论是前⾯学习压缩感知，还是这半年学习机器学习，⼀直离不开最优化，⽐如压缩感知的基追踪类重构算法，核⼼问题就是⼀个优化问题，⽽机器学习中的很多算法也需要最优化的知识，⽐如⽀持向量机算法。看来必须得把最优化的基本内容学习⼀下了，不求理解的有多么深，⾄少要知道怎么⽤。其实前⾯已经写过⼀篇与最优化相关的内容了，就是《》这篇。

从本篇起，开始学习⼀些有关最优化的基础知识，重点是了解概念和如何应⽤。本篇是参考⽂献第1.1节的⼀个摘编或总结，主要是把⼀些概念集中起来，可以随时查阅。

1、⼀般形式

最优化问题的数学模型的⼀般形式为（以下称为最优化数学模型）：

其中数，，不等式约束的指标集为

2、概念

如果点Region)，⽤有效约束或起作⽤约束(activeconstraint)，并称可⾏点位于约束是⽆效约束或不起作⽤约束(inactiveconstraint)；对于⼀个可⾏点是内点的可⾏点就是可⾏域的边界点。显然在边界点⾄少有⼀个不等式约束是有效约束，当存在等式约束时，任何可⾏点都要满⾜等式约束，因此不可能是等式约束的内点。如果⼀个可⾏点，则称为最优化问题的严格全局最优解（或严格总体最优解）；对于可⾏点

使得⾏点⽰，点是严格全部极⼩解，是⽔平的）

⼀般常见的最优化⽅法只适⽤于确定最优化问题的局部最优解，有关确定全局最优解的最优化⽅法属于最优化问题的另⼀个领域——全局最优化。然⽽，如果最优化问题的⽬标函数是凸的，⽽可⾏域是凸集，则问题的任何最优解（不⼀定唯⼀）必是全局最优解，这样的最优化问题⼜称为凸规划。进⼀步，对于凸集上的严格凸函数的极⼩化问题，存在唯⼀的全局最优解。

3、分类

1）约束最优化问题

只要在问题中存在任何约束条件，就称为约束最优化问题。

只有等式约束时，称为等式约束最优化问题，数学模型为：

只有不等式约束时，称为不等式约束最优化问题，数学模型为：

。矩阵向量形式为，为半正定矩阵，则称此规划为凸⼆次规划，否则为⾮凸规划。对于⾮凸规

既有等式约束，⼜有不等式约束，则称为混合约束优化问题（或⼀般约束优化问题）；。矩阵向量形式为，为半正定矩阵，则称此规划为凸⼆次规划，否则为⾮凸规划。对于⾮凸规

把简单界约束优化问题称为盒式约束优化问题（或有界约束优化问题），数学模型为：

2）⽆约束最优化问题

如果问题中⽆任何约束条件，则称为⽆约束最优化问题，数学模型为：

3）连续与离散最优化问题

决策变量的取值是连续的，称为连续最优化问题；

决策变量的取值是离散的，称为离散最优化问题，⼜称为组合最优化问题。如整数规划、资源配置、邮路问题、⽣产安排等问题都是离散最优化问题的典型例⼦，求解难度⽐连续最优化问题更⼤。

4）光滑与⾮光滑最优化问题

如果最优化数学模型中的所有函数都连续可微，则称为光滑最优化问题；

只要有⼀个函数⾮光滑，则相应的优化问题就是⾮光滑最优化问题。

5）线性规划问题

对于连续光滑最优化问题，如果最优化数学模型中的所有函数都是决策变量的线性函数，则称为线性规划问题。线性规划问题的⼀般形式为：

其中

其中

，

6）⼆次规划问题

对于连续光滑最优化问题，如果最优化数学模型中的⽬标函数是决策变量的⼆次函数，⽽所有约束都是决策变量的线性函数，则称为⼆次规划问题。⼆次规划问题的⼀般形式为：

其中，为纯量，为阶对称矩阵。如果划，由于存在⽐较多的驻点，求解⽐较困难。

7）⾮线性最优化问题

只要最优化数学模型中的函数有⼀个关于决策变量是⾮线性的，则称为⾮线性最优化问题。

⾮线性最优化问题是最⼀般的最优化问题，⽽线性规划和⼆次规划问题却是相当重要的特殊的最优化问题，因为在实际中形成的许多最优化问题都是线性规划问题或⼆次规划