第八节 坐标轮换法
把一个多维问题转化为一系列较少维数的问题称为降维。降维方法有几种，坐标轮换法是用得较多的一种，这是一种不需要求函数导数的直接探索目标函数最优解的方法。
直接法、降维法
一、坐标轮换法的基本思想
其基本思想就是通过每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止，以达到将一个多维的无约束最优化问题，转化为一系列的一维问题来求解的目的。为简明起见，现以二元函数来说明
基本步骤：
1.从初始点(0)(0)(0)(0)12(,,)nXxxx出发，依次沿各坐标轴方向搜索最优点，保持其余n-1个变量不变。
例：如果(0)(0)(0)(0)(0)123(,,,)(3,5,23,21)nXxxxx，如果沿x1轴方向搜索，则搜索过后改变的仅仅是x1的值3，其余坐标的值均保持不变。假设搜索到的值是8，则下一个点的值为(1)(1)(0)(0)(0)1123(,,,)(8,5,23,21)nXxxxx。
迭代点的序列为：
(0)(1)(0)(0)(0)(0)0123(,,,)nXXxxxx
(1)(1)(0)(0)(0)1123(,,,)nXxxxx
(1)(1)(1)(0)(0)2123(,,,)nXxxxx
(1)(1)(1)(1)(0)3123(,,,)nXxxxx
(1)(1)(1)(1)(1)(1)(2)1230(,,,)nnXxxxxXX
上标表示搜索的轮次，下标表示对应的坐标，亦即该轮次的第几次迭代。
经过一轮（n次）迭代后，得到一个新点，然后进行下一轮迭代。只到满足精度。
二、步长()ki可以有以下几种取法
1.随机选择()ki值的方法
2. 加速步长法
为方向的初始试验了加快探索过程，可以采用加速步长法。
用此法时，先规定沿()kiS方向的初始试验步长()kih，并用它探测跨步轮沿第的前、后方向。若第k轮沿第i个坐标方向进行探索时所获得的探索点
第９卷第９期
２０１０年９月 软件导刊
Ｓｏｆｔｗａｒｅ Ｇｕｉｄｅ Ｖｏ１．９ ＮＯ．９
Ｓｅｐ．２０１０
一种求解无约束非线性规划的切线相交法
程国建，卢飞远，房 华
（西安石油大学计算机学院，陕西西安７１００６５）
摘要：切线相交法是基于切线法的思想并结合黄金分割法而应用于求解无约束非线性规划问题的最优解。提出了
一个新的求解无约束非线性规划的有效算法，并在搜索区间已经确定和适当的条件下证明了该算法的收敛性，对几
个标准函数的测试表明了该算法的有效性。
关键词：单峰函数；切线相交法；无约束非线性规划
中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１６７２—７８００（２０１０）０９—００４５—０２
０ 引言
本文首先介绍切线相交法的基本思想和原理，推导其算法
形成过程；其次，给出算法的一般求解步骤，以及算法的收敛性
证明；再次用一些函数来测试算法的正确性以及和其他经典一
维搜索算法对比；最后对本文进行总结以及对算法作进一步的
研究
１算法基本原理
在求解无约束非线性规划的单峰函数问题时，若一维探索
区间为［ｎ，６］已经确定，ｍ ， ），其中／为实值连续函数，且在
［。，６］上有一阶连续导数。
图１算法原理图
如图１，在给定的搜索区间［０，ｂ］上，端点处的切线为ｙａ，ｙｂ
相交于一点ａｏ．且两条切线的方程为： ｆｙ￣＝ｆ（Ⅱ） 七 ａ）－ａｆ（口）
（ｙｂ＝ｆ（６） ｂ）一６，（ｂ）
解其交点为ｎｏ＝ 占
点（。 。））和（ｂ ６））的直线。 。其中，ｙａｂ是过
如果－厂（ａｏ）＝０，则ａｏ就是最优点；
如果，（ａｏ）＜Ｏ，则作过点（（叶６）／２，ｙａｈ）的切线ｙｎ的平行线
ｙａｐ，ｙａｐ 厂（。） ＋（７ｎ（ｂ）ｔ 口）－ｆ（Ⅱ）（ａ＋ｂ））／２又与ｙ６ （ｂ） ｔ ｂ）
一 （ｂ）相交于点（６ｏ ｂｏ））。
￣ｅｏ ｂｏ＝ 。若 （ｂｏ）＝０，则ｂ。
就是最优点；若厂（ｂｏ）＜０，令ａ＝ｂ０；若 （ｂｏ）＞０，令ａ＝ａｏ，ｂ＝ｂ０；
1. 非线性规划
我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。
非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年.库恩和.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。
非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。
非线性规划举例
[库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为A箱,每箱啤酒的平均库存成本为H元,每次订货成本都为F元。如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。
我们以Q表示每次定货数量,那么年定货次数可以为QA,年订货成本为QAF。由于平均库存量为2Q,所以,年持有成本为2QH,年库存成本可以表示为:
第三章 非线性规划
§1 非线性规划
1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问
题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有
单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都
有自己特定的适用范围。
下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本
概念。
例 1 （投资决策问题）某企业有 n 个项目可供选择投资，并且至少要对其中一个
项目投资。已知该企业拥有总资金 A 元，投资于第 i(i 1,L, n) 个项目需花资金 ai 元，
并预计可收益 bi 元。试选择最佳投资方案。
解 设投资决策变量为
1, 决定投资第i个项目
x ， i 1,L, n ，
0 ， 决定不投资第i个项目 n n
则投资总额为 ai xi ，投资总收益为 bi xi 。因为该公司至少要对一个项目投资，并
i 1 i 1
且总的投资金额不能超过总资金 A ，故有限制条件
n
0 ai xi A
i 1
另外，由于 xi (i 1,L, n) 只取值 0 或 1，所以还有
xi (1 xi ) 0, i 1,L, n.
最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归
结为总资金以及决策变量（取 0 或 1）的限制条件下，极大化总收益和总投资之比。因
此，其数学模型为：
n bi xi
max Q i 1 n ai xi
i 1
n
s.t. 0 ai xi A
i 1
xi (1 xi ) 0, i 1,L, n.
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问
题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式
