最优化方法_Part1

第一讲 最优化问题概述

1.1 什么是最优化问题

最优化问题是决策问题，选择一些可以执行的策略来使得目标最优，一个最优化问题包括：

• 决策变量
• 一个或多个目标函数
• 一个由可行策略纽成的集合，可由等式或者不等式刻画

1.2 基本形式

(一) 视频中的形式

$$\begin{cases}\text { min or max } & f(\boldsymbol x) \\ \text{ s.t.} & g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m \\ & h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l\end{cases}$$

其中，$\boldsymbol x = (x_1, x_2, \cdots, x_n)^{\mathrm T} \in \boldsymbol X$是决策变量，$\boldsymbol X$表示给定的集合，比如$\mathbb{R}_+^n、 \mathbb{Z}n$等。

• $f(\boldsymbol x)$即目标函数，$g_i(\boldsymbol x) \leq 0, h_i(\boldsymbol x)=0$分别为不等式约束和等式约束
• 集合$\boldsymbol S = \begin{Bmatrix} \boldsymbol x \in X \mid g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m, h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l \end{Bmatrix}$称为最优化问题的可行集(可行域)

(二) 参考其他文献的形式

$$\begin{cases}\text { min } & f(\boldsymbol x) \\ \text{ s.t.} & \boldsymbol x \in \mathcal{X} \end{cases}$$

其中，$\boldsymbol x = (x_1, x_2, ··· , x_n)^{\mathrm T} ∈ \mathbb{R}^n ​$是决策变量，$f : \mathbb{R}^n → \mathbb{R}​$ 是目标函数，$\mathcal{X} ⊆ \mathbb{R}^n​$是约束集合或可行域，可行域包含的点称为可行解或可行点。记号 s.t.是 “subject to”的缩写，专指约束条件。当$\mathcal{X} = \mathbb{R}^n​$时，上式称为无约束优化问题。集合$\mathcal{X}​$通常可以由约束函数$c_i( \boldsymbol x): \mathbb{R}^n → \mathbb{R} ,i = 1, 2,··· ,m + l ​$表达为如下具体形式：

$$\begin{aligned} \mathcal{X}=\left\{x \in \mathbb{R}^{n} \mid c_{i}(x) \leqslant 0,\right.& i=1,2, \cdots, m \\ c_{i}(x)=0, &i=m+1, m+2 \cdots, m+l\} \end{aligned}$$

参考资料1：课本——最优化：建模、算法与理论

参考资料2：最优化问题简介 - jbb0523 - CSDN

1.3 最优化问题分类

(一) 无约束优化/约束优化

• 无约束优化问题：没有约束条件
  • 常见求解方法：梯度下降法(最速下降法)、牛顿法、共轭梯度法等等
• 约束优化问题：在一定约束条件下求解目标函数的min OR max

易知，实际中最碰见的是约束优化问题，但是我们在课程中却要大量研究无约束优化问题，这个有两方面的原因：一是无约束优化问题求解相对简单；二是可以通过一定的变换将有约束转变为无约束优化。

(二) 线性/非线性优化

• 线性优化问题的一般形式

$$\begin{cases}\text { min } & \boldsymbol{Cx} \\ \text{ s.t.} & \boldsymbol{Ax = b}\end{cases}$$

单纯形方法：在数学优化领域中常用于线性规划问题的数值求解。由线性规划问题的可行集的特征来决定的(线性规划最优解存在时，那么最优解一定存在与问题可行集的顶点位置)，单纯性方法就是关注这些顶点。

参考资料：单纯形算法

• 非线性优化(例子说明)：均值-方差模型

(三) 连续优化/离散优化

• 连续优化：$\boldsymbol x = (x_1, x_2, \cdots, x_n)^{\mathrm T} \in \boldsymbol X$中每一个$x_n$的取值是连续的
• 离散优化：$\boldsymbol x = (x_1, x_2, \cdots, x_n)^{\mathrm T} \in \boldsymbol X$中每一个$x_n$的取值是离散的，比如$0-1$规划

(四) 单目标优化/多目标优化

• 单目标优化
• 多目标优化(均值-方差模型)常采用的办法：
  • 法1：转化为单目标，即可以将某些目标经过一定形式转化到约束条件中去。
  • 法2：想办法将多个目标融合为单个目标

(五) 动态规划

(六) 随机规划

参数中有不确定系数的优化问题。

(七) 鲁棒优化

1.4 最优化方法主要讲解内容

• 凸优化理论：凸集，凸函数，凸优化问题；
• 无约束优化问题的算法；
• 约束优化的最优性条件及对偶理论；
• 线性规划、二次规划算法；
• 约束优化的罚函数方法；
• 优化软件：CVX，CPLEX

1.5 预备知识

• 向量、矩阵、二次型等知识；
• 微积分知识；
• 简单的概率知识。

课后小问题：

• $n$元二次函数$f(\boldsymbol x)=\boldsymbol x^{\mathrm T} \boldsymbol H \boldsymbol x ＋\boldsymbol c^{\mathrm T} \boldsymbol x$,其中$\boldsymbol H$为$n$阶对称矩阵，$\boldsymbol c$为$n$维向量；给出$f(\boldsymbol x)$的梯度和hesse炬阵?
• 设随机向量服从联合正态分布：$\epsilon = (\epsilon_1, \epsilon_2, \cdots, \epsilon_n) \sim N(\mu, \sigma^2)$，令$η = x_1\epsilon_1 + \cdots + x_n\epsilon_n$，给出$η$的$c$分位数。

第二讲 凸集

在最优化范畴里面，凸优化问题是一类常见的且性质很好的(很多时候可以帮助我们解决非凸优化问题)。

如果目标函数$f(\boldsymbol x)$是一个凸函数，可行集$\boldsymbol S$或者$\mathcal{X}$是凸集，通常来讲就是凸优化问题。

• 为什么凸优化问题具有比较好的性质呢？
  • 例子1：一元最小化问题：$\text{min } f(x), \text{ s.t. } x\in[a, b]$

• • 例子2：二元最小化问题：$\text{min } f(x_1, x_2) = x_1^2 + x_2^2, \text{ s.t. } x\in S$

凸集：集合中的任意两点连线的点都在该集合中，则称该集合为凸集；凹集为非凸集。

2.1 凸集的定义

(一) 凸集定义的数学表示

凸集：对于任意的$x, y \in \boldsymbol C$与任意$\lambda \in [0,1]$，有

$$\lambda x + (1-\lambda)y \in \boldsymbol C$$

那么$\boldsymbol C$为凸集。凸集中任意两点连线的点都在该集合中。

• 推广表示方法：

$$\lambda_1 x_1 + \cdots + \lambda_k x_k \in \boldsymbol C, \text{ }\forall x_1, \cdots, x_k \in \boldsymbol C$$

其中，$\lambda_i \geq 0, \lambda_1 + \cdots + \lambda_k = 1$。

(二) 凸组合：

