EC Lecture 1 Optimization
常见的优化问题 Optimization problem：
旅行商问题 Traveling Salesman Problem (TSP) /
二次指派问题 Quadratic Assignment Problem (QAP) /
背包问题 Knapsack problem
目标与约束 Objectives & Constraints
例如：
这是目标函数 Objective function。
这是约束 Constraint。
- 可行域 Feasible space：满足所有约束条件的所有可能解的集合。
- 可行解 Feasible solution：位于可行域中的一个具体解。
一个优化问题 Optimization problem的三个基本要素：
决策变量 Decision variables、目标函数 Objective functions 与约束 Constraints。
- 对于最小化问题 Minimization problem：目标值越小越好；（若是最大化问题则相反）
- 对于约束 Constraint：只区分“可行”或“不可行”：
- 所有可行解在可行性上是等价的。
- 不可行解之间可以根据违约程度 Violation判断好坏。
多目标 Multi-objectives
支配 Domination
若有两个解
- 在所有目标 Objective上，解
都不比解 差； - 在至少一个目标上，解
比解 严格更优；
则称：
支配 dominates 。
对于任意两个解
帕累托最优解 Pareto-Optimal Solution
- 帕累托最优解 Pareto-optimal solution：指不被任何其他解支配的解。
- 帕累托解集 Pareto Set, PS：所有帕累托最优解的集合。
- 帕累托前沿 Pareto-optimal front, PF：所有帕累托最优解在目标空间 Objective space中的函数值集合。
- 数学上：
解的优先级 Solution ranks
- 可行解 Feasible solution 优于 不可行解 Infeasible solution。
- 两个可行解：由支配关系决定，支配者 Dominating solution 更好。
- 两个不可行解：违背约束越少、违背程度越小者更好。
全局与局部优化 Global & Local Optimization
全局最优解 Global optimal solution
考虑如下最大化问题 Maximization problem：
若存在
则称
一个优化问题可能存在多个全局最优解 Global optimal solutions。
邻域 Neighborhood
- 定义：与某一点
“足够接近 close”的一组点。 - “接近 close”的具体定义依赖于
- 具体问题本身；
- 自己选择的距离度量 Distance measure或邻域结构。
局部最优解 Local optimal solution
- 定义：在其邻域 Neighborhood内不比其他任一点更差的点。
- 是否为局部最优解依赖于邻域的定义。
- 性质：全局最优解 Global optimal solution 一定是局部最优解 Local optimal solution。
局部优化 Local optimization
- 局部优化 Local optimization旨在找到某个局部最优点，或在搜索空间 Search space的某个特定区域内找到最优解。
- 通常需要一个初始点 Starting point来说明从哪个区域开始搜索。
全局优化 Global optimization
- 全局优化 Global optimization尝试在整个搜索空间中找到一个或多个全局最优点。
- 可能有初始点，也可能没有；多数情况下只给出搜索空间。
- 一般不保证 guarantee一定能找到全局最优解，只是“尽量接近”。
单峰与多峰优化问题 Unimodal and multimodal optimization problems
- 单峰问题 Unimodal problem：目标函数的“地形 landscape”只有一个主要峰/谷。凸最小化问题也不会有非全局的局部极小值，但“单峰”和“凸”不是完全等价的概念。
- 多峰问题 Multimodal problem：目标函数存在多个局部极小值 Local minima。