Convex Optimization

Convex Sets and Cones

先认识凸集及其构造方法，再用超平面描述凸集，最后讨论如何由锥定义大小关系，以及对偶锥如何检验这些关系。

Definition 1 (Affine and Convex Sets, 仿射集与凸集). A set $C\subseteq\mathbb R^n$ is affine if

$$ \theta x+(1-\theta)y\in C,\qquad x,y\in C,\quad\theta\in\mathbb R. $$

It is convex if the same condition holds for every $\theta\in[0,1]$.

仿射集包含任意两点之间的整条直线，凸集只要求包含线段。因此仿射集一定凸，反之不成立。

Definition 2 (Convex Combination and Convex Hull, 凸组合与凸包). A convex combination of $x_1,\ldots,x_k$ is

$$ x=\sum_{i=1}^k\theta_i x_i,\qquad \theta_i\geq0,\quad\sum_{i=1}^k\theta_i=1. $$

The convex hull of $C$ is the set of all finite convex combinations of points in $C$:

$$ \operatorname{conv}C= \left\lbrace\sum_{i=1}^k\theta_i x_i: k\geq1,\ x_i\in C,\ \theta_i\geq0,\ \sum_i\theta_i=1\right\rbrace. $$

It is the smallest convex set containing $C$.

凸集的两点定义反复应用后，便得到对任意有限凸组合的封闭性。下面先列出常见的凸集，再讨论如何构造新的凸集。

Definition 3 (Hyperplanes and Polyhedra, 超平面与多面体). For $a\neq0$, a hyperplane and a closed halfspace are respectively

$$ H=\lbrace x:a^\top x=b\rbrace,\qquad H_-=\lbrace x:a^\top x\leq b\rbrace. $$

A polyhedron is a set $\mathcal P=\lbrace x:Gx\leq h,\ Ax=b\rbrace$. All these sets are convex.

超平面是平直的边界，半空间选取边界的一侧，多面体则同时满足有限个这样的线性要求。

Definition 4 ($\ell_p$ Norms and Norm Balls, 向量范数与范数球). For $x\in\mathbb R^n$,

$$ \|x\|_p=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p},\quad 1\leq p<\infty,\qquad \|x\|_\infty=\max_i|x_i|. $$

For any norm and $r\geq0$, the norm ball $\lbrace x:\|x-x_c\|\leq r\rbrace$ is convex.

$p=1,2,\infty$ 分别对应绝对值之和、欧氏长度和最大绝对值；在二维中，单位球分别呈菱形、圆形和正方形。

Remark：函数空间中的 Lp 范数

有限维向量用 $\ell_p$，函数空间中对应的是 $L_p$。对测度 $\mu$ 下的可测函数，

$$ \|f\|_{L_p}=\left(\int|f|^p\,d\mu\right)^{1/p},\quad 1\leq p<\infty, \qquad\|f\|_{L_\infty}=\operatorname*{ess\,sup}|f|. $$

下文默认 $\|\cdot\|_p$ 表示向量范数。

Proposition 5 (Operations that Preserve Convexity, 保凸运算). Convexity is preserved under:

• Intersection: $\bigcap_\alpha C_\alpha$ when every $C_\alpha$ is convex.
• Affine image and inverse image: $AC+b$ and $\lbrace x:Ax+b\in C\rbrace$ when $C$ is convex.
• Perspective mapping: the image of a convex set in $\lbrace(x,t):t>0\rbrace$ under $P(x,t)=x/t$.
• Linear-fractional mapping: the image of a convex set under $$ f(x)=\frac{Ax+b}{c^\top x+d},\qquad c^\top x+d>0. $$

前两项可直接代入凸组合验证。透视映射通过重新分配正权重保持凸性；线性分式映射则是仿射映射与透视映射的复合。

例如，椭球是单位球的仿射像。对可逆矩阵 $A$，令 $P=AA^\top$，则

$$ \mathcal E=\lbrace x_c+Au:\|u\|_2\leq1\rbrace =\lbrace x:(x-x_c)^\top P^{-1}(x-x_c)\leq1\rbrace. $$

前面通过组合点构造凸集；反过来，也可以用超平面从外部描述它。

Theorem 6 (Separating and Supporting Hyperplanes, 分离与支撑超平面). Any two nonempty disjoint convex sets $C,D\subseteq\mathbb R^n$ admit a separating hyperplane:

$$ a^\top x\leq b\leq a^\top y,\qquad x\in C,\ y\in D,\quad a\neq0. $$

If one set is compact and the other is closed, they can be strongly separated. At every boundary point $x_0$ of a nonempty convex set $C$, there exists a supporting hyperplane:

$$ a^\top x\leq a^\top x_0,\qquad x\in C,\quad a\neq0. $$

分离超平面把两个集合放在两侧；支撑超平面则贴住集合的边界，让整个集合位于同一侧。特别地，闭凸集外的点可以被线性不等式与集合严格区分，这将用于后面的双对偶刻画。

接下来把凸集增加一个结构：允许从原点沿其中的方向任意非负缩放。凸组合去掉权重和为 $1$ 的限制，就得到锥组合。

Definition 7 (Conic Combination and Convex Cone, 锥组合与凸锥). A conic combination is a sum $\sum_i\theta_i x_i$ with $\theta_i\geq0$. A nonempty set $K$ is a convex cone if

$$ x,y\in K,\quad\alpha,\beta\geq0\quad\Longrightarrow\quad\alpha x+\beta y\in K. $$

常见凸锥包括非负正交锥 $\mathbb R_+^n$、半正定锥 $\mathbb S_+^n$ 和二阶锥

$$ \mathcal Q^{n+1}=\lbrace(x,t):\|x\|_2\leq t\rbrace. $$

结合前面的保凸运算，$\lbrace x:\|Ax+b\|_2\leq c^\top x+d\rbrace$ 是二阶锥的仿射逆像，因此也是凸集。

实数中，$a\leq b$ 等价于 $b-a\in\mathbb R_+$。推广到向量时，可以用锥 $K$ 规定哪些方向算作“非负”。

Definition 8 (Proper Cone and Generalized Inequality, 正则锥与广义不等式). A cone $K$ is proper if it is closed, convex, pointed, and has nonempty interior, where pointedness means $K\cap(-K)=\lbrace0\rbrace$. A proper cone induces

$$ x\preceq_K y\iff y-x\in K,\qquad x\prec_K y\iff y-x\in\operatorname{int}K. $$

当 $K=\mathbb R_+^n$ 时，得到逐分量不等式；当 $K=\mathbb S_+^n$ 时，得到矩阵的 Loewner 次序 $A\preceq B\iff B-A\succeq0$。

Remark：为什么用正则锥定义广义不等式

普通锥只要求沿已有方向非负缩放后仍在集合中；前面定义的凸锥还要求非负组合封闭。在此基础上，正则锥进一步要求闭、尖且内部非空，使它适合规定“正方向”：