凸组合是指，假设$x_1, x_2, \cdots , x_n$是一组对象（要根据讨论问题的背景来确定），$\lambda_1, \lambda_2, \cdots, \lambda_k$是$k$个常数，并且满足$\lambda_i \geq 0, \lambda_1 + \cdots + \lambda_k = 1$，那么这些点的凸组合即一个这样的点：

$$\lambda_1 x_1 + \cdots + \lambda_k x_k \$$

就称为$x_1, x_2, \cdots , x_n$的凸组合。注意区分线性组合,仿射组合,非负组合,凸组合。

通常你看到凸组合只意味着一个意思：线性组合，系数和为一

任意两个点的凸组合都在它们之间的线段上。

(三) 凸包：

凸包是针对一个集合来说的。任意一个集合(不一定是凸集)$\boldsymbol C$，其中的点的凸组合构成的集合就称为凸包。

点集的凸包等价于该点集的所有凸组合。

凸包一定是凸集合，通过凸包操作能够将非凸集合转变为凸集合。

2.2 常见凸集

(一) 超平面

• 定义：$n$维线性空间中维度为$n−1$的子空间，它可以把线性空间分割为不相交的两部分。

  这里的$n$必须大于$3$，其子空间才能称之为超平面。

  更直观理解超平面：其实就是平面中的直线、空间中的平面的推广。在三维坐标系，XoY平面把三维坐标系”分割”成两个空间，这个分割平面引申到一维，二维，四维空间…来，他就是一个超平面。

• 超平面方程推导：

$$\boldsymbol H = \begin{Bmatrix} \boldsymbol x |\boldsymbol a^{\mathrm T} \boldsymbol x = \boldsymbol b ,(\boldsymbol a \neq \boldsymbol 0) \end{Bmatrix}$$

式中，$\boldsymbol a^{\mathrm T}$垂直于超平面$\boldsymbol x$。

参考资料1：机器学习01-超平面理解

参考资料2：超平面是什么？——理解超平面（SVM开篇之超平面详解）

(二) 半空间：

$$\boldsymbol H^+ = \begin{Bmatrix} \boldsymbol x |\boldsymbol a^{\mathrm T} \boldsymbol x \geq \boldsymbol b ,(\boldsymbol a \neq \boldsymbol 0) \end{Bmatrix}$$ $$\boldsymbol H^- = \begin{Bmatrix} \boldsymbol x |\boldsymbol a^{\mathrm T} \boldsymbol x \leq \boldsymbol b ,(\boldsymbol a \neq \boldsymbol 0) \end{Bmatrix}$$

(三) 多面体：

• 定义：多个线性不等式所刻画的集合

$$\begin{Bmatrix} \boldsymbol x \mid \boldsymbol a_i^{\mathrm T} \boldsymbol x \leq \boldsymbol b_i , i = 1, \cdots, m \end{Bmatrix}$$

注意：线性等式刻画的集合也是多面体，因为等式约束可以转换为不等式约束，如

