<aside>

SCS 编译步骤,基本算法流程和实现。

</aside>

Project onto P/D Exponential cone

Friberg - 2023 - Projection onto the exponential cone a univariate root-finding problem.pdf

  1. closed conic hull of its epigraph (conic extensions)

    凸函数的上图可以用锥闭包(凸包)表示,只需增加一个透视 perspective 维度$(x,t\ge f(x))$ → $(x,s,t),s>0$

    $$ cl\{(t,s,x)\in \mathbb R^{1\times 1\times n}\mid \frac ts\ge f(\frac xs),s\ge 0\} $$

    单纯的凸集不能满足cone $kv\in \Omega,\forall v\in \Omega$

    img_v3_02tf_54092300-4639-4bde-8850-824281cbe55g.jpg


    注意,“透视源”不一定是点,可以是线、面,只要作为极限存在并以边界点囊括入闭包即可。

    Rockafellar, R.T.: Level sets and continuity of conjugate convex functions. Trans. Amer. Math. Soc. 123(1), 46–63 (1966). https://doi.org/10.1090/S0002-9947-1966-0192318-X

    如指数锥常表示为第三象限和透视锥的并集。

  2. 指数函数生成指数锥

    $$ \mathcal K_{\exp}\equiv cl([\mathcal K_{\exp}]{++}) =[\mathcal K{\exp}]{++} \cup[\mathcal K{\exp}]_{0} $$

    其中$[\mathcal K_{\exp}]_{++}$是指数函数符合透视的集合(perspective interior)

    $$ [\mathcal K_{\exp}]_{++} =\big\{ (t,s,x)\in \mathbb R^{1\times 1\times n}\mid \frac ts\ge \exp(\frac xs),s\ge 0 \big\} $$

    作为闭包,需要考虑并包括边界点。这里就是取$s\to 0$后只有极限定义的点集(指数函数被无穷缩小,取极限后上图为第四象限全体, perspective boundary)

    $$ [\mathcal K_{\exp}]_{0} =\big\{ s=0,t\ge 0,r\le 0 \big\} $$

    <aside>

    Friberg - 2023 - Projection onto the exponential cone a univariate root-finding problem.pdf

    指数锥优势

    1. expressive abilities

      指数函数上图,对数函数下图,exponentials指数多项式,logarithms,entropy funxtions熵,product logarithms, soft-max, soft-plus

    2. numerically stable 3-self-concordant barrier functions

      兼容对偶、facial reduction、内点特性

    3. 非symmetric cone,仍然能够快速收敛 </aside>

    3. 指数锥的投影问题

  3. 指数锥的投影问题

projection problem

$$ d(\vec v_0)=\min \|\vec v-\vec v_0\|2 \\ s.t. \ \ v\in \mathcal K{\exp} $$

  1. 最优性条件

    最优性条件

    KKT 条件,或者The Moreau decomposition theorem

    Moreau envelope

SCS algorithm

SCS maker

SCS Test & CI/CD


scs parse