RDA: An Accelerated Collision Free Motion Planner for Autonomous Navigation in Cluttered Environments

---

---

🧠另一篇

问题描述

1. 障碍物模型

   1. 环境由M个非点质量障碍物组成。第m个障碍物(m = 1,…,M)被建模为紧凸集Om,由锥不等式表示:

      O m = { o ∈ R o m ∣ D m o ⪯ O m b m } O_m = \{o \in \mathbb{R}^{o_m} | D_m o \preceq_{\mathcal{O}_m} b_m\} Om​={o∈Rom​∣Dm​o⪯Om​​bm​}

      其中$D_m\in {\mathbb{R}}^{l_m\times o_m}$,$b_m\in {\mathbb{R}}^{l_m}$,${\mathcal{O}}_m$是适当锥。

2. 机器人模型

   1. 每个机器人在时间t的状态由其中心点表示,记为$s_t\in {\mathbb{R}}^{n_r}$。给定某个状态,机器人可以建模为随状态变量$s_t$变化的紧集$Z_t$:

      $$Z_t(s_t)=R(s_t)z+p(s_t),\forall z\in \mathcal{C}$$

      C = { z ∈ R n r ∣ G z ⪯ K r h } \mathcal{C} = \{z \in \mathbb{R}^{n_r} | Gz \preceq_{\mathcal{K}_r} h\} C={z∈Rnr​∣Gz⪯Kr​​h}

      其中$R(s_t)$是表示机器人方向的旋转矩阵,$p(s_t)$是表示机器人位置的平移矩阵。

3. 动力学约束

   1. 机器人状态演化可以描述为:

      $$s_{t+1}=s_t+f(s_t,u_t)\Delta t$$

      对于线性机器人动力学:

      $$s_{t+1}=A_t{s}_t+B_t{u}_t+c_t$$

      NEUPAN:全向机器人的模型：

      $$A_t=\frac{\partial \mathbf{g}}{\partial \mathbf{s}}=\left[\begin{array}{ccc}1& 0& \left(-{\bar{v}}_x\sin \bar{\theta }-{\bar{v}}_y\cos \bar{\theta }\right)\Delta t\\ 0& 1& \left({\bar{v}}_x\cos \bar{\theta }-{\bar{v}}_y\sin \bar{\theta }\right)\Delta t\\ 0& 0& 1\end{array}\right]$$

      $$B_t=\frac{\partial \mathbf{g}}{\partial \mathbf{u}}=\left[\begin{array}{ccc}\cos \bar{\theta }\Delta t& -\sin \bar{\theta }\Delta t& 0\\ \sin \bar{\theta }\Delta t& \cos \bar{\theta }\Delta t& 0\\ 0& 0& \Delta t\end{array}\right]$$

$$\begin{array}{rl}{\mathbf{c}}_t& =\mathbf{g}({\bar{\mathbf{s}}}_t,{\bar{\mathbf{u}}}_t)-A_t{\bar{\mathbf{s}}}_t-B_t{\bar{\mathbf{u}}}_t\\ & =\left[\begin{array}{c}\bar{x}+\left({\bar{v}}_x\cos \bar{\theta }-{\bar{v}}_y\sin \bar{\theta }\right)\Delta t\\ \bar{y}+\left({\bar{v}}_x\sin \bar{\theta }+{\bar{v}}_y\cos \bar{\theta }\right)\Delta t\\ \bar{\theta }+\bar{\omega }\Delta t\end{array}\right]\left[\begin{array}{c}\bar{x}+\left(-{\bar{v}}_x\sin \bar{\theta }-{\bar{v}}_y\cos \bar{\theta }\right)\bar{\theta }\Delta t\\ \bar{y}+\left({\bar{v}}_x\cos \bar{\theta }-{\bar{v}}_y\sin \bar{\theta }\right)\bar{\theta }\Delta t\\ \bar{\theta }\end{array}\right]\left[\begin{array}{c}\left({\bar{v}}_x\cos \bar{\theta }-{\bar{v}}_y\sin \bar{\theta }\right)\Delta t\\ \left({\bar{v}}_x\sin \bar{\theta }+{\bar{v}}_y\cos \bar{\theta }\right)\Delta t\\ \bar{\omega }\Delta t\end{array}\right]\end{array}$$

