FATT的个人博客

技术笔记和随笔

0%

凸优化

发表于

凸优化基础

1. 凸集合

1.1 定义

在凸优化中，凸集合是一种具有特殊性质的集合。给定一个集合C，如果对于C中的任意两个元素x₁和x₂，以及0到1之间的任意实数t，都有\(t \cdot x₁ + (1 - t) \cdot x₂ \in C\)，那么集合C就是一个凸集合。

1.2 凸组合

凸组合是凸集合中的一种特殊组合形式。给定一个凸集合C和C中的n个元素\(x₁, x₂, ..., x_n\)，对于任意非负实数\(t₁, t₂, ..., t_n\)，且满足\(t₁ + t₂ + ... + t_n = 1\)，凸组合定义为\(y = t₁ \cdot x₁ + t₂ \cdot x₂ + ... + t_n \cdot x_n\)。当所有的\(t\_i\)非负且满足和为1时，y是C中的一个凸组合。

1.3 凸包

凸包是包含凸集合中所有点的最小凸集合。换句话说，凸包是由凸集合中所有凸组合形成的集合。凸包可以用来描述凸集合的边界。

1.4 示例与图像展示

下面是一些常见的凸集合的示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np
import matplotlib.pyplot as plt
# 示例1: 凸集合为一个球体
center = np.array([0, 0])  # 球心
radius = 1  # 半径
theta = np.linspace(0, 2 * np.pi, 100)  # 角度
x = center[0] + radius * np.cos(theta)
y = center[1] + radius * np.sin(theta)
plt.plot(x, y, label="Convex Set 1")
# 示例2: 凸集合为一个正方形
x = [-1, 1, 1, -1, -1]
y = [-1, -1, 1, 1, -1]
plt.plot(x, y, label="Convex Set 2")
# 示例3: 凸集合为一个多边形
x = [0, 2, 4, 3, 1]
y = [0, 1, 0, -1, -1]
plt.plot(x, y, label="Convex Set 3")
plt.xlabel("x")
plt.ylabel("y")
plt.title("Examples of Convex Sets")
plt.legend()
plt.grid(True)
plt.show()

上述示例中，示例1展示了一个球体作为凸集合，示例2展示了一个正方形作为凸集合，示例3展示了一个多边形作为凸集合。

2. 凸函数

2.1 定义

凸函数是一类具有特殊性质的函数。给定定义在实数域上的函数\(f(x)\)，如果对于任意的实数x₁和x₂，以及0到1之间的任意实数t，都有\(f(t \cdot x₁ + (1 - t) \cdot x₂) \leq t \cdot f(x₁) + (1 - t) \cdot f(x₂)\)，那么函数\(f(x)\)就是凸函数。

2.2 一阶凸性和二阶凸性

凸函数的一阶和二阶导数性质对其凸性起到重要作用。

  • 一阶凸性：如果对于定义在开区间(a, b)上的函数f(x)，对于任意两个实数x₁和x₂，以及0到1之间的任意实数t，如果\(f(tx₁ + (1 - t)x₂) \leq tf(x₁) + (1 - t)f(x₂)\)，那么函数f(x)在区间(a, b)上是凸函数。

  • 二阶凸性：如果定义在开区间\((a, b)\)上的函数\(f(x)\)的二阶导数存在且非负，即\(f''(x) \geq 0\)，那么函数\(f(x)\)在区间\((a, b)\)上是凸函数。

2.3 凸函数的性质

凸函数具有以下重要性质：

  • 对于凸函数f(x)，对于任意的实数x₁和x₂，以及0到1之间的任意实数t，都有\(f(tx₁ + (1 - t)x₂) \leq tf(x₁) + (1 - t)f(x₂)\)。这被称为凸函数的凸组合性质。

  • 凸函数的局部最小值也是全局最小值。对于凸函数\(f(x)\)，任何局部最小值都是其全局最小值。

3. 保凸运算

3.1 加法和标量乘法

保凸运算是指对凸集合和凸函数进行一些操作后仍然保持其凸性质的运算。

  • 加法：如果C₁和C₂是凸集合，那么它们的和集合C = C₁ + C₂定义为\(C = {x + y | x \in C₁, y \in C₂}\)，并且C也是凸集合。

  • 标量乘法：如果C是凸集合，那么对于任意的实数a，集合\(aC\)定义为\(aC = {ax | x \in C}\)，并且\(aC\)也是凸集合。

