凸优化笔记

Reference

  1. Stephen Boyd.Convex Optimization
  2. 凌青老师凸优化课程

Intro

本学期非常有幸能听凌青老师讲解凸优化. 凸优化这门课分为两个部分, 一是晦涩的理论部分, 二则是算法部分. 凌青老师能深入浅出地讲解理论, 为抽象的理论举一些具体的例子, 也穿插介绍了一些他敬佩的学者和学科历史, 虽然我们都不是很聪明, 有事跟不上他讲课, 但他都十分耐心地放缓进度. 在讲算法时, 凌青老师也会结合实际应用, 讨论算法的应用场景, 如何使用等问题. 非常感谢凌青老师!

接近结课, 翻一翻ipad发现已经做了100页A4纸的笔记, 我打算整理笔记, 一是做复习内化之用, 二是想与大家分享.

凌青老师在理论部分选取的参考书为boyd的Convex Optimization, 在算法部分则参考了另一本书.

说起来, 知道自己不可能保研, 甚至读研的可能性很小, 还这么认真地学这门课, 这是为什么呢? 可能还是有些不甘心吧.

前言

说到凸优化, 就不得不说一下优化问题, 凸优化研究的对象是凸的优化问题. 这里涉及到两个概念:

  1. 何为优化问题?
  2. 什么是凸的优化问题?

这两个问题都将在前言回答, 首先谈优化问题:

优化问题

定义

从一个可行解集寻找最好的元素

这个定义有三个组成部分

  1. 可行解集
  2. 寻找
  3. 最好的元素

其中1和3确定问题, 2则为解决问题的算法.

形式

  • $f_0(x)$为目标函数/损失函数
  • $f_i(x) \leq 0$为不等式约束
  • $h_j(x)=0$为等式约束

其中$x$为$\mathbb{R}^n$上的向量, 每一个函数$f_0, f_i, h_j$都为$\mathbb{R}^n \rightarrow \mathbb{R}$的函数.

可行解集: $\{x|f_i(x)\leq 0, h_j(x)=0\}$

最优解(optimal): $x^$在可行解集中,且$\forall z, f_i(z)\leq 0, h_j(z)=0, \Rightarrow f_0(z)\geq f_0(x^)$

凸优化问题

凸优化问题即为有如下性质的优化问题:

  1. 可行解集为凸集
  2. 目标函数为凸函数

为什么我们要关注凸优化问题? 因为凸优化问题本身具有结构, 更容易解.

应用

最小二乘

神经网络

图像增强(TV范数)

1558686596525

推荐系统(低秩矩阵补全)

1558686578546

理论

凸集(Convec set)

直线与线段(Lines and line segments)

1558687988615

假设$x_1 \neq x_2$且$x_1,x_2\in\mathbb{R}^n$, 则对以下公式:

若$\theta\in[0,1]$, 则$y$形成一条线段. 若$\theta\in\mathbb{R}$, 则$y$形成一条直线.

也可以写成这种形式

仿射集(Affine sets)

一个集合$C\in\mathbb{R}^n$是仿射集(Affine sets), 当且仅当经过任意两个在$C$内的点的直线也在$C$内.

可以证明仿射集必定为凸集.

特殊情况:

  • 如果$x_1 =x_2$, 则$C=\{x_1\}$
  • $Ax=b$确定一个仿射集, 可以是$\varnothing$, ${x_1}$, 超平面

仿射组合(affine combination)

仿射包(affine hull)

一个集合的仿射包是最小的包含该集合的仿射集.

凸集(Convex sets)

1558688043091

一个集合$C\in\mathbb{R}^n$是凸集(Convex sets), 当且仅当经过任意两个在$C$内的点的线段也在$C$内.

凸组合(convex combination)

凸包(convex hull)

1558688071617

一个集合的凸包是最小的包含该集合的凸集.

凸锥(Convex cones)

1558688560015

一个集合$C\in\mathbb{R}^n$是凸锥(Convex cones), 当且仅当满足下列条件

可以证明凸锥必定为凸集

凸锥组合(conic combination)

