我正在研究
Python中的一个程序,其中一小部分涉及优化方程/不等式系统.理想情况下,我本来想做的就像在Modelica中一样,写出方程并让解算器处理它.
解算器和线性编程的操作有点超出我的舒适范围,但我决定尝试.问题是程序的一般设计是面向对象的,组合方程有许多不同的可能性,以及一些非线性,所以我无法将其转化为线性规划问题(但我可能错了).
经过一些研究,我发现Z3求解器似乎做了我想要的.我想出了这个(这看起来像我想要优化的典型情况)：
from z3 import *
a = Real('a')
b = Real('b')
c = Real('c')
d = Real('d')
e = Real('e')
g = Real('g')
f = Real('f')
cost = Real('cost')
opt = Optimize()
opt.add(a + b - 350 == 0)
opt.add(a - g == 0)
opt.add(c - 400 == 0)
opt.add(b - d * 0.45 == 0)
opt.add(c - f - e - d == 0)
opt.add(d <= 250)
opt.add(e <= 250)
opt.add(cost == If(f > 0, f * 50, f * 0.4) + e * 40 + d * 20 +
If(g > 0, g * 50, g * 0.54))
h = opt.minimize(cost)
opt.check()
opt.lower(h)
opt.model()
现在这个工作,并给我我想要的结果,尽管它不是非常快(我需要解决这样的系统数千次).
但我不确定我是否正在使用正确的工具(Z3是一个“定理证明者”).
API基本上就是我需要的,但我很好奇其他包是否允许类似的语法.或者我应该尝试以不同的方式制定问题以允许标准LP方法？ (虽然我不知道怎么样)

四边形不等式优化
在动态规划中，经常遇到形如下式的转台转移方程：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)（min也可以改为max）

上述的m(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。

下面我们通过四边形不等式来优化上述方程，首先介绍什么是”区间包含的单调性“和”四边形不等式“

（1）区间包含的单调性：如果对于i≤i’<j≤j’，有w(i’,j)≤w(i,j’)，那么说明w具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的w值不超过大区间的w值）

（2）四边形不等式：如果对于i≤i’<j≤j’，有w(i,j)+w(i’,j’)≤w(i’,j)+w(i,j’)，我们称函数w满足四边形不等式。（可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和）

下面给出两个定理

定理一：如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数m也满足四边形不等式性质。

我们再定义s(i,j)表示m(i,j)取得最优值时对应的下标（即i≤k≤j时，k处的w值最大，则s(i,j)=k）。此时有如下定理

定理二：假如m(i,j)满足四边形不等式，那么s(i,j)单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。

好了，有了上述的两个定理后，我们发现如果w函数满足区间包含单调性和四边形不等式性质，那么有s(i,j-1)≤s(i,j)≤s(i+1,j)。即原来的状态转移方程可以改写为下式：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))（min也可以改为max）

由于这个状态转移方程枚举的是区间长度L=j-i，而s(i,j-1)和s(i+1,j)的长度为L-1，是之间已经计算过的，可以直接调用。不仅如此，区间的长度最多有n个，对于固定的长度L，不同的状态也有n个，故时间复杂度为O(N2)，而原来的时间复杂度为O(N3)，实现了优化！今后只需要根据方程的形式以及w函数是否满足两条性质即可考虑使用四边形不等式来优化了。

在学习SVM的原理时，接触到了等式约束优化与不等式约束优化，下面是根据相关资料自己总结出来的自己的，希望对大家有所帮助，这是第一篇博客。

1.等式约束优化

1.1.问题描述

当目标函数加上等式约束条件之后，原本的非约束优化变成了等式约束优化，如下：

  .....................................................................................(1)

  ............................................................................(2)

因为存在约束条件，所以将的解限定在了一个可行域的区域，此时可能找不到可以使得为0的点，但是我们的目的是找到可行域范围内的最小值即可。

1.2.解法

利用拉格朗日乘子法，引入拉格朗日算子  ,构建拉格朗日函数如下：

 ..........................................................(3)

然后对拉格朗日函数求的偏导，令偏导为0，即：

 ..............................................................................(4)

对（2）（4）式进行求解即得到此类问题的最优解。

1.3.解释

假设我们的目标函数为二维的，即，在平面中画出的等高线，如下图的虚线所示


显而易见，只有当等高线与目标函数的曲线相切时才有可能得到可行解。因此拉格朗日取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即

 ................................................................(5)

