最优化理论

在实际应用中，人们总是想要一个最优的结果：最小的成本，最大的利益。自然界的运行规则也是如此：以最小的能量，占据最大的空间；或者以最短的时间，走过最远的路程。这是天命使然。微积分的出发点就是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中的每一个点，并且不能积分化，和式的收敛性都不能保证；基于极限概念的微分法显然无能为力了。用离散抽样的方法或可一试，还得定义一些统计量，以及一个“最佳逼近”的标准；即所谓的数值解法。如果没有高速的计算机，靠人力是无法完成的。