$$a_{i}^{T} x=b_{i} \Leftrightarrow\left\{\begin{array}{l} a_{i}^{T} x \leq b_{i} \\ -a_{i}^{T} x \leq-b_{i} \end{array}\right.$$

(四) 球体：（Euclidean）ball with center $\boldsymbol x_c$and radius r

$$B\left(\boldsymbol x_{c}, r\right)=\left\{ \boldsymbol x \mid \left\| \boldsymbol x - \boldsymbol x_{c}\right\|_{2} \leq r\right\}=\left\{\boldsymbol x_{c}+r\boldsymbol u \mid \| \boldsymbol u \|_{2} \leq 1\right\}$$

式中，$\boldsymbol x_c$为球心，$r$为半径，$\boldsymbol u$表示某一距离长度范围。

(五) 椭球（Ellipsoid）

$$\left\{\boldsymbol x \mid\left(\boldsymbol x - \boldsymbol x_{c}\right)^{T} \boldsymbol P^{-1}\left(\boldsymbol x- \boldsymbol x_{c}\right) \leq 1\right\}$$

其中$\boldsymbol P$为正定矩阵；椭球的半轴长为$\sqrt \lambda_i$($\lambda_i$为正定矩阵的特征值)。

(六) 二阶(次)锥 ：Second-order cone, ice-cream cone

假设有一个$n+1$维的锥，其前面$n$维写为$\boldsymbol x$，最后第$n+1$维分量记为$t$。

$$\left\{(\boldsymbol x, t) \mid ||\boldsymbol x||_2 \leq t\right\}$$

什么是锥：

如果$\boldsymbol x \in \boldsymbol C$，那么若有$\lambda \boldsymbol x \in \boldsymbol C, \forall \lambda \geq 0$，此时就称为锥。

(七) 半定矩阵锥

1. $\boldsymbol S^n$：所有$n$阶对称矩阵组成的集合；
2. $$\boldsymbol S _ +^n = \begin{Bmatrix} \boldsymbol X \in \boldsymbol S^n \mid \boldsymbol X \geq 0\end{Bmatrix} $$：所有**半正定矩阵**组成的集合，其中：$$\boldsymbol X \geq 0 \Leftrightarrow \boldsymbol z^T \boldsymbol X \boldsymbol z \geq 0, \forall \boldsymbol z$$
3. $$\boldsymbol S _ {++}^n = \begin{Bmatrix} \boldsymbol X \in \boldsymbol S^n \mid \boldsymbol X > 0\end{Bmatrix}$$：所有**正定矩阵**的集合，其中：$$\boldsymbol X > 0 \Leftrightarrow \boldsymbol z^T \boldsymbol X \boldsymbol z > 0, \forall \boldsymbol z$$

半定矩阵锥常用于半定规划里面(一种常见的凸优化问题)。

• 例子：$\left[\begin{array}{cc} x & y \\ y & x\end{array}\right] \in \boldsymbol S_+^2$，如下图所示。

小问题：

线性规划

$$\min \begin{Bmatrix} \boldsymbol{c^Tx} \mid \boldsymbol A \boldsymbol x = \boldsymbol b , \boldsymbol x \geq 0 \end{Bmatrix}$$

的最优解组成的集合为$\boldsymbol S$，$\boldsymbol S$是凸集合吗？【答案——$\boldsymbol S$是凸集合】

证明：

$$\begin{aligned} &\forall \boldsymbol x_{1}, \boldsymbol x_{2} \in\boldsymbol S,有\boldsymbol c^{T} \boldsymbol x_{1}=\boldsymbol c^{T} \boldsymbol x_{2}=\boldsymbol v^* \\ \\ &\forall \lambda \in[0,1], 验证\lambda \boldsymbol x_{1}+(1-\lambda) \boldsymbol x_{2} 是否属于\boldsymbol S\\ \\ &c^{T}\left(\lambda \boldsymbol x_{1}+(1-\lambda) \boldsymbol x_{2} \right) \\ &=\lambda c^{T}\boldsymbol x_{1}+(1-\lambda) c^{T} \boldsymbol x_{2} \\ &=\boldsymbol v^* \in \boldsymbol S \end{aligned}$$

2.3 保持集合凸性的运算

(一) 第一种

设$\boldsymbol C_1, \boldsymbol C_2 ⊂ \mathbb{R}^n$是凸集，$a \in \mathbb{R}$则

• （1）$\boldsymbol C_{1} \cap \boldsymbol C_{2}=\left\{\boldsymbol x \mid \boldsymbol x \in \boldsymbol C_{1}, \boldsymbol x \in \boldsymbol C_{2}\right\}$是凸集
• （2）$\boldsymbol C_{1} \pm \boldsymbol C_{2}=\left\{\boldsymbol{x \pm y} \mid \boldsymbol x \in \boldsymbol C_{1}, \boldsymbol y \in \boldsymbol C_{2}\right\}$是凸集

问题：$\boldsymbol S=\left\{\boldsymbol x \in \mathbb{R}^n \mid |p(t)|\leq 1,| t \mid \leq \pi / 3\right\}$，其中$p(t) = \sum_{i=1}^{n}x_i \cos it$是否为凸集？

答：带入$p(t)$得到：$-1 \leq x_{1} \cos t+x_{2} \cos 2 t+\cdots+x_{n} \cos n t \leq 1$

上不等式表示两个半空间交集。如果$t$只有两种取值，那么就是两个上不等式刻画的集合的交；事实上$t$无穷多取值，那么就是无穷多个上不等式刻画的集合的交，即结果仍然是凸集。

(二) 仿射变换

线性变换是特殊的仿射变换。或者说仿射变换就是线性变换加平移。

假设$f: \mathbb R^n \to \mathbb R^m$是仿射函数，即$f(\boldsymbol x) = \boldsymbol{Ax +b}, \boldsymbol A \in \mathbb R^{m \times n}, \boldsymbol b \in \mathbb R^m $

• $\boldsymbol C$为凸集$\Rightarrow f(\boldsymbol C) = \left\{f(\boldsymbol x) \mid \boldsymbol x \in \boldsymbol C \right\}$是凸集
• $\boldsymbol C$为凸集$\Rightarrow f^{-1}(\boldsymbol C) = \left\{\boldsymbol x \mid f(\boldsymbol x) \in \boldsymbol C \right\}$是凸集

特殊仿射变换：

• 放缩scaling：$\alpha \boldsymbol C = \left\{\alpha \boldsymbol x \mid \boldsymbol x \in \boldsymbol C \right\}$
• 平移translation：$\boldsymbol x_0 + \boldsymbol C = \left\{\boldsymbol x_0 + \boldsymbol x \mid \boldsymbol x \in \boldsymbol C \right\}$
• 投影projection：$\left\{x^{1} \mid\left(\begin{array}{l} x^{1} \\ x^{2} \end{array}\right) \in \boldsymbol C\right\}$

2.4 凸集的基本性质——投影定理

(一) 投影定理概念

设$\boldsymbol C ⊂ \mathbb{R}^n$是一个非空闭凸集，$\boldsymbol y \in \mathbb{R}^n, \boldsymbol y \notin \boldsymbol C$，则：

（1）存在唯一的一点$\overline{\boldsymbol x} \in \boldsymbol C$，使得$\overline{\boldsymbol x}$是$\boldsymbol y$到$\boldsymbol C$的距离最小的点(即投影点)，即有

$$|| \overline{\boldsymbol x} - \boldsymbol y || = \inf \begin{Bmatrix} ||\boldsymbol x - \boldsymbol y|| \mid \boldsymbol x \in \boldsymbol C \end{Bmatrix} > 0$$

（2）$\overline{\boldsymbol x}$是$\boldsymbol y$到$\boldsymbol C$的投影点(最小距离点)的充要条件是：

$$(\boldsymbol x - \overline{\boldsymbol x})^{\mathrm T} (\boldsymbol y - \overline{\boldsymbol x}) \leq 0 , \forall \boldsymbol x \in \boldsymbol C$$

(二) 投影定理的证明

不妨设，$\overline{\boldsymbol x}、\boldsymbol x’$都是投影点，则：$|| \overline{\boldsymbol x} - \boldsymbol y || = || \boldsymbol x’ - \boldsymbol y ||$

存在$\hat{\boldsymbol x}$在$\overline{\boldsymbol x}、\boldsymbol x’$两点之间，并作为连接三角形的中垂线，而小于其他两条边，从而小于投影点距离，矛盾！

因此投影点是唯一的。

(三) 点与凸集的分离

• 分离

设$\boldsymbol C_1, \boldsymbol C_2 ⊂ \mathbb{R}^n$是两个非空凸集，若非零$\boldsymbol a \in \mathbb{R}^n$和$\boldsymbol b$使得：

$$\boldsymbol{a^{\mathrm T}x} \geq \boldsymbol b, \forall \boldsymbol x \in \boldsymbol C_1, \boldsymbol{a^{\mathrm T}z} \leq \boldsymbol b, \forall \boldsymbol z \in \boldsymbol C_2 \\ \Updownarrow \\ \boldsymbol{a^{\mathrm T}x} \geq \boldsymbol{a^{\mathrm T}z}, \forall \boldsymbol x \in \boldsymbol C_1,\forall \boldsymbol z \in \boldsymbol C_2$$

则称超平面$\boldsymbol H = \begin{Bmatrix} \boldsymbol x \mid \boldsymbol{a^{\mathrm T}} \boldsymbol x = \boldsymbol b \end{Bmatrix}$分离集合$\boldsymbol C_1, \boldsymbol C_2$。

• 严格分离

设$\boldsymbol C_1, \boldsymbol C_2 ⊂ \mathbb{R}^n$是两个非空凸集，若非零$\boldsymbol a \in \mathbb{R}^n$和$\boldsymbol b$使得：

$$\boldsymbol{a^{\mathrm T}x} > \boldsymbol b, \forall \boldsymbol x \in \boldsymbol C_1, \boldsymbol{a^{\mathrm T}z} < \boldsymbol b, \forall \boldsymbol z \in \boldsymbol C_2 \\ \Updownarrow \\ \boldsymbol{a^{\mathrm T}x} > \boldsymbol{a^{\mathrm T}z}, \forall \boldsymbol x \in \boldsymbol C_1,\forall \boldsymbol z \in \boldsymbol C_2$$

则称超平面$\boldsymbol H = \begin{Bmatrix} \boldsymbol x \mid \boldsymbol{a^{\mathrm T}} \boldsymbol x = \boldsymbol b \end{Bmatrix}$严格分离集合$\boldsymbol C_1, \boldsymbol C_2$。

小问题1：两个不相交的非空凸集一定能分离吗？

答：一定能分离。

小问题2：设$\boldsymbol C ⊂ \mathbb{R}^n$是两个非空闭凸集，$\boldsymbol y \notin \boldsymbol C$，是否存在超平面分离$\boldsymbol y$ 和$\boldsymbol C$？

答：存在

2.5 支撑超平面定理

设$\boldsymbol C ⊂ \mathbb{R}^n$是非空凸集，$\overline{\boldsymbol x} \in \partial \boldsymbol C $(意思是$\overline{\boldsymbol x}$是$\boldsymbol C$的边界点)，则存在非零向量$\boldsymbol a \in \mathbb{R}^n$使得：

$$\boldsymbol{a^{\mathrm T}x} \leq \boldsymbol{a^{\mathrm T}} \overline{\boldsymbol x}, \forall \boldsymbol x \in \boldsymbol {c|C}$$

其中，$\boldsymbol {c|C}$是凸集$\boldsymbol C$的全域，称为闭包，包括内部和边界。当$\boldsymbol C$不是紧的的时候，$\boldsymbol {c|C}$也是指$\boldsymbol {C}$的全域，即包括$\boldsymbol {C}$不包括的边界。

此时，也称超平面$\boldsymbol H = \begin{Bmatrix} \boldsymbol x \in \mathbb{R}^n \mid \boldsymbol{a^{\mathrm T}} \boldsymbol x =\boldsymbol{a^{\mathrm T}} \overline{\boldsymbol x} \end{Bmatrix}$是集合$\boldsymbol C$在$\overline{\boldsymbol x}$处的支撑超平面。

通俗来说，该定理描述为：在凸集$\boldsymbol C$的边界一点$\overline{\boldsymbol x}$寻找一个超平面$\boldsymbol H$，将凸集$\boldsymbol C$放在超平面负半空间中。

• 证明：

由于$\overline{\boldsymbol x} \in \partial \boldsymbol C $，则$\boldsymbol x_k \to \overline{\boldsymbol x}$(点列，收敛到$\overline{\boldsymbol x}$)，且$\boldsymbol x_k \notin \boldsymbol {c|C}$

因为$\boldsymbol x_k \notin \boldsymbol {c|C}​$，则存在$\boldsymbol a_k(\neq \boldsymbol 0)​$（边界点法向量），使得：

$$\boldsymbol{a_k^{\mathrm T}x} \leq \boldsymbol{a_k^{\mathrm T}} \boldsymbol x_k, \forall \boldsymbol x \in \boldsymbol {c|C}$$

不妨设，$||\boldsymbol a_k|| = 1$，则$\begin{Bmatrix} \boldsymbol a_k \end{Bmatrix}$存在收敛子列。

令上式中$k \to \infty$得：

$$\boldsymbol{a^{\mathrm T}x} \leq \boldsymbol{a^{\mathrm T}} \overline{\boldsymbol x}, \forall \boldsymbol x \in \boldsymbol {c|C}$$

参考链接：最优化理论与方法-第二讲-凸集 - skycrygg - CSDN

2.6 凸集之Farkas引理

Farkas引理好像可以用于升维度。

(一) Farkas引理定义

给定矩阵$\boldsymbol A_{m \times n}$以及$n$维向量$\boldsymbol c$，则以下两个问题有且只有一个有解：

• 问题1——$\boldsymbol{Ax \leq 0}, \boldsymbol{c^Tx > 0}$
• 问题2——$\boldsymbol{A^Ty = c}, \boldsymbol{y \geq 0}$

Farkas引理在几何上讨论矩阵$\boldsymbol A​$的行向量与向量$\boldsymbol c​$的位置关系。

矩阵

$$\boldsymbol{A}=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array}\right] =\left[\begin{array}{c} \boldsymbol a_{1}^{\mathrm T} \\ \boldsymbol a_{2}^{\mathrm T} \\ \vdots \\ \boldsymbol a_{m}^{\mathrm T} \end{array}\right]$$

