计算科学 - 优化问题中的变量倒数之和 - 吾爱随笔录

优化问题中的变量倒数之和

计算科学优化非线性规划混合整数规划组合学

2021-12-14 16:09:17

我有以下优化问题：

\begin{array}{ll} Minimize & \frac{1}{x_{1}} + \frac{1}{x_{2}} + \dots + \frac{1}{d_{n}} \\ Subject to & A x \leq b \end{array}

$\begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array}$ 在哪里

x = [x_{1} x_{2} \dots x_{n}]^{T}

$x = [x_1~~x_2~~\ldots~~x_n]^T$ ,

x_{1}, x_{2}, \dots, x_{n} \in {1, \frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{k}}

$x_1,x_2,\ldots,x_n \in \left\{1,\frac{1}{2},\frac{1}{3},\ldots, \frac{1}{k} \right\}$ 对于一些

k

$k$ ，和

A

$A$ 和

b

$b$ 有积极的条目（

A

$A$ 很大但实际上很稀疏）。

维度 $n$ 不是太大（我会说最多 100 个），但约束的数量可能很大（数十万）。它们是与成对相关的约束 $x$ 的。如何尝试解决这样的问题？有没有办法将其转换为可以使用 Mosek 等优化包解决的标准形式？

最后，如果离散版本被证明非常困难，我可以解决这个问题的持续放松。如果变量是连续的，则可行空间成为标准凸多面体，但目标函数仍然存在问题。任何想法表示赞赏。

谢谢你。

1个回答

对于离散版本，它可以转换为混合整数线性程序。你只需要注意每个元素 $x_i$ 可以写成 $x_i = \sum_{j=1}^k \frac{\delta_{ij}}{j}$ 在哪里 $\sum_{j=1}^k \delta_{ij} = 1$ 在哪里 $\delta_{ij}$ 是二进制的。使用相同的二进制变量，倒数很简单 $x_{i}^{-1} = \sum_{j=1}^k j\delta_{ij}$

这是用于设置和解决概念验证等问题的 YALMIP 代码（免责声明，与 Mosek 接口的 MATLAB Toolbox YALMIP 由我开发）

k = 5;
n = 10;
delta = binvar(n,k,'full')
x =    delta*(1./(1:k))';
xinv = delta*(1:k)';
A = randn(2*n,n);
b = 10*rand(2*n,1);
Constraints = [A*x <= b, sum(delta,2) == 1];
Objective = sum(xinv);
optimize(Constraints,Objective)
value(x)

你所说的连续版本是一个凸程序，因为逆在正正数上是凸的。反标量可以很容易地重新表述为涉及二阶锥的模型，因此您可以在 Mosek 中将其作为二阶锥程序来解决。如果您使用凸性感知 cpower 运算符，YALMIP 会自动执行此操作。

x = sdpvar(n,1);    
Constraints = [A*x <= b, 0 <= x <= 1];
optimize(Constraints,sum(cpower(x,-1)))
value(x)

手动引入新变量 $t_i$ 替换倒数并添加约束 $x_i^{-1} \leq t_i$ ， IE， $1 \leq x_it_i$ , 可以写成圆锥约束 $\Big|\Big| \begin{matrix}1\\t_i-x_i\end{matrix}\Big|\Big|\leq x_i+t_i$

现在，这是否适用于大型实例，这是一个完全不同的问题。

其它你可能感兴趣的问题

上一篇更新密集 QR 和 Cholesky 分解的代码下一篇获取矩阵伪逆的列向量