3.2 函数复合

如果\(f(x)\)是一个凸函数，\(g(x)\)是一个仿射函数（线性函数加上常数项），那么复合函数\(h(x) = f(g(x))\)也是凸函数。

4. 凸优化问题

4.1 问题形式

在数学上，优化问题通常被定义为如下形式：

\[\min f_{0}(x) \\ \text{s. t.} f_{i}(x) \leq b_{i}, i=1, \ldots, m\]

在优化问题中，我们定义了一个优化变量 \(x\)，目标是最小化目标函数 \(f_0(x)\)，同时满足一系列约束函数 \(f_i(x)\)。通过在优化变量的可行域中搜索，我们可以找到目标函数的最大值或最小值，同时满足约束函数的限制。对于最小化问题，我们的目标是找到一个最优解 \(x^*\)，使得目标函数在约束函数限制的值域内取得最小值。

在搜索优化变量的可行域时，我们使用的方法被称为优化算法。

在优化问题中，全局最优解指的是在整个变量集合上取得最小值的解。局部最优解指的是在某个特定区域内取得最小值的解。对于凸优化问题，任何局部最优解都是其全局最优解。利用凸函数的性质，研究者们开发了许多高效的算法来寻找凸优化问题的全局最优解。

然而，对于非凸优化问题，情况变得更加复杂。非凸优化问题的目标函数和约束条件可能存在多个局部最优解，因此寻找全局最优解变得困难且计算复杂度较高。除了一些特殊问题可以被特定方法解决外，大部分非凸优化问题仍然缺乏有效的解决方法。

凸优化问题总能找到全局最优解，因此将非凸优化问题转化为凸优化问题成为研究的重点。

5. 实例

逐次凸逼近

Sequential Convex Approximation，SCA）是一种常用的方法，用于处理非凸优化问题。它通过将非凸问题逐步逼近为一系列凸子问题来求解。

SCA的基本原理如下：

  1. 初始化：给定初始点 \(\mathbf{x}_0\)。
  2. 进行迭代：
    1. 在当前点 \(\mathbf{x}_k\) 处，对非凸目标函数进行一次凸逼近，得到局部凸近似目标函数 \(f_k(\mathbf{x})\)。
    2. 求解凸近似问题，即最小化 \(f_k(\mathbf{x})\)，在一组凸约束条件下，找到局部最优解 \(\mathbf{x}_{k+1}\)。
    3. 检查终止准则，如果满足，则停止迭代，返回最优解 \(\mathbf{x}_{k+1}\)；否则，返回步骤 b，继续迭代。
  3. 返回最优解 \(\mathbf{x}_{k+1}\)。

在每一次迭代中，我们将原始非凸目标函数进行一次凸逼近。这可以通过不同的方法实现，如一阶泰勒展开、凸松弛或仿射逼近等。通过逐步逼近，我们可以在每个迭代步骤中获得目标函数在一点处的全局上估计，并求解凸近似问题，逐步接近原始非凸问题的最优解。

下面，我们使用SCA方法来解决之前提到的波束赋形设计优化问题。假设我们已经将问题转化为如下形式：

目标函数：最大化总传输速率 \[ \begin{align*} \text{maximize} & \quad R_{\text{sum}}(\mathbf{w}) \\ \end{align*} \] 约束条件： \[ \begin{align*} \text{subject to} & \quad \|\mathbf{w}\|_2^2 \leq P_{\text{max}} \\ \end{align*} \] 具体步骤如下：

  1. 初始化：给定初始波束权向量 \(\mathbf{w}_0\)。
  2. 进行迭代：
    1. 在当前波束权向量 \(\mathbf{w}_k\) 处，对总传输速率进行一次凸逼近，得到局部凸近似目标函数 \(R_{\text{sum}}(\mathbf{w})_k\)。
    2. 求解凸近似问题，即最大化 \(R_{\text{sum}}(\mathbf{w})_k\)，在一组凸约束条件下，找到局部最优解 \(\mathbf{w}_{k+1}\)。
    3. 检查终止准则，如果满足，则停止迭代，返回最优解 \(\mathbf{w}_{k+1}\)；否则，返回步骤 b，继续迭代。
  3. 返回最优解 \(\mathbf{w}_{k+1}\)。