• 凸： 两个允许的位移合起来，仍然允许。因此先从 $a$ 正向走到 $b$，再从 $b$ 正向走到 $c$，总位移仍为正，即 $a\preceq_K b$ 且 $b\preceq_K c$ 推出 $a\preceq_K c$。
• 尖： 不能同时允许一个非零位移和它的反方向。例如 $(1,0)$ 与 $(-1,0)$ 不能同时属于 $K$，否则向右、向左都算正，两个不同的点就可能互相“比对方大”。尖性排除这种情况，保证 $a\preceq_K b$ 且 $b\preceq_K a$ 时只能有 $a=b$，这就是反对称性。
• 闭： 边界也算进去，不会无限接近一个允许方向，极限却突然不允许。因此一串成立的广义不等式在两端点收敛后仍然成立。
• 内部非空： 在所在空间里有厚度，不只是细线或薄片。位移若落在内部，稍微扰动仍为正，这给出了有余量的严格不等式。

“尖”不要求不同向量的长度不同，也不要求图形一定有一个尖角；它只禁止同时包含 $v$ 和 $-v$（$v\neq0$）。例如右上象限同时包含等长的 $(1,0)$ 与 $(0,1)$，但不包含它们的反方向，因而仍然是尖锥。相反，上半平面同时包含向左和向右的水平向量，所以不尖。

锥结构还保证平移和非负数乘保持次序：

$$ x\preceq_K y\Longrightarrow \alpha x+z\preceq_K\alpha y+z,\qquad\alpha\geq0. $$

不需要四个条件全部满足才能定义某种次序。例如二维空间中向右的射线，只允许同一水平线上的点比较，但它没有二维厚度，也就没有上述内部意义下的严格正方向。右上象限则有内部：向右且向上移动对应严格大于，只向右移动虽然两点不同，却只对应非严格大于。两个点也可能不可比，例如从一点到另一点，一个坐标增加、另一个减少。

锥规定了正方向，接下来问：哪些线性测量会把这些正方向读成非负数？

Definition 9 (Dual Cone, 对偶锥). The dual cone of $K\subseteq\mathbb R^n$ is

$$ K^*=\lbrace y:y^\top x\geq0\text{ for every }x\in K\rbrace. $$

这个定义来自保持次序的要求：若 $u\preceq_K v$，希望 $y^\top u\leq y^\top v$，就必须要求 $y^\top x\geq0$ 对所有 $x\in K$ 成立。因此，$K$ 规定正方向，$K^*$ 收集与这些方向相容的线性测量。广义不等式由 $K$ 本身诱导；定义 $K^*$ 并不要求 $K$ 正则。

Theorem 10 (Dual-Cone Properties, 对偶锥的性质). The dual cone is always closed and convex. For a closed convex cone $K$,

$$ K^{**}=K,\qquad z\in K\iff y^\top z\geq0\text{ for every }y\in K^*. $$

The dual of a proper cone is proper.

双对偶结论是分离定理的直接应用：若 $z\notin K$，就存在 $y\in K^*$ 使 $y^\top z<0$。因此，对偶锥不仅给出必要的不等式，还能完整刻画闭凸锥。

Remark：对偶锥的结构与拉格朗日乘子

闭凸锥的尖性和内部通过对偶交换角色：

$$ K\text{ is pointed}\iff\operatorname{int}K^*\neq\varnothing,\qquad \operatorname{int}K\neq\varnothing\iff K^*\text{ is pointed}. $$

这解释了正则锥的对偶为何仍然正则。它在优化中的作用也由符号要求决定：对可行约束 $g(x)\preceq_K0$，选择 $\lambda\in K^*$，便有

$$ \lambda^\top g(x)\leq0,\qquad f_0(x)+\lambda^\top g(x)\leq f_0(x). $$

这正是拉格朗日下界的来源。普通不等式对应 $K=K^*=\mathbb R_+$，因此恢复熟悉的乘子条件 $\lambda\geq0$；完整推导放在对偶章节。

最后，用范数锥把这些抽象定义落到具体计算上。为计算它的对偶，先引入单位球上线性测量的最大值。

Definition 11 (Dual Norm, 对偶范数). The dual norm of $\|\cdot\|$ is

$$ \|y\|_*=\sup_{\|x\|\leq1}y^\top x. $$

由定义可得 $|y^\top x|\leq\|y\|_*\|x\|$。对共轭指数 $p,q\in[1,\infty]$，满足 $1/p+1/q=1$ 时，Hölder 不等式及取等条件给出

$$ \|\cdot\|_p^*=\|\cdot\|_q. $$

特别地，欧氏范数自对偶，$\ell_1$ 与 $\ell_\infty$ 互为对偶。

Proposition 12 (Norm-Cone Duality, 范数锥的对偶). For

$$ K=\lbrace(x,t):\|x\|\leq t\rbrace, $$

the dual cone is

$$ K^*=\lbrace(y,s):\|y\|_*\leq s\rbrace. $$

证明只需检查 $y^\top x+st$ 在锥上是否非负。对 $t>0$ 缩放到 $t=1$ 后，其最小值为 $s-\|y\|_*$；$t=0$ 时只有 $x=0$，不增加限制。因此二阶锥自对偶。非负正交锥和半正定锥也自对偶，后者使用矩阵内积 $\langle A,B\rangle=\operatorname{tr}(AB)$。

几何直观：凸锥、广义不等式、对偶锥与对偶范数

图 (a)：锥组合是在两根方向之间“铺出一片区域”。 把 $a,b$ 分别拉长、缩短，再首尾相加；只允许非负倍数，不允许反向。所有结果组成蓝色扇形 $K$，例如橙色的 $a+b$。凸组合要求权重和为 $1$，只铺出 $a,b$ 之间的线段；锥组合没有这个限制，便能从原点向外无限延伸。凸锥中的两点连线仍在锥内，每个方向也能任意非负缩放。

正则锥是适合规定“正方向”的凸锥。 图中的闭扇形和非负象限都是例子：边界包含在内（闭）；内部没有缺口（凸）；不同时容纳某个非零方向及其反方向（尖）；也不是一条细线，而有真正的内部区域（内部非空）。半平面虽然闭、凸且有内部，但边界包含一整条过原点的直线，不尖；单独一条射线则没有二维内部。这两者都不是二维正则锥。

图 (b)：比较大小，就是把锥的顶点搬到 $x$。 以 $K=\mathbb R_+^2$ 为例，蓝色区域 $x+K$ 中的点就是所有满足 $x\preceq_K y$ 的点。$y$ 在内部，两个坐标都增加，所以 $x\prec_K y$；$z$ 在边界，一个坐标不变，所以只有 $x\preceq_K z$，不是严格次序。$w$ 在左上方：一个坐标减少、另一个增加，故它与 $x$ 不可比。这里的“大”不是离原点更远，而是位移属于规定的正方向。

图中的 $y,z$ 都比 $x$ 大，但它们彼此不可比：$z$ 比 $y$ 靠左，也比 $y$ 靠上。传递性说的是另一种情形，例如另取 $a=(0,0)$、$b=(1,2)$、$c=(3,3)$，两次移动都向右上，总移动也向右上，因此 $a\preceq_K b\preceq_K c$。把这些点一起平移，或把位移乘以非负数，都不改变比较关系。