凸锥包(convex hull)

比较

1558688768127

重要例子

超平面(Hyperplanes)

1558689462656

超平面为仿射集, 超平面形如下面集合, 其中$a\in \mathbb{R}^n,a\neq0,b\in \mathbb{R}$

这是非平凡线性组合的解集.

半空间(halfspaces)

1558689450887

半空间为凸集, 一个空间可以被超平面划分为两个半空间, 其中$a\in \mathbb{R}^n,a\neq0,b\in \mathbb{R}$

1558689514788

球(balls)

其中$r > 0$, $||\cdot||$为欧氏距离, 也可以改写为

可以证明球为凸集

设$\left|x_{1}-x_{c}\right|_{2} \leq r,\left|x_{2}-x_{c}\right|_{2} \leq r$, $0 \leq \theta \leq 1$, 则有

椭球(ellipsoids)

1558690249852

其中$P=P^{T}>0$, $P$为对称正定矩阵.

可以证明, 椭球是凸集

1558791186850

多面体(Polyhedra)

多面体是有限数量的线性等式约束和线性不等式约束的解集

保持集合凸性的操作(Operations that preserve convexity)

取交集(Intersection)

如果$S_1,S_2$都为凸集, 则$S_1\cap S_2$也为凸集

这带来了一个启发, 即线性规划的可行解集必为凸.

仿射函数(Affine functions)和逆仿射函数

如果一个函数$f:\mathbb{R}^n\Rightarrow\mathbb{R}^m$是形如$f(x)=Ax+b$的函数, 那么这个函数为仿射函数.

对于仿射函数$f$, 如果原像$S\in\mathbb{R}^n$是凸集, 那么它的像$f(S)$也是凸集.

这是因为$\theta f(x)+(1-\theta)f(y)=f[\theta x+(1-\theta)x]$, 所以$\forall f(x),f(y)\in f(S),\rightarrow f[\theta x+(1-\theta)x]\in f(S)$

对于逆仿射函数$f^{-1}$也有保凸性, 换句话说, 如果仿射函数$f$的像为凸集, 那么它的原像也为凸集.

因为$f^{-1}(S)=\bigcap\limits_{y}^{y\in S}\{x|Ax+b=y\}$, 本质上为多个超平面的交集

缩放和平移(scaling and translation)

投影(projection)

一个凸集在局部维度下的投影为凸集.

即如果$S\subseteq \mathbb{R}^m\times \mathbb{R}^n$, 那么有

易证

笛卡尔积(direct product)

加和(sum)

两个集合的和定义为

首先我们知道$S_1\times S_2$为凸集, 我们还知道仿射函数保持凸性, 那么我们可以构造:

显然先进行笛卡尔积, 再用两个单位矩阵构造出$A$进行$b=0$的仿射变换.

透视函数(The perspective function)

定义透视函数$P:\mathbb{R}^{n+1}\rightarrow \mathbb{R}^n$, 定义域为$P=\mathbb{R}^n\times \mathbb{R}_{++}$, $P(z,t)=z/t$($\mathbb{R}_{++}=\{x|x>0\}$).

我们有, 当$C\subseteq P$为凸集时, 它的像

也为凸集.

逆透视函数

一个凸集在透视函数下的原像也为凸集:

如果凸集$C\in\mathbb{R}^n$, 那么有

设$(x, t) \in P^{-1}(C),(y, s) \in P^{-1}(C)$, $0 \leq \theta \leq 1$, 有

因为

线性分式函数(Linear-fractional functions)

线性分式函数是由透视函数和仿射函数组合而成的, 设仿射函数$g:\mathbb{R}^n\rightarrow\mathbb{R}^{m+1}$, 其中$A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{m}, c \in \mathbf{R}^{n},d \in \mathbf{R}$

那么线性分式函数可以定义为$f=P \circ g$:

保凸性易证

凸函数(Convex functions)

基本属性(Basic properties)

基本定义(basic definition)

1558753235532

一个函数$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是凸函数, 仅当$\mathbf{dom} f$是凸集且$\forall x,y\in \mathbf{dom}f$, $0\leq \theta\leq 1$我们有:

