凸优化问题的定义_如何证明一个问题是凸优化问题

4.1 优化问题

基本术语
问题的标准表示
等价问题
参数与谕示问题描述

4.1.1 基本术语

$\begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

$x \in R^n$ 是优化变量也叫决策变量；

$f_0:R^n \rightarrow R$ 为目标函数，或者费用函数；

$f_i:R^n \rightarrow R,i=1,\cdots, m$ 是不等式约束函数；

$h_i:R^n \rightarrow R,i=1,\cdots, p$ 是等式约束函数。

如果 m=p=0 ，即没有约束，此时问题为无约束问题。

在实际生活中可以这样理解该优化问题，即我们要生产产品，其数量为x，要确定生产数量以使得利润最高，而约束函数则可以理解为在实际产生中受到的限制比如资源消耗等。

问题的定义域： $\mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i}$

可行点： $x \in D,f_i(x)\leq 0,i=1,\cdots m,h_i(x)=0,i=1,\cdots p$ ，此时x是可行的，x为可行点。

可行集：所以有可行点的集合。

当问题的可行集非空时，我们称为问题是可行的，否则称为不可行。

问题的最优值记为 $p^*=inf \left\{ f_0(x)|f_i(x)\leq 0,i=1,\cdots m,h_i(x)=0,i=1,\cdots p\right \}$ 。

如果问题不可行，记 $p^*=\infty$ ；

如果存在可行解 $x_k:k\rightarrow \infty ,f_0(x_k)\rightarrow -\infty$ ，记 $p^*=-\infty$ ，此时称问题无下界。

最优点和局部最优点

如果 x^* 是可行的且，我们称 x^* 为最优点（解、全局最优），所有最优解的集合称为最优集，记为 $X_{opt}=\left \{x|f_i(x)\leq 0,i=1,\cdots m,h_i(x)=0,i=1,\cdots p,f_0(x)=p^* \right \}$

如果存在0,f_0(x)=inf\left\{f_0(z)|f_i(z)\leq 0,i=1,\cdots m,h_i(z)=0,i=1,\cdots p,\begin{Vmatrix} z-x \end{Vmatrix}_2\leq R \right \}”>，称x为局部最优。

即，x是关于z的优化问题的解：

$\begin{array}{ll} \operatorname{minimize} & f_{0}(z) \\ \text { subject to } & f_{i}(z) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(z)=0, \quad i=1, \cdots, p \\ & \|z-x\|_{2} \leqslant R \end{array}$

全局最优一定是局部最优，局部最优不一定是全局最优。

例子：

$f_0(x)=1/x,dom(f_0)=R_{++}:p^*=0$ ，但是没有最优点。

$f_0(x)=-log(x),dom(f_0)=R_{++}:p^*=-\infty$ 。

$f_0(x)=xlog(x),dom(f_0)=R_{++},p^*=-1/e,x=1/e$ 是最优点。

$f_0(x)=x^3-3x,p^*=-\infty$ ，但有局部最优点在x=1。

min VS minimize

minimize不是min。min是一个取最小值的函数，比如min{0,-1,2}=-1。minimize是优化问题中的一部分，不是对一组数中取出最小值，而是针对一个目标函数，找到使目标函数最小的点。

可行性问题

如果目标函数恒等于零,那么其最优解要么是零(如果可行集非空),要么是∞(如果可行集是空集)。我们称其为可行性问题，有些时候将其写作：

$\begin{array}{ll} \text { find } & x \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$
因此，可行性问题可以用来判断约束是否一致，如是，则找到一个满足它们的点。
可以用它来找到函数的定义域（另外还要加上目标函数的隐式约束）。

4.1.2 问题的标准表示

$\begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

为极小化问题的标准表示形式。

如果是极大问题，即：

$\begin{array}{ll} \operatorname{maximize} & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

极大化问题变极小化问题只需对目标函数取相反数即可得到。

可以将目标函数理解为效用函数。

4.1.3 等价问题

如果从一个问题的解，很容易就能得到另一个问题的解，反之亦然，则称两个问题是等价的。

产生等价问题的变换包括：变量变换、目标函数与约束函数变换、松弛变量、消除等式约束、消除线性等式约束、引入等式约束、优化部分变量、上境图问题形式、隐式与显示约束。

变量变换

$\phi :R^n\rightarrow R^n$ 是一一映射，其像包含定义域D，即 $\phi(dom \phi)\supseteq D$ ，定义函数 $\tilde{f_i}(z)=f_i(\phi(z)),i=0,\cdots m,\tilde{h_i}(z)=h_i(\phi(z)),i=1,\cdots p,$

那么问题变为：

$\begin{array}{ll} \operatorname{minimize} & \tilde{f}_{0}(z) \\ \text { subject to } & \tilde{f}_{i}(z) \leqslant 0, \quad i=1, \cdots, m \\ & \tilde{h}_{i}(z)=0, \quad i=1, \cdots, p \end{array}$

目标函数与约束函数变换

$\varphi _0:R\rightarrow R$ 单增， $\varphi _1,\varphi_2\cdots \varphi_m:R\rightarrow R$ 满足当且仅当 $u\leq 0$ 时， $\varphi _i(u)\leqslant 0$ ， $\varphi _{m+1},\varphi_{m+2}\cdots \varphi_{m+p}:R\rightarrow R$ 满足当且仅当 u= 0 时， $\varphi _i(u)=0$ ，则定义函数：

$\tilde{f_i}(x)=\varphi _i(f_i(x)),i=0,\cdots m,\tilde{h_i}(x)=\varphi _{m+i}(h_i(x)),i=1,\cdots p$

那么问题变为：