图 (c)：对偶锥收集所有“看原锥不带负投影”的方向。 蓝色为原锥 $K$，橙色为对偶锥 $K^*$，两者重叠处颜色加深。对非零向量，内积非负等价于夹角不超过 $90^\circ$：一个方向只有与蓝色锥中的每个方向都满足这个要求，才能进入对偶锥。橙色边界方向 $q$ 恰好与蓝色下边界方向 $v$ 垂直，与其他蓝色方向则成锐角；再向外转到红色 $w$，它与 $v$ 就成钝角，因而被排除。对偶锥不是原锥的外部，而是另一组满足夹角条件的方向；在这个例子中，原锥较窄，对偶锥反而较宽。

这里的“球”是范数单位球，不一定是圆：欧氏范数要求 $\sqrt{x_1^2+x_2^2}\leq1$，得到圆盘；$\ell_1$ 范数要求 $|x_1|+|x_2|\leq1$，得到菱形；$\ell_\infty$ 范数要求 $\max(|x_1|,|x_2|)\leq1$，也就是两个坐标分别处于 $[-1,1]$，得到正方形。例如 $(1,0)$ 与 $(1,1)$ 的欧氏长度不同，但 $\ell_\infty$ 长度都为 $1$。这里先选定范数，再由它构造范数球和范数锥，不是由任意锥直接诱导出范数。

图 (d)、(e)：对偶范数是单位球在给定测量方向上的最大读数。 固定 $y$，把垂直于它的直线 $y^\top x=c$ 沿箭头方向推，直到最后一次碰到蓝色单位球；这时的 $c$ 就是 $\|y\|_*$。图中同取 $y=(1,0.6)$：菱形单位球在 $(1,0)$ 取得最大读数 $1$，因此 $\ell_1$ 的对偶是 $\ell_\infty$；正方形单位球在 $(1,1)$ 取得最大读数 $1.6$，因此 $\ell_\infty$ 的对偶是 $\ell_1$。若单位球是圆，接触点沿 $y$ 的方向，最大读数就是 $\|y\|_2$，所以欧氏范数自对偶。这里的读数是内积；只有 $y$ 为欧氏单位向量时，它才等于投影长度。

为什么 $\ell_1$ 的单位球是菱形？ 在第一象限，$|x_1|+|x_2|\leq1$ 就是 $x_1+x_2\leq1$，边界是连接 $(1,0)$ 与 $(0,1)$ 的斜线。其余三个象限对称复制，四条斜边围成菱形。为什么 $\ell_\infty$ 的单位球是正方形？ $\max(|x_1|,|x_2|)\leq1$ 等价于 $|x_1|\leq1$ 且 $|x_2|\leq1$：横坐标、纵坐标各自在 $[-1,1]$ 内，围成正方形。前者限制两个坐标的总额度，后者分别限制每个坐标的额度。

图 (g)–(i)：范数锥就是把逐渐放大的范数球叠起来。 $K=\lbrace(x,t):\|x\|\leq t\rbrace$ 中，$x$ 是横向位置，$t$ 是额外增加的高度。在高度 $1$ 放一个单位球，在高度 $2$ 放一个放大两倍的球，依此类推，把所有高度的实心截面叠起来。菱形叠成一种四棱锥，正方形叠成另一种四棱锥，圆盘叠成圆锥。因此“截面”是固定高度后横切出来的形状，不是把整个锥压到平面上的投影。

图 (f) 也不是投影，而是直接画出低维的范数锥。 那里 $x$ 只有一个坐标，单位球是区间 $[-1,1]$；不同高度的区间叠起来，就是 $|x|\leq t$ 的 V 形内部。橙色横线是高度 $1$ 的截面；斜虚线则是支撑线，不是投影线。

Norm-Cone Duality 问的不是“截面长什么样”，而是“哪些测量在整个锥上都不会给出负数”。 一个候选测量 $(y,s)$ 给锥中点 $(x,t)$ 的读数为 $y^\top x+st$。先看高度 $1$：横向部分 $y^\top x$ 有时为负，而高度部分统一补上 $s$。要让截面上所有点的总读数非负，$s$ 必须补得住最坏的负数。

以图 (e) 的正方形截面为例，取 $y=(1,0.6)$。横向得分最高为 $1.6$，在对面的角点 $(-1,-1)$，最低就是 $-1.6$。所以候选测量必须满足 $s\geq1.6$。换一个 $y$，需要补上的数就是 $|y_1|+|y_2|=\|y\|_1$；因此正方形截面生成的 $\ell_\infty$ 范数锥，其对偶具有菱形截面：

$$ K_\infty^*=\lbrace(y,s):\|y\|_1\leq s\rbrace. $$

若原截面是菱形，最坏负分的大小则为 $\max(|y_1|,|y_2|)$，所以对偶截面变成正方形。若原截面是圆盘，最坏负分的大小为 $\|y\|_2$，所以对偶截面仍为圆盘。这就是三类截面之间的对应：菱形与正方形互换，圆盘保持不变。

为什么只检查高度 $1$ 就够？因为高度 $t>0$ 的每个点都能写成 $t(v,1)$，其中 $\|v\|\leq1$；它的总读数只是高度 $1$ 时读数的 $t$ 倍，不改变正负。原点的读数则为零。于是一般结论正是

$$ K^*=\lbrace(y,s):s\geq\|y\|_*\rbrace. $$

Convex Functions

Definition 1 (Convex Function, 凸函数). A function $f:D\to\mathbb R$ is convex if $D\subseteq\mathbb R^n$ is convex and

$$ f(\theta x+(1-\theta)y) \leq\theta f(x)+(1-\theta)f(y), \qquad x,y\in D,\quad\theta\in[0,1]. $$

If the inequality is strict whenever $x\neq y$ and $0<\theta<1$, then $f$ is strictly convex. A function is concave if $-f$ is convex. Affine functions are both convex and concave.

Theorem 2 (Equivalent Characterizations, 凸性的等价判据). Let $D$ be a nonempty convex set. Each of the following characterizes convexity of $f:D\to\mathbb R$; the differential criteria require the additional assumptions stated below.

• First order. If $D$ is open and $f$ is differentiable, then

  $$ f(y)\geq f(x)+\nabla f(x)^\top(y-x),\qquad x,y\in D. $$

  即一阶近似是全局下界。

• Second order. If $D$ is open and $f$ is twice continuously differentiable, then

  $$ \nabla^2f(x)\succeq0,\qquad x\in D. $$

• Restriction to a line. Every $g(t)=f(x+tv)$ is convex on $\lbrace t:x+tv\in D\rbrace$.

  直观上，输入沿任意直线移动时，记录下来的高度曲线都是凸的。这里的直线在输入空间中，读出的函数值并不一定形成直线。例如，$f(x_1,x_2)=x_1^2+x_2^2$ 沿 $(x_1,x_2)=(t,0)$ 的限制是 $g(t)=t^2$。

• Epigraph. The epigraph (上图集) $\operatorname{epi}f=\lbrace(x,t):x\in D,\ f(x)\leq t\rbrace$ is a convex set.

  上图集包含函数图像及其上方的所有点。$t$ 可以看成预算，$(x,t)$ 属于上图集就是“预算足以支付成本 $f(x)$”。凸性要求连接图像上两点的弦位于图像上方；把端点再向上移动，线段仍在上方，因此整个上图集凸。反过来，对图像上的点使用上图集的凸性，就得到凸函数定义。