其中，$\boldsymbol a_i$为$n$维列向量，将其带入问题1、2可得：

• 问题1——$\boldsymbol{a_i^Tx \leq 0}(i = 1,2, \cdots, m), \boldsymbol{c^Tx >0}$
• 问题2——$\boldsymbol{A^Ty} = (\boldsymbol a_1, \boldsymbol a_2, \cdots, \boldsymbol a_m) \left[\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_{m} \end{array}\right] = \boldsymbol c, y_i \geq 0(i = 1,2, \cdots, m)$

(二) Farkas引理证明

• 证明方法1：

• 证明方法2：利用线性规划对偶理论

(三) Farkas引理的推论

• Gordan定理：给定矩阵$\boldsymbol A_{m \times n}$，则以下两个问题有且只有一个有解：
  • 问题1——$\boldsymbol{Ax < 0}$
  • 问题2——$\boldsymbol{A^Ty = 0}, \boldsymbol{y \geq 0}, \boldsymbol{y \neq 0}$
• 给定矩阵$\boldsymbol A_{m \times n}$以及$n$维向量以及$n$维向量$\boldsymbol c$，则以下两个问题有且只有一个有解：
  • 问题1——$\boldsymbol{Ax \leq 0}, \boldsymbol{x \geq 0}, \boldsymbol{c^Tx > 0}$
  • 问题2——$\boldsymbol{A^Ty \geq c}, \boldsymbol{y \geq 0}$
• 其他还有好几个推论。。。

第三讲 凸函数

3.1 凸函数与凹函数定义

(一) 凸函数

设$\boldsymbol C$为非空凸集，$f$是定义在$\boldsymbol C$上的函数，如果对任意的$\boldsymbol x, \boldsymbol y \in \boldsymbol C, \alpha \in (0,1)$，均有：

$$f(\alpha \boldsymbol x + (1-\alpha)\boldsymbol y) \leq \alpha f(\boldsymbol x) + (1-\alpha)f\boldsymbol (y)$$

则称$f$为$\boldsymbol C$上的凸函数。

(二) 严格凸函数

$$f(\alpha \boldsymbol x + (1-\alpha)\boldsymbol y) < \alpha f(\boldsymbol x) + (1-\alpha)f\boldsymbol (y)$$

(三) 凹函数

设$\boldsymbol C$为非空凸集，$f$是定义在$\boldsymbol C$上的函数，如果对任意的$\boldsymbol x, \boldsymbol y \in \boldsymbol C, \alpha \in (0,1)$，均有：

$$f(\alpha \boldsymbol x + (1-\alpha)\boldsymbol y) \geq \alpha f(\boldsymbol x) + (1-\alpha)f\boldsymbol (y)$$

则称$f$为$\boldsymbol C$上的凹函数。

(四) 严格凹函数

$$f(\alpha \boldsymbol x + (1-\alpha)\boldsymbol y) > \alpha f(\boldsymbol x) + (1-\alpha)f\boldsymbol (y)$$

若$-f$是凸函数，那么$f$为凹函数。

如果原来要求解一个凹函数$f(x)$的最大值，则可以转换为凸函数的最小值：

$$\max f(x) \Longleftrightarrow \min -f(x)$$

3.2 常见凸函数

(一) 线性函数

$$f(\boldsymbol x) = \boldsymbol a^{\mathrm T} \boldsymbol x + b$$