在每一次迭代中，我们使用适当的凸逼近方法对目标函数 \(R_{\text{sum}}(\mathbf{w})\) 进行逼近，并求解凸近似问题。重复迭代过程，直到满足终止准则为止，最终得到原始非凸问题的一个局部最优解。

需要注意的是，由于SCA是一种近似方法，它只能提供非凸问题的局部最优解，并且收敛性也无法保证。因此，对于实际应用中的非凸优化问题，需要综合考虑算法的性能和求解结果的质量。

拉格朗日对偶方法

非常感谢您的建议。现在我将使用拉格朗日对偶方法来解决无线通信领域的波束赋形设计优化问题。

问题描述： 考虑一个MIMO通信系统，其中有一个基站（发射端）和多个用户设备（接收端）。我们的目标是设计基站的波束权向量，以最大化系统的总传输速率。假设我们有 \(N_t\) 个发射天线和 \(N_r\) 个接收天线。波束赋形设计问题可以表述为优化波束权向量 \(\mathbf{w}\)，使得总传输速率最大化。

目标函数：最大化总传输速率 \[ \begin{align*} \text{maximize} & \quad R_{\text{sum}} = \sum_{i=1}^{K} R_i \\ \end{align*} \] 其中，\(R_{\text{sum}}\) 是总传输速率，\(R_i\) 是用户 \(i\) 的传输速率。

约束条件： \[ \begin{align*} \text{subject to} & \quad \|\mathbf{w}\|_2^2 \leq P_{\text{max}} \end{align*} \] 其中，\(\|\mathbf{w}\|_2^2\) 表示波束权向量的模长的平方，\(P_{\text{max}}\) 是基站的总发射功率限制。

解决思路： 使用拉格朗日对偶方法，我们可以将非凸的波束赋形设计优化问题转化为一个凸优化问题。

  1. 定义拉格朗日乘子 \(\lambda \geq 0\)。

  2. 构造拉格朗日函数： \[ \begin{align*} L(\mathbf{w}, \lambda) &= R_{\text{sum}} - \lambda \left(\|\mathbf{w}\|_2^2 - P_{\text{max}}\right) \end{align*} \]

  3. 对拉格朗日函数 \(L(\mathbf{w}, \lambda)\) 求解最大化问题： \[ \begin{align*} \text{maximize} & \quad L(\mathbf{w}, \lambda) \\ \text{subject to} & \quad \mathbf{w} \in \mathcal{W} \end{align*} \] 其中，\(\mathcal{W}\) 是波束权向量的可行域，根据具体的问题可以定义不同的约束条件。

  4. 进行迭代：

      1. 在当前拉格朗日乘子 \(\lambda\) 的估计下，固定波束权向量 \(\mathbf{w}\)，通过求解最大化问题来更新拉格朗日乘子的估计 \(\lambda\)。
      1. 在当前拉格朗日乘子 \(\lambda\) 的估计下，固定拉格朗日乘子 \(\lambda\)，通过求解波束权向量的最大化问题来更新波束权向量 \(\mathbf{w}\)。
      1. 更新迭代次数。
      1. 检查终止准则，如果满足则停止迭代，否则返回步骤a。

  5. 利用最优解 \(\mathbf{w}^*\) 和拉格朗日乘子 \(\lambda^*\)，计算总传输速率 \(R_{\text{sum}}^*\)。

通过拉格朗日对偶方法，我们可以将原始的非凸优化问题转化为求解拉格朗日函数的凸优化问题。然后通过求解凸优化问题，可以得到最优的波束权向量和总传输速率。

拉格朗日对偶方法通常需要进行迭代求解。在每一次迭代中，我们会更新波束权向量和拉格朗日乘子的估计，并计算相应的拉格朗日函数值。通过迭代，我们逐步接近最优解。

在每一次迭代中，通过交替地更新波束权向量和拉格朗日乘子，我们可以逐步接近最优解。停止准则通常可以设置为达到最大迭代次数或达到满足收敛条件（目标函数收敛或者函数上估计与下估计间隙收敛）。