一个函数$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是严格凸函数, 仅当$\mathbf{dom} f$是凸集且$\forall x,y\in \mathbf{dom}f$, $0<\theta< 1$我们有:

高维定义

若$f:\mathbf{R}^n\rightarrow \mathbf{R}$为凸函数, 则与以下命题等价

  1. $\mathbf{dom}f$为凸集

即将$\mathbf{dom}f$截出一条线, 在这个线上观察$f$的性质

微商定义(First-order conditions)[?]

如果函数$f$可微, 那么如果函数为凸函数当且仅当$\mathbf{dom}f$为凸集且:

如果函数$f$可微, 那么如果函数为严格凸函数当且仅当$\mathbf{dom}f$为凸集且:

1558791256231

Hessian矩阵定义(Second-order conditions)

假设$f$是二阶可微的, 那么$f$是凸函数当且仅当$\mathbf{dom}f$是凸集且:

1558791273087

凸函数拓展(Extended-value extensions)

我们可以很方便地将一个凸函数的定义域拓展到整个空间:

集合的示性函数

经典示例(Examples)

Log-sum-exp

1558754678445

这个函数是凸函数, 而且具有很好的性质, 可以看做是$\mathbf{max}$的可微近似

1558754860516

Log-derterminant

函数$f(X)=\operatorname{log}\operatorname{det}{X}$是在$\mathbf{dom}f=S_{++}^{n}$上的凸函数

1558755010284

保持函数凸性的操作(Operations that preserve convexity)

仿射映射(affine maSpping)

设: $f:\mathbf{R}^n\rightarrow \mathbf{R}$, $A\in \mathbf{R}^{n\times m}$, $b\in \mathbf{R}^n$. 定义$g:\mathbf{R}^m\rightarrow\mathbf{R}$:

如果$f$是凸函数, 则$g$也是凸函数

  1. 定义域为凸, 由逆仿射映射保持集合凸性
  2. $\theta g(x)+(1-\theta)g(y)\geq g(\theta x+(1-\theta)y)$

极大值函数(pointwise maximum)

如果$f_1,f_2$均为凸函数, 则它们的极大值函数$f$也为凸函数

任取$0\leq \theta \leq 1$, $x,y\in \mathbf{dom}f$

第2个公式到第三个公式是因为

应用例子

  1. 分段线性函数(Piecewise-linear functions)

显然这也是凸函数, 而且任意分段线性凸函数, 都可以被表示为这种形式.

  1. Sum of r largest components

对于$x\in\mathbf{R}^n$, 设$x_{[i]}$为第$i$大的$x$中的分量

所以设函数$f$为

这个函数也是凸的

将$x$中$n$个分量任选$r$个分量视为不同种组合, 每个组合的和都可以视为是仿射函数, 则对所有仿射函数取最大值, 必然产生凸函数.

  1. 无穷的情况(extends to the pointwise supremum)

极大值函数可以推广到无穷的情况, 比如:

设$f$对$x$为凸函数

则, $g$也为凸函数

  1. 点到集合到距离(Distance to farthest point of a set)

由无穷情况的极大值保凸性, 可以得知, 因为范数为凸函数

非负加权和(Nonnegative weighted sums)

设$\omega_i \geq 0$, $f_i$为凸函数, 则:

$f$为凸函数

因为$\omega_if_i$为凸函数, 而凸函数之和仍然为凸函数.

这个可以拓展到无穷的情况, 即:

extend to infinite sums and integrals

设$f(x,y)$是关于$x$的凸函数, 且$y \in \mathcal{A}$. 而且对每个$y \in \mathcal{A}$有$\omega(y)\geq 0$, 则$g(x)$为凸函数:

函数的组合Composition

