basic

<aside> 🧸 凸优化问题有多项式解法。

凸优化问题的最优性条件总可以写为等价条件。[【Convex Optimization 】【充分条件】 凸优化总有稳定点是全局极值点，是KKT系统的解，是拉格朗日函数的鞍点](https://hazysite.notion.site/KKT-13ed969b881f809c83f1ebe6ded223fc) 【定理】凸优化的局部极小点就是全局极小点，两者等价。 （必要性）全局极小一定局部极小 （充分性）反证，若存在全局极小比局部极小更小，两点凸组合的函数值小于函数值的凸组合，函数值的凸组合小于局部极小不组合；小量凸组合也是凸组合，进而局部极小条件矛盾。

约束优化问题的难点在于判断问题是否是凸优化问题：是则易否则找特例。

Convex Optimization

无动画Chapter22Convex.pdf

$$ \R^n, \ \lang x,y\rang=x^Ty,\ \|\| $$

</aside>

Convexity

<aside>

Convex Set

$\forall x,y\in S$ and $\alpha \in [0,1]$, we have their convex combination / line segment is also belongs to $S$

$$ \alpha x+(1-\alpha)y\in S $$

凸集定义为 存在加法运算和对应标量空间的集合的子集，满足集合中任意元素的凸组合仍在集合内。

A set is convex: $x\in S,y\in S$→ segment $xy\subset S$.

segment $xy:\alpha x+\beta y,\alpha,\beta\ge0,\alpha+\beta =1$. to Convex Combination to barycentric coordinates.

$$ \boxed{ \alpha x+\beta y\in \Omega}\\x,y\in \Omega,\alpha +\beta=1,\alpha,\beta \in \R $$

</aside>

Affine Set

a specific convex set with the line rather line segment

$$ \alpha x+(1-\alpha )y\in S,\ \alpha \in \R $$

凸组合是两变量的线性组合，其线性因子和为1且0~1。

affine combination $\sum_i \alpha_i=1\to \sum_i \alpha_ix_i$, $A(M\in \R^n)=\sum_i^r \alpha_im_i,r\in N_+\}$

锥组合类似，线性因子非负

Theorem

An affine set is subspace of $\R^n$

iff $0\in S$

S is parallel to $U$ if $\exists x$

$$ S=x+U. $$

  1. for any affine set $S$, we can find A subspace $U=S-S$, it means $convex(x,y)\in U=convex(x_1-x_2,y_1-y_2)\in S-S$ rather than just zero:
  2. for any $x\in S$, we have $S=x+U,U//S$
  3. $U$ is unique

⇒ affine space = its any element + unique subspace with U//S = x + $\ker S$

and Affine dimension: $\dim S=\dim U$

Affine hyperplane: $H_{S,r}=\{x\in \R^n:\lang s,x\rang =r\}$ s 法向量，r是截距

$H_{S,0}=\{s\}^\perp$ 垂直超平面

Half Spaces: $\{x\in \R^n:\lang s, r\rang\le r\}$is closed and $\{x\in \R^n:\lang s, r\rang>r\}$is open affine set

Affine Hull: $Aff\ M=\bigcap_{M\subset S} S_{affine}$ smallest affine hull of subset

property

  1. insert of a family of affine sets is affine set.
  2. $Aff\ M =A(M)$
    1. A(M) is an affine set: affine is addable to vector
    2. $\forall$ affine set S containing M

Affine independent

$x_0,x_1,\cdots,x_p$ are affine independent iff $x_1-x_0,\cdots,x_p-x_0$ are linear independent.

prop these are quivalent

  1. $x_0,x_1,\cdots,x_p$ are affine independent

  2. $(x_0,1),(x_1,1),\cdots,(x_p,1)$ are linear independent

  3. below admits a unique solution

    $$ \begin{aligned} \sum_{i-0}^p\alpha_ix_i=0,\\ \sum_{i=0}^p \alpha_i=0 \end{aligned} $$

(1) ⇒ (2) $\sum_{i-0}^p\alpha_ix_i-\sum_{i=0}^px_0=$affine independent

(2) <⇒ (3)

(3) ⇒ (1) let $\alpha_0=-\sum_{i=1}^P \alpha_i$, we get linear combination

Unit Simplex Set

$$ \Delta n=\{ \alpha\in \R^n:\sum{i=1}^n\alpha_i=1,\alpha_i\ge 0 \}\subset \R^n\\= \{\alpha\in \R^n:e^T\alpha =1,e_i^T\alpha\ge 0\} $$

$e_i$ is orthonormal basis;

n half-space within a hyperplane

  1. intersection of a family of convex sets is convex set
  2. 笛卡尔积$\prod C_i$ 也是 convex set
  3. 明可夫斯基和 $\lambda A+\mu B$ is also convex set
  4. $int\ C$ and $cl\ C$ are convex set

<aside> <img src="/icons/chess-bishop_yellow.svg" alt="/icons/chess-bishop_yellow.svg" width="40px" /> 【定理】凸优化的局部极小点就是全局极小点，两者等价。 （必要性）全局极小一定局部极小 （充分性）反证，若存在全局极小比局部极小更小，两点凸组合的函数值小于函数值的凸组合，函数值的凸组合小于局部极小不组合；小量凸组合也是凸组合，进而局部极小条件矛盾。

</aside>

analysis

convex function

Prelimilary