该函数很特殊，它既唯一一类是凸函数又是凹函数。

(二) 二次函数

$$f(\boldsymbol x) = \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol a^{\mathrm T} \boldsymbol x + b, \boldsymbol Q \in \boldsymbol S_+^n$$

其中$\boldsymbol Q \in \boldsymbol S_+^n$是指$\boldsymbol Q$为半正定矩阵。该式子涉及二次型的知识。

(三) 最小二乘函数

$$f(\boldsymbol x) = ||\boldsymbol{Ax - b}||_2^2$$

(四) $p$范数

$$f(\boldsymbol x) = \left( \sum_{i = 1}^n |x_i|^p\right)^{\frac{1}{p}}, p \geq 1$$

0范数：$f(\boldsymbol x) = ||\boldsymbol x||_0$表示向量$\boldsymbol x$中0元素的个数。

3.3 凸函数的性质

(一)连续性

一个函数若是凸函数，那么该函数一定是连续函数。

(二) 性质2

$f(\boldsymbol x)$为凸函数，等价于对任意的$\boldsymbol{x,y} \in \mathbb{R}^n$，一元函数：

$$\varphi(\alpha) = f(\boldsymbol x + \alpha \boldsymbol y)$$

为凸函数。相当于把函数竖着切一下得到的切面？？？

(三) 性质3——判定凸函数的一阶条件

$f(\boldsymbol x)$为$\boldsymbol C$上的凸函数的充要条件为：

$$f(\boldsymbol y) \geq f(\boldsymbol x) + \bigtriangledown f(\boldsymbol x)^{\mathrm T}(\boldsymbol y - \boldsymbol x), \forall \boldsymbol {x, y \in C}$$

几何上的意义就是$f(\boldsymbol x)$要在经过某一点的切面的上方，注意到上式中右式为函数在点处的一阶泰勒展开，在$n = 1$情形下的几何意义如下图：

对应的切线方程为：$g(y) = f(x) + \bigtriangledown f(x)^{\mathrm T}(y - x)$

证明：参考网络上的一些博客/b站视频。

(四) 性质4——判定凸函数的二阶条件

一阶条件在工作中很少被使用，我们往往使用的是二阶条件来判定函数的凸性。

二阶条件涉及到了Hessian matrix，它是这样定义的。

在数学中，海森矩阵（Hessian matrix 或 Hessian）是一个多变量实值函数的二阶偏导数组成的方块矩阵，假设有一实数函数$f (x_1 , x_2 , . . . , x_n )$ ，如果$f$所有的二阶偏导数都存在，那么$f$的海森矩阵是长下面这样：

设$\boldsymbol C \in \mathbb{R}^n$是非空开凸集，$f(\boldsymbol x)$在$\boldsymbol C$上二阶连续可微，则$f(\boldsymbol x)$是$\boldsymbol C$上的凸函数，等价于$f(\boldsymbol x)$的二阶Hessian matrix：

$$\bigtriangledown^2 f(\boldsymbol x) \geq 0, \forall \boldsymbol x \in C$$

即函数的二阶Hessian matrix需要是半正定的。

对于$\boldsymbol C \in \mathbb{R}$上的函数, 上式退化为$ \dfrac{\mathrm d}{\mathrm d x} \left( \dfrac{\mathrm d f}{\mathrm d x} \right) = f′′(x) ⩾ 0$. 该条件表明函数$f$的导数非减，从几何上解释就是函数$f$在点$x$处具有向上(正)的曲率。

3.4 保持函数凸性的运算

(一) Perspective function

若$f(\boldsymbol x)$为凸函数，则：

$$g(\boldsymbol x, t) = t f(\dfrac{\boldsymbol x}{t}), t > 0$$

为凸函数，设$f(x) = x^2$，则$g(x,t)$的可视化如下图所示。

(二) 非负组合

设有一组凸函数：$f_1(\boldsymbol x), f_2(\boldsymbol x), \cdots, f_m(\boldsymbol x)$，则有：

$$g(\boldsymbol x) = w_1 f_1(\boldsymbol x) + w_2 f_2(\boldsymbol x) + \cdots + w_m f_m(\boldsymbol x), w_i \geq 0$$

为凸函数。

(三) 凸函数求最大

设有一组凸函数：$f_1(\boldsymbol x), f_2(\boldsymbol x), \cdots, f_m(\boldsymbol x)$，则有：

$$g(\boldsymbol x) = \max \begin{Bmatrix} f_1(\boldsymbol x), f_2(\boldsymbol x), \cdots, f_m(\boldsymbol x) \end{Bmatrix}$$

为凸函数。

3.5 凸集与凸函数的关系

讨论凸集和凸函数的两个工具：凸集，上(镜)图Epigraph

(一) 水平集

任意一个函数(不一定是凸函数)$f(\boldsymbol x)$的水平集：

$$\boldsymbol L_a = \begin{Bmatrix} \boldsymbol x \mid f(\boldsymbol x) \leq a, \boldsymbol x \in C \end{Bmatrix}$$

其中$a$为给定的水平值。

$f(\boldsymbol x)​$是凸函数，则其水平集均为凸集。反之，则不成立，即函数不是凸函数时，其水平集也可能是凸集。

(二) 上(镜)图Epigraph

函数$f(\boldsymbol x)$的Epigraph定义为：

$$\text{epi} (f) = \begin{Bmatrix} (\boldsymbol x, \boldsymbol y)^{\mathrm T} \mid f(\boldsymbol x) \leq \boldsymbol y, \boldsymbol x \in \boldsymbol C \end{Bmatrix}$$ $$f(\boldsymbol x)是凸函数为凸集 \Longleftrightarrow \text{epi} (f)为凸集合$$

小问题：给定非空闭凸集$\boldsymbol C$，证明距离函数$f(\boldsymbol y)$是凸函数，其中：

$$f(\boldsymbol y) = \min \begin{Bmatrix}||\boldsymbol{y-x}||_2 \mid \boldsymbol x \in \boldsymbol C \end{Bmatrix}$$

第四讲 凸优化问题

4.1 凸优化问题通式

考虑最优化问题（P）：

$$\begin{cases}\text { min } & f(\boldsymbol x) \\ \text{ s.t. } & g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m \\ & h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l\end{cases}$$

记P的可行域为$\boldsymbol S = \begin{Bmatrix} \boldsymbol x \in \mathbb{R}^n \mid g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m, h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l \end{Bmatrix}$，则当$f(\boldsymbol x), g_{i}(\boldsymbol x)$是凸函数，$h_{i}(\boldsymbol x)$是线性函数时，问题（P）称为凸优化问题。

• 为什么特别强调不等式约束条件$g_{i}(\boldsymbol x)$是凸函数呢？

首先，$g_{i}(\boldsymbol x) \leq 0$刻画的是水平值取0时的一个水平集；又知当函数为凸函数时，其水平集均为凸集合。

• 为什么特别强调等式约束条件$h_{i}(\boldsymbol x)$是线性函数呢？