1
2
3
4
f is convex if h is convex and nondecreasing, and g is convex,
f is convex if h is convex and nonincreasing, and g is concave,
f is concave if h is concave and nondecreasing, and g is concave,
f is concave if h is concave and nonincreasing, and g is convex.
1
2
3
4
f is convex if h is convex, h̃ is nondecreasing, and g is convex,
f is convex if h is convex, h̃ is nonincreasing, and g is concave,
f is concave if h is concave, h̃ is nondecreasing, and g is concave,
f is concave if h is concave, h̃ is nonincreasing, and g is convex.

例题

  1. $e^{g(x)}, \log{g(x)},\frac{1}{g(x)}$

  2. 该函数既不凸也不凹

函数的透视Perspective of a function

如果$f:\mathbf{R}^n\rightarrow \mathbf{R}$, 那么该函数的透视为$g:\mathbf{R}^{n+1}\rightarrow\mathbf{R}$

这里$g(x,t)$相对于$(x,y)$联合凸

例子

拟凸函数(Quasiconvex functions)与alpha次水平集

一个函数$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$称为拟凸函数, 如果它的定义域和所有次水平集都是凸集.

次水平集(sublevel set)

1558767991568

凸优化问题(Convex optimization problems)

优化问题(Optimization problems)的基本术语(Basic terminology)

域(domain): 目标函数和约束函数的定义域的交集

可行解集(feasible set): 在域中满足约束的x组成的集合

最优值(optimal value)

最优解(optimal point)最优解集(optimal set): 当$x^$满足约束且$f_0(x^)=p^$, 我们说$x^$是最优解

最优解集是包含所有最优解的集合.

次优解集(epsilon -suboptimal):

局部最优解(locally optimal):

设$R>0$, 则局部最优解可以定义为

或者说, 此时局部最优解为以下优化问题的最优解

注意: 局部最优解不是在一个小球内$f_0(x)$的最优解, 而是说一个小球的球心恰好是这个小球区域的最优解.

凸优化问题(Convex optimization)

标准形式(standard form)

局部最优解必定为全局最优解(Local and global optima)

这是凸函数一个非常好的性质, 正是这个性质使很多类梯度下降的优化算法能找到最优解.

用反证法来证明.

已知$x_0$为局部最优解, 设在可行解集$X$上存在一个点$x^*$使得:

因为$f(x)$是凸函数, 所以对$0\leq t\leq 1$有:

注意,这个$t$是$0$到$1$之间的任意值,所以$t$可以非常接近$0$,此时$(tx_+(1-t)x_0)$这个点就可以无限接近$x_0$,但是函数在这个点的值又比$f(x_0)$小,所以$f(x_0)$不可能是局部最小值。故假设矛盾,因此不存在这样的$x_$。$f(x_0)$必定为最小值。

最优解的充要条件(An optimality criterion for differentiable)

如果凸优化问题中目标函数$f_0$可微,如果$x=x^*$, $x\in X$

如果凸优化问题中目标函数$f_0$可微, 则对于$x,y\in \operatorname{dom} f_0$有

只需要令一个变量为最优解即可.

例题:

证明$x^{\star}=(1,1 / 2,-1)$是优化问题的最优解

其中

优化问题例子

线性规划(Linear optimization problems)

由于线性规划问题的特殊结构, 最优解必定在顶点上.

线性分式规划(Linear-fractional programming)

半正定规划(Semidefinite programming)

谱范数极小化(Matrix norm minimization)

$A(x)=A_{0}+x_{1} A_{1}+\cdots+x_{n} A_{n}$, $A_{i} \in \mathbf{R}^{p \times q}$

这个问题可以改写为

谱范数与内积的关系

最快分布式线性平均(Fastest mixing Markov chain on a graph)

多目标优化(Multicriterion optimization)

  1. 帕累托最优解

若另有一个解在某个目标更优,那么它必定在另外一个目标更差。

1558768918843

帕累托最优值

帕累托最优面

  1. 加权

1558768939891

二次规划(Quadatic optimization problems)

1558769056808

二次约束的二次规划QCQP

一范数最小化

1558769157340

岭回归

1558769164788

投资组合

1558769168542

对偶(Duality)

拉格朗日对偶函数(The Lagrange dual function)

拉格朗日函数(The Lagrangian)

