优化/数学规划

定义

从一个可行解的集合中，寻找出最优的元素

  • 需要有一个可行解的集合
  • 什么是最优的元素？即最优的准则是什么
  • 怎么寻找最优的元素？

数学形式

minimize  f0(x)subject to  fi(x)≤bi  ,  i=1,…,M(M个约束条件)其中  x=[X1,…,Xn]T  ,  Optimization Variable（优化向量）f0:Rn→R  ,  Objection function（目标函数）fi:Rn→R  ,  不等式约束则最优解  X∗optimal⟺∀z  ,  z∈{fi(z)≤bi}（可行解集）  ,  f0(z)≥f0(X∗)\text{minimize} \; f_0(x) \\ \text{subject to} \; f_i(x) \leq b_i \;,\; i = 1,\dots,M \text{(M个约束条件)} \\ 其中 \; x = [X_1,\dots,X_n]^T \;, \; \text{Optimization Variable（优化向量）} \\ f_0 : \mathbb{R}^n \rightarrow \mathbb{R} \;, \; \text{Objection function（目标函数）} \\ f_i : \mathbb{R}^n \rightarrow \mathbb{R} \;, \; \text{不等式约束} \\ 则最优解 \; X^* \text{optimal} \Longleftrightarrow \forall z \;,\; z \in \{ f_i(z) \leq b_i \} \text{（可行解集）} \;,\; f_0(z) \geq f_0(X^*)

其他

最优解一般是一个集合，也即最优解可能不止一个

e.g.

数据拟合问题，线性二次调节器LQR，多用户能量控制问题，图像处理，超大规模集成电路，最短路径问题

分类

线性规划/非线性规划

  • 如果$$f_i(\alpha x + \beta y) = \alpha f_i(x) + \beta f_i(y) ;,; i = 0,1,\dots,M ;,; \forall i \in {0,1,\dots,M}$$则是线性规划问题。
  • 即目标函数、约束函数都满足该条件则为线性规划问题。此外则为非线性规划问题。
  • 可以通过单纯形法来解决，但是并不能保证在多项式时间内解决。
  • 内点法可以保证在多项式时间内解决线性规划问题。

凸规划/非凸规划

  • 如果$$f_i(\alpha x + \beta y) \leq \alpha f_i(x) + \beta f_i(y) ;,; \forall i \in {0,1,\dots,M}$$则是凸优化问题。

  • 可行解集是凸集，且目标函数是凸函数。

  • 任何一个线性规划问题都是凸规划问题。

  • 凸优化问题一定能够在多项式时间内求解出来。

光滑/非光滑问题

如果目标函数是光滑的（处处可微），则是光滑问题。

连续/离散

可行域连续/离散，离散的问题一般比较难。

单目标/多目标优化问题

  • 多目标：帕累托曲面

    image-20240301200011676

    解决：多目标加权->化为单目标（如f1+f2），但不总是有用

  • 在帕累托曲面上，对于所有的点，无法找到任意一个x，使得其在两个f上都更小

聚焦凸优化问题、光滑问题、单目标优化问题。

主要内容

  • 凸集、凸函数
  • 凸优化
  • 若干算法