等式约束当为线性函数是，就相当于$h_{i}(\boldsymbol x) = \boldsymbol a^{\mathrm T} \boldsymbol x + \boldsymbol b = 0$，这种形式所刻画的集合是一个超平面，而超平面也是一个凸集合。

由以上两个小问题分析可知，在上面的条件下，由不等式约束和等式约束所刻画的集合$\boldsymbol S$也是一个凸集合，这是凸优化问题的一个特点。

4.2 区分凸优化与非凸优化

区分凸优化与非凸优化是一个非常重要的事情，若是我们能够判断出该问题为凸优化问题，那么就能利用凸优化很多很好的性质进行求解分析问题。下面介绍凸优化问题的两个比较好的性质。

(一) 局部最优即全局最优

对于凸优化问题，其局部最优解就是全局最优解。

• 局部最优解

设现在有一个问题可行解为$\overline{\boldsymbol x}$满足：$f(\overline{\boldsymbol x}) \leq f(\boldsymbol x), \forall \boldsymbol x \in \boldsymbol S \cap \boldsymbol N_{\epsilon}(\overline{\boldsymbol x})$即在$\overline{\boldsymbol x}$很小的范围内的函数值都要大于$\overline{\boldsymbol x}$处的函数值，此时$\overline{\boldsymbol x}$为局部最优解。

• 全局最优解

设现在有一个问题可行解为$\overline{\boldsymbol x}^*$满足：$f(\overline{\boldsymbol x}^*) \leq f(\boldsymbol x), \forall \boldsymbol x \in \boldsymbol S$即在整个可行域范围内的函数值都要大于$\overline{\boldsymbol x}^*$处的函数值，此时$\overline{\boldsymbol x}^*$为全局最优解。

证明：

设对于凸优化，$\overline{\boldsymbol x}$是局部最优解，但不是全局最优，即存在${\boldsymbol x}^*$使得$f({\boldsymbol x}^*) < f(\overline{\boldsymbol x}), \forall \boldsymbol x \in \boldsymbol S$，取$\lambda \in (0,1)$，则有：

$$\begin{aligned} f\left(\overline{\boldsymbol{x}}+\lambda\left(\boldsymbol{x}^{*}-\overline{\boldsymbol{x}}\right)\right) &\left.=f\left(\lambda \boldsymbol{x}^{*}+(1-\lambda) \overline{\boldsymbol{x}}\right)\right) \\ & \leq \lambda f\left(\boldsymbol{x}^{*}\right)+(1-\lambda) f(\overline{\boldsymbol{x}}) \\ &<f(\overline{\boldsymbol{x}}) \end{aligned}$$

当$\lambda \to 0$时，$\left(\overline{\boldsymbol{x}}+\lambda\left(\boldsymbol{x}^{*}-\overline{\boldsymbol{x}}\right)\right) $就非常趋近与$\overline{\boldsymbol x}$，即在$\overline{\boldsymbol x}$的邻域里面。那么就可以得出结论：凸优化的局部最优一定时全局最优，不然后产生矛盾。

(二) 凸优化问题最优性条件

最优性条件其实就是在讨论优化问题的最优解要满足的条件：充分条件、必要条件、充要条件。

设$\overline{\boldsymbol x}^* \in \boldsymbol S$为某一最优化问题的最优解，则等价于(充要条件)：

$$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0, \forall \boldsymbol x \in \boldsymbol S$$

证明——充分性：已知$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0, \forall \boldsymbol x \in \boldsymbol S$，求证此时$\overline{\boldsymbol x}^* \in \boldsymbol S$为某一最优化问题的最优解。

首先$f(\overline{\boldsymbol x}^*) + \triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*)$是一个经过$(\overline{\boldsymbol x}^*, f(\overline{\boldsymbol x}^*))$点的切平面，因为目标函数$f$是凸函数，则函数在其切平面的上方，即满足：

$$f(\boldsymbol x) \geq f(\overline{\boldsymbol x}^*) + \triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq f(\overline{\boldsymbol x}^*) , \forall \boldsymbol x \in \boldsymbol S$$

即，对于任意$\boldsymbol x$都有$f(\boldsymbol x) \geq f(\overline{\boldsymbol x}^*)$，即$\overline{\boldsymbol x}^* \in \boldsymbol S$为最优化问题的最优解。

证明——必要性：已知$\overline{\boldsymbol x}^* \in \boldsymbol S$为某一最优化问题的最优解，求证$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0, \forall \boldsymbol x \in \boldsymbol S$。

(反证法)：设存在$\overline{\boldsymbol x} \in \boldsymbol S$使得$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\overline{\boldsymbol x} - \overline{\boldsymbol x}^*) < 0$，$\lambda \in (0,1)$

$$f(\overline{\boldsymbol{x}}^*+\lambda(\overline{\boldsymbol{x}}-\overline{\boldsymbol{x}}^*))\overset{泰勒展开}{=} f(\overline{\boldsymbol{x}}^*) + \lambda \triangledown f (\overline{\boldsymbol{x}}^*)(\boldsymbol x - \overline{\boldsymbol x}^*) + o(\lambda||\boldsymbol x - \overline{\boldsymbol x}^*)||)$$

整理可得：

$$\frac{f(\overline{\boldsymbol{x}}^*+\lambda(\overline{\boldsymbol{x}}-\overline{\boldsymbol{x}}^*))-f(\overline{\boldsymbol{x}}^*)}{\lambda} = \triangledown f (\overline{\boldsymbol{x}}^*)(\boldsymbol x - \overline{\boldsymbol x}^*) + \frac{o(\lambda||\boldsymbol x - \overline{\boldsymbol x}^*)||)}{\lambda}$$

当$\lambda \to 0$时，$\dfrac{o(\lambda||\boldsymbol x - \overline{\boldsymbol x}^*)||)}{\lambda} \to 0$，$\triangledown f (\overline{\boldsymbol{x}}^*)(\boldsymbol x - \overline{\boldsymbol x}^*) < 0$，则：

$$\triangledown f (\overline{\boldsymbol{x}}^*)(\boldsymbol x - \overline{\boldsymbol x}^*) + \dfrac{o(\lambda||\boldsymbol x - \overline{\boldsymbol x}^*)||)}{\lambda} < 0$$

此时等式左边$\dfrac{f(\overline{\boldsymbol{x}}^*+\lambda(\overline{\boldsymbol{x}}-\overline{\boldsymbol{x}}^*))-f(\overline{\boldsymbol{x}}^*)}{\lambda} < 0$，即我们找到比$f(\overline{\boldsymbol x}^*)$函数值更小的，即与$\overline{\boldsymbol x}^*$是最优解矛盾。

几何解释：