简化得：

$${\mathbf{c}}_t=\left[\begin{array}{c}\bar{\theta }\left({\bar{v}}_x\sin \bar{\theta }+{\bar{v}}_y\cos \bar{\theta }\right)\Delta t\\ \bar{\theta }\left({\bar{v}}_x\cos \bar{\theta }-{\bar{v}}_y\sin \bar{\theta }\right)\Delta t\\ 0\end{array}\right]$$

4. 碰撞约束

   机器人与障碍物之间的最小距离$\text{dist}(Z_t(s_t),O)$满足:

dist ( Z t ( s t ) , O ) = min ⁡ { ∥ e ∥ 2 ∣ ( Z t ( s t ) + e ) ∩ O ≠ ∅ } \text{dist}(Z_t(s_t), O) = \min \{ \|e\|_2 | (Z_t(s_t) + e) \cap O \neq \emptyset \} dist(Zt​(st​),O)=min{∥e∥2​∣(Zt​(st​)+e)∩O=∅}

为了保证碰撞避免,我们有以下约束:

$$\text{dist}(Z_t(s_t),O)\ge d_{\text{safe}}$$

其中$d_{\text{safe}}$是表示安全距离的正实数。约束(5)是非凸的

5. 速度约束

1. $u_{\min }⪯u_t⪯u_{\max },\forall t$

2. $a_{\min }⪯u_{t+1}-u_t⪯a_{\max },\forall t$

---

问题形式：

采用 MPC 预测窗口长度为 $N$。路径跟踪的代价函数示例：

C 0 ( { s t , u t } ) = ∑ t = 0 N [ Q t ∥ s t − s ~ t ∥ 2 + P t ( v t − v ~ t ) 2 ] . (12) C_0(\{s_t,u_t\}) = \sum_{t=0}^N \big[ Q_t \|s_t - \tilde s_t\|^2 + P_t (v_t - \tilde v_t)^2 \big]. \tag{12} C0​({st​,ut​})=t=0∑N​[Qt​∥st​−s~t​∥2+Pt​(vt​−v~t​)2].(12)

NEUPAN：

$$C_0(S,U)=\sum _{h=t}^{t+H}q\ast ||s_{h+1}-s_{h+1}^{\diamond }|{|}^2+p\ast ||u_{speed,h}-u_{speed}^{\diamond }|{|}^2$$

优化目标：在有限预测窗内最小化 $C_0$，受动力学与边界及碰撞约束限制：

P 0 : min ⁡ { s t , u t } C 0 ( { s t , u t } ) s.t. s t + 1 = A t s t + B t u t + c t , ∀ t , u min ⁡ ≤ u t ≤ u max ⁡ , ∀ t , a min ⁡ ≤ u t + 1 − u t ≤ a max ⁡ , ∀ t , dist ⁡ ( Z t ( s t ) , O m ) ≥ d safe , ∀ t , m . (13) \begin{aligned} P_0:\quad &\min_{\{s_t,u_t\}} C_0(\{s_t,u_t\})\\ \text{s.t.}\quad & s_{t+1} = A_t s_t + B_t u_t + c_t, \quad\forall t,\\ & u_{\min} \le u_t \le u_{\max},\quad\forall t,\\ & a_{\min} \le u_{t+1}-u_t \le a_{\max},\quad\forall t,\\ & \operatorname{dist}(Z_t(s_t),O_m) \ge d_{\text{safe}},\quad\forall t,m. \tag{13} \end{aligned} P0​:s.t.​{st​,ut​}min​C0​({st​,ut​})st+1​=At​st​+Bt​ut​+ct​,∀t,umin​≤ut​≤umax​,∀t,amin​≤ut+1​−ut​≤amax​,∀t,dist(Zt​(st​),Om​)≥dsafe​,∀t,m.​(13)

困难点：碰撞约束是充分但非必要，难以满足；障碍数 $M$ 可能很大导致计算量激增。后续给出解决方案。

---

创新点：