• Jensen’s inequality. For all finite choices of $x_i\in D$ and $\theta_i\geq0$ with $\sum_i\theta_i=1$,

  $$ f\left(\sum_{i=1}^k\theta_i x_i\right) \leq\sum_{i=1}^k\theta_i f(x_i). $$

Hessian 处处正定是严格凸的充分条件，但不是必要条件。凹函数的一阶不等式方向相反，二阶判据为 Hessian 半负定。

除了直接使用判据，也可以通过以下运算构造凸函数。

Proposition 3 (Operations that Preserve Convexity). The following constructions preserve convexity on their natural convex domains.

• Nonnegative weighted sums. If $f_i$ are convex and $\alpha_i\geq0$, then $\sum_i\alpha_i f_i$ is convex.

• Affine composition. If $f$ is convex, then $x\mapsto f(Ax+b)$ is convex on $\lbrace x:Ax+b\in\operatorname{dom}f\rbrace$.

• Pointwise maximum and supremum. The pointwise supremum $g(x)=\sup_\alpha f_\alpha(x)$ of convex functions on a common convex domain is convex wherever finite. Finite maxima are a special case.

• Partial minimization. If $F(x,y)$ is jointly convex and $C$ is a nonempty convex set, then

  $$ g(x)=\inf_{y\in C}F(x,y) $$

  is convex, provided the infimum never equals $-\infty$; values $+\infty$ may represent infeasible $x$.

• Perspective. If $f$ is convex, then

  $$ g(x,t)=t f(x/t),\qquad \operatorname{dom}g=\lbrace(x,t):t>0,\ x/t\in\operatorname{dom}f\rbrace $$

  is jointly convex in $(x,t)$. The perspective of a concave function is jointly concave.

Proposition 4 (Scalar Composition, 标量复合). On a convex domain, $h\circ g$ is convex if either:

• $g$ is convex, and $h$ is convex and nondecreasing;
• $g$ is concave, and $h$ is convex and nonincreasing.

The stated properties of $h$ must hold on an interval containing the range of $g$.

Remark：保凸运算的几何直观

注意，逐点上确界只要求每个函数分别对 $x$ 凸；部分最小化要求对 $(x,y)$ 联合凸。一般凸函数的逐点最小值不一定凸。

如果把全部变量都取下确界，得到的是一个数 $p^*=\inf_{x,y}F(x,y)$，不再有剩余变量可讨论曲率。若这个数有限，把它视作常函数时自然既凸又凹，但这对任意函数都成立，并非原函数凸性的特殊结果。部分最小化的内容在于：消去一些变量后，关于其余变量的函数仍凸。

最大值的几何直观是：位于最高曲线上方，等价于同时位于每条曲线上方。因此

$$ t\geq\sup_\alpha f_\alpha(x) \iff t\geq f_\alpha(x)\quad\forall\alpha, \qquad \operatorname{epi}\!\left(\sup_\alpha f_\alpha\right) =\bigcap_\alpha\operatorname{epi}f_\alpha. $$

每个上图集凸，交集也凸，所以逐点最大值及上确界保持凸性。下图左侧的蓝色区域是上图集，橙色线段仍在其中；右侧蓝色区域同时位于两条曲线上方，其下边界就是最大值。

部分最小化则是“消去 $y$，只保留每个 $x$ 能达到的最低高度”。考虑凸集

$$ E=\lbrace(x,y,t):y\in C,\ F(x,y)\leq t\rbrace. $$

将它沿 $y$ 方向投影到 $(x,t)$ 平面，便保留所有“存在某个 $y$ 能支付得起”的点。投影保持凸性；若每个有限的下确界都能取到，投影恰好就是 $g(x)=\inf_{y\in C}F(x,y)$ 的上图集。若下确界取不到，边界上可能缺点；使用严格上图集 $t>g(x)$ 可得到同样的凸性结论。

具体看 $F(x,y)=(x-y)^2+y^2=2(y-x/2)^2+x^2/2$。固定 $x$ 后沿 $y$ 方向寻找最低点，得到 $y=x/2$、$g(x)=x^2/2$。下图左侧是高度不超过 $2$ 的椭圆区域，它在 $x$ 轴上的投影为 $[-2,2]$；右侧恰好有 $g(x)\leq2\iff x\in[-2,2]$。让高度 $t$ 变化，就得到整个投影后的上图集。

透视函数可以理解为：把原函数的上图集放在 $t=1$ 的截面上，再从原点沿射线伸缩。以下取 $f(u)=u^2$，用 $s$ 表示高度，避免与尺度 $t$ 混淆。

左图蓝色区域位于 $t=1$ 平面，是原上图集 $s\geq u^2$。从其中一点 $(u,1,r)$ 出发，将三个坐标同时乘以 $t>0$，得到 $(x,t,s)=(tu,t,tr)$。例如，边界点 $(1,1,1)$ 缩放后变为 $(2,2,2)$，而不是 $(2,2,4)$：沿射线缩放时，横坐标和高度一起加倍。

因为 $u=x/t$、$r=s/t$，缩放后的区域满足

$$ r\geq f(u) \iff\frac{s}{t}\geq f(x/t) \iff s\geq t f(x/t). $$

所以这些射线扫出的区域，正是透视函数 $g(x,t)=t f(x/t)$ 的上图集。右图将不同 $t$ 的截面叠放在同一平面；三个彩色点来自同一个原始边界点，沿射线对应，而每条曲线的表达式为 $s=x^2/t$。

这个区域为什么凸？取其中两点 $p_i=t_i(u_i,1,r_i)$，其中 $(u_i,r_i)\in\operatorname{epi}f$。将线段上的点 $p_\theta=\theta p_1+(1-\theta)p_2$ 归一化到 $t=1$，得到原上图集中两点的凸组合，其权重为

$$ \alpha=\frac{\theta t_1}{\theta t_1+(1-\theta)t_2}, \qquad 1-\alpha=\frac{(1-\theta)t_2}{\theta t_1+(1-\theta)t_2}. $$

原上图集凸，归一化后的点仍在其中，因此 $p_\theta$ 仍在射线扫出的区域内。这就证明了透视函数的联合凸性。集合的透视映射则沿同一射线反向归一化：$(x,t,s)\mapsto(x/t,s/t)$。一个从截面向外伸缩，一个投回截面，二者由同一套几何结构联系起来。

外层的单调性负责传递内层的不等式，外层的凸性则负责把“平均输入的输出”控制在“输出的平均”之下。以 $g$ 凸、$h$ 凸且非减为例，令 $x_\theta=\theta x+(1-\theta)y$，有

$$ \begin{aligned} h(g(x_\theta)) &\leq h\bigl(\theta g(x)+(1-\theta)g(y)\bigr) &&\text{（内层凸，外层非减）}\\ &\leq\theta h(g(x))+(1-\theta)h(g(y)) &&\text{（外层凸）}. \end{aligned} $$

第二步正是最终所需的弦上界，单调性无法替代它。例如 $g(x)=x$、$h(u)=\sqrt u$ 在正半轴上都递增，但复合函数仍然凹。这里给的是保证凸性的充分条件；某个具体复合函数即使不满足这些条件，也可能凸。

典型凹凸函数

凸函数：