$$\overline{\boldsymbol x}^* \in \boldsymbol S是最优解 \\ \Updownarrow \\ \triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0, \forall \boldsymbol x \in \boldsymbol S \\ \Updownarrow \\ -\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}\overline{\boldsymbol x}^* \geq -\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T} \boldsymbol x, \forall \boldsymbol x \in \boldsymbol S \\ \Updownarrow \\ 令\boldsymbol \alpha = -\triangledown f(\overline{\boldsymbol x}^*) \\ \Updownarrow \\ \boldsymbol \alpha^{\mathrm T} \overline{\boldsymbol x}^* \geq \boldsymbol \alpha^{\mathrm T} {\boldsymbol x}, \forall \boldsymbol x \in \boldsymbol S$$

由上面的等价表达可知，若$\boldsymbol \alpha \neq \boldsymbol 0(\triangledown f(\overline{\boldsymbol x}^*) \neq \boldsymbol 0)$，则就找到了一个支撑超平面，该支撑超平面经过$\overline{\boldsymbol x}^*$，在该点处恰好支撑整个凸集合$\boldsymbol S$。

几类特殊凸问题的最优性条件：

• 无约束凸优化$\min f(\boldsymbol x) \text{ over } \mathbb{R}^n$：$\overline{\boldsymbol x}^*最优 \Longleftrightarrow \triangledown f(\overline{\boldsymbol x}^*) = \boldsymbol 0$

  • 根据前面的条件，可知：$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0$，由于没有约束条件，即$(\boldsymbol x - \overline{\boldsymbol x}^*)$可以取遍$\mathbb{R}^n$中的所有向量，那么此时$\triangledown f(\overline{\boldsymbol x}^*) = \boldsymbol 0$。

• 等式约束凸问题$\min \begin{Bmatrix} f(\boldsymbol x) \mid \boldsymbol{Ax = b}\end{Bmatrix}$：$\overline{\boldsymbol x}^*最优 \Longleftrightarrow ∃\boldsymbol \mu,使得 \triangledown f(\overline{\boldsymbol x}^*) + \boldsymbol A^{\mathrm T} \boldsymbol \mu= \boldsymbol 0, \boldsymbol A \overline{\boldsymbol x}^* = \boldsymbol b$

  • 根据前面的条件，可知：$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) \geq 0$，满足$\boldsymbol{Ax = b}, \boldsymbol{A\overline{\boldsymbol x}^* = b}$，令向量$\boldsymbol d = \boldsymbol x - \overline{\boldsymbol x}^*$，那么将满足等式约束的两个式子相减：$\boldsymbol{A(x - \overline{x}^*) = \boldsymbol{Ad}= 0}$，即向量$\boldsymbol d$在$\boldsymbol A$的零空间中。又由于向量$\boldsymbol d$在$\boldsymbol A$的零空间中，那么$-\boldsymbol d$同样在$\boldsymbol A$的零空间中，因此向量$\boldsymbol d$和$-\boldsymbol d$都是$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) = \triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T} \boldsymbol d\geq 0$的解，也就是该不等式添加负号不等号不变方向，也就等价于$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}(\boldsymbol x - \overline{\boldsymbol x}^*) = \triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T} \boldsymbol d = 0$。由于$\boldsymbol d$在$\boldsymbol A$的零空间中，而$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T} \boldsymbol d = 0$，所以$\triangledown f(\overline{\boldsymbol x}^*)^{\mathrm T}$在$\boldsymbol A$的正交补空间中，也就是$\boldsymbol A$的行空间，所以$\triangledown f(\overline{\boldsymbol x}^*)$可以表示成$\boldsymbol A^{\mathrm T}$的线性组合：
  $$∃\boldsymbol \mu,使得 \triangledown f(\overline{\boldsymbol x}^*) + \boldsymbol A^{\mathrm T} \boldsymbol \mu= \boldsymbol 0, \boldsymbol A \overline{\boldsymbol x}^* = \boldsymbol b$$
  • 这个就是KKT条件在本问题中的具体表现形式。

• 非负约束凸优化$\min \begin{Bmatrix} f(\boldsymbol x) \mid \boldsymbol{x \geq 0}\end{Bmatrix}$：$\overline{\boldsymbol x}^*最优 \Longleftrightarrow \triangledown f(\overline{\boldsymbol x}^*)_i \overline{\boldsymbol x}^*_i= \boldsymbol 0, \overline{\boldsymbol x}^*>\boldsymbol 0, \triangledown f(\overline{\boldsymbol x}^*) \geq \boldsymbol 0$

  • 证明暂略，比较复杂，看视频吧

4.3 常见凸优化问题分类

(一) 线性规划 (Linear Programming, LP)

1 线性规划的标准形式

$$\begin{cases}\text { min } & \boldsymbol c^{\mathrm T}\boldsymbol x + d \\ \text{ s.t.} & \boldsymbol{Gx = b}, \\ & \boldsymbol{Hx \leq e}. \end{cases}$$

一言以蔽之，目标函数和约束条件都是仿射函数。

注意，凸优化问题中很多形式可以通过转换变为标准形式的！！！如下面几种情况：

• 线性分式规划

• 最小化绝对值函数

$$\min \begin{Bmatrix}|\boldsymbol a^{\mathrm T} \boldsymbol x + \boldsymbol c| \boldsymbol{AX = b} \end{Bmatrix}$$

• 最小化多面体函数

2 标准解法——单纯形法

单纯形法的基本思想是——基于线性规划的可行集是一个多面体，目标函数是线性的，绘制其等值面的时候是一组平行的线/面，找到多面体的支撑超平面。所以说，如果线性规划存在最优解，则可在极点(多面体的顶点)达到。

若$\overline{\boldsymbol x}$是一个极点，则需判断$\overline{\boldsymbol x}$是否是最优解：

• 若是最优解，则求解完成；
• 若不是最优解，则需从$\overline{\boldsymbol x}$出发，找一个更优的极点。

详细参见：线性规划问题（LP问题）， 解决线性规划问题为什么要加入松弛变量？

(二) 凸二次规划 (Quadratic Programming, QP)

1 凸二次规划基本形式

$$\begin{cases}\text { min } & \frac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x \\ \text{ s.t.} & \boldsymbol{Ax = b}, \\ & \boldsymbol{x \geq 0}. \end{cases}$$

其中，$\boldsymbol Q \geq \boldsymbol 0$。

2 标准解法——有效集法

后面讲解。

3 示例

• 均值-方差模型
• 最小二乘模型

(三) 带凸二次约束的二次规划(Quadraticlly Constrained Quadratic Program, QCQP)

1 基本形式

$$\begin{cases}\text { min } & \frac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q_0 \boldsymbol x + \boldsymbol c_0^{\mathrm T} \boldsymbol x \\ \text{ s.t.} & \frac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q_i \boldsymbol x + \boldsymbol c_i^{\mathrm T} \boldsymbol x + b_i \leq 0, \text{ } i = 1,2, \cdots, k \\ & \boldsymbol{Ax \leq d}. \end{cases}$$

其中，$\boldsymbol Q_i \geq \boldsymbol 0, i = 0, 1, \cdots, k.$。