1. 动态安全距离方法：其中$d_{\text{safe}}$被向量变量$d=[d_1,...,d_N{]}^T$替换，但是这样忽略了即将到来和未来状态的不同重要性，于是进一步提出l1正则化方法,通过对d施加稀疏性来在不同时间步之间生成不均匀的 { d t } \{d_t\} {dt​}值，,l1正则化通过向$C_0$添加d的惩罚函数来实现:

   $$C_1(d)=-\eta \Vert d{\Vert }_1=-\eta \sum _{t=0}^N{d}_t$$

   其中$\eta \in {\mathbb{R}}_{\ge 0}$是调整不同场景中碰撞避免能力的权重因子。

   1. 可以从表达式看出来，这个会使得d尽可能的变小

   2. $d_{\text{safe}}$原本标量的距离变成向量,在真正危险的地方 $d_t$ 可以 **自动变大,**在安全的位置 $d_t$ 可以 变小甚至为 0

   3. 当$\eta$较大时 :倾向于$d_t\to d_{\max }$(更安全)；当$\eta$较小时 :倾向于$d_t\to d_{\min }$(更灵活)；l1范数使得$d_t$在时间维度上不均匀分布

   4. 加上$C_1$之后，整体的问题变了整体问题为：

      min ⁡ { s t , u t } , d C 0 ( { s t , u t } ) + C 1 ( d ) s.t.  ( 13 a ) – ( 13 d ) , d t ∈ [ d min ⁡ , d max ⁡ ] , ∀ t , dist ⁡ ( Z t ( s t ) , O m ) ≥ d t , ∀ t , m . (14) \begin{aligned} \min_{\{s_t,u_t\}, d} &\quad C_0(\{s_t,u_t\}) + C_1(d)\\ \text{s.t.}\ & (13a)\text{--}(13d),\\ & d_t\in[d_{\min},d_{\max}],\quad\forall t,\\ & \operatorname{dist}(Z_t(s_t),O_m) \ge d_t,\quad\forall t,m. \end{aligned} \tag{14} {st​,ut​},dmin​s.t. ​C0​({st​,ut​})+C1​(d)(13a)–(13d),dt​∈[dmin​,dmax​],∀t,dist(Zt​(st​),Om​)≥dt​,∀t,m.​(14)

      较大的 $\eta$ 鼓励 $d_t$ 靠近上界 $d_{\max }$，反之靠近下界。

2. 将约束$\text{dist}(Z_t(s_t),O_m)\ge d_t$转换为其线性化对偶，通过ADMM求解

$$\begin{array}{rl}& \mathrm{dist}(Z_t(s_t),O_m)\ge d_t⟺\\ & {\lambda }_{t,m}{⪰}_{O_m^{\ast }}0,{\mu }_{t,m}{⪰}_{K_r^{\ast }}0,\\ & {\lambda }_{t,m}^{\top }{D}_m{p}_t(s_t)-{\lambda }_{t,m}^{\top }{b}_m-{\mu }_{t,m}^{\top }h\ge d_t,\\ & {\mu }_{t,m}^{\top }G+{\lambda }_{t,m}^{\top }{D}_m{R}_t(s_t)=0,\\ & \Vert D_m^{\top }{\lambda }_{t,m}{\Vert }_{\ast }\le 1.\end{array}\text{\hspace{1em}(15)}$$

这里 ${\lambda }_{t,m}$ 与 ${\mu }_{t,m}$ 是对偶变量；$\Vert \cdot {\Vert }_{\ast }$ 为对偶范数（Euclidean 的对偶范数仍为 Euclidean）。这个变换与文献 [12] 不同之处在于本文对平移 $p_t$ 与旋转 $R_t$ 做了线性化，从而得到一个平滑的双凸（bi-convex）对偶形式，便于并行求解。

之后把上面的约束都写进拉格朗日，其中第三行经过非负数松弛变成I，第三项转换成H

推导：

参考Apollo星火计划学习笔记——Apollo开放空间规划算法原理与实践_apollo openspace-CSDN博客

对偶是对原来的变量求极小值，然后对拉格朗系数求极大值

补充：

对于任何范数 $\Vert \cdot \Vert$ 及其对偶范数 $\Vert \cdot {\Vert }_{\ast }$，都有

