计算科学 - 具有绝对值约束总和的凸优化问题 - 吾爱随笔录

计算科学约束优化二次规划

2021-12-12 00:59:51

如何解决下面写的优化问题？

\begin{aligned} {argmax}_{a} a^{T} b - \frac{1}{2} a^{T} X a \\ subject to \sum_{i} | a_{i} | = 4, \sum_{i} a_{i} = 0 \end{aligned}

$\begin{align} &\operatorname{argmax}\limits_{a}\; a^T b - \frac{1}{2} a^T X a\\ &\text{subject to } \sum_i |a_i|=4,\; \sum_i a_i = 0 \end{align}$

在哪里 $a$ , $b$ 是 $n$ -向量和 $X$ 是一个 $n\times n$ 矩阵。还， $b$ 和 $X$ 是常数。

我的主要问题是关于绝对值。没有绝对值，实际上有一个解析解。我猜对于绝对值，我必须使用迭代方法，例如二次规划，但仍然不确定如何表达问题以调用相关的优化程序。

1个回答

不幸的是，您的问题不是凸优化问题，因为约束 $\Sigma_{i} | a_{i}|=4$ 描述了一个非凸可行域。如果您可以将其更改为 $\Sigma_{i} | a_{i} | \leq 4$ ，你会有一个凸约束。

如果约束是 $\Sigma_{i} | a_{i} | \leq 4$ ，那么可以引入辅助变量 $t_{i}$ ，并添加约束

$\Sigma_{i} t_{i} \leq 4$

$t_{i} \geq a_{i}$ 对所有人 $i$

$t_{i} \geq -a_{i}$ 对所有人 $i$

这是凸优化中的标准重构技术。

您原始问题陈述的另一个问题是 $X$ 必须是半正定的，以确保目标函数的凹度。

假如说 $X$ 是半正定的，你现在有一个线性约束凸二次规划问题，可以由许多求解器解决。

其它你可能感兴趣的问题