数论人生

数论是一门学科,也是我的人生。有人把酒论英雄,我用数字描天下。
个人资料
欧洲联盟 (热门博主)
  • 博客访问:
正文

最优化理论

(2022-02-05 16:09:25) 下一个

在实际应用中,人们总是想要一个最优的结果:最小的成本,最大的利益。自然界的运行规则也是如此:以最小的能量,占据最大的空间;或者以最短的时间,走过最远的路程。这是天命使然。微积分的出发点就是Fermat的极值原理,整个高等数学的终止点便是变分法;中间引进了各种关系(运算的、顺序的、几何的),最终目的都是最优化。我以为微分法解决了所有的优化问题,近日却遇到了例外。

在微积分中,条件极值问题的提法是:给定一组等式限制条件gi(x1, …, xn) = 0, i = 1, …, m, (x1, …, xn) 属于n维欧氏空间中的某个区域D,要求目标函数f(x1, …, xn)的极值。拉格郎日(Lagrange)乘子法,可以不必显式解出一些限制变量,而求出一些可能的驻点(各个一阶偏导数为0的点);对于区域D内部的驻点,可以把拉格郎日函数L = f + sigma(tigi: i = 1, .,.., m)在此点作Taylor展开,然后判定二阶微分式的正定性,可知驻点是否为极值点。如果各二阶偏导全为零,而某些三阶偏导数不为零,那就肯定不是极值点。如果三阶偏导还是0,那就要看四阶偏导和四阶微分式的正定性。遗憾的是,我们并没有所谓的四次型的正定性的判定方法,只是在《线性代数》中有二次型的正定性判定;以后的六次型、八次型呢,提都没人提起。

Fermat的极值原理只能用于 “内点” ,边界点还要单独考虑。可以把区域D的边界参数方程化,从而变成等式限制条件。我们看一个最简当的例子:x1 + … + xn = a, 0 ≤xi ≤ b, 0 < a ≤nb,n > 1, 求y = (x1)^2 + … + (xn)^2 的最大值和最小值。根据Cauchy不等式可知y的最小值为a^2/n(无需乘子法);用乘子法求出的也正是极小值。区域的边界是一些xi = b,一些Xi = 0 或者≤ b, 还得满足x1 + … + xn = a;这里,微分法用不上了,对n用数学归纳法,可以证明y的最大值为kb^2 + (a – kb)^2,其中k是【a/b】(向下取整)。

其它一些著名的不等式也可以用来求最大/最小值,而不需要求微分。如算术—几何平均值不等式,可以用来求一组正数的和式的最小值,如果其乘积给定的话;或者一组正数的乘积的最大值如果其和固定的话。AM-GM不等式可以归纳法证明,也可以用对数函数的凸性去证明。凸函数本身就是用不等式定义的,加上归纳法,可以用到数列上;更可以积分化,导出相应的不等式。Jenson不等式说,一组正数的r (> 0) 次幂之和再开r次方,对r是单调不增的。Holder不等式推广了Cauchy不等式,给出正数幂的乘积的加权平均不等式:(xi)^y1* … (xn)^yn ≤ {(sigmaxiyi)/sigma(yi)}^(sig,a(yi));Minkowski不等式则给出了两组正数的和的r次幂不等式:当r > 1时,(sigma(xi + yi)^r)^1/r ≤ (sigma(xi)^r)^1/r + (sigma(yi)^r)^1/r;当0 < r < 1时,不等式反号。

在《线性规划》中,限制条件都是一些线性不等式:sigma(aij*xi) ≤ bj, j = 1, …, k。如果目标函数f也是线性的,那么,它的最大/最小值必定在边界上:sigma(aij*xi) = bj, 取得;这很容易理解:这些线性表达式其实是一些 “超平面” ,目标平面沿着各个方向运动,最高/最低点只能是各个超平面的交点。如果目标函数是非线性的,我们可以引进一些非负变量yj,把不等式限制变为等式条件,然后用拉格郎日乘子法求解。

在赋范线性空间中,可以依照范数定义距离(反之不然);一个向量到一个子流形(子空间的平移)的最短距离,可以用平移的向量往子空间上作正交投影,这个正交分量的范数就是所求的最短距离。纯几何的方法,无需微分。

在《变分法》中,研究的是一些积分式,其中含有未知函数y(x)及其导数,要求找出一个函数,使得积分值最小;比如最快滑行曲线(在重力作用下)、面积最小的旋转曲面、变形薄膜的平衡。解决方法是,给未知函数一个小的“扰动”,即加上一项tg(x),t充分小;如果y是最佳选项,那么变化了那个积分在t = 0取极值,它对t的导数必定为零;由此便可推出欧拉方程。如果有多个未知函数,就给每个函数加上一个扰动项。

最一般的情况是,目标函数是一个连续和:被加项遍布于n维空间里的某个区域D中的每一个点,并且不能积分化,和式的收敛性都不能保证;基于极限概念的微分法显然无能为力了。用离散抽样的方法或可一试,还得定义一些统计量,以及一个“最佳逼近”的标准;即所谓的数值解法。如果没有高速的计算机,靠人力是无法完成的。

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.