电磁力中的对偶.doc

电、磁、力中的对偶电、磁、力中的对偶刘红摘要：本文从对偶的角度解释了电、磁、力之间的关系，总结了高扬提出的用于全局优化的典范对偶理论及利用它解决非线性非凸问题的主要思路和优点。引言 电、磁、力三大物理分支存在对偶关系。透过它们之间的不同外部现象，抽象出数学模型，看到他们的本质却是相同的。三大系统的物理量间又存在着对偶关系，这就是典范对偶理论。非线性的变量关系或非凸性的能量函数是造成系统复杂性的关键原因。典范对偶理论旨在利用非线性变换，凸化的手段，把原空间中不便于处理的问题转化到对偶空间中来处理。这就是把“不美”的东西转化为“美”的东西，然后处理“美”的东西，最后通过能量守恒的原理把处理的结果反馈回原空间中。而三个驻点对偶定理提供了能量在原空间和对偶空间中进行的最优化的理论基础。 本文先从最简单的线性电阻电路模型开始，表示出在线性情况下的典范对偶模型。描述这种电路的数学模型是线性方程组。解这类线性方程组等价于二次规划的最优解。线性模型对应线性算子，非线性模型对应非线性算子。通过非线性变换，以及利用任何函数都可以分解为凸函数之差的方法，可将非线性非凸问题转换为线性的凸的问题。这种转换，有别于泰勒展开后取线性部分近似。这里不是近似而是变换，所以能得到更准确的效果。1. 线性电阻电路的数学描述考虑如图1所示的电路。此电路中，节点为1，2，3，4。令为各节点的电位，假设节点4的电位为零，分别从节点1，2，3，4流进电路的电流，设网络除节点4外没有其它的接地点，所以。为各支路的电流，为各支路电阻上的电压。 各支路上电阻的电压与电流取关联参考方向。图 1 一个电路 该电路各变量之间的关系可由下列三式描述。 由基尔霍夫电压定律可得： （1） 由欧姆定律可得： （） 由基尔霍夫电流定律可得： （）其中，式（）称为代数变换关系，将各节点的电位变换为各支路电阻元件上的电压降，即仿射变换。式（）称为对偶关系，所对应的矩阵称为本构矩阵，反映系统的本质。很显然矩阵是正定矩阵，这个矩阵确定了电压和电流的一一对应关系。一对一的关系就是“美”的关系，它常常使问题变得简单。式（3）称为平衡方程，是能量守恒（功率平衡）的必然结果。2. 电路变量间的对偶关系将上述三式合成，可得：。令，则可得。电路各变量间的对偶关系如图2所示。图 2 电路变量的典范对偶图图2中，上面一行是在原空间中的两个向量。原空间中的内积定义为：。 （4） 图2中，下面一行是在对偶空间中的两个向量。对偶空间中的内积定义为： 。 （5）由，定义的三个变换代表的三组对偶关系称为电路的典范对偶关系。从下文可以看出，典范的含义就在于对于非凸的系统或者非线性的系统，通过选取合适的变换算子，总可以化成凸的系统， 即典范化理解为标准化、凸化。3. 功率平衡与能量最小化若，将会有。从物理的角度，可理解为功率平衡（能量守恒）。不同的空间，只是选择了不同的坐标系，也就是说选择了不同的度量方式，但无论怎么度量，能量是不变的。 从数学的角度，根据两个向量内积的定义及矩阵乘法的结合律，易知：。系统的内能定义为，对应于动力系统的动能；系统的外能定义为，对应于外力对动力系统所作的功。系统在运动中，具有动能，外力要使系统稳定，就要对系统作功，外力所做的反功就是在消耗系统的动能。 为此，定义系统的总能量（自由能）为：。系统总能量为的二次型。令，即得到了平衡方程。这就说明了解电路的平衡方程可等价为求解一个二次规划。4. 二次规划二次规划可描述为： （）其中为对称阵。如果有约束，则可以通过lagrangian乘子法松弛为无约束规划。这里总假设为对称阵，否则用代替它，因为。下面先讨论是正定矩阵的情况。若是正定矩阵，是的凸函数，令偏导数为零可解出唯一的最小值点。事实上，正定矩阵可分解为，其中为对角阵，对角线元素都是正数。令（代数变换方程），（对偶方程），（平衡方程）。这三个方程合在一起，就是所谓的三典范对偶。 通过典范对偶的转化，原二次规划问题可转为问题： （7） 其中， 在处取到。函数关于是凹函数，关于是线性函数。上述问题的最优解在鞍点处取到。图 3 二次规划的典范对偶图 若不是正定矩阵，原二次规划不是凸规划，如果直接在原空间中求解，问题会变得麻烦。为此，可将分解为两个正定矩阵之差（任何实数可以分解为两个正数之差，任何对称矩阵都可以分解为两个正定矩阵之差，任何函数都可以分解为两个凸函数之差）。这样，原问题变成为：。 对进行分解，。原二次规划问题可转化为：。 （8）函数关于是凹函数，关于也是凹函数，但关于不一定是凹函数。5. 非线性系统的典范对偶实际上，图3中的算子可以矩阵，可以是微分，积分，还可以是非线性算子等等。算子也可能是非线性的。由算子引起的非线性称为代数非线性，由算子引起的非线性称为物理非线性。非线性系统的典范对偶图如图4所示。图4中的算子分解为切向算子和余算子。是的逆算子。是的共轭对偶变量。 如果系统的变量间是非线性的关系，那么能量函数不再是二次的，更难以保证是凸函数。非线性非凸最优化问题一般可表示为：。 （9） 其中，为非凸函数。图 4 非线性系统的典范对偶图 典范对偶理论的关键思想就是选择一个代数变换， 使得为关于的凸函数。例如关于不一定凸，但如果选择， 则是凸函数。如果是n维向量，它的对偶变量是个一维的变量。函数共轭变换定义为：。显然，当满足时，上式的最大值取到。由确定的算子，即是对偶图中的。共轭变换的几何含义：对于一个函数，常规的看法就是给定每个自变量和对应函数值可以确定这个函数而共轭变换函数的自变量是原函数的切线的斜率（导数），函数值就是切线的截距。任何函数通过共轭变换得到的函数总是凸函数。如果原函数本身是凸函数，那么共轭变换的共轭变换就是原函数， 即。因此，经过共轭变换，优化问题（9）转换为：。 （10）所以，求解问题（10）成为解决非线性非凸问题的关键。函数关于总是凸函数，但关于的凸凹性随着及的不同而不同。要使问题（10）简单易解，技巧就在于选择合适的算子，这需要具体问题具体分析，此处不作详细讨论。下一节讨论在知道的关于凸凹性的情况下，如何得到问题的解。6. 驻点对偶定理 定义1：若点满足: （11）则称是的鞍点。 若使得定义中的两个不等式均反过来也是鞍点。若关于其中一个是凹函数，关于另一个是凸函数，它就是个鞍形函数，必然存在鞍点。 定理1（鞍点对偶定理）：若点是的鞍点，则：。 （12） 证明：由于是的鞍点，由不等式（11）可知：（*）。由于，由（*）式左边可知。由于，由（*）式右边可知。所以，即（12）的右边成立。同理可证（12）的左边成立。 鞍点对偶定理说明在对于鞍函数求鞍点的时候，可以交换变量的最优化顺序。 定义2：若点满足: （13）则称是的上驻点。若点满足: （14）则称是的下驻点。 定理2（上驻点对偶定理）：点是的上驻点，则下列两式必有一个成立：；。 证明：点是的上驻点，所以（*）。（*）说明是的驻点，是的驻点，所以是的驻点。因此，必是的驻点。若是的最大值点，即（*）。由（*）和（*）知，于是，所以，即， 这说明。即证成立；若是的最小值点，即（*）。另一方面，必是的驻点。若为的最大值点，或者拐点，则可推出与（*）式矛盾。所以必是的最小值点。即证得成立。同理可知对应的下驻点对偶定理。鞍点定理，上驻点定理，下驻点定理，三个对偶定理合称驻点对偶定理（这三个定理的逆定理也成立，此处不证）。驻点对偶定理在典范对偶理论中起着至关重要的作用。有了驻点对偶定理，式（7）或（8）所示二次规划问题可以通过交换变量的顺序来求解。 一个例子： 考查二元函数，其中为常数，。对任意固定的，是关于的凹函数。对任意固定的，是关于的凹函数。也就是说，分别关于或关于是凹函数。 但是，由于Hessian矩阵不一定是负定的，所以关于不一定是凹函数。函数关于的极大值是； 关于的极大值是。 令的两个偏导数为零，可解得其驻点为，这里假设，否则原问题没有极值点。易知是的驻点，是的驻点。由于分别关于或关于是凹函数，所以下式成立：。这就说明是的上驻点。容易验证：若 ，Hessian矩阵不是负定的，所以关于不是凹函数，并且。图 5 m=10,k=1的图像若，Hessian矩阵是负定的，所以关于是凹函数，唯一的驻点必是全局最大值点，即，并且。7. 结论 本文总结了电、磁、力三个系统的对偶，每个系统中的物理量的三个典范对偶，每个系统平衡时的三个驻点对偶。由于对偶关系间的传递性，可以产生更多的对偶关系。电、磁、力之间的相生相克与相互对偶，使得它们相互转化、相互控制。参考文献: 1 Gao, D.Y. (2000). Duality Principles in Nonconvex Systems: Theory, Methods and Applications, Kluwer Academic Publishers, Dordrecht /Boston /London, xviii + 454pp.2 Gao, D.Y. (2000). Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Global Optimization, 17 (1/4), pp. 127-160.3 Gao, D.Y. (2004). Canonical duality theory and solutions to constrained nonconvex quadratic programming, J. Global Optimization, 29, 377-399.4 Wu ,Z.Y. Bai, F.S. Zhang L.S. (2005). Convexification and Concavification for a General Class of Global Optimization Problems, J. Global Optimization, 31, (1) :4560.5 Li, D. Sun, X.L. Biswal, M.P. and Gao, F. (2001) . Convexification, concavificati