常用算法的计算复杂度
凸优化中常用算法的计算复杂度线性规划(LP)逐次凸逼近(SCA)块坐标下降(BCD)二分法 (Bisection)穷举法参考文献线性规划(LP)As explained in [12], the complexity of a standard linear problem is of order O(a2b)\mathcal{O} (a^2b)O(a2b),where aaa is the nu
常用算法的计算复杂度
穷举法 (Method of Exhaustion)
穷举法的计算复杂度就是穷举次数 N N N。
二分法 (Bisection)
二分法的计算复杂度是 O ( log 2 ( L 0 / e ) ) \mathcal{O} (\log_2(L_0/e)) O(log2(L0/e)) , 其中 L 0 L_0 L0 是最初的长度间隔, e e e 是要求的精度。
线性规划(LP)
The complexity of a standard linear problem is of order
O
(
a
2
b
)
\mathcal{O} (a^2b)
O(a2b), where
a
a
a is the number of variables and
b
b
b is the number of constraints.
For instance, the problem (P2.1) in ref [2], it is easy to show that the complexity of (P2.1) is of order
O
(
(
M
N
+
K
N
+
K
+
K
M
N
)
(
K
M
)
2
)
\mathcal{O} \left ( (MN + KN + K+ KMN)(KM)^2 \right)
O((MN+KN+K+KMN)(KM)2).
Note that (P2.1) is a linear function which only consists of the scheduling variables.
- 变量个数:KM,为什么不是KMN?
- 约束(10) 的个数 M N + K N MN+KN MN+KN
- 约束(11) 的个数 K K K
- 约束(14) 的个数 K M N KMN KMN
半定规划(SDP)
解决半定规划问题的计算复杂度为 O ( ( M + 1 ) 4.5 ) \mathcal{O} ((M+1)^{4.5}) O((M+1)4.5),其中 M M M代表变量个数 【8】。
逐次凸逼近(SCA)
SCA算法的计算复杂度和 “迭代次数( I I I)”,以及每次迭代中的 “更新变量的个数( N K NK NK)”有关;计算复杂度的表达式为 O ( I ( N K ) 3 ) \mathcal{O} (I(NK)^3) O(I(NK)3).
块坐标下降(BCD)
BCD algorithm 即 Alternating algorithm.
- BCD算法的收敛要求每一个块的优化要达到最优解,而实际问题中每个块问题往往是非凸的,用凸优化技术SCA求解得到的往往是次优解,所以在证明算法的收敛性的时候,需要自行证明一下优化目标函数的非减、非增,证明是存在 upper bound 或 lower bound,如此可证明问题收敛。
- 当BCD算法的某个块问题是采用SCA算法来解决的,则该块算法的计算复杂度和解决单独问题的SCA算法一样:计算复杂度为 O ( N 3.5 ) \mathcal{O} (N^{3.5}) O(N3.5) 【1】, N N N为变量个数。
- 在保证问题收敛后,解决每个块问题的算法的复杂度进行相加,即为BCD算法的复杂度。
- 如果算法的外部有循环 N o u t N_{out} Nout时,还需要在内部循环算法复杂度的基础上乘以 N o u t N_{out} Nout。
内点法(Interior Point Method)
内点法的计算复杂度为 O ( n 3.5 log ( 1 / ϵ ) ) \mathcal{O} (n^{3.5}\log(1/ \epsilon)) O(n3.5log(1/ϵ)),其中 n n n 为变量维度, ϵ \epsilon ϵ 为目标精度 【7】。
待整改
参考文献
【1】S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
【2】A. Bejaoui, K. Park and M. Alouini, “A QoS-Oriented Trajectory Optimization in Swarming Unmanned-Aerial-Vehicles Communications,” in IEEE Wireless Communications Letters, vol. 9, no. 6, pp. 791-794, June 2020, doi: 10.1109/LWC.2020.2970052.
【3】With Wireless Power Transfer," in IEEE Internet of Things Journal, vol. 8, no. 10, pp. 7833-7848, 15 May15, 2021, doi: 10.1109/JIOT.2020.3041303.
【4】C. Zhan and Y. Zeng, “Aerial–Ground Cost Tradeoff for Multi-UAV-Enabled Data Collection in Wireless Sensor Networks,” in IEEE Transactions on Communications, vol. 68, no. 3, pp. 1937-1950, March 2020, doi: 10.1109/TCOMM.2019.2962479.
【5】 R. Duan, J. Wang, C. Jiang, H. Yao, Y. Ren and Y. Qian, “Resource Allocation for Multi-UAV Aided IoT NOMA Uplink Transmission Systems,” in IEEE Internet of Things Journal, vol. 6, no. 4, pp. 7025-7037, Aug. 2019, doi: 10.1109/JIOT.2019.2913473.
【6】Q. Hu, Y. Cai, A. Liu, G. Yu and G. Y. Li, “Low-Complexity Joint Resource Allocation and Trajectory Design for UAV-Aided Relay Networks With the Segmented Ray-Tracing Channel Model,” in IEEE Transactions on Wireless Communications, vol. 19, no. 9, pp. 6179-6195, Sept. 2020, doi: 10.1109/TWC.2020.3000864.
【7】https://blog.csdn.net/weixin_39274659/article/details/121834231
【8】Luo Z Q , Ma W K , So M C , et al. Semidefinite Relaxation of Quadratic Optimization Problems[J]. IEEE Signal Processing Magazine, 2010, 27(3):20-34.
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)