EE364A Lecture 5 and Lecture 6

课程主页:https://see.stanford.edu/Course/EE364A

这次回顾凸优化第五,第六讲,这部分介绍了凸优化问题。

Lecture 5 and Lecture 6 Convex optimization problems

优化问题的标准形式

  • $x \in \mathbf{R}^{n}$为优化变量
  • $f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为目标或损失函数
  • $f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, i=1, \dots, m$,为不等式约束
  • $h_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为等式约束

最优值

  • 如果问题是不可行(没有$x$满足约束),那么$p^{\star}=\infty$
  • 如果问题无下界,那么$p^{\star}=-\infty$

最优和局部最优点

$x$是可行的,如果$x \in \operatorname{dom} f_{0}$并且满足约束。

一个可行的$x$是最优的,如果$f_{0}(x)=p^{\star}$;$X_{\mathrm{opt} }$是最优点构成的集合。

$x$是局部最优的,如果存在$R>0$,使得$x$为满足如下条件的最优点:

例子($n=1, m=p=0$)

  • $f_{0}(x)=1 / x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=0$,无最优点
  • $f_{0}(x)=-\log x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=-\infty$
  • $f_{0}(x)=x \log x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=-1 / e$,$x=1/e$最优
  • $f_{0}(x)=x^{3}-3 x, p^{\star}=-\infty$,在$x=1$局部最优

隐式约束

标准优化问题有隐式约束

  • 我们称$\mathcal D$维问题的定义域
  • 约束$f_{i}(x) \leq 0, h_{i}(x)=0$为显式约束
  • 一个问题是无约束的,如果没有显示约束($m=p=0$)

例子:

上述问题为无约束问题,隐式约束为$a_{i}^{T} x<b_{i}$

可行性问题

上述问题可以被看出一般问题的特殊情形, 其中$f_0 (x)=0$:

  • $p^{\star}=0$如果约束可行;任何可行的$x$都是最有
  • $p^{\star}=\infty$如果约束不可行

凸优化问题

标准凸优化问题:

  • $f_{0}, f_{1}, \ldots, f_{m}$为凸函数;等式约束为仿射
  • 问题是拟凸的,如果$f_0$拟凸(并且$f_{1}, \ldots, f_{m}$凸)

上述问题常写成

重要性质:凸优化问题的可行解为凸集。

例子:

  • $f_0$是凸集;可行集$\left\{\left(x_{1}, x_{2}\right) | x_{1}=-x_{2} \leq 0\right\}$是凸集

  • 不是凸优化问题:$f_1$非凸,$h_1$不是仿射函数

  • 等价于如下凸优化问题

局部和全局最优

凸优化问题的局部最优点为(全局)最优。

证明:假设$x$局部最优,$y$是最优点并且$f_{0}(y)<f_{0}(x)$

$x$局部最优意味着存在$R>0$,使得

考虑$z=\theta y+(1-\theta) x$,$\theta=R /\left(2|y-x|_{2}\right)$

  • $|y-x|_{2}>R$,所以$0<\theta<1 / 2$

  • $z$是两个可行点的凸组合,因此也是可行的

  • $|z-x|_{2}=\theta| x-y | =\frac R 2$并且

    这就与$x$局部最优矛盾

可微$f_0$的最优判别条件

$x$是最优的当且仅当其可行,并且

如果非零,$\nabla f_{0}(x)$定义了可行集合$X$在$x$的支撑超平面。

  • 无约束问题:$x$是最优的当且仅当

  • 等式约束问题

    $x$最优当且仅当存在$\nu$使得

  • 关于非负条件最小化

    $x$最优当且仅当

等价凸优化问题

两个问题等价当且仅当解相同。

一些变换保凸:

  • 消除等式约束

    等价于

    其中$F$和$x_0$满足

  • 引入等式约束

    等价于

  • 对线性不等式引入松弛变量

    等价于

  • 上镜图:标准凸优化问题等价于

  • 关于某些变量最小化

    等价于

    其中$\tilde{f}_{0}\left(x_{1}\right)=\inf _{x_{2} } f_{0}\left(x_{1}, x_{2}\right)$

拟凸优化问题

其中$f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$拟凸,$f_{1}, \ldots, f_{m}$凸。这时可能存在局部最优点不是全局最优点。

$f_0$的下水平集表示:

如果$f_0$是拟凸函数,那么存在一族函数$\phi_t$使得:

  • 对固定的$t$,$\phi_t(x)$关于$x$是凸函数

  • $f_0$的$t$下水平集是$\phi_t$的$0$水平集,即

例子

$p$为凸,$q$为凹,以及在$\operatorname{dom} f_{0}$上有$p(x) \geq 0, q(x)>0$。

可以取$\phi_{t}(x)=p(x)-t q(x)$:

  • 对$t\ge 0$,$\phi_t $关于$x$为凸集
  • $p(x) / q(x) \leq t$当且仅当$\phi_{t}(x) \leq 0$

拟凸优化问题可以通过二分法求解。

线性规划(LP)

考虑线性规划问题

线性规划问题为

  • 目标函数以及约束函数为仿射函数的凸优化问题
  • 可行集为多面体
例子

分段线性最小化

等价于LP

多面体的切比雪夫中心

多面体

的切比雪夫中心为最大内切球的中心

  • $a_{i}^{T} x \leq b_{i}$对所有$x\in \mathcal B$当且仅当

  • 因此$x_c, r$可以通过求解LP来决定

线性分式规划

依然考虑优化问题

线性分式规划

  • 该问题是拟凸优化问题;可以通过二分法求解

  • 该问题等价于LP(变量为$y,z$)

广义线性分式规划

该问题依然是拟凸优化问题;可以通过二分法求解。

二次规划(QP)

  • $P \in \mathbf{S}_{+}^{n}$,所以目标函数为凸二次函数
  • 在多面体上最小化凸二次函数
例子

最小二乘法

  • 解析解$x^{\star}=A^{\dagger} b$($A^{\dagger}$是伪逆)
  • 可以增加线性约束

二次约束二次规划(QCQP)

  • $P_i \in \mathbf{S}_{+}^{n}$,所以目标函数和约束为凸二次函数
  • 如果$P_{1}, \ldots, P_{m} \in \mathbf{S}_{++}^{n}$,可行区域为$m$个椭球以及仿射集合的交集

二阶锥规划(SOCP)

其中$\left(A_{i} \in \mathbf{R}^{n_{i} \times n}, F \in \mathbf{R}^{p \times n}\right)$

  • 不等式被称为二阶锥约束:

  • 如果$n_i =0$,那么问题退化为LP;如果$c_i =0$,问题退化为QCQP

鲁棒线性规划

优化问题中的参数通常有不确定性,例如在LP中

$c,a_i, b_i$可能有不确定性。

两种处理不确定性的常见方法(以$a_i$为例):

  • 确定性模型:约束对所有$a_{i} \in \mathcal{E}_{i}$成立

  • 随机模型:$a_i$是随机变量;约束以$\eta$的概率成立

通过SOCP处理确定性模型

  • 选择$\mathcal E _i$为椭球:

    中心为$\bar a_i$,半轴由$P_i$的奇异值决定

  • 鲁棒LP

    等价于SOCP

    上述事实是因为

通过SOCP处理随机模型

  • 假设$a_{i} \sim \mathcal{N}\left(\bar{a}_{i}, \Sigma_{i}\right)$

  • 那么$a_i^T x\sim \mathcal N(\bar a_i^T x, x^T \Sigma_i x)$,因此

  • 鲁棒LP

    其中$\eta \ge 1/ 2$等价于SOCP

几何规划

单项式函数

其中$c>0, \alpha_i \in \mathbf R$

多项式函数

几何规划(GP)

其中$f_i $是多项式,$h_i$是单项式

凸形式的几何规划

令$y_i =\log x_i$,那么

  • 单项式$f(x)=c x_{1}^{a_{1} } \cdots x_{n}^{a_{n} }$转换成

  • 多项式$f(x)=\sum_{k=1}^{K} c_{k} x_{1}^{a_{1 k} } x_{2}^{a_{2 k} } \cdots x_{n}^{a_{n k} }$转换成

  • 几何规划转换成凸问题

本文标题:EE364A Lecture 5 and Lecture 6

文章作者:Doraemonzzz

发布时间:2019年09月02日 - 23:13:00

最后更新:2019年09月09日 - 20:39:08

原始链接:http://doraemonzzz.com/2019/09/02/EE364A Lecture 5 and Lecture 6/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。