(四) 二阶锥规划 (Second-Order Cone Program, SOCP)

1 基本形式

$$\begin{cases}\text { min } & \boldsymbol f^{\mathrm T}\boldsymbol x \\ \text{ s.t.} & \|\boldsymbol{A_i x + b_i} \|_2 \leq \boldsymbol c_i^{\mathrm T}\boldsymbol x + \boldsymbol d_i, \text{ } i = 1,2, \cdots, k \\ & \boldsymbol{Hx \leq e}. \end{cases}$$

当$k = 0$时，为LP问题；当所有$\boldsymbol {c_i = 0}$时，为QCQP问题。

(五) 半定规划 (Semidefinite Program, SDP)

1 半定规划标准形式

$$\begin{cases}\text { min } & \text{tr}(\boldsymbol C\boldsymbol X) \\ \text{ s.t.} & \text{tr}(\boldsymbol Q_i\boldsymbol X) = b_i, \text{ } i = 1,2, \cdots, m \\ & \boldsymbol{x \geq 0}. \end{cases}$$

其中，$\boldsymbol C, \boldsymbol Q_i$均为对称矩阵。

转化为：线性矩阵不等式形式(LMI)：

$$\begin{cases}\text { min } & \boldsymbol c^{\mathrm T}\boldsymbol x \\ \text{ s.t.} & \sum\limits_{i=1}^{n} {\boldsymbol {x_iQ_i}} \leq \boldsymbol Q_0 \\ & \boldsymbol{Ax \geq b}. \end{cases}$$

注意：若矩阵$\boldsymbol {Q_1 \leq Q_2}$，则有$\boldsymbol {Q_2 - Q_1}$是半正定矩阵。

(六) 几何规划 (Geometric Programming, GP)

1 例子：切比雪夫中心(集合中心)

• 给定有界的集合$\boldsymbol C, \boldsymbol x \in \boldsymbol C$的深度定义为：

$$\text{depth}(\boldsymbol x, \boldsymbol C) = \text{dist}(\boldsymbol x, \mathbb{R}^n(去除 \boldsymbol C) )$$

可以理解为集合$\boldsymbol C$中的点到集合$\boldsymbol C$边界的距离。

• 集合$\boldsymbol C$的中心(chebyshev center)定义为具有最大深度的点：

$$\boldsymbol x_{\text{center}}(\boldsymbol C) = \arg \max_{\boldsymbol x \in \boldsymbol C} \text{dist}(\boldsymbol x, \mathbb{R}^n(去除 \boldsymbol C) )$$

• 集合的中心即包含于该集合的最大球体的球心。

2 凸集合的中心问题为凸优化问题

(1) 假设$\boldsymbol S = \begin{Bmatrix} \boldsymbol x \mid f_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m \end{Bmatrix}$，其中$f_{i}(\boldsymbol x)$是凸函数，寻找包含$\boldsymbol S$的最大球体。

设该球体球心为$\boldsymbol x$，半径为$r$，该球可以表示为：$\boldsymbol B = \begin{Bmatrix} \boldsymbol x+r \boldsymbol u \mid \| \boldsymbol u \|_2 \leq 1 \end{Bmatrix}$

$$\begin{cases}\text { max } &\text { } \text { } r \\ \text{ s.t.} & \sup\limits_{\| \boldsymbol u \|_2 \leq 1} f_i(\boldsymbol x+r \boldsymbol u) \leq 0 , \text{ } i=1, \cdots, m\\ \end{cases}$$

注意：max/sup、min/inf辨析，sup, inf 与 min, max

使用 inf 或 sup 总能保证一个函数的 inf 或 sup 存在，而函数的 min 或 max 有时候不存在。

(2) 多面体的中心：假设多面体$\boldsymbol P = \begin{Bmatrix} \boldsymbol x \in \R ^n\mid \boldsymbol a_i^{\mathrm T} \boldsymbol x \leq \boldsymbol b_i, \text{ } i=1, \cdots, m \end{Bmatrix}$，寻找包含$\boldsymbol P$的最大球体，其球心即为集合$\boldsymbol P$的中心。

通过题目，可将优化问题抽象如下：(球体可以表示为：$\boldsymbol B = \begin{Bmatrix} \boldsymbol x+r \boldsymbol u \mid \| \boldsymbol u \|_2 \leq 1 \end{Bmatrix}$)

$$\begin{cases}\text { max } &\text { } \text { } r \\ \text{ s.t.} & \boldsymbol a_i^{\mathrm T} \boldsymbol x + \|\boldsymbol a_i \|_2 r \leq \boldsymbol b_i, \text{ } i=1, \cdots, m\\ \end{cases}$$

(3) 椭球交集的中心：假设$\boldsymbol S = \begin{Bmatrix} \boldsymbol x \in \R ^n \mid \boldsymbol x^{\mathrm T}\boldsymbol A_i \boldsymbol x + 2\boldsymbol b_i^{\mathrm T}\boldsymbol x + c_i \leq 0, \text{ } i=1, \cdots, m \end{Bmatrix}$，其中$\boldsymbol A_i \geq \boldsymbol 0$，寻找包含$\boldsymbol S$的最大球体和球心。

通过问题描述，可将该问题建模为：

$$\begin{cases} \max & r \\ \text { s.t. } & \left(\begin{array}{ccc} \boldsymbol A_{i}^{-1} & r l & -\left( \boldsymbol x+\boldsymbol A_{i}^{-1} \boldsymbol b_{i} \right) \\ r l & \lambda_{i} l & 0 \\ -\left( \boldsymbol x+\boldsymbol A_{i}^{-1}\boldsymbol b_{i}\right)^{T} & 0 & -\lambda_{i}-c_{i}+\boldsymbol b_{i}^{T} \boldsymbol A_{i}^{-1}\boldsymbol b_{i} \end{array}\right) \geq 0, \end{cases}$$

本问题涉及两个小知识点：

• S-Procedure：
  • $x^{\top} F_{1} x+2 b_{1}^{\top} x+c_{1} \leq 0 \Rightarrow x^{\top} F_{2} x+2 b_{2}^{\top} x+c_{2} \leq 0$，当且仅当$\exist \lambda \geq 0$使得$\left(\begin{array}{ll} F_{1} & b_{1} \\ b_{1}^{T} & c_{1} \end{array}\right)-\left(\begin{array}{ll} F_{2} & b_{2} \\ b_{2}^{T} & c_{2} \end{array}\right) \geq 0$
• Schur complement 对称分块矩阵：
  • 如$X=\left(\begin{array}{cc} A & B \\ B^{T} & C \end{array}\right)$，若$\boldsymbol A \geq \boldsymbol 0$，则$\boldsymbol X \geq \boldsymbol 0$当且仅当$C-B^{\top} A^{-1} B \geq0$

---

参考资料：

【1】为啥要知道一个对称方阵是否为各种定呢

【2】浅谈「正定矩阵」和「半正定矩阵」

【3】正定(positive definite)与半正定(semi-positive definite)