$$ \begin{gathered} \|x\|,\qquad \log\!\left(\sum_i e^{x_i}\right),\qquad \sum_{i=1}^r x_{[i]},\\[4pt] x\log x,\quad -\log x\quad(x>0),\\[4pt] \frac{x^\top x}{y}\quad(y>0),\qquad t\log\frac{t}{x}\quad(x,t>0),\\[4pt] \lambda_{\max}(X)=\sup_{y\neq0}\frac{y^\top Xy}{y^\top y} \quad(X\in\mathbb S^n),\\[4pt] \max_i f_i(x)\quad(f_i\text{ convex on a common convex domain}). \end{gathered} $$

其中 $x_{[1]}\geq\cdots\geq x_{[n]}$，$1\leq r\leq n$；$x\log x$ 在 $x=0$ 处可取连续延拓值 $0$。

凹函数：

$$ \begin{gathered} \left(\prod_{i=1}^n x_i\right)^{1/n}\quad(x_i\geq0),\\[4pt] \log\det X\quad(X\succ0),\\[4pt] \log\det(I+HXH^\top)\quad(X\in\mathbb S^n,\ I+HXH^\top\succ0). \end{gathered} $$

既凸又凹：

$$ a^\top x+b,\qquad \operatorname{tr}(AX)+b. $$

这里 $a,A,H,b$ 均为固定参数，矩阵维数按表达式匹配。

以下是几种相关的凸性概念。

Definition 5 (Quasiconvex Function, 拟凸函数). A function $f:D\to\mathbb R$ is quasiconvex if $D$ is convex and every sublevel set

$$ S_\alpha=\lbrace x\in D:f(x)\leq\alpha\rbrace, \qquad\alpha\in\mathbb R, $$

is convex. Equivalently,

$$ f(\theta x+(1-\theta)y) \leq\max\lbrace f(x),f(y)\rbrace, \qquad\theta\in[0,1]. $$

A function is quasiconcave if $-f$ is quasiconvex, or equivalently if all its superlevel sets are convex. A function that is both quasiconvex and quasiconcave is called quasilinear.

凸函数一定拟凸，反之不成立。拟凸性只要求沿线段的函数值不超过两个端点中的较大值，比凸性要求的加权平均上界更弱。

Remark：拟凸、拟凹与拟线性的直观

在一维中，可以用一条水平线 $\alpha$ 检查：把满足 $f(x)\leq\alpha$ 的横坐标标出来，如果对任意高度都得到区间、射线、空集或整个定义域，函数就是拟凸的。它可以有尖点或跳跃，也不必向上弯；关键是低值区域不能被中间的高值隔开。

图中橙色虚线表示一个选定高度；浅蓝色竖带和横轴粗线标出对应下水平集，均只展示绘图区内的部分。图 (d) 则直接画出二维的上水平集。

• $f(x)=\sqrt{|x|}$ 在 $\mathbb R$ 上拟凸但不凸。对 $\alpha\geq0$，下水平集为 $[-\alpha^2,\alpha^2]$：虽然两侧曲线并非向上弯，低值区域仍是完整区间。
• $f(x)=\lceil x\rceil$ 在 $\mathbb R$ 上拟线性，即同时拟凸、拟凹。它单调不减，因此下水平集是向左的射线，上水平集是向右的射线；跳跃不影响这些集合的凸性。这里“拟线性”不表示图像是直线。
• $f(x)=\log x$ 在 $x>0$ 上拟线性。它严格递增，下水平集为 $(0,e^\alpha]$，上水平集为 $[e^\alpha,\infty)$。
• $f(x_1,x_2)=x_1x_2$ 在 $x_1,x_2>0$ 上拟凹。对 $\alpha>0$，上水平集为 $x_2\geq\alpha/x_1$，即凸曲线 $\alpha/x_1$ 的上图集；对 $\alpha\leq0$，上水平集是整个正象限。它不是拟凸函数。
• $f(x)=(a^\top x+b)/(c^\top x+d)$ 在 $c^\top x+d>0$ 上拟线性。固定高度 $\alpha$ 后，下水平集满足 $(a-\alpha c)^\top x\leq\alpha d-b$，上水平集则将不等号反向；两者都是半空间与定义域的交集。图 (e) 取 $f(x)=x/(x+1)$，$x>-1$。

图 (f) 的 $f(x)=(x^2-1)^2$ 不拟凸：低于所示水平线的点分成两个互不相连的区间，两个低谷之间有一个更高的隆起。相比之下，一维拟凸函数的典型形态是先不增、再不减，单调函数也包含在内。

拟凹则反过来看高值区域：两个端点的值都不低，中间就不能跌到较低端点以下，即 $f(\theta x+(1-\theta)y)\geq\min\lbrace f(x),f(y)\rbrace$。凹函数要求中间值不低于两端的加权平均，拟凹只要求不低于两端中较小的值，因此条件更弱。它可以形成一个山峰，也可以始终单调；不要求每一段都向下弯。

拟线性同时满足拟凸与拟凹，因此沿任意线段都有

$$ \min\lbrace f(x),f(y)\rbrace \leq f(\theta x+(1-\theta)y) \leq\max\lbrace f(x),f(y)\rbrace. $$

也就是中间值始终落在两端值之间，既不冒出更高的峰，也不陷入更低的谷。在一维区间上，这等价于函数单调（允许平台和跳跃），而不是图像为直线。因此，单调递增的 $\log x$ 和 $\lceil x\rceil$ 都拟线性。

Definition 6 (Log-Convexity and Log-Concavity, 对数凸与对数凹). A positive function $f$ on a convex domain is log-convex if $\log f$ is convex, equivalently,

$$ f(\theta x+(1-\theta)y) \leq f(x)^\theta f(y)^{1-\theta}. $$

It is log-concave if $\log f$ is concave, in which case the inequality is reversed.

由加权算术—几何平均不等式，对数凸函数一定凸；正值凹函数一定对数凹。由于对数保持水平集的次序，对数凹函数也一定拟凹。

最后，对向量值函数，可以用上一节的广义不等式替代标量不等式。

Definition 7 ($K$-Convexity, 关于广义不等式的凸性). Let $K\subseteq\mathbb R^m$ be a proper cone. A function $F:D\to\mathbb R^m$ is $K$-convex if $D$ is convex and

$$ F(\theta x+(1-\theta)y) \preceq_K\theta F(x)+(1-\theta)F(y), \qquad x,y\in D,\quad\theta\in[0,1]. $$

当 $K=\mathbb R_+^m$ 时，$K$-凸等价于各分量分别凸。一般地，可借助对偶锥统一刻画：

$$ F\text{ is }K\text{-convex} \quad\Longleftrightarrow\quad x\mapsto\lambda^\top F(x)\text{ is convex for every }\lambda\in K^*. $$

这里用到了闭凸锥的刻画：$z\in K$ 当且仅当对所有 $\lambda\in K^*$，都有 $\lambda^\top z\geq0$。

Convex Problems

Definition 1 (Standard Form and Convex Problem, 标准形式与凸优化问题). An optimization problem has the form

$$ \begin{aligned} \operatorname{minimize}_{x}\quad & f_0(x)\\ \text{subject to}\quad & f_i(x)\leq0,\quad i=1,\ldots,m,\\ & h_j(x)=0,\quad j=1,\ldots,p. \end{aligned} $$