考虑形式如下的优化问题

其中$x \in \mathbf{R}^{n}$, 定义域$\mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i}$, 最优值为$p^*$, 我们并不假设这是一个图问题

那么我们有以下拉格朗日函数$L : \mathbf{R}^{n} \times \mathbf{R}^{m} \times \mathbf{R}^{p} \rightarrow \mathbf{R}$, 定义域为$\operatorname{dom} L=\mathcal{D} \times \mathbf{R}^{m} \times \mathbf{R}^{p}$

其中$\lambda$和$\nu$为拉格朗日乘子, 作为变量则称为拉格朗日对偶变量, 而$x$为原变量

拉格朗日对偶函数(The Lagrange dual function)

定义拉格朗日对偶函数$g : \mathbf{R}^{m} \times \mathbf{R}^{p} \rightarrow \mathbf{R}$为:

注意到拉格朗日对偶函数为凹函数

  1. 固定$x$, $L$是$(\lambda,\nu)$的仿射函数, 故为凹函数
  2. $inf$一个凹函数, 得到凹函数

原问题最优值的下界(Lower bounds on optimal value)

我们有以下结论, 当$\lambda \succeq0$, 可以获取原问题最优值的一个下界:

因为$\widetilde{x}$是原问题的可行解, 所以有

所以拉格朗日函数满足

所以有

拉格朗日对偶问题

这是一个凹问题.

conjugate functions

考虑一个优化问题

应用例子

  1. Least-squares solution of linear equations

写出拉格朗日函数

有对偶函数

故得到下界估计

  1. 线性规划(Standard form LP)

拉格朗日函数

对偶函数为

易知

故只有${A^{T} \nu-\lambda+c=0}$及$\lambda \succeq 0$时, 对偶问题才有解.

等等! 注意到没有, 实际上这个对偶问题也是一个LP问题

只是问题的规模改变了, 我们仔细看看就有:

原问题对偶问题
变量维数nm
等式约束m0
不等式约束nn

那么, 能不能再对这个对偶问题再做一次拉格朗日对偶? 我们有

问题又变回来了.

总结: LP问题的结构特殊, 对偶之后还是LP问题, 再对偶就变回原问题. 但是, 不是所有问题都能变为原问题, 因为拉格朗日对偶将问题变为一个凹问题, 那么非凹->凹->凹, 就变不回原问题了.

  1. Two-way partitioning problem

拉格朗日函数为

对偶函数为

强对偶和弱对偶

对偶间隙(optimal duality gap): $p^-d^$

弱对偶(Weak duality)

弱对偶问题是指$d^\leq p^$的优化问题的对偶性质

强对偶(Strong duality)

弱对偶问题是指$d^= p^$的优化问题的对偶性质

一般来说判断强对偶和弱对偶的依据是:

  • 对于非凸问题, 通常$p^\neq d^$
  • 对于凸问题, 只要满足Slater条件, 就有$p^=d^$

Slater’s condition

$relint$其实就是找集合的内点.

slater条件用于判断问题是否具有强对偶性, 是充分条件.

  1. 问题为凸问题

例子

对偶解释

Weak and strong duality via set of values

1558783646819

几何解释

1558783450752

经济学解释(Price or tax interpretation)

多目标优化解释(Multicriterion interpretation)

相当于$\min{f_0+\sum\lambda_if_i}$

鞍点解释(Saddle-point interpretation)[?]

极小最大不等式(Max-min characterization)

鞍点(Saddle-point)

1558784500472

当点对$\tilde{w} \in W, \tilde{z} \in Z$满足下列条件时, 称为鞍点

其中

1558784584222

KKT条件(optimality conditions)[?]

必要条件

  1. (primal feasibility)
  1. (dual feasibilitydual feasibility)
  1. 互补松弛条件(complementary slackness)
  1. 微分

充要条件

1558785992743

例子

Water-filling

1558786794121

敏感性分析(Perturbation and sensitivity analysis)

出发点:研究调参影响

干扰问题(The perturbed problem)

1558786967373

When the original problem is convex, the function p⋆is a convex function of u and v;

