计算科学 - 你建议用什么方法来解决这个极小值，两个变量的二次方问题？ - 吾爱随笔录

你建议用什么方法来解决这个极小值，两个变量的二次方问题？

计算科学优化凸优化

2021-12-10 18:03:08

我的形式有问题，如何有效地解决这个问题？是一个半定矩阵。我所做的：您可以对内部问题进行双重处理，并使用两个 sdp 变量得到一个半定问题。但是这种方法太慢了，大多数求解器都无法热启动，这是我需要的。我想要一个具有热启动能力的快速方法，即当我添加一个简单的约束时，我可以使用之前的迭代结果，而不是从头开始。

\begin{aligned} m i n i m i z e_{y} m a x i m i z e_{x} & x^{T} y - y^{T} (B ⊙ x x^{T}) y \\ s . t . & x \in [l, u] \\ A y = b \end{aligned}

$\begin{align} minimize_{y} maximize_{x}&\quad x^T y - y^T (B\odot x x^T) y\\ s.t. &x\in [l,u]\\ &Ay=b \end{align}$

B

$B$

编辑：不幸的是，我有一些额外的困难，是整数。尽管我将其放松到之间的值。使用半定松弛，是否有任何有效的算法来解决这个问题？这样，@Brian Borchers 提到这种方法对我的应用程序很有用，因为我至少可以对使用 warmstart 。你有什么建议？ $y$ $[-1,1]$ $y$ $x$ $x$

2个回答

你可以把你内心的问题写成

$\max_{x} x^{T}y - x^{T}Cx$

受制于

$x \in [l,u]$

其中。这是一个框约束 QP。 $C=\mathrm{diag}(y)B\mathrm{diag}(y)$

由于，也是半正定的，所以内部问题是一个凹最大化问题。 $C=\mathrm{diag}(y) B \mathrm{diag}(y)$ $C$

您可以使用多种方法（例如活动集方法）轻松解决内部问题。您还可以计算最优值对变化的敏感度。有了这些敏感性，您就可以应用一阶方法来解决外部最小化问题。 $y$

有多种算法可以解决凸凹极小极大问题

$\min_{y} \max_{x} f(x,y)$

其中是一个函数，对于固定 y 在 x 中是凹函数，对于在中是凸。例如，参见 Rustem 和 Howe 的书中的第 3 章，Algorithms for Worst-Case Design and Applications to Risk Management。这些算法几乎可以与任何解决内部问题的方法一起使用，作为子程序。 $f$ $x$ $y$ $y$ $x$

在您的情况下，固定的函数不是凸的。您还有其他复杂的约束条件。您仍然可以尝试这种通用方法，但常规分析无法确保收敛。 $f$ $y$ $x$

使用整数变量，在整数和二次规划的一些技巧之后，整个问题可以转换为 MILP。也许不是您想在您的情况下做的事情，但至少这是一种有保证的全局方法

可以使用线性约束和辅助变量来编写二进制和连续之间的乘法。
二进制多项式可以使用线性约束和辅助变量来编写。
有界整数变量可以使用二进制变量来编写。
内部 QP 的最优解可以使用 KKT 条件编写，涉及和之间的乘积以及互补性。 $y$ $x$
可以使用附加的二进制变量和约束来处理互补约束。

首先规范化符号并假设内部程序是最小化，受约束。最优解由 KKT 条件 $c^T(y)x + \frac{1}{2}x^TQ(y)x$ $Ex\leq f$

Q (y) x + c (y) + E^{T} λ = 0 λ^{T} (f - E x) = 0 λ \geq 0 f - E x \geq 0

$Q(y)x + c(y) + E^T\lambda=0\\ \lambda^T(f - Ex) = 0\\\lambda\geq 0\\f-Ex\geq 0$

在满足最优性条件的任何点，目标等于。在我们希望最小化目标的外部程序中，我们因此想要最小化。 $\frac{1}{2}(c(y)^Tx-f^T\lambda)$ $-\frac{1}{2}(c(y)^Tx-f^T\lambda)$

我们注意到，我们有一个等式，其中涉及乘以的二次函数（因此可线性化）、互补性条件（可线性化）和目标中的双线性项（可线性化）。 $y$ $x$

有很多不同的东西可以放在一起。在下面的代码中，我将使用 MATLAB Toolbox YALMIP（免责声明：由我开发）对此进行测试。它具有用于线性化和互补性的 MILP 建模的内置功能。

% Define a random problem
n = 4;
B = randn(n);
B = B*B';
A = ones(1,n);
b = 1;
U = rand(n,1);
L = -rand(n,1);
E = [eye(n);-eye(n)];
f = [U;-L];

% Define decision variables
x = sdpvar(n,1);
% y is modelled as a selection from possible values
PossibleY = [-1;0;1];
Selector = binvar(n,length(PossibleY),'full');
y = Selector*PossibleY;
ConstrainSelection = sum(Selector,2) == 1

% Inner problem min_x c(y)'*x + .5*x'*Q(y)*x
lambda = sdpvar(length(f),1);
c = -y;
Q = 2*(B.*(y*y'));

Stationary = Q*x+c+E'*lambda == 0;
Complementarity = complements(lambda>=0, f - E*x>=0);
Objective = 0.5*(c'*x - f'*lambda);

% Objective we actually maximized in inner and whish o minimize in
% the outer problem
OuterObjective = -Objective;
% Linearize binary*binary and binary*continuous 
LinearizedStationary = binmodel([Stationary,[L<=x<=U]]);
[LinearizedObjective,Cuts] =  binmodel(OuterObjective,[L<=x<=U]);
% Solve the problem
optimize([LinearizedStationary, 
          Complementarity,
          Cuts,
          A*y == b,ConstrainSelection],LinearizedObjective)
% Check that the linearization actually worked
[value(LinearizedObjective) -value(c'*x + .5*x'*Q*x)]

% Small sanity check. Check by solving everything for fixed x, keeping
% kkt conditions, to ensure the new y still renders x optimal.
Objective = value(x)'*y - y'*(B.*(value(x*x')))*y;
[LinearizedObjective,Cuts] =  binmodel(Objective);
LinearizedStationary = binmodel([Q*value(x)+c+E'*lambda == 0]);
optimize([Cuts,A*y == b,lambda>=0, lambda'*(f - E*value(x))==0,LinearizedStationary],LinearizedObjective)
value(Objective)

其它你可能感兴趣的问题

上一篇具有多个右手边的线性系统下一篇在 Matlab 中通过曲线拟合找到收敛速度