$$\Vert x\Vert =\underset{\Vert w{\Vert }_{\ast }\le 1}{\sup }{w}^{\top }x.$$

对欧几里得范数，$\Vert \cdot {\Vert }_2$ 的对偶也是 $\Vert \cdot {\Vert }_2$。

把这个应用到目标上：

$$\Vert Rz+p-o{\Vert }_2=\underset{\Vert w{\Vert }_2\le 1}{\sup }{w}^{\top }(Rz+p-o).$$

因此：在满足强对偶（Slater）条件时可以交换 $\min$ 和 $\sup$

$$\delta =\underset{z,o}{\min }\underset{\Vert w\Vert \le 1}{\sup }{w}^{\top }(Rz+p-o)=\underset{\Vert w\Vert \le 1}{\sup }\underset{z,o}{\min }{w}^{\top }(Rz+p-o)$$

三、对内层 min 做对偶 → 引入 λ 与μ

内层问题（固定 $w$）是

$$\underset{z,o}{\min }{w}^{\top }(Rz+p-o)\text{s.t. }{D}_{m}o-b_m\in -O_m,Gz-h\in -K_r.$$

对这两个锥约束引入对偶变量：

• $\lambda \in O_m^{\ast }$（对应障碍约束 $D_{m}o⪯b_m$），

• $\mu \in K_r^{\ast }$（对应机器人形状约束 $Gz⪯h$）。

构造 Lagrangian（只对内层问题）：

$$\mathcal{L}(z,o;\lambda ,\mu )=w^{\top }(Rz+p-o)+{\lambda }^{\top }(D_{m}o-b_m)+{\mu }^{\top }(Gz-h),$$

要求内层最小值不是 $-\infty$ 的条件是：对 $z$ 与 $o$ 的线性项系数必须为零（否则可以把变量推向 $\pm \infty$ 使目标趋 $-\infty$）。因此求极小化对 $z,o$ 给出必要条件：

对 $o$：

$$\frac{\partial }{\partial o}:-w+D_m^{\top }\lambda =0\Rightarrow w=D_m^{\top }\lambda .\text{\hspace{1em}(A)}$$

对 $z$：

$$\frac{\partial }{\partial z}:R^{\top }w+G^{\top }\mu =0\Rightarrow R^{\top }w+G^{\top }\mu =0.\text{\hspace{1em}(B)}$$

把 (A) 代入 (B)：

$$R^{\top }{D}_m^{\top }\lambda +G^{\top }\mu =0\iff {\mu }^{\top }G+{\lambda }^{\top }{D}_{m}R=0,$$

这正是论文式 (15) 中的等式约束之一（见论文 (15)）

内层最小值（代入可行的 $\lambda ,\mu$ 与 $w$）变为：

$$w^{\top }p-{\lambda }^{\top }{b}_m-{\mu }^{\top }h.$$

将 $w=D_m^{\top }\lambda$ 替回，得到对偶目标（关于 $\lambda ,\mu$）的线性形式：

$$\underset{\text{来自 }{w}^{\top }p}{\underbrace{{\lambda }^{\top }{D}_{m}p}}-{\lambda }^{\top }{b}_m-{\mu }^{\top }h.$$

同时因为我们要求 $\Vert w{\Vert }_{\ast }\le 1$（这是原来 ${\sup }_{\Vert w{\Vert }_{\ast }\le 1}$ 的约束），代入 $w=D_m^{\top }\lambda$ 得到

$$\Vert D_m^{\top }\lambda {\Vert }_{\ast }\le 1.$$

最后把“$\delta \ge d_t$”（距离不小于某个 $d_t$）转成对偶不等式：

$${\lambda }^{\top }{D}_{m}p-{\lambda }^{\top }{b}_m-{\mu }^{\top }h\ge d_t.$$

把这些条件合起来就是论文式 (15) 的全部内容（写成对偶变量形式）：

