最优化方法

1. Introduction to optimization

1.1. 范数

1.2. 泰勒展开

𝑓 (𝑥_{0} + 𝑥) = 𝑓 (𝑥_{0}) + 𝑓^{'} (𝑥_{0}) 𝑥 + \frac{𝑓^{″} (𝑥_{0})}{2!} 𝑥^{2} + \dots

1.3. Hessian 矩阵

\nabla^{2} 𝑓 (𝑥) = (\begin{matrix} \frac{\partial^{2} 𝑓 (𝑥)}{\partial 𝑥_{1}^{2}} & \dots & \frac{\partial^{2} 𝑓 (𝑥)}{\partial 𝑥_{𝑛} \partial 𝑥_{1}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial^{2} 𝑓 (𝑥)}{\partial 𝑥_{1} \partial 𝑥_{𝑛}} & \dots & \frac{\partial^{2} 𝑓 (𝑥)}{\partial 𝑥_{𝑛}^{2}} \end{matrix})

1.4. 矩阵正定的判定

$\forall 𝑥, 𝑥^{𝑇} 𝐴 𝑥 > 0$
各阶顺序主子式都大于0
（负定的判定是奇数阶为负，偶数阶为正）

1.5. 矩阵逆的计算

(\begin{matrix} 0 & 1 & 2 \\ 2 & - 1 & 4 \\ 2 & - 1 & 0 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \overset{初等行变换}{\to} (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}) (\begin{matrix} \frac{1}{2} & - \frac{1}{4} & \frac{3}{4} \\ 1 & - \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{4} & - \frac{1}{4} \end{matrix})

右侧即为逆矩阵

2. Approximation and fitting

2.1. 范数近似

\min_{𝑥} {‖ 𝐴 𝑥 - 𝑏 ‖}_{2}

𝐴 \in ℝ^{𝑚 \times 𝑛} 𝑥 \in ℝ^{𝑛 \times 1} 𝑏 \in ℝ^{𝑚 \times 1}

求导：

\begin{matrix} \nabla_{𝑥} ({(𝐴 𝑥 - 𝑏)}^{𝑇} (𝐴 𝑥 - 𝑏)) & = 2 𝐴^{𝑇} (𝐴 𝑥 - 𝑏) \end{matrix}

\begin{matrix} 𝑓 (𝑥) : ℝ^{𝑛} \to ℝ^{𝑚}, 𝑔 (𝑥) : ℝ^{𝑛} \to ℝ^{𝑚} \\ \nabla ({𝑓 (𝑥)}^{𝑇} 𝑔 (𝑥)) = \nabla {𝑓 (𝑥)}^{𝑇} 𝑔 (𝑥) + \nabla {𝑔 (𝑥)}^{𝑇} 𝑓 (𝑥) \end{matrix}

\begin{matrix} 𝑓 (𝑥) : ℝ^{𝑛} \to ℝ, 𝑔 (𝑥) : ℝ^{𝑛} \to ℝ^{𝑚} \\ \nabla (𝑓 (𝑥) 𝑔 (𝑥)) = 𝑔 (𝑥) {(\nabla 𝑓 (𝑥))}^{𝑇} + 𝑓 (𝑥) \nabla 𝑔 (𝑥) \end{matrix}

3. Convex sets

3.1. affine set

集合中任意两点的连线也都在集合中 $\forall 𝑥_{1}, 𝑥_{2} \in 𝑆, \forall 𝜃 \in ℝ, 𝑥 = 𝜃 𝑥_{1} + (1 - 𝜃) 𝑥_{2} also in 𝑆$

3.2. convex set

集合中任意两点的连线段也在集合中 $\forall 𝑥_{1}, 𝑥_{2} \in 𝑆, \forall 𝜃 \in [0, 1], 𝑥 = 𝜃 𝑥_{1} + (1 - 𝜃) 𝑥_{2} also in 𝑆$

3.3. convex hull

convex combination: $\forall 𝑥_{𝑖}, \forall 𝜃_{𝑖} \geq 0 and \sum_{𝑖} 𝜃_{𝑖} = 1, \sum_{𝑖} 𝜃_{𝑖} 𝑥_{𝑖}$

convex hull is:

conv 𝑆 = set of all convex combination points of 𝑆

3.4. convex cone

conic combination: $\forall 𝑥_{1}, 𝑥_{2}, \dots 𝑥_{𝑛}, \forall 𝜃_{1}, 𝜃_{2}, \dots 𝜃_{𝑛} \geq 0, \sum_{𝑖} 𝜃_{𝑖} 𝑥_{𝑖}$

convex cone is: set that contains all conic combinations of points in the set

3.5. simplices （单纯型）

{𝑥 \in ℝ^{𝑛} | 𝑥^{𝑇} 𝟏 = 1, 𝑥 ⪰ 0}

3.6. 是 norm 函数的要求

$‖ 𝑥 ‖ \geq 0; ‖ 𝑥 ‖ = 0 \Leftrightarrow 𝑥 = 0$
$‖ 𝑡 𝑥 ‖ = | 𝑡 | ‖ 𝑥 ‖ for 𝑡 \in ℝ$
$‖ 𝑥 + 𝑦 ‖ \leq ‖ 𝑥 ‖ + ‖ 𝑦 ‖$

3.7. Positive semidefinite cone （半正定锥）

𝑆_{+}^{𝑛} = {𝑋 \in ℝ^{𝑛 \times 𝑛} | 𝑋 ⪰ 0}

为什么是锥？举个例子

(\begin{matrix} 𝑥 & 𝑦 \\ 𝑦 & 𝑧 \end{matrix}) ⪰ 0 \Leftrightarrow 𝑥 𝑧 - 𝑦^{2} \geq 0

在 $(𝑥, 𝑦, 𝑧)$ 的空间上是一个锥

3.8. closure, interior and boundary

closure of $𝑆$: $cl (𝑆) = set of all limit points of 𝑆$
interior of $𝑆$: $int (𝑆) = {𝑥 | Ball (𝑥, 𝑟) \in 𝐶, 𝑟 > 0}$
boundary of $𝑆$: $bd 𝑆 = \partial (𝑆) = cl (𝑆) - int (𝑆)$

𝑆 is convex \Rightarrow int (𝑆) is convex and cl (𝑆) is convex

3.9. relative interior

relint (𝑆) = {𝑥 | Ball (𝑥, 𝑟) \cap Aff (𝐶) \in 𝐶, 𝑟 > 0}

and relative boundary is

cl (𝑆) - relint (𝑆)

4. Convex functions

4.1. strict convex

𝑓 (𝜃 𝑥_{1} + (1 - 𝜃) 𝑥_{2}) < 𝜃 𝑓 (𝑥_{1}) + (1 - 𝜃) 𝑥_{2}

4.2. strongly convex

𝑓 (𝜃 𝑥_{1} + (1 - 𝜃) 𝑥_{2}) \leq 𝜃 𝑓 (𝑥_{1}) + (1 - 𝜃) 𝑓 (𝑥_{2}) - \frac{1}{2} 𝑐 𝜃 (1 - 𝜃) {‖ 𝑥_{2} - 𝑥_{1} ‖}^{2}

which is equivalent to $𝑓 - \frac{1}{2} 𝑐 {‖ \cdot ‖}^{2}$ is convex

4.3. 扩充定义域

对于不在 $𝑓$ 定义域中的函数值定义为 $+ \infty$

$dom 𝑓$ 需要是凸集

4.4. 凸函数的一阶判定条件

𝑓 (𝑥) \geq 𝑓 (𝑥_{0}) + {(\nabla 𝑓 (𝑥_{0}))}^{𝑇} (𝑥 - 𝑥_{0})

4.5. 凸函数的二阶判定条件

\nabla^{2} 𝑓 (𝑥) ⪰ 0

矩阵 $𝐻$ 正定的一个判定方法：对于任意向量 $𝑣$ ，都有 $𝑣^{𝑇} 𝐻 𝑣 \geq 0$

4.6. epigraph and $𝛼$ -sublevel set

$𝛼$ -sublevel set: $𝐶_{𝛼} = {𝑥 | 𝑓 (𝑥) \leq 𝛼}$
epigraph: $epi 𝑓 = {(𝑥, 𝑡) | 𝑓 (𝑥) \leq 𝑡, 𝑥 \in dom 𝑓}$ $epi 𝑓 is convex set \Leftrightarrow 𝑓 is convex function$

4.7. closed convex function

闭集(closed set)

包含其所有极限点的集合

lower semi-continuous (l.s.c)

\lim_{𝑦 \to 𝑥} 𝑓 (𝑦) \geq 𝑓 (𝑥)

也叫下半连续

closed function

l.s.c everywhere
or epigraph is closed
or all sublevel sets are closed

紧集 (compact set)

有界闭集

4.8. Pointwise supremum and Minimization

if $𝑓 (𝑥, 𝑦)$ is convex in $𝑥$ for each $𝑦 \in 𝒜$ , then $𝑔$ is convex

𝑔 (𝑥) = \sup_{𝑦 \in 𝒜} 𝑓 (𝑥, 𝑦)

if $𝑓 (𝑥, 𝑦)$ is convex in $(𝑥, 𝑦)$ and $𝐶$ is convex set, then $𝑔$ is convex

𝑔 (𝑥) = \inf_{𝑦 \in 𝐶} 𝑓 (𝑥, 𝑦)

4.9. Conjugate function （共轭函数）

𝑓^{*} (𝑦) = \sup_{𝑥 \in dom 𝑓} (𝑦^{𝑇} 𝑥 - 𝑓 (𝑥))

共轭函数 $𝑓^{*} (𝑦)$ 总是凸的，因为它是一系列直线的 sup

记几个例子：

\begin{matrix} 𝑓^{*} (𝑦) & = \sup_{𝑥} (𝑦^{𝑇} 𝑥 - \max (𝑥)) \\ = {\begin{matrix} 0 & if 𝑦 ⪰ 0 and 𝑦^{𝑇} 𝟏 = 1 \\ + \infty & otherwise \end{matrix} \end{matrix}

\begin{matrix} 𝑓^{*} (𝑦) & = \sup_{𝑥} (𝑦^{𝑇} 𝑥 - \sum_{𝑖 = 1}^{𝑟} 𝑖 -largest (𝑥)) \\ = {\begin{matrix} 0 & if 𝑦 ⪰ 0 and 𝑦^{𝑇} 𝟏 = 𝑟 \\ + \infty & otherwise \end{matrix} \end{matrix}

\begin{matrix} 𝑓^{*} (𝑦) & = \sup_{𝑥} (𝑦 𝑥 - \frac{{| 𝑥 |}^{𝑝}}{𝑝}) \\ = \frac{{| 𝑦 |}^{𝑞}}{𝑞} (where \frac{1}{𝑝} + \frac{1}{𝑞} = 1 and 𝑥, 𝑦 \in ℝ) \end{matrix}

4.10. 对偶范数

{‖ 𝑦 ‖}_{*} = \sup_{‖ 𝑥 ‖ \leq 1} 𝑦^{𝑇} 𝑥

$𝑙_{𝑝}$ 范数和 $𝑙_{𝑞}$ 范数互为对偶范数的条件是（如 $1$ 和 $\infty$ 、 $2$ 和 $2$ ）
$\frac{1}{𝑝} + \frac{1}{𝑞} = 1$
范数 $𝑓 (𝑥) = ‖ 𝑥 ‖$ 的共轭函数是 $𝑓^{*} (𝑦) = {\begin{matrix} 0 & if {‖ 𝑦 ‖}_{*} \leq 1 \\ + \infty & otherwise \end{matrix}$
(对偶范数单位球的指示函数)
$\sup_{𝑥 \in dom 𝑓} (𝑦^{𝑇} 𝑥 - ‖ 𝑥 ‖) = {\begin{matrix} 0 & if {‖ 𝑦 ‖}_{*} \leq 1 \\ + \infty & otherwise \end{matrix}$
对于一般的 $‖ \cdot ‖$ ， $𝑓 (𝑥) = \frac{1}{2} {‖ 𝑥 ‖}^{2}$ 的共轭函数是 $𝑓^{*} (𝑦) = \frac{1}{2} {‖ 𝑦 ‖}_{*}^{2}$

4.11. conjugate of conjugate

if $𝑓$ is convex and closed

𝑓 (𝑥) = 𝑓^{* *} (𝑥)

5. Convex optimization problems

5.1. standard form convex optimization problem

\begin{matrix} \min & 𝑓_{0} (𝑥) \\ s.t. & 𝑓_{𝑖} (𝑥) \leq 0 𝑖 = 1, \dots, 𝑚 \\ 𝑎_{𝑖}^{𝑇} 𝑥 = 𝑏_{𝑖} 𝑖 = 1, \dots, 𝑛 \end{matrix}

where $𝑓_{0}, 𝑓_{1}, \dots, 𝑓_{𝑚}$ are convex functions

等式约束需要是线性的（要不然定义域就不是凸的了）

5.2. Optimality criterion for differentiable $𝑓_{0}$

if $𝑥$ is optimal, for all feasible $𝑦$

\nabla 𝑓_{0} {(𝑥)}^{𝑇} (𝑦 - 𝑥) \geq 0

不仅对于无约束问题成立（废话因为 $𝑓_{0} (𝑥) = 0$ ），对于有约束问题也是成立的

5.3. Equivalent convex problems

如果一个问题的解很容易从另一个问题的解中得到，那么两个问题就是（非正式的）等价的，反之亦然例如

\begin{matrix} \min_{𝑥} & 𝑓_{0} (𝑥) \\ s.t. & 𝑓_{𝑖} (𝑥) \leq 0 \\ 𝐴 𝑥 = 𝑏 \end{matrix}

可以等价于

\begin{matrix} \min_{𝑧} & 𝑓_{0} (𝐹 𝑧 + 𝑥_{0}) \\ s.t. & 𝑓_{𝑖} (𝐹 𝑥 + 𝑧_{0}) \leq 0 \end{matrix}

where 𝐴 𝑥 = 𝑏 \Leftrightarrow 𝑥 = 𝐹 𝑧 + 𝑥_{0}

又例如

\begin{matrix} \min_{𝑥} & 𝑓_{0} (𝐴_{0} 𝑥 + 𝑏_{0}) \\ s.t. & 𝑓_{𝑖} (𝐴_{𝑖} 𝑥 + 𝑏_{𝑖}) \leq 0 \end{matrix}

可以等价于

5.4. piecewise-linear minimization

\min_{𝑥} (\max_{𝑖} (𝑎_{𝑖}^{𝑇} 𝑥 + 𝑏_{𝑖}))

等价于

\begin{matrix} \min_{𝑥, 𝑡} & 𝑡 \\ s.t. & 𝑎_{𝑖}^{𝑇} 𝑥 + 𝑏_{𝑖} \leq 𝑡 \end{matrix}

5.5. Chebyshev center of a polyhedron

\begin{matrix} 𝒫 = {𝑥 | 𝑎_{𝑖}^{𝑇} 𝑥 \leq 𝑏} \\ ℬ = {𝑥 + 𝑢 | {‖ 𝑢 ‖}_{2} \leq 𝑟} \end{matrix}

求这个最大半径的问题可以化简成LP

\begin{matrix} \max & 𝑟 \\ s.t. & 𝑎_{𝑖}^{𝑇} 𝑥 + 𝑟 {‖ 𝑎_{𝑖} ‖}_{2} \leq 𝑏 \end{matrix}

5.6. Quadratic program (QP)

\begin{matrix} \min_{𝑥} & \frac{1}{2} 𝑥^{𝑇} 𝑃 𝑥 + 𝑞^{𝑇} 𝑥 + 𝑟 \\ s.t. & 𝐺 𝑥 \leq ℎ \\ 𝐴 𝑥 = 𝑏 \end{matrix}

QP的不等式约束也是线性的，不等式约束是二次的叫QCQP
二阶锥规划的不等式约束形式是 ${‖ 𝐴_{𝑖} 𝑥 + 𝑏_{𝑖} ‖}_{2} \leq 𝑐_{𝑖}^{𝑇} 𝑥 + 𝑑_{𝑖}$

6. Unconstrained minimization

6.1. 对于强凸函数

\nabla^{2} 𝑓 (𝑥) ⪰ 𝑚 𝐼

\begin{matrix} 𝑓 (𝑦) & = 𝑓 (𝑥) + \nabla {𝑓 (𝑥)}^{𝑇} (𝑦 - 𝑥) + \frac{1}{2} {(𝑦 - 𝑥)}^{𝑇} \nabla^{2} 𝑓 (𝜉) (𝑦 - 𝑥) \\ \geq 𝑓 (𝑥) + \nabla {𝑓 (𝑥)}^{𝑇} (𝑦 - 𝑥) + \frac{1}{2} 𝑚 {‖ 𝑦 - 𝑥 ‖}_{2}^{2} \end{matrix}

在右侧对 $𝑦$ 求最小值 $\nabla 𝑓 (𝑥) + 𝑚 (𝑦 - 𝑥) = 0$ , 所以 $𝑦 = 𝑥 - \frac{1}{𝑚} \nabla 𝑓 (𝑥)$

带入到右式子是 $𝑓 (𝑥) - \frac{1}{2 𝑚} {‖ \nabla 𝑓 (𝑥) ‖}_{2}^{2}$

\begin{matrix} 𝑓 (𝑦) \geq 𝑓 (𝑥) - \frac{1}{2 𝑚} {‖ \nabla 𝑓 (𝑥) ‖}_{2}^{2} \\ 𝑓 (𝑥) - 𝑝^{*} \leq \frac{1}{2 𝑚} {‖ \nabla 𝑓 (𝑥) ‖}_{2}^{2} \end{matrix}

6.2. general descent method

given starting point $𝑥_{0}$
repeat
1. 计算下降方向 $Δ 𝑥$
2. 选择更新步长 $𝑡 > 0$
3. $𝑥 ≔ 𝑥 + 𝑡 Δ 𝑥$
until stopping criterion is satisfied

6.3. exact line search

𝑡 = {argmin}_{𝑡 > 0} 𝑓 (𝑥 + 𝑡 Δ 𝑥)

6.4. backtracking line search

$𝛼 \in (0, \frac{1}{2}), 𝛽 \in (0, 1)$
初始时 $𝑡 = 1$
不断令 $𝑡 = 𝛽 𝑡$ 直到

𝑓 (𝑥 + 𝑡 Δ 𝑥) < 𝑓 (𝑥) + 𝑡 𝛼 \nabla {𝑓 (𝑥)}^{𝑇} Δ 𝑥

6.5. gradient descent method

Δ 𝑥 = - \nabla 𝑓 (𝑥)

以指数收敛：

𝑓 (𝑥^{(𝑘)}) - 𝑝^{*} = 𝑐^{𝑘} (𝑓 (𝑥^{(0)}) - 𝑝^{*})

6.6. steepst descent method

normalized steepst descent direction: $Δ 𝑥_{nsd} = {argmin}_{‖ 𝑣 ‖ = 1} \nabla {𝑓 (𝑥)}^{𝑇} 𝑣$
(unnormalized) steepst descent direction: $Δ 𝑥_{sd} = {‖ \nabla 𝑓 (𝑥) ‖}_{*} Δ 𝑥_{nsd}$

6.7. Newton Step

Δ 𝑥_{nt} = - {(\nabla^{2} 𝑓 (𝑥))}^{- 1} \nabla 𝑓 (𝑥)

因为取 $𝑓$ 的二阶近似

\begin{matrix} \hat{𝑓} (𝑥 + 𝑣) = 𝑓 (𝑥) + \nabla 𝑓 (𝑥) 𝑣 + \frac{1}{2} 𝑣^{𝑇} \nabla^{2} 𝑓 (𝑥) 𝑣 \\ \nabla_{𝑣} \hat{𝑓} (𝑥 + 𝑣) = \nabla 𝑓 (𝑥) + \nabla^{2} 𝑓 (𝑥) 𝑣 \\ Δ 𝑥_{nt} = 𝑣 = - {(\nabla^{2} 𝑓 (𝑥))}^{- 1} \nabla 𝑓 (𝑥) \end{matrix}

可以认为牛顿步是 ${‖ \cdot ‖}_{\nabla^{2} 𝑓 (𝑥)}$ 下的最速下降

{‖ 𝑥 ‖}_{𝑃} = {(𝑥^{𝑇} 𝑃 𝑥)}^{\frac{1}{2}}

${‖ \cdot ‖}_{𝑃}$ 的对偶范数是 ${‖ \cdot ‖}_{𝑃^{- 1}}$

6.8. Newton decrement

\begin{matrix} \hat{𝑓} (𝑥 + Δ 𝑥_{nt}) = 𝑓 (𝑥) - \frac{1}{2} \nabla 𝑓 (𝑥) \nabla^{2} {𝑓 (𝑥)}^{- 1} \nabla 𝑓 (𝑥) \\ 𝑓 (𝑥) - \hat{𝑓} (𝑥 + Δ 𝑥_{nt}) = \frac{1}{2} \nabla 𝑓 (𝑥) \nabla^{2} {𝑓 (𝑥)}^{- 1} \nabla 𝑓 (𝑥) \end{matrix}

\begin{matrix} 𝜆 (𝑥) = {(\nabla 𝑓 (𝑥) \nabla^{2} {𝑓 (𝑥)}^{- 1} \nabla 𝑓 (𝑥))}^{\frac{1}{2}} \\ 𝑓 (𝑥) - {\hat{𝑓}}^{*} = \frac{1}{2} {𝜆 (𝑥)}^{2} \end{matrix}

Also,

𝜆 (𝑥) = {(Δ 𝑥_{nt} \nabla^{2} 𝑓 (𝑥) Δ 𝑥_{nt})}^{\frac{1}{2}}

\nabla {𝑓 (𝑥)}^{𝑇} Δ 𝑥_{nt} = - {𝜆 (𝑥)}^{2}

6.9. Newton method

given starting point $𝑥_{0}$ , tolerance $𝜀$
repeat
1. 计算 $Δ 𝑥_{nt}$ 和 $𝜆^{2}$
2. 如果 $\frac{1}{2} 𝜆^{2} < 𝜀$ 结束
3. backtracking line search 得到 $𝑡$
4. $𝑥 ≔ 𝑥 + 𝑡 Δ 𝑥_{nt}$

收敛性要求的假设：

$𝑚$ 强凸
$\nabla^{2} 𝑓$ Lipschitz continuous ( $𝐿 > 0$ )
${‖ \nabla^{2} 𝑓 (𝑥) - \nabla^{2} 𝑓 (𝑦) ‖}_{2} \leq 𝐿 {‖ 𝑥 - 𝑦 ‖}_{2}$

收敛的两个阶段：
存在常数 $𝜂 \in (0, \frac{𝑚^{2}}{𝐿}), 𝛾 > 0$

if ${‖ \nabla 𝑓 (𝑥) ‖}_{2} \geq 𝜂$ then $𝑓 (𝑥^{(𝑘 + 1)}) - 𝑓 (𝑥^{(𝑘)}) \leq - 𝛾$
if ${‖ \nabla 𝑓 (𝑥) ‖}_{2} < 𝜂$ then
$\frac{𝐿}{2 𝑚^{2}} {‖ \nabla 𝑓 (𝑥^{(𝑘 + 1)}) ‖}_{2} \leq {(\frac{𝐿}{2 𝑚^{2}} {‖ \nabla 𝑓 (𝑥^{(𝑘)}) ‖}_{2})}^{2}$

达到 $𝑓 (𝑥) - 𝑝^{*} \leq ϵ$ 的算法总步数为

\frac{𝑓 (𝑥^{(0)}) - 𝜂}{𝛾} + \log_{2} \log_{2} (\frac{ϵ_{0}}{ϵ})

7. Duality

7.1. Lagrange dual 和 conjugate function 的关系

当不等式约束是线性的时候

\begin{matrix} \min_{𝑥} & 𝑓_{0} (𝑥) \\ s.t. & 𝐴 𝑥 \leq 𝑏 \\ 𝐶 𝑥 = 𝑑 \end{matrix}

Lagrange dual function 是

\begin{matrix} 𝑔 (𝜆, 𝜈) = & \inf_{𝑥} (𝑓_{0} (𝑥) + 𝜆 (𝐴 𝑥 - 𝑏) + 𝜈 (𝐶 𝑥 - 𝑑)) \\ = & \inf_{𝑥} (𝑓_{0} (𝑥) + (𝜆 𝐴 + 𝜈 𝑐) 𝑥) - 𝜆 𝑏 - 𝜈 𝑑 \\ = & - \sup_{𝑥} ((- 𝜆 𝐴 - 𝜈 𝑐) 𝑥 - 𝑓_{0} (𝑥)) - 𝜆 𝑏 - 𝜈 𝑑 \\ = & - 𝑓_{0}^{*} (- 𝜆 𝐴 - 𝜈 𝑐) - 𝜆 𝑏 - 𝜈 𝑑 \end{matrix}

7.2. Lagrange dual problem

\begin{matrix} \max 𝑔 (𝜆, 𝜈) \\ s.t. 𝜆 ⪰ 0 \end{matrix}

最优解的值是 $𝑑^{*} = 𝑔 (𝜆^{*}, 𝜈^{*})$

weak duality: $𝑑^{*} \leq 𝑝^{*}$ 总是成立
strong duality: 如果 $𝑑^{*} = 𝑝^{*}$ ，则称为强对偶性，一般对凸问题成立成立的条件叫做 constraint qualification

7.3. Slater's constraint qualification

如果凸优化问题是 strict feasible 的，那么强对偶性成立

\exists 𝑥 \in int 𝒟 : 𝑓_{𝑖} (𝑥) < 0, 𝐶 𝑥 = 𝑑

条件可以被放松： $\exists 𝑥 \in relint 𝒟$ 也就是线性的不等式约束不要求严格小于，可以是小于等于

7.4. Complementary slackness

𝜆_{𝑖} 𝑓_{𝑖} (𝑥) = 0, 𝑖 = 1, \dots, 𝑚

要么 $𝜆_{𝑖} = 0$ ，要么 $𝑓_{𝑖} (𝑥) = 0$

7.5. KKT conditions

$𝑓_{𝑖} (𝑥) \leq 0, ℎ_{𝑖} (𝑥) = 0$
$𝜆_{𝑖} \geq 0$
$𝜆_{𝑖} 𝑓_{𝑖} (𝑥) = 0$
$\nabla_{𝑥} 𝐿 (𝑥, 𝜆, 𝜈) = 0$

KKT condition ⇌_{always}^{is convex} is optimal

7.6. 利用对偶问题求解原问题

求解 $\max_{𝜆, 𝜈} 𝑔 (𝜆, 𝜈)$ 得到 $𝜆^{*}, 𝜈^{*}$
固定 $𝜆^{*}, 𝜈^{*}$ 的情况下求解 $\min_{𝑥} 𝐿 (𝑥, 𝜆^{*}, 𝜈^{*})$ 得到 $𝑥^{*}$

8. Equality constrained minimization

(ps. 也可以如小节 7.6 用对偶问题求解)

8.1. 等式约束的二阶最小化

已知 $𝑃 \in 𝕊_{+}^{𝑛}$

\begin{matrix} \min_{𝑥} & \frac{1}{2} 𝑥^{𝑇} 𝑃 𝑥 + 𝑞^{𝑇} 𝑥 + 𝑟 \\ s.t. & 𝐴 𝑥 = 𝑏 \end{matrix}

由KKT条件

\begin{matrix} 𝑃 𝑥 + 𝑞 + 𝐴^{𝑇} 𝜈 = 0 \\ 𝐴 𝑥 = 𝑏 \end{matrix}

整理一下就得到

(\begin{matrix} 𝑃 & 𝐴^{𝑇} \\ 𝐴 & 0 \end{matrix}) (\begin{matrix} 𝑥^{*} \\ 𝜈^{*} \end{matrix}) = (\begin{matrix} - 𝑞 \\ 𝑏 \end{matrix})

其中 $(\begin{matrix} 𝑃 & 𝐴^{𝑇} \\ 𝐴 & 0 \end{matrix})$ 叫做KKT矩阵

KKT矩阵是非奇异的 $\Leftrightarrow$ $𝐴 𝑥 = 0, 𝑥 \neq 0 \Rightarrow 𝑥^{𝑇} 𝑃 𝑥 > 0$
非奇异的等价条件 $𝑃 + 𝐴^{𝑇} 𝐴 ≻ 0$

如果KKT矩阵是奇异的，并且等式不可解，那么问题是unbounded below 或 infeasible 的
如果KKT矩阵是奇异的并且可解，那么问题是多个最优解的

8.2. 等式约束的消元

$𝐴 𝑥 = 𝑏$ 可以写成 $𝐹 𝑧 + \hat{𝑥}$ 的形式，其中 $\hat{𝑥}$ 是任意一个特解， $𝐹$ 是 $𝐴$ 的零空间的一组基

8.3. Newton step with equality constraints

将原问题看成二阶展开的近似

\begin{matrix} 𝑓 (𝑥 + 𝑣) = 𝑓 (𝑥) + \nabla {𝑓 (𝑥)}^{𝑇} 𝑣 + \frac{1}{2} 𝑣^{𝑇} \nabla^{2} 𝑓 (𝑥) 𝑣 \\ s.t. 𝐴 (𝑥 + 𝑣) = 𝑏 \end{matrix}

由KKT条件 (加上 $𝐴 𝑥 = 𝑏$ )

(\begin{matrix} \nabla^{2} 𝑓 (𝑥) & 𝐴^{𝑇} \\ 𝐴 & 0 \end{matrix}) (\begin{matrix} 𝑣 \\ 𝜈 \end{matrix}) = (\begin{matrix} - \nabla 𝑓 (𝑥) \\ 0 \end{matrix})

Δ 𝑥_{nt} = 𝑣

此时 $𝜆 (𝑥)$ 的计算可以是

𝜆 (𝑥) = {(Δ 𝑥_{nt}^{𝑇} \nabla^{2} 𝑓 (𝑥) Δ 𝑥_{nt})}^{\frac{1}{2}}

或者是

𝜆 (𝑥) = {(- \nabla {𝑓 (𝑥)}^{𝑇} Δ 𝑥_{nt})}^{\frac{1}{2}}

但是因为不满足等式约束，不能是

𝜆 (𝑥) \neq {(\nabla {𝑓 (𝑥)}^{𝑇} {(\nabla^{2} 𝑓 (𝑥))}^{- 1} \nabla 𝑓 (𝑥))}^{\frac{1}{2}}

因为是线性变换，算法的收敛性质不变

9. Inequality constrained minimization

9.1. Logarithmic barrier

\begin{matrix} 𝑓_{𝑖} (𝑥) \leq 0 \\ \frac{1}{𝑡} ϕ (𝑥) = - \frac{1}{𝑡} \log (- 𝑓_{𝑖} (𝑥)) \\ where 𝑡 > 0 \end{matrix}

approximation improves as $𝑡 \to \infty$

Logarithmic barrier function $ϕ$ :

9.2. 中心路径 (central path)

\begin{matrix} \min_{𝑥} & 𝑡 𝑓_{0} (𝑥) + ϕ (𝑥) \\ s.t. & 𝐴 𝑥 = 𝑏 \end{matrix}

central path 是 ${𝑥^{*} (𝑡) | 𝑡 > 0}$

对有barrier的最优化目标求KKT条件有

𝑡 \nabla 𝑓_{0} (𝑥) + \sum_{𝑖 = 1}^{𝑚} \frac{1}{- 𝑓_{𝑖} (𝑥)} \nabla 𝑓_{𝑖} (𝑥) + 𝐴^{𝑇} 𝑤

整体除以 $𝑡$ 是

\nabla 𝑓_{0} (𝑥) + \sum_{𝑖 = 1}^{𝑚} \frac{1}{- 𝑡 𝑓_{𝑖} (𝑥)} \nabla 𝑓_{𝑖} (𝑥) + 𝐴^{𝑇} \frac{𝑤}{𝑡}

按照上式格式，定义

𝜆^{*} (𝑡) = - \frac{1}{𝑡 𝑓_{𝑖} (𝑥^{*} (𝑡))}, 𝜈^{*} (𝑡) = \frac{𝑤}{𝑡}

带入到不带barrier的 $𝐿$ 中有：

\begin{matrix} 𝑝^{*} \geq & 𝑓_{0} (𝑥^{*} (𝑡)) + \sum_{𝑖 = 1}^{𝑚} 𝜆^{*} (𝑡) 𝑓_{𝑖} (𝑥^{*} (𝑡)) + 𝐴^{𝑇} 𝜈^{*} (𝑡) \\ = & 𝑓_{0} (𝑥^{*} (𝑡)) - \frac{𝑚}{𝑡} \end{matrix}

因此有

有barrier的KKT条件变化的只有 complementary slackness

- 𝜆_{𝑖} 𝑓_{𝑖} (𝑥) = \frac{1}{𝑡}, 𝑖 = 1, \dots, 𝑚

9.3. Barrier method （内点法）

给定 strictly feasible $𝑥, 𝑡 > 0, 𝜇 > 1$ 和 tolerance $𝜀 > 0$
repeat
1. 求解 $𝑡 𝑓_{0} (𝑥) + ϕ (𝑥)$ 得到 $𝑥^{*} (𝑡)$
2. $𝑥 ≔ 𝑥^{*} (𝑡)$
3. 如果 $\frac{𝑚}{𝑡} < 𝜀$ 结束
4. $𝑡 ≔ 𝜇 𝑡$

收敛性

外层循环要做 $𝑘$ 次
$\frac{𝑚}{𝜇^{𝑘} 𝑡} < 𝜀 \Rightarrow 𝑘 = ⌈ \log_{𝜇} (\frac{𝑚}{𝑡 𝜀}) ⌉$
内层循环与牛顿法相同

9.4. phase I methods

用来找到一个feasible的初始点，将原本的 feasibliity problem 转化为一个优化问题

\begin{matrix} \min_{𝑥, 𝑠} & 𝑠 \\ s.t & 𝑓_{𝑖} (𝑥) \leq 𝑠, 𝑖 = 1, \dots, 𝑚 \\ 𝐴 𝑥 = 𝑏 \end{matrix}

如果解出来的 $𝑠 > 0$ ，那么原问题是infeasible的