$\begin{array}{ll} \operatorname{minimize} & \tilde{f}_{0}(x) \\ \text { subject to } & \tilde{f}_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & \tilde{h}_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

松弛变量

$f_{i}(x) \leqslant 0$ 等价为 $\exists s_{i} \geqslant 0\Rightarrow f_{i}(x)+s_{i}=0$

那么问题变为：

$\begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & s_{i} \geqslant 0, \quad i=1, \cdots, m \\ & f_{i}(x)+s_{i}=0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

消除等式约束

利用参数 $z\in R^k$ 来显示地参数化等式约束 $h_i(x)=0,i=1,\cdots p$ ，设函数 $\phi :R^k\rightarrow R^n$ 满足：x满足等式约束等价于存在一些 $z\in R^k$ 使得， $x=\phi (z)$ ，于是问题变为：

$\begin{array}{ll} \operatorname{minimize} & \tilde{f}_{0}(z)=f_{0}(\phi(z)) \\ \text { subject to } & \tilde{f}_{i}(z)=f_{i}(\phi(z)) \leqslant 0, \quad i=1, \cdots, m \end{array}$

消除线性等式约束

如果等式约束均是线性的，即 A x=b ，那么可以更清晰地描述消除变量的过程，并且简单地进行数值计算。如果 A x=b 不相容，即 $b \notin \mathcal{R}(A)$ ，那么原问题无可行解。假设不是这种情况，令 x_0 表示等式约束的任意可行解。令 $F \in \mathbf{R}^{n \times k}$ 为满足 $\mathcal{R}(F)=\mathcal{N}(A)$ 的矩阵，那么线性方程 A x=b 的通解可以表示为 $F z+x_{0}$ ，其中 $z \in \mathbf{R}^{k}$ 。(我们可以选择F为满秩矩阵，如此的话，我们有 $k=n-\operatorname{rank} A$ )

将 $x=F z+x_{0}$ 代入原问题可以得到关于z的问题：

$\begin{array}{ll} \operatorname{minimize} & f_{0}\left(F z+x_{0}\right) \\ \text { subject to } & f_{i}\left(F z+x_{0}\right) \leqslant 0, \quad i=1, \cdots, m \end{array}$

它与原问题等价，不含有等式约束并且减少了rankA个变量。

引入等式约束

考虑这样的问题：

$\begin{array}{ll} \operatorname{minimize} & f_{0}\left(A_{0} x+b_{0}\right) \\ \text { subject to } & f_{i}\left(A_{i} x+b_{i}\right) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

其中 $x \in \mathbf{R}^{n}, A_{i} \in \mathbf{R}^{k_{i} \times n}, f_{i}: \mathbf{R}^{k_{i}} \rightarrow \mathbf{R}$ 。引入 $y_{i} \in \mathbf{R}^{k_{i}}$ 及 $y_{i}=A_{i} x+b_{i}, i=0, \cdots, m$ 从而可得到：

$\begin{array}{ll} \operatorname{minimize} & f_{0}\left(y_{0}\right) \\ \text { subject to } & f_{i}\left(y_{i}\right) \leqslant 0, \quad i=1, \cdots, m \\ & y_{i}=A_{i} x+b_{i}, \quad i=0, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

优化部分变量

我们总有： $\inf _{x, y} f(x, y)=\inf _{x} \tilde{f}(x)$ ，其中 $\tilde{f}(x)=\inf _{y} f(x, y)$ 。

因此，问题：

$\begin{array}{ll} \operatorname{minimize} & f_{0}\left(x_{1}, x_{2}\right) \\ \text { subject to } & f_{i}\left(x_{1}\right) \leqslant 0, \quad i=1, \cdots, m_{1} \\ & \tilde{f}_{i}\left(x_{2}\right) \leqslant 0, \quad i=1, \cdots, m_{2} \end{array}$

等价于：

$\begin{array}{ll} \operatorname{minimize} & \tilde{f}_{0}\left(x_{1}\right) \\ \text { subject to } & f_{i}\left(x_{1}\right) \leqslant 0, \quad i=1, \cdots, m_{1} \end{array}$

其中： $\tilde{f}_{0}\left(x_{1}\right)=\inf \left\{f_{0}\left(x_{1}, z\right) \mid \tilde{f}_{i}(z) \leqslant 0, i=1, \cdots, m_{2}\right\}$

上镜图问题形式

$\begin{array}{ll} \operatorname{minimize} & t \\ \text { subject to } & f_{0}(x)-t \leqslant 0 \\ & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array}$

无约束问题的上境图形式问题的几何解释。其目标是寻找上境图中(阴影所示)极小化t的一点，即上境图中最“低”的一点，最优点是(x*,t*)。

隐式和显式约束

上面谈到的不等式约束与等式约束被称为显式约束，他们及目标函数的定义域被称为隐式约束。

4.1.4 参数与谕示问题描述

参数问题描述：对于一个问题为确定目标函数，我们给出函数的系数。即待解决的特定问题被出现在目标和约束函数中的函数参数确定。

谕示问题描述：无法显式地知道f，但对于每个在f的定义域内的x，可以计算得到f(x)。

参考：凸优化第四章凸优化问题 4.1 优化问题

今天的文章凸优化问题的定义_如何证明一个问题是凸优化问题分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/84639.html

凸优化问题的定义_如何证明一个问题是凸优化问题

4.1 优化问题

4.1.1 基本术语

最优点和局部最优点

min VS minimize

可行性问题

4.1.2 问题的标准表示

变量变换

目标函数与约束函数变换

松弛变量

消除等式约束

消除线性等式约束

引入等式约束

优化部分变量

上镜图问题形式

隐式和显式约束

4.1.4 参数与谕示问题描述

相关推荐

发表回复