1558786972263

A global inequality

1558787003056

观察知为泰勒展开

敏感性分析(Local sensitivity analysis)

1558787062327

1558787067846

例子

1558787072130

1558787093932

算法(Algorithm)

优化算法的特点

所有的算法都是迭代的

优化算法的迭代形式是

其中$\alpha^k$是步长, $d^k$是方向

如何选择步长

  • 确定步长

    • 固定步长
    • 变化步长(一般递减)
  • 搜索步长(代价高)

    • 最优步长

    • 线搜索
      可以用黄金分割法, 一般迭代三四次就可以
      1558788116871

    • 不精确线搜索
      可以用Armijo Rule
      1558788164043

如何选择方向

优化算法分析

关注问题

  • 能否收敛
  • 收敛位置
  • 收敛速度

假设

基本假设

目标函数为可微凸函数,最小值和最优解有限

次要假设

  1. lipschitz连续梯度(lipschitz continuous gradient)
    1558788343415
  2. 强凸(strong convex)
    1558788353802

无约束优化算法

对于光滑(可微)优化问题, 我们用梯度下降法求解. 对于非光滑优化问题, 我们使用次梯度法或邻近点投影法求解.

光滑优化问题: $f_0$连续, 凸, 可微

非光滑优化问题: $f_0$连续, 凸, 不可微, 最优解满足$0 \in \partial f_{0}(x)$

梯度下降法(Gradient descent method)

1558789361068

步长可调节, 方向为$-\nabla f\left(x^{k}\right)$.

梯度下降法尽量不选递减步长, 虽然一定收敛到最优, 但慢.

解释

步长

1558789994622

方向

1558790005512

固定步长, 有lipschitz连续梯度

1558789457107

此时收敛速度为$O(\frac{1}{n})$

1558789588281

如何调节步长?

1558789603224

lipschitz连续梯度, 强凸

1558789670404

步长不能随意变化, 因为

1558789721830

速度分析

1558789745390

注意到是对条件数敏感的, 解决方法可以是将$H$变为单位矩阵, 和选择牛顿方向

精确线搜索, lipschitz, 强凸

1558789861452

不精确线搜索

1558789881836

次梯度法(sub gradient method)

1558790195375

次梯度(sub gradient)

次梯度是一个集合

1558790243971

步长

  • 固定步长
  • 变化步长
    • 不可加平方不可加
    • 不可加平方可加

假设

函数lipschitz连续

1558790350113

分析

收敛性与收敛速度

1558790372701

1558790405463

邻近点投影法()

次梯度法性能不好

假设

1558790461452

迭代方法

1558790477824

邻近点投影

1558790590976

例子

  1. lasso解法

1558790509904

  1. 梯度投影法(box constrained optimization)

1558790551714

  1. 矩阵补全

1558790623758

牛顿法(Newton’s method)

1558790680834

假设

  • 海参矩阵正定-强凸
  • 二阶lipschitz梯度连续

分析

1558790726364

问题

计算$\nabla^{2} f_{0}(x)$用时$O(n^2)$, $A^{-1}$用时$O(n^3)$

例子

1558790828880

拟牛顿法(quasi newton method)

1558790867723

有约束优化算法

约束满足牛顿法

1558790886297

拉格朗日乘子法/对偶分解法

1558790896262

原对偶梯度法

1558790914298

增广拉格朗日法

1558790923866

简单例子

1558790948140

非凸例子

1558790958527

交替方向乘子法

1558790972508

例子

1558790985223

特殊情形的优化算法

并行优化

1558791012170

无中心分布式优化

1558791023156

大数据及人工智能中的优化问题及算法

1558791037523

方差消减

1558791045548

  1. SURG

1558791053117

  1. SAG

1558791059575

深度学习

1558791076486

在线优化

1558791137284

动态优化

1558791149043

