01 什么是凸优化问题？主要目标和内容是什么？

2024-07-29 14:26:03

1. 优化问题的一般形式：

$\\begin{align}\\min\\limits_x~~&f_0(x)\ otag\\\\s.t.~~&f_i(x_0)\\leq 0, i=1,\\ldots,m\ otag\\\\~~&h_j(x)=0,j=1,\\ldots,p.\\end{align}$

2.优化问题的几种分类：

? 特点：由于线性约束的存在，线性规划的最优点和可行点一般都是在边界上，所以单纯形法之类的算法是有用的。

凸规划( $f_i,h_j$ 凸)/非凸规划( $f_i,h_j$ 非凸)【终极分类，有本质区别】
光滑/非光滑【针对目标函数 $f_0(x)$ 来说】
连续/离散【针对可行域/约束集来说】：离散的一般都比较难，因为离散集合是非凸的，连续问题有难有易。
单目标( $\\min\\limits_x f(x)$ )/多目标( $\\min\\limits_x f_1(x),~f_2(x)$ )【针对目标函数个数而言】:
特点：往往只能折中的求解最优解。
比如：目标函数 $f_1,f_2$ 均是 $x$ 的函数，他们本身两个维度之间的关系如下:

一方增加的同时一方会减少，只能折中求解。
解决方法：用加权思想，组合成一个目标，令 $f_0(x)=\\alpha f_1(x)+\\beta f_2(x)$ ，然后去 $\\min~f_0(x)$ 。

3.什么是凸优化问题？

广义定义：凸目标函数、凸约束集。
$\\min\\limits_x~~f(x)\\\\~~~~s.t.~~x\\in \\Omega,$
其中 $f(x)$ 是凸函数， $\\Omega$ 是凸集。
【注：函数 $f$ 凸表明两件事： $f$ 满足凸函数的性质； $domf$ 是凸集。这里的 $\\Omega$ 是约束集。】
狭义定义： $f_i(x),i=0,\\ldots,m$ 是凸函数， $h_j(x),j=1,\\ldots,p$ 是仿射函数。
$\\begin{align}\\min\\limits_x~~&f_0(x)\ otag\\\\~s.t.~~&f_i(x_0)\\leq 0, i=1,\\ldots,m\\\\~~&h_j(x)=0,j=1,\\ldots,p.~~~\\end{align}$

4.凸优化的目标是什么？

解一些比较容易的问题，包括：凸问题、单目标问题、光滑问题等等。
能将一些实际问题构造成上述容易的问题类型。
容易和难指的是求解最优值的难易，对于函数 $f_i$ 的获得往往假设是可知的(就是假设函数都是给定的，针对不同情况去分析问题的性质和解法，不去讨论函数是怎么构造/建模出来的)。

5.凸优化的主要内容是什么？