2020年7月17日,星期五

凹凸凹面游戏

如果您现在需要解决凸优化问题,那么您的情况就很好。任何形式为$$的问题
\ begin {alignat} {2}
&\!\ inf_z&\ qquad&f(z)\\
&\ text {取决于}&&h(z)= 0 \\
&&&g(z)\ preceq 0
\ end {alignat}
$$,其中$ f $和$ g $是凸的,而$ h $是仿射的,可以用几个优秀的免费提供的软件包来攻击:我目前最喜欢的是 cvxpy,使用起来很愉快。如果您有很多变量而不是很多约束,则可以解决一个双重问题。最终看起来像$$
\ begin {alignat} {2}
&\!\ sup_ {x}和\ qquad&L(x)\\
&\ text {取决于}&&\ tilde {h} _x(x)= 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0
\ end {alignat}
$$,其中$ L $是凹面的,假设您很幸运,并且可以分析地消除所有原始变量$ z $,从而仅保留对偶变量$ x $。但是,如果您不能消除所有原始变量,而只能消除其中的大多数,那该怎么办?您可能会遇到类似$$的问题
\ begin {alignat} {2}
&\!\ sup_ {x} \ inf_y&\ qquad&L(x,y)\\
&\ text {取决于}&&\ tilde {h} _x(x)= 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0 \\
&&&\\ tilde {h} _y(y)= 0 \\
&&&\\ tilde {g} _y(y)\ preceq 0
\ end {alignat}
$$,其中$ \ tilde {g} _x $和$ \ tilde {g} _y $是凸的,而$ \ tilde {h} _x $和$ \ tilde {h} _y $是仿射的,$ L(x,\ cdot)$在给定$ x $的情况下在$ y $中是凸的,而$ L(\ cdot,y)$在给定$ y $的情况下在$ x $中是凹的。如果已分析上消除了许多原始变量,似乎该问题应该比原始问题更容易解决。不幸, 我最喜欢的凸优化工具包都不会接受这种形式的问题。 尽管 内点方法解决此类问题的可行性。笨蛋

我尝试的一件事是使用标准工具包求解内部极小值,通过灵敏度图计算带有外部参数的解的梯度,然后对外部极值使用一阶方法。这对我不起作用:它适用于玩具问题,但在实际问题上,外部上层的收敛非常缓慢,这表明身体不适。

我需要的是内点方法通过二阶信息处理疾病的能力。我可以通过顺序二次极大极小编程来实现此目标:首先,在当前点周围用二次方局部逼近目标$ L(\ lambda,\ mu,y)$并将约束线性化。 $$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x} \ inf _ {\ delta y}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)^ \ top \ left(\ begin {array} {cc} P_ {xx}和P_ {yx} ^ \ top \\ P_ {yx}&P_ {yy} \ end {array} \ right )\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ q_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\\
&\ text {根据}&&\ left(\ begin {array} {cc} A_x&0 \\ 0&A_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ b_y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0 \\ 0&G_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ h_y \ end {array} \ right)\\
\ end {alignat}
$$ 沃尔夫双重 将此问题转换为标准的QP:$$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x,\ delta y,\ lambda,\ mu}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)^ \ top \ left(\ begin {array} {cccc} P_ {xx}&0&0&0 \\ 0&-P_ {yy} &0&0 \\ 0&0&0&0 \\ 0&0&0&0 \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ \ \ lambda \\ \ mu \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ 0 \\ -b_y \\ -h_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\\
&\ text {取决于}&&\ left(\ begin {array} {cc} A_x&0&0&0 \\ P_ {yx}&P_ {yy}&A_y ^ \ top&G_y ^ \ top \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ -q_y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0&0&0 \\ 0&0&0&-I \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ 0 \ end {array} \ right)\ \
\ end {alignat}
$$如果为$(\ delta x,\ delta y)$解决此问题,您将获得牛顿步骤以解决原始问题。这里的步验收标准很棘手:如果迭代可行,则您希望利用鞍点条件(请参见方程式(11) Essid等。等)。如果迭代不可行,则需要更复杂的方法,但是幸运的是,我的约束实际上是线性的,因此,进行初始的精确内部求解可使我在保持可行的同时进行迭代。 (注意:如果您在每个步骤上都解决了更一般的凸问题,则无需线性化$ x $约束。)

YMMV!