文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. 前言
    1. 3.1. 优化问题
      1. 3.1.1. 定义
      2. 3.1.2. 形式
      3. 3.1.3. 凸优化问题
    2. 3.2. 应用
      1. 3.2.1. 最小二乘
      2. 3.2.2. 神经网络
      3. 3.2.3. 图像增强(TV范数)
      4. 3.2.4. 推荐系统(低秩矩阵补全)
  4. 4. 理论
    1. 4.1. 凸集(Convec set)
      1. 4.1.1. 直线与线段(Lines and line segments)
      2. 4.1.2. 仿射集(Affine sets)
      3. 4.1.3. 凸集(Convex sets)
      4. 4.1.4. 凸锥(Convex cones)
      5. 4.1.5. 比较
      6. 4.1.6. 重要例子
        1. 4.1.6.1. 超平面(Hyperplanes)
        2. 4.1.6.2. 半空间(halfspaces)
        3. 4.1.6.3. 球(balls)
        4. 4.1.6.4. 椭球(ellipsoids)
        5. 4.1.6.5. 多面体(Polyhedra)
      7. 4.1.7. 保持集合凸性的操作(Operations that preserve convexity)
        1. 4.1.7.1. 取交集(Intersection)
        2. 4.1.7.2. 仿射函数(Affine functions)和逆仿射函数
        3. 4.1.7.3. 缩放和平移(scaling and translation)
        4. 4.1.7.4. 投影(projection)
        5. 4.1.7.5. 笛卡尔积(direct product)
        6. 4.1.7.6. 加和(sum)
        7. 4.1.7.7. 透视函数(The perspective function)
        8. 4.1.7.8. 逆透视函数
        9. 4.1.7.9. 线性分式函数(Linear-fractional functions)
    2. 4.2. 凸函数(Convex functions)
      1. 4.2.1. 基本属性(Basic properties)
        1. 4.2.1.1. 基本定义(basic definition)
        2. 4.2.1.2. 高维定义
        3. 4.2.1.3. 微商定义(First-order conditions)[?]
        4. 4.2.1.4. Hessian矩阵定义(Second-order conditions)
        5. 4.2.1.5. 凸函数拓展(Extended-value extensions)
      2. 4.2.2. 经典示例(Examples)
        1. 4.2.2.1. Log-sum-exp
        2. 4.2.2.2. Log-derterminant
      3. 4.2.3. 保持函数凸性的操作(Operations that preserve convexity)
        1. 4.2.3.1. 仿射映射(affine maSpping)
        2. 4.2.3.2. 极大值函数(pointwise maximum)
        3. 4.2.3.3. 非负加权和(Nonnegative weighted sums)
        4. 4.2.3.4. 函数的组合Composition
        5. 4.2.3.5. 函数的透视Perspective of a function
      4. 4.2.4. 拟凸函数(Quasiconvex functions)与alpha次水平集
    3. 4.3. 凸优化问题(Convex optimization problems)
      1. 4.3.1. 优化问题(Optimization problems)的基本术语(Basic terminology)
      2. 4.3.2. 凸优化问题(Convex optimization)
        1. 4.3.2.1. 标准形式(standard form)
        2. 4.3.2.2. 局部最优解必定为全局最优解(Local and global optima)
        3. 4.3.2.3. 最优解的充要条件(An optimality criterion for differentiable)
      3. 4.3.3. 优化问题例子
        1. 4.3.3.1. 线性规划(Linear optimization problems)
        2. 4.3.3.2. 线性分式规划(Linear-fractional programming)
        3. 4.3.3.3. 半正定规划(Semidefinite programming)
        4. 4.3.3.4. 谱范数极小化(Matrix norm minimization)
        5. 4.3.3.5. 最快分布式线性平均(Fastest mixing Markov chain on a graph)
        6. 4.3.3.6. 多目标优化(Multicriterion optimization)
        7. 4.3.3.7. 二次规划(Quadatic optimization problems)
        8. 4.3.3.8. 二次约束的二次规划QCQP
        9. 4.3.3.9. 一范数最小化
        10. 4.3.3.10. 岭回归
        11. 4.3.3.11. 投资组合
    4. 4.4. 对偶(Duality)
      1. 4.4.1. 拉格朗日对偶函数(The Lagrange dual function)
        1. 4.4.1.1. 拉格朗日函数(The Lagrangian)
        2. 4.4.1.2. 拉格朗日对偶函数(The Lagrange dual function)
        3. 4.4.1.3. 原问题最优值的下界(Lower bounds on optimal value)
        4. 4.4.1.4. 拉格朗日对偶问题
        5. 4.4.1.5. conjugate functions
        6. 4.4.1.6. 应用例子
      2. 4.4.2. 强对偶和弱对偶
        1. 4.4.2.1. 弱对偶(Weak duality)
        2. 4.4.2.2. 强对偶(Strong duality)
        3. 4.4.2.3. Slater’s condition
      3. 4.4.3. 对偶解释
        1. 4.4.3.1. Weak and strong duality via set of values
        2. 4.4.3.2. 几何解释
        3. 4.4.3.3. 经济学解释(Price or tax interpretation)
        4. 4.4.3.4. 多目标优化解释(Multicriterion interpretation)
        5. 4.4.3.5. 鞍点解释(Saddle-point interpretation)[?]
      4. 4.4.4. KKT条件(optimality conditions)[?]
        1. 4.4.4.1. 必要条件
        2. 4.4.4.2. 充要条件
        3. 4.4.4.3. 例子
      5. 4.4.5. 敏感性分析(Perturbation and sensitivity analysis)
        1. 4.4.5.1. 干扰问题(The perturbed problem)
        2. 4.4.5.2. A global inequality
        3. 4.4.5.3. 敏感性分析(Local sensitivity analysis)
  5. 5. 算法(Algorithm)
    1. 5.1. 优化算法的特点
      1. 5.1.1. 所有的算法都是迭代的
      2. 5.1.2. 如何选择步长
      3. 5.1.3. 如何选择方向
    2. 5.2. 优化算法分析
      1. 5.2.1. 关注问题
      2. 5.2.2. 假设
        1. 5.2.2.1. 基本假设
        2. 5.2.2.2. 次要假设
    3. 5.3. 无约束优化算法
      1. 5.3.1. 梯度下降法(Gradient descent method)
        1. 5.3.1.1. 解释
        2. 5.3.1.2. 固定步长, 有lipschitz连续梯度
        3. 5.3.1.3. lipschitz连续梯度, 强凸
        4. 5.3.1.4. 精确线搜索, lipschitz, 强凸
        5. 5.3.1.5. 不精确线搜索
      2. 5.3.2. 次梯度法(sub gradient method)
        1. 5.3.2.1. 次梯度(sub gradient)
        2. 5.3.2.2. 步长
        3. 5.3.2.3. 假设
        4. 5.3.2.4. 分析
      3. 5.3.3. 邻近点投影法()
        1. 5.3.3.1. 假设
        2. 5.3.3.2. 迭代方法
        3. 5.3.3.3. 邻近点投影
        4. 5.3.3.4. 例子
      4. 5.3.4. 牛顿法(Newton’s method)
        1. 5.3.4.1. 假设
        2. 5.3.4.2. 分析
        3. 5.3.4.3. 问题
        4. 5.3.4.4. 例子
      5. 5.3.5. 拟牛顿法(quasi newton method)
    4. 5.4. 有约束优化算法
      1. 5.4.1. 约束满足牛顿法
      2. 5.4.2. 拉格朗日乘子法/对偶分解法
      3. 5.4.3. 原对偶梯度法
      4. 5.4.4. 增广拉格朗日法
        1. 5.4.4.1. 简单例子
        2. 5.4.4.2. 非凸例子
      5. 5.4.5. 交替方向乘子法
        1. 5.4.5.1. 例子
    5. 5.5. 特殊情形的优化算法
      1. 5.5.1. 并行优化
      2. 5.5.2. 无中心分布式优化
      3. 5.5.3. 大数据及人工智能中的优化问题及算法
        1. 5.5.3.1. 方差消减
        2. 5.5.3.2. 深度学习
        3. 5.5.3.3. 在线优化
        4. 5.5.3.4. 动态优化
|