最优点为交点与切点的优化搜索例[]

3.3　约束优化问题的最优搜索

设目标函数Y⑷=f（X），函数值变化规律仍如图4-3实线，与两处虚线部分无关，但有如图右侧区间x6—x9的约束域（阴影部分）。该函数无约束时的全局最优值为图中Y * ，约束后Y * 已处约束域，全局最优值只能是Y6（见该图）。设变量仍分3点和搜最小。

首轮搜中变量区间为x1—x9，取x1﹑x5﹑x9﹑三点搜，x9落入约束域，按前述规定，无Y9值，当轮只对搜得的Y1﹑Y5比较取优，最优为（Y5，x5）；区间调整中因不计约束域的存在，仍按x1—x9范围计，Y5对应的优点x5居中，以其为准，将变量区间由两端向内收缩各半个步长(λ/2)。调整后所确定的下轮（第2轮）区间为x3—x7段，仍包含部分约束域。第2轮搜中，搜点为x3﹑x5﹑x7，其中x7落入约束域，无Y7值，只比较Y3﹑Y5，当轮最优仍为Y5，变量x5仍居中；下轮（第3轮）搜索区间为x4—x6段。再搜索将得函数值Y4﹑Y5﹑Y6，因Y6落入约束域（边界点），仍按Y5居中进行区间调整。以下做一般性搜索说明。由于函数在区间x4— x6内单调降低（左高右低），搜索中因x6处约束域，使函数最优点居中，当轮区间调整以x5为准由两端向内收缩，新的区间右端点将离开约束域边界；下轮再搜后，所得优点必居边（右），当轮区间调整中,区间将向右游移并使新区间右端点又落入约束域；再搜后的区间调整又将区间向内收缩，使新区间右端点又离开约束域边界…。实际搜索中，搜得优点将不断自左向右向x6“爬”近，每两轮搜索爬近当轮一个步长，直到满足ε要求。虽然从道理上说，只能取得接近Y6的值，不能等于Y6，因其为约束域边界点，实际因ε甚小，仔细搜索后所得最优结果必相当于Y6。

以上是约束域居变量区间右端情形，显然，若约束域居区间左端，其搜索历程应与此类似。

当约束域居变量区间两侧（含端点）可行域居中时，首轮分三点搜必取得区间中点函数值。若以后各轮也仅搜得该值，最后会确定该值为最优值；因区间不断向内缩小，搜索点会向可行域集中，若某轮搜到两个或三个函数值时，可按正常搜索比较取优。

若约束域处变量区间中部，包含端点在内的两个端点邻域为可行域，因每个可行域内皆有函数局优值，成多解问题，按多解问题处理即可。进而言之，当变量搜索区间因受多个约束被分成互相独立的多个可行域时，无论其可行域居区间何处，因每个可行域内皆有函数局优值，皆可按多解问题处理。

第二节　本法实施中一些搜索操作问题的说明

1.一般说明

搜索会否失误　无约束优化问题搜索，任意给定变量搜索组合，总有与之对应的函数值存在，无论目标函数如何畸形，只要多分点搜索，不会失误。下文例4-1即属此情形，可参看。有约束问题的多遍搜索，某一两遍可能会失误（下文有进一步说明），但大量搜索实践证明，即使约束十分复杂，失误率也不高，在多于5遍的不同分点方案搜索中，一般总可有两遍以上搜得相同解。 因“分点位置互异”，多遍搜索也不会得到相同的失误的解（这里的“失误”仅指解不精确，或搜得局优解，非指不能满足约束）。

本法适用的问题维数范围　变量分点数D越多，搜索越精细，但当n很大时，增加D会使C（R）极快增加，搜索时间增长甚快。通常，为适应搜索含更多变量的较大规模优化问题，多取较小D值。低维，例如2- 3维，即使取D =20，搜一遍也不足1分钟。用当前微机，本法约适于搜索十维以下优化问题，此空间已很大，应能满足用微机处理一般工程优化问题的需求。

常用的变量搜索分点方案　为判定解的正确性等要求，搜索需有两遍以上搜得相同解并解最优，故搜索须多遍进行。改变变量搜索分点数，使各遍取点位置互异，成功概率增加。建议通常搜索都应使用（D1，D2）=（3,3）、（4,3）、（4,4）、（1,4）几个方案，费时较少；若解不稳定，至少再增加一遍后轮分点为6以上的费时较多的精细搜索。此即推荐的本法搜索常用分点方案。

强调说明精细搜索方法　当问题经几遍搜索后发现结果波动较大，此时可能遇到了难搜索情形，如函数图形奇异﹑多解﹑变量搜索范围过大、约束过分苛刻等，此时应注意进行精细搜索。精细搜索包括改变变量分点方案﹑多分点搜索和不断手工缩小变量区间的多遍逼近搜索。

对一个具体问题，究竟搜索分点多到何种程度，可成为限制因素的只是占用机时的长短。建议以分点数逐渐增加的搜索为好，只要发现达到精度要求了——有两遍搜得函数值最优并前三位有效数字相同——就可停止搜索。

搜几遍后若发现各遍函数值波动较大，应注意观察搜索所给变量区间是否过大，一般缩小区间再搜应总能提高精度，或有高精度要求时，须采用不断缩小区间的逐遍搜索。具体操作中，一是既要缩小区间，又不主张一次缩小很多，例如可每遍舍弃3～5%，以改变变量取点位置为主，防止最优域丢失。既可每次改变区间两个端点的值，也可只改变一端的值。用不断缩小区间并结合多分点，只要不怕时间长，可将函数值搜索得很精确。

无解现象说明　当问题复杂，例约束很多又分点少时，首轮取得的变量分点组合C（R）中，可能每个组合皆含不落入可行域的变量搜点，首轮搜空。程序规定，此时按问题无解判定。可采用各种方法确保首轮搜到可行解。实践证明，即使仅用变量多分点一项措施，也总会使首轮搜到可行解，从而确保搜索成功。

2.约束优化问题只搜一遍可能失误的举例说明

约束区间过大可能造成失误　图4-5为搜最小的有唯一解优化问题，有分处区间两侧的很大约束域，分三点搜无搜点落入可行域，首轮搜空，为下轮作准备的区间调整无可靠依据。规定：凡首轮搜不到可行解者作无解问题处理。从图形看，本题首轮若分四点搜索可搜到可行域，可保搜索成功。