Its domain is $D=\bigcap_{i=0}^m\operatorname{dom}f_i\cap\bigcap_{j=1}^p\operatorname{dom}h_j$. A point is feasible if it belongs to $D$ and satisfies all constraints. Write the feasible set as $C$ and the optimal value as

$$ p^*=\inf_{x\in C}f_0(x). $$

If $C=\varnothing$, set $p^*=+\infty$; if the objective is unbounded below on $C$, then $p^*=-\infty$. A feasible $x^*$ is optimal if $f_0(x^*)=p^*$. 有限最优值不保证最优解存在。只寻找可行点时，可令目标函数为常数 $0$。

A standard-form problem is convex if $f_0,f_1,\ldots,f_m$ are convex and the equality constraints are affine, written as $Ax=b$.

这些条件保证可行域是凸集：每个不等式选取凸函数的下水平集，仿射等式选取仿射集，再取交集仍然凸。因此，凸优化是在凸可行域上最小化凸函数；不是要求所有约束函数都“严格向上弯”，仿射函数本身也既凸又凹。一般的凸函数等式则不能保证可行域凸，例如 $x_1^2+x_2^2=1$ 是圆周。

这里判断的是问题的表达形式。同一个可行集可以由非凸函数表达，因此不符合标准凸形式的问题，有时仍能通过等价改写成为凸问题。

Definition 2 (Stationary Point and Saddle Point, 驻点与鞍点). Let $f$ be differentiable on an open domain $D$. A point $x\in D$ is stationary if $\nabla f(x)=0$. It is a saddle point if it is stationary and, for every $\varepsilon>0$, there exist $y,z\in D\cap B_\varepsilon(x)$ such that

$$ f(z)\lt f(x)\lt f(y). $$

If $f$ is twice continuously differentiable, a necessary condition for a saddle point is

$$ \lambda_{\min}(\nabla^2f(x))\leq0\leq\lambda_{\max}(\nabla^2f(x)). $$

A sufficient condition at a stationary point is

$$ \lambda_{\min}(\nabla^2f(x))\lt0\lt\lambda_{\max}(\nabla^2f(x)). $$

鞍点一阶上是平的，但任意近处既有上坡也有下坡，因此既不是局部极小点，也不是局部极大点。例如 $f(x_1,x_2)=x_1^2-x_2^2$ 在原点沿一个方向上弯、沿另一个方向下弯。若驻点处 Hessian 同时有正、负特征值，则它是鞍点；仅有最小特征值不大于零不足以判断。这里讨论的是无约束函数的鞍点，与后面拉格朗日函数关于两组变量的鞍点概念需区分。

Theorem 3 (Optimality, 最优性判据). For a convex problem:

• Every local minimum is a global minimum.

• The set of optimal points is convex. If $f_0$ is strictly convex on $C$, there is at most one optimal point.

• If $f_0$ is differentiable on an open set containing $C$, a feasible $x^*$ is optimal if and only if

  $$ \nabla f_0(x^*)^\top(y-x^*)\geq0,\qquad y\in C. $$

最后一个条件表示：任何可行方向都不能在一阶上降低目标值。它包含以下常用情形，假设 $f_0$ 定义并可微于整个 $\mathbb R^n$：

$$ \begin{array}{ll} C=\mathbb R^n: &\nabla f_0(x^*)=0,\\[3pt] C=\lbrace x:Ax=b\rbrace: &Ax^*=b,\quad\nabla f_0(x^*)+A^\top\nu=0 \text{ for some }\nu,\\[3pt] C=\mathbb R_+^n: &x^*\geq0,\quad\nabla f_0(x^*)\geq0,\quad x_i^*\nabla_i f_0(x^*)=0\text{ for every }i. \end{array} $$

Remark：约束最优点的几何直观与互补松弛

对于等式约束 $Ax=b$，可行移动 $d$ 满足 $Ad=0$，而且正反两个方向都允许。最优点处必须有 $\nabla f_0(x^*)^\top d=0$，即梯度垂直于可行仿射空间。因此梯度可以不为零，但必须属于 $A$ 的行空间，等价地写成 $\nabla f_0(x^*)+A^\top\nu=0$。图 (a) 中，等高线在最优点与可行直线相切。

对于非负约束，把 $x\geq0$ 写成 $-x\leq0$，拉格朗日函数为

$$ L(x,\lambda)=f_0(x)-\lambda^\top x,\qquad\lambda\geq0. $$

这里的驻点条件是对 $x$ 求偏导，而不是要求原目标的梯度为零：

$$ \nabla_xL(x^*,\lambda)=\nabla f_0(x^*)-\lambda=0 \quad\Longrightarrow\quad\lambda=\nabla f_0(x^*). $$

因此 $x_i^*\nabla_i f_0(x^*)=0$ 正是互补松弛 $x_i^*\lambda_i=0$。若 $x_i^*>0$，该坐标可以向两边移动，偏导数必须为零；若 $x_i^*=0$，只能向正方向移动，偏导数只需非负。图 (b) 取 $f(x)=(x_1+1)^2+(x_2-1)^2$，最优点为 $(0,1)$：向左下坡被边界挡住，沿边界上下移动则已到谷底。

整理模型时，常通过引入变量或消去变量，把问题变成更容易识别的形式。

Proposition 4 (Equivalent Reformulations, 等价改写). The following preserve the optimal value, with solutions recovered as indicated.

• Eliminating affine equalities. If $Ax=b$ is consistent, write $x=x_0+Fz$, where $Ax_0=b$ and the columns of $F$ span $\ker A$, then substitute into the objective and inequalities.
• Slack variables. Replace $Gx\leq h$ by $Gx+s=h$, $s\geq0$.
• Epigraph form. Replace minimizing $f_0(x)$ over $C$ by minimizing $t$ subject to $x\in C$ and $f_0(x)\leq t$.
• Partial minimization. Replace $\inf_{x\in C,y}F(x,y)$ by $\inf_{x\in C}\widetilde f(x)$, where $\widetilde f(x)=\inf_yF(x,y)$. Recovering an optimal pair requires the inner infimum at the chosen $x$ to be attained.

上图集改写把“降低函数值”变成“降低一个足以覆盖函数值的高度 $t$”。例如，无穷范数最小化满足

$$ \min_{x\in C}\|Ax-b\|_\infty \quad\Longleftrightarrow\quad \begin{aligned} \operatorname{minimize}_{x,t}\quad&t\\ \text{subject to}\quad&-t\mathbf1\leq Ax-b\leq t\mathbf1,\\ &x\in C. \end{aligned} $$

因为 $\|Ax-b\|_\infty\leq t$ 等价于每个残差都落在 $[-t,t]$ 中，$t$ 就是统一的最大误差上界。对固定的 $x$，最小可行 $t$ 恰好等于原范数，因此改写是精确的；若原问题有最优解，最优点上必有 $t=\|Ax-b\|_\infty$。当 $C$ 由线性约束给出时，新问题就是线性规划：不可微的最大绝对值目标被换成了线性目标与线性不等式，便于直接使用 LP 算法。取 $A=I,b=0$ 即得到 $\min_{x\in C}\|x\|_\infty$；若完全没有约束，其最优解就是 $x=0$。