所以正好可以得到（3）式，需要注意的是，仅仅要求不等于0即可，正负号不需要确定。

 

2.不等式约束优化

2.1.问题描述

不等式约束优化问题为：

 ...........................................................................................(6)

 ..................................................................................(7)

2.2.解法

首先构建拉格朗日函数如下：

 ...............................................................(8)

对(8)式关于求偏导，可得

 ...................................................................................(9)

另外还有KKT条件如下：

          或者  .....................(10)

由（9）（10）两式可以得出最后的最优解。对于（10）式的解释请看2.3节。

2.3.解释        

假设我们的目标函数为二维的，下图给出了目标函数的等高线与不等式约束：



根据上图可知，可行解存在于或者的区域里取到，存在下列两种情况：



a)当可行解落在的区域内，此时约束条件不起作用，直接极小化即可，所以（1）式中，只需满足即可。即上图左侧所示.

b)当可行解落在的区域内，此时等价于等式约束优化问题。即上图右侧所示。此时目标函数的梯度方向为指向中心位置的反方向，而约束函数由约束区域指向非约束区域。由下图可以看出，在最优解的位置，约束函数的梯度方向于目标函数的梯度方向正好相反，从而有：



  ..................................................(11)

（11）式其实就是（9）式的变形。当然（11）式有一个限制条件 。

 

 

不等式约束的优化问题求解

与前文讨论的只含等式约束的优化问题求解类似，含不等式约束的优化问题同样可以用拉格朗日乘子法进行求解 

对于一般形式的优化问题： 

 $$minimize\quad f(x)\\
subject\  to\quad h(x)=0\\
\quad\quad g(x)\le 0$$  

其中，$f:R^{n}\to R,h:R^{n}\to R^{m},m\le n,g:R^{n}\to R^{p}$ 

引入下面两个定义：


定义1：对于一个不等式约束$g_{j}(x)\le 0$，如果在$x^{*}$处$g_{j}(x^{*})=0$，那么称该不等式约束是$x^{*}$处的起作用约束；如果在$x^{*}$处$g_{j}(x^{*})<0$，那么称该约束是$x^{*}$处的不起作用约束。按照惯例，总是把等式约束$h_{i}(x)$当作起作用的约束

定义2：设$x^{*}$满足$h(x^{*})=0,g(x^{*})\le 0$，设$J(x^{*})$为起作用不等式约束的下标集： 

 $$J(x^{*})\triangleq \{j:g_{j}(x^{*})=0\}$$  

如果向量 

 $$\nabla h_{i}(x^{*}),\nabla g_{j}(x^{*}),1\le i\le m,j\in J(x^{*})$$  

是线性无关的，那么称$x^{*}$是一个正则点


下面介绍某个点是局部极小点所满足的一阶必要条件，即KKT条件。 

KKT条件：设$f,h,g\in C^{1}$，设$x^{*}$是问题$h(x)=0,g(x)\le 0$的一个正则点和局部极小点，那么必然存在$\lambda^{*}\in R^{m}$和$\mu^{*}\in R^{p}$，使得以下条件成立： 

 $$\mu^{*}\ge0\\
Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T}\\
\mu^{*T}g(x^{*})=0\\
h(x^{*})=0\\
g(x^{*})\le0$$  

那么在求解不等式约束的最优化问题的时候，可以搜索满足KKT条件的点，并将这些点作为极小点的候选对象。


二阶充分必要条件

除了一阶的KKT条件之外，求解这类问题还有二阶的充分必要条件。

二阶必要条件：在上述的问题中若$x^{*}$是极小点且$f,h,g\in C^{2}$。假设$x^{*}$是正则点，那么存在$\lambda^{*}\in R^{m}$和$\mu^{*}\in R^{p}$使得


$\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0$
对于所有$y\in T(x^{*})$，都有$y^{T}L(x^{*},\lambda^{*},\mu^{*})y\ge0$成立


二阶充分条件：假定$f,h,g\in C^{2}$，$x^{*}\in R^{n}$是一个可行点，存在向量$\lambda^{*}\in R^{m}$和$\mu^{*}\in R^{p}$使得


$\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0$
对于所有$y\in \widetilde{T}(x^{*},\mu^{*}),y\neq0$，都有$y^{T}L(x^{*},\lambda^{*},\mu^{*})y>0$成立


那么$x^{*}$是优化问题$h(x)=0,g(x)\le 0$的严格局部极小点