$$\{\begin{array}{l}{\lambda }_{t,m}\in O_m^{\ast },{\mu }_{t,m}\in K_r^{\ast },\\ {\mu }_{t,m}^{\top }G+{\lambda }_{t,m}^{\top }{D}_m{R}_t(s_t)=0,\\ {\lambda }_{t,m}^{\top }{D}_m{p}_t(s_t)-{\lambda }_{t,m}^{\top }{b}_m-{\mu }_{t,m}^{\top }h\ge d_t,\\ \Vert D_m^{\top }{\lambda }_{t,m}{\Vert }_{\ast }\le 1.\end{array}$$

（论文式 (15)）

论文给出带有 $H_{t,m}$ 与 $I_{t,m}$ 的非线性等式：

$$\begin{array}{rl}{H}_{t,m}(s_t,{\lambda }_{t,m},{\mu }_{t,m})& ={\mu }_{t,m}^{\top }G+{\lambda }_{t,m}^{\top }{D}_m{R}_t(s_t),\\ I_{t,m}(s_t,{\lambda }_{t,m},{\mu }_{t,m},d_t,z_{t,m})& ={\lambda }_{t,m}^{\top }{D}_m{p}_t(s_t)-{\lambda }_{t,m}^{\top }{b}_m-{\mu }_{t,m}^{\top }h-d_t-z_{t,m}.\end{array}\text{\hspace{1em}(17-18)}$$

利用 ADMM，把原问题分为两组主变量：一组为 { s t , u t , d t } \{s_t,u_t,d_t\} {st​,ut​,dt​}（跨时间耦合，因动力学约束）；另一组为每个障碍/时刻独立的对偶变量 { λ t , m , μ t , m , z t , m } \{\lambda_{t,m},\mu_{t,m},z_{t,m}\} {λt,m​,μt,m​,zt,m​}。

其要点是：(20a) 求解关于 { s t , u t , d t } \{s_t,u_t,d_t\} {st​,ut​,dt​} 的大规模但与障碍数无关的凸子问题；(20b) 对每个 $(t,m)$ 并行求解小的对偶子问题；(20c)-(20d) 更新拉格朗日乘子。停止准则也给出（原文式 (21)-(22)）

为什么引入松弛变量 $z_{t,m}$ 以及 $H_{t,m},I_{t,m}$ 的定义

论文把上面的对偶条件写成 ADMM 易处理的等式形式，并为不等式引入松弛量。具体步骤如下：

1. 原来有（对偶形式）不等式：

   $${\lambda }^{\top }{D}_{m}p-{\lambda }^{\top }{b}_m-{\mu }^{\top }h\ge d_t.$$

   我们把它改写成等式，加上非负松弛 $z_{t,m}\ge 0$（它原本来自“≥”加松弛变量变成的“=0”）：

   $${\lambda }^{\top }{D}_{m}p-{\lambda }^{\top }{b}_m-{\mu }^{\top }h-d_t-z_{t,m}=0,z_{t,m}\ge 0.$$

   这样把“≥”变成了“=0 且 z≥0”，便于在增广拉格朗日中统一写法。

2. 把等式约束（来自 $R^{\top }w+G^{\top }\mu =0$）写成函数 $H_{t,m}(\cdot )=0$，并把上面的等式写成 $I_{t,m}(\cdot )=0$。论文定义（式 (17)-(18)）：

$$\boxed{H_{t,m}(s_t,{\lambda }_{t,m},{\mu }_{t,m})={\mu }_{t,m}^{\top }G+{\lambda }_{t,m}^{\top }{D}_m{R}_t(s_t)}\text{\hspace{1em}(17)}$$

$$\boxed{I_{t,m}(s_t,{\lambda }_{t,m},{\mu }_{t,m},d_t,z_{t,m})={\lambda }_{t,m}^{\top }{D}_m{p}_t(s_t)-{\lambda }_{t,m}^{\top }{b}_m-{\mu }_{t,m}^{\top }h-d_t-z_{t,m}}\text{\hspace{1em}(18)}$$

这两式就是论文中 $H$ 和 $I$ 的来源：把对偶等式与把不等式变成等式后的表达。

增广拉格朗日写成：

L = C 0 ( { s t , u t } ) + C 1 ( d ) + J ( { s , u , d } ) + ∑ t , m Q t , m ( λ t , m , μ t , m , z t , m ) + ρ 2 ∑ t , m ∥ H t , m ( s t , λ t , m , μ t , m ) + ξ t , m ∥ 2 2 + ρ 2 ∑ t , m ∥ I t , m ( s t , λ t , m , μ t , m , d t , z t , m ) + ζ t , m ∥ 2 2 . \begin{aligned} \mathcal{L} = {} & C_0(\{s_t,u_t\}) + C_1(d) + J(\{s,u,d\})+ \sum_{t,m} Q_{t,m}(\lambda_{t,m},\mu_{t,m},z_{t,m}) \\[3pt] & + \frac{\rho}{2}\sum_{t,m}\|H_{t,m}(s_t,\lambda_{t,m},\mu_{t,m}) + \xi_{t,m}\|_2^2+ \frac{\rho}{2}\sum_{t,m}\|I_{t,m}(s_t,\lambda_{t,m},\mu_{t,m},d_t,z_{t,m}) + \zeta_{t,m}\|_2^2. \end{aligned} L=​C0​({st​,ut​})+C1​(d)+J({s,u,d})+t,m∑​Qt,m​(λt,m​,μt,m​,zt,m​)+2ρ​t,m∑​∥Ht,m​(st​,λt,m​,μt,m​)+ξt,m​∥22​+2ρ​t,m∑​∥It,m​(st​,λt,m​,μt,m​,dt​,zt,m​)+ζt,m​∥22​.​

(1) J

表示“动力学和控制范围的可行域”：

J ( { s , u , d } ) = { 0 , 如果  s t + 1 = A t s t + B t u t + c t ,   u ∈ U , + ∞ , 否则 . J(\{s,u,d\}) = \begin{cases} 0, & \text{如果 } s_{t+1}=A_ts_t+B_tu_t+c_t,\ u\in\mathcal{U},\\ +\infty, & \text{否则}. \end{cases} J({s,u,d})={0,+∞,​如果 st+1​=At​st​+Bt​ut​+ct​, u∈U,否则.​

这样在最小化 $\mathcal{L}$ 时，就自然强制满足动力学与控制约束。

---

(2) Q

表示对偶变量的锥可行性（在论文里是 $O_m^{\ast }$、$K_r^{\ast }$、$z\ge 0$）：

$$Q_{t,m}(\lambda ,\mu ,z)=\{\begin{array}{ll}0,& \lambda \in O_m^{\ast },\mu \in K_r^{\ast },z\ge 0,\\ +\infty ,& \text{否则.}\end{array}$$

这样在最小化 $\mathcal{L}$ 的时候，也自然保证这些变量在正确的锥里。

---

• ps:复杂度

论文说：

$$O((N(n_r+n_u+1){)}^{3.5})$$

与障碍数 $M$ 无关；
然后并行解 $N\times M$ 个小问题，每个复杂度 $O(({\ell }_m+h+1{)}^{3.5})$。

在 RDA 中有两类变量：

• 状态变量：$s_t\in {\mathbb{R}}^{n_r}$

• 控制变量：$u_t\in {\mathbb{R}}^{n_u}$

• 再加上动态安全距离 $d_t\in \mathbb{R}$

所以在一个时刻的决策变量维度是 $n_r+n_u+1$。

预测窗口长度为 $N$ 的 MPC 问题

{ s 0 , s 1 , … , s N , u 0 , u 1 , … , u N − 1 , d 0 , … , d N } \{ s_0, s_1, \dots, s_N, u_0, u_1, \dots, u_{N-1}, d_0, \dots, d_N \} {s0​,s1​,…,sN​,u0​,u1​,…,uN−1​,d0​,…,dN​}

总维度近似为：

$$\text{dim}\approx N\times (n_r+n_u+1)$$

这就是复杂度里 $N(n_r+n_u+1)$ 的来源。

求解凸优化（特别是二次规划 QP 或二次锥规划 SOCP）时，IPM 的迭代次数是 $O(\sqrt{n})$，每次迭代要解一个 $n\times n$ 线性系统（成本 $O(n^3)$），所以总体复杂度约为：

$$O(n^{3.5})$$

👉 注意这是理论上界，表示“随维度增长的趋势”，不是实际程序运行时间。

因此，如果 (20a) 的 QP 子问题维度是 $N(n_r+n_u+1)$，
则它的理论复杂度为：

$$O((N(n_r+n_u+1){)}^{3.5})$$

这一步求解的时间复杂度不随障碍数 $M$ 变化，因为每个障碍的对偶变量都被固定了

第二部分：复杂度

$$O(({\ell }_m+h+1{)}^{3.5})$$

在 ADMM 的 (20b) 步，每个障碍 / 时刻的子问题变量是：

$${\lambda }_{t,m},{\mu }_{t,m},z_{t,m}$$

其中：

• ${\lambda }_{t,m}\in {\mathbb{R}}^{{\ell }_m}$：障碍多面体的面数；

• ${\mu }_{t,m}\in {\mathbb{R}}^h$：机器人形状约束的行数；

• $z_{t,m}$ 是标量松弛。

所以子问题维度为 ${\ell }_m+h+1$，
使用相同的 IPM 理论复杂度为：

$$O(({\ell }_m+h+1{)}^{3.5})$$

而且有 $N\times M$ 个这样的子问题可以并行求解。

综上：

• (20a)：大问题，复杂度随 $N$ 增，但与 $M$ 无关；

• (20b)：小问题，复杂度随 $M$ 线性增长，但每个都可并行。

---

1️⃣ 什么是 “sup”-（上确界）

• 如果最大值存在，sup = max；

• 如果函数没有真正达到最大值，但有一个“最小上界”，那它就是 sup。

• 举个例子：

  $$\underset{x<1}{\sup }x=1$$

  虽然 $x=1$ 取不到，但 1 是所有 $x<1$ 的最小上界。

  所以在数学上，

$$\underset{\Vert w{\Vert }_{\ast }\le 1}{\sup }{w}^{\top }x=\Vert x\Vert$$

这就是所谓的 范数对偶（dual norm） 关系。

这是一个非常重要的结论：

对于任意范数 $\Vert \cdot \Vert$，存在一个对偶范数 $\Vert \cdot {\Vert }_{\ast }$，定义为：

$$\Vert y{\Vert }_{\ast }=\underset{\Vert x\Vert \le 1}{\sup }{x}^{\top }y$$

也就是说：

$$\Vert x\Vert =\underset{\Vert y{\Vert }_{\ast }\le 1}{\sup }{y}^{\top }x$$

对欧几里得范数 $\Vert x{\Vert }_2$，它的对偶也是 $\Vert \cdot {\Vert }_2$。

---

增广拉格朗日函数

🧩 一、从标准约束问题开始

我们从一般的优化问题开始：

$$\underset{x}{\min }f(x)\text{s.t. }Ax=0.$$

这个等式约束的标准 拉格朗日函数 (Lagrangian) 是：

$$\mathcal{L}(x,y)=f(x)+y^{\top }(Ax),$$

其中 $y$ 是拉格朗日乘子。

🧩 二、加上“增广”项——得到增广拉格朗日

在 ADMM 中，为了更好收敛，我们不是只用线性乘子项，而是再加一个 二次罚项：

$${\mathcal{L}}_{\rho }(x,y)=f(x)+y^{\top }(Ax)+\frac{\rho }{2}\Vert Ax{\Vert }_2^2.$$

其中 $\rho >0$ 是罚参数。
它相当于既保证约束残差 $Ax=0$，又让违反约束的解被二次惩罚。

🧩 三、改写为“scaled form”——引入缩放乘子

我们定义新的变量：（可以凑平方项）

$$u=\frac{1}{\rho }y\Rightarrow y=\rho u.$$

把上式代入：

$${\mathcal{L}}_{\rho }(x,u)=f(x)+\rho u^{\top }(Ax)+\frac{\rho }{2}\Vert Ax{\Vert }^2=f(x)+\frac{\rho }{2}\Vert Ax+u{\Vert }^2-\frac{\rho }{2}\Vert u{\Vert }^2.$$

这个形式就是 ADMM 通常使用的 scaled augmented Lagrangian。
为什么？因为更新时 $u$ 的规则变得非常简单：

$$u^{k+1}=u^k+A{x}^{k+1},$$

不需要显式乘上 $\rho$，数值稳定且易写。

---