下面几类模型都有专门的算法。矩阵 $P_i$ 均取对称矩阵，SOCP 中的范数为欧氏范数。

Definition 5 (LP, QP, and QCQP). A linear program (LP) has affine objective and constraints. A convex quadratic program (QP) allows a convex quadratic objective; a convex QCQP also allows convex quadratic inequalities:

$$ \begin{array}{lll} \text{(LP)}&\min_x c^\top x+d &\text{s.t. }Gx\leq h,\ Ax=b,\\[3pt] \text{(QP)}&\min_x\frac12x^\top Px+q^\top x+r &\text{s.t. }Gx\leq h,\ Ax=b,\quad P\succeq0. \end{array} $$

A convex QCQP has the form

$$ \text{(QCQP)}\qquad \begin{aligned} \operatorname{minimize}_x\quad &\frac12x^\top P_0x+q_0^\top x+r_0\\ \text{subject to}\quad &\frac12x^\top P_ix+q_i^\top x+r_i\leq0,\quad i=1,\ldots,m,\\ &Ax=b. \end{aligned} $$

Convexity requires $P_i\succeq0$ for $i=0,\ldots,m$. Equality constraints remain affine.

Definition 6 (SOCP and SDP). A second-order cone program (SOCP) has the form

$$ \text{(SOCP)}\qquad \begin{aligned} \operatorname{minimize}_x\quad &c^\top x\\ \text{subject to}\quad &\|A_ix+b_i\|_2\leq c_i^\top x+d_i,\quad i=1,\ldots,m,\\ &Fx=g. \end{aligned} $$

A semidefinite program (SDP) has an affine objective, affine equalities, and linear matrix inequalities (LMIs):

$$ \text{(SDP)}\qquad \begin{aligned} \operatorname{minimize}_x\quad &c^\top x\\ \text{subject to}\quad &\sum_{i=1}^n x_iF_i\preceq G,\\ &Ax=b, \end{aligned} \qquad F_i,G\in\mathbb S^r. $$

Remark：LP、QP、QCQP、SOCP 与 SDP 如何转换

这里 QP、QCQP 均指凸情形。LP 是令二次项为零的 QP；QP 又是所有不等式约束均为仿射的 QCQP。这两步只是特殊情形的包含，不需要引入变量。

凸 QCQP → SOCP：把半正定二次型写成平方范数。 对 $P_i\succeq0$，取分解 $P_i=R_i^\top R_i$。令 $s_i=-q_i^\top x-r_i$，则每个二次约束等价于

$$ \frac12x^\top P_ix+q_i^\top x+r_i\leq0 \quad\Longleftrightarrow\quad \left\|\begin{pmatrix}\sqrt2R_ix\\s_i-1\end{pmatrix}\right\|_2\leq s_i+1. $$

右侧平方展开即为 $\|R_ix\|_2^2\leq2s_i$，且范数不等式自动保证 $s_i\geq0$。对二次目标先引入上图集变量 $t$，把目标改为最小化 $t$，再将 $\frac12x^\top P_0x+q_0^\top x+r_0\leq t$ 同样转换即可。因此凸 QP 也可以沿这条路径写成 SOCP。

SOCP → SDP：把范数约束写成块矩阵半正定约束。 利用

$$ \|u\|_2\leq t \quad\Longleftrightarrow\quad \begin{pmatrix}tI&u\\u^\top&t\end{pmatrix}\succeq0. $$

在 SOCP 中代入 $u=A_ix+b_i$、$t=c_i^\top x+d_i$，块矩阵的每个元素都是 $x$ 的仿射函数，因此得到 LMI。

这里用到 Schur 补：对称分块矩阵消去左上角的块后，右下角剩下的部分为

$$ M=\begin{pmatrix}A&B\\B^\top&C\end{pmatrix}, \qquad S=C-B^\top A^{-1}B. $$

当 $A\succ0$ 时，$M\succeq0$ 当且仅当 $S\succeq0$。可以把它记成“右下角 − 左下角 × 左上角的逆 × 右上角”，类似分块高斯消元。

对上面的范数约束，$t>0$ 时取 $A=tI$、$B=u$、$C=t$，直接代入：

$$ S=t-u^\top(tI)^{-1}u =t-\frac{u^\top u}{t} =t-\frac{\|u\|_2^2}{t}. $$

因此

$$ M\succeq0 \iff t-\frac{\|u\|_2^2}{t}\geq0 \iff t^2\geq\|u\|_2^2 \iff t\geq\|u\|_2. $$

上述 Schur 补判据要求左上角正定，因此这里先取 $t>0$。$t=0$ 时半正定要求 $u=0$；$t<0$ 时对角元素为负，不可能半正定。合起来即得到完整的等价关系。

反向转换取决于结构。 SOCP 中若所有范数都是标量绝对值，就可拆成两条线性不等式，得到 LP；SDP 中若所有矩阵约束都是对角矩阵半正定，也退化为 LP。具有上述块结构的 LMI 可以还原为 SOCP，但一般 SDP 不能统一写成 SOCP。类似地，不能把一般 SOCP 直接平方就声称得到凸 QCQP：平方后可能丢失右侧非负条件，所得二次型也未必半正定。

沿箭头转换的意义是获得统一的建模与求解形式，并不意味着一定求得更快；能保留更简单的模型结构时，通常优先保留。

例：不定二次规划的提升与秩一约束

考虑 $\min_{Ax\leq b}\frac12x^\top Px+q^\top x$，其中 $P$ 对称但可以不定。引入 $X=xx^\top$，利用 $x^\top Px=\operatorname{tr}(PX)$，原问题精确等价于

$$ \begin{aligned} \operatorname{minimize}_{X,x}\quad &\frac12\operatorname{tr}(PX)+q^\top x\\ \text{subject to}\quad &Ax\leq b,\\ &Y=\begin{pmatrix}X&x\\x^\top&1\end{pmatrix}\succeq0, \quad\operatorname{rank}Y=1. \end{aligned} $$

二次目标变成了线性目标，但非凸性转移到了秩约束中。删掉秩约束便得到 SDP 松弛，其最优值是原问题的下界。

对 $Y\succeq0$，特征值非负，因而

$$ \operatorname{tr}Y-\lambda_{\max}(Y) =\sum_{i=2}^{n+1}\lambda_i(Y)=0 \iff\operatorname{rank}Y\leq1. $$

这里 $Y_{n+1,n+1}=1$ 排除了零矩阵，所以恰好等价于秩一。因此，保留 $Y=\begin{pmatrix}X&x\\x^\top&1\end{pmatrix}\succeq0$，将 $\operatorname{rank}Y=1$ 替换为 $\operatorname{tr}Y-\lambda_{\max}(Y)=0$，仍是精确改写；该等式不能替代半正定约束。

也可以在目标中加入惩罚 $\rho[\operatorname{tr}Y-\lambda_{\max}(Y)]$，其中 $\rho>0$。取当前矩阵 $Y_k$ 的单位最大特征向量 $u_k$，有

$$ \lambda_{\max}(Y)\geq u_k^\top Yu_k, \qquad\lambda_{\max}(Y_k)=u_k^\top Y_ku_k. $$

迹是线性函数，最大特征值是凸函数，因此该惩罚具有 DC（Difference of Convex Functions，凸函数之差）结构。用在当前点贴合的线性上界 $\operatorname{tr}Y-u_k^\top Yu_k$ 替换惩罚项，每步求解一个凸 SDP，这就是 MM（Majorization–Minimization，上界最小化）的思路。

Proposition 7 (Cone Constraints, 锥约束). A problem with convex objective, affine equalities, and constraints $F_i(x)\preceq_{K_i}0$ is convex when each $F_i$ is $K_i$-convex and each $K_i$ is proper. If the objective and all constraint maps are affine, this is a conic program. LP, SOCP, and SDP correspond respectively to nonnegative, second-order, and positive-semidefinite cones.

Definition 8 (Quasiconvex Problem, 拟凸优化问题). A problem is quasiconvex if its objective is quasiconvex and its feasible set $C$ is convex. For fixed $t$, the problem

$$ \text{find }x\in C\quad\text{such that }f_0(x)\leq t $$

is a convex feasibility problem.

给定 $\ell\leq p^*\leq u$ 且上界 $u$ 对应可行点，测试 $t=(\ell+u)/2$：若可行，令 $u=t$；若不可行，令 $\ell=t$。每次将区间长度减半。

拟凸问题不保证每个局部最优点都是全局最优点；二分法依赖的是水平集的凸性及可行性随 $t$ 的单调变化。

Lagrange Duality

对偶的出发点是构造原问题最优值的下界。以下先考虑标准形式问题，定义域为非空集合 $D$，暂不要求问题凸。

Definition 1 (Lagrangian and Dual Function, 拉格朗日函数与对偶函数). Define

$$ L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^m\lambda_if_i(x) +\sum_{j=1}^p\nu_jh_j(x), \qquad g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu). $$

其中 $\lambda$ 和 $\nu$ 为乘子。取下确界时保留 $x\in D$，但去掉显式约束。对固定的 $x$，$L$ 关于乘子是仿射函数，因此其逐点下确界 $g$ 是凹函数，也可能取 $-\infty$。

Proposition 2 (Lower Bounds and Weak Duality, 下界与弱对偶). For any primal-feasible $x$ and any $\lambda\geq0$,

$$ g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x). $$

因此 $g(\lambda,\nu)\leq p^*$。不等式乘子要求非负，是为了保证可行点上 $\lambda_if_i(x)\leq0$；等式项在可行点上为零，所以 $\nu$ 没有符号限制。

Definition 3 (Dual Problem, 对偶问题). The Lagrange dual problem seeks the best such lower bound:

$$ \begin{aligned} \operatorname{maximize}_{\lambda,\nu}\quad &g(\lambda,\nu)\\ \text{subject to}\quad &\lambda\geq0. \end{aligned} $$

有效可行域还要求 $g(\lambda,\nu)>-\infty$，记最优值为 $d^*$。由于 $g$ 凹，对偶问题总是最大化形式的凸优化问题；即使原问题非凸，也有弱对偶 $d^*\leq p^*$。

Definition 4 (Strong Duality, 强对偶). Strong duality means $d^*=p^*$. When both values are finite, $p^*-d^*$ is the duality gap.

对目标值有限的原始可行点 $x$ 和对偶可行点 $(\lambda,\nu)$，有

$$ 0\leq f_0(x)-p^*\leq f_0(x)-g(\lambda,\nu). $$

因此，可行原始解与对偶解之间的差可以作为最优性误差上界；若两者目标值相等，它们分别就是原问题和对偶问题的最优解。凸性本身不保证强对偶，通常还需要约束资格条件。

Theorem 5 (Slater’s Condition, Slater 条件). Consider a convex problem with affine equalities $Ax=b$ and common convex domain $D$. If there exists $\bar x\in\operatorname{ri}D$ such that

$$ f_i(\bar x)<0,\quad i=1,\ldots,m, \qquad A\bar x=b, $$

then strong duality holds. If $p^*$ is finite, the dual optimum is attained.

$\operatorname{ri}D$ 表示 $D$ 在其仿射包中的相对内部；满维时就是 $\operatorname{int}D$。

在 $p^*$ 有限时，Slater 条件保证对偶最优解存在，但不保证原始最优解存在。对于仿射不等式，严格可行要求可以放宽为普通可行；非仿射不等式仍需严格成立。

Proposition 6 (Complementary Slackness, 互补松弛). Suppose strong duality holds with finite optimal value, and both optima are attained at $x^*$ and $(\lambda^*,\nu^*)$. Then

$$ \lambda_i^*f_i(x^*)=0,\quad i=1,\ldots,m, \qquad x^*\in\operatorname*{arg\,min}_{x\in D}L(x,\lambda^*,\nu^*). $$

因为 $g(\lambda^*,\nu^*)\leq L(x^*,\lambda^*,\nu^*)\leq f_0(x^*)$ 两端相等，中间两步也必须取等。特别地，

$$ f_i(x^*)<0\Longrightarrow\lambda_i^*=0, \qquad \lambda_i^*>0\Longrightarrow f_i(x^*)=0. $$

约束取等号不意味着乘子一定为正；乘子也可能为零。

Theorem 7 (KKT Conditions, KKT 条件). Assume the objective and constraint functions are differentiable on an open domain $D$. The Karush–Kuhn–Tucker conditions are

$$ \begin{aligned} &f_i(x^*)\leq0,\quad h_j(x^*)=0, &&\text{(primal feasibility)},\\ &\lambda_i^*\geq0, &&\text{(dual sign condition)},\\ &\lambda_i^*f_i(x^*)=0, &&\text{(complementary slackness)},\\ &\nabla f_0(x^*)+\sum_i\lambda_i^*\nabla f_i(x^*) +\sum_j\nu_j^*\nabla h_j(x^*)=0, &&\text{(stationarity)}. \end{aligned} $$

• Necessity. A primal-dual optimal pair with finite equal values satisfies KKT. More generally, suitable constraint qualifications give KKT multipliers at a local optimum.
• Sufficiency for convex problems. Any KKT triple is primal-dual optimal, with zero duality gap. Slater’s condition is not needed for this implication.
• Necessary and sufficient under Slater. For a differentiable convex problem satisfying Slater’s condition, a feasible $x^*$ is optimal if and only if some multipliers make it a KKT triple.

充分性的关键是：凸问题的 $L(\cdot,\lambda,\nu)$ 在 $\lambda\geq0$ 时为凸函数，驻点条件便保证全局最小，再由互补松弛得到 $g(\lambda,\nu)=f_0(x)$。非凸问题中的 KKT 通常只是必要条件。

Proposition 8 (Dual Multipliers for Cone Constraints, 锥约束的对偶乘子). For a constraint $F_i(x)\preceq_{K_i}0$, use a multiplier $\lambda_i\in K_i^*$ and the Lagrangian term $\langle\lambda_i,F_i(x)\rangle$. Then the same lower-bound argument applies, and complementary slackness becomes

$$ \langle\lambda_i^*,F_i(x^*)\rangle=0. $$

对称矩阵的内积取 $\langle A,B\rangle=\operatorname{tr}(AB)$。原始锥规定约束的方向，对偶锥规定哪些线性权重能保持下界成立。