§ 4.3 可行方向法
作者：黃希勇 2013.5.28
引入： 對於非線性規劃問題，如果不存在約束，從任乙個初始點出發，沿的負梯度方向進行一維收索，便可求得目標函式的無約束極小值；而對有約束的極小化問題來說，除要使目標函式在每次迭代有所下降之外，還要注意解的可行性問題，為此，在求解約束非線性規劃迭代法的設計中，應在每個迭代點出構造乙個可行下降方向。
引入：有效約束和可行下降方向的概念
考慮非線性規劃
4.3.1）
其中，均為實值連續函式，且具有二階連續偏導數。
設是非線性規劃的乙個可行解。現考慮某一不等式約束條件
滿足它有兩種可能：其一為，這時，點不是處於由這一約束條件形成的可行域邊界上，因而這一約束對點的微小攝動不起限制作用，從而稱這個約束條件是點的不起作用約束(或無效約束)；其二是，這時點處於該約束條件形成的可行域邊界上，它對的攝動起到了某種限制作用，故稱這個約束是點的起作用約束(有效約束)。
顯而易見，等式約束對所有可行點來說都是起作用約束。
： 設可行域是非空集，，若對某非零向量，存在，使對任意均有,則稱為從出發的可行方向。
若非線性規劃的某一可行點，對該點的任一方向來說，若存在實數，使對任意
均有就稱方向為點的乙個下降方向。
如果方向既是點的可行方向，又是這個點的下降方向，就稱它是該點的可行下降方向。
eg 4.4: 略
現考慮非線性規劃（4.3.1）式，設是它的乙個可行解，但不是要求的極小點。為了求它的極小點或近似極小點，根據以前所說，應在點的可行下降方向中選取某一方向，並確定步長，使
4.3.2）
若滿足精度要求，迭代停止，就是所要的點。否則，從出發繼續進行迭代，直到滿足要求為止。上述方法稱為可行方向法；
其特點是：迭代過程中採用的搜尋方向為可行方向，所產生的迭代點列｛x(k)｝始終在可行域內，目標函式值單調下降。
下面介紹zoutendijk可行方向法
簡介● zoutendijk可行方向法是zoutendijk於2023年提出的.
● zoutendijk可行方向法中選擇搜尋方向包括:起作用（有效）約束構造可行方向和ε起作用約束構造可行方向.
● zoutendijk可行方向法可以求解線性約束優化問題和非線性約束優化問題.
考慮線性約束問題
4.3.3）
其中可微，，
怎樣選擇下降可行方向？
由於問題（4.3.3）中約束是線性的，是非線性的，在附近考察，
我們用在處的一階多項式代替。
設滿足，其中,，令，於是（4.3.3）轉化為下述線性規劃：
由於為常數且，故上述線性規劃等價於
4.3.4）
因為為（4.3.4）的可行點，其對應的目標函式值為0，即為（4.3.4）的最優解，則：
（1）若，為原問題（4.3.3）在處的下降可行方向；
（2）若，為（4.3.3）的點；
證明（2）：見課本p79
現在來確定一維搜尋的步長？
設是（4.3.3）的可行解，不妨設第次迭代的出發點為處乙個下降可行方向後繼點由下列迭代公式給出：
為確定，取值遵循下列原則：
（1）保持迭代的可行性；
（2）使目標函式值盡可能減小；
根據上述原則,可以通過求解下列一維搜尋問題來確定步長，這裡不再贅述，我們只要知道怎麼計算就可以了。
綜上得可行方向法的步驟為：
（1）確定允許誤差，任選可行點作初始點，令；
（2）根據的有效約束把分解為,相應的把分解為，使得；
（3）求解線性規劃
設最優解為，式中為向量的分量，限制是為使該線性規劃有有限最優解；
（4）若，則為所求最優點，停止，否則轉（5）；
（5）若，則由一維線收索得，令轉（2），否則轉（6）；
（6）設，計算
由確定，令轉（2）；
例：見課本p80
第四章線性規劃
在企業的經營管理中，常常遇到如何在現有條件下，獲得最大經濟效益的諸多方面的具體問題，如如何磁品產量和質量的要求下，合理配置裝置，合理儲存備件，合理制定生產計畫，以及合理運輸 下料，正確決策 等等一系列優化生產組織與計畫管理的問題。被廣泛用來解決這類優化問題的重要工具之一就是線性規劃。由於它具有廣泛適...
第四章對偶線性規劃問題
1.略2.用對偶單純形方法解1.1 解 把問題標準化 即 1 作對應於對偶可行基的單純形表 2 因表中基變數值有負數，而且 2對應的行都有負數，所以要進行換基迭代。3 換基迭代 求軸心項 以基變數中 2對應的行中所有負數去除檢驗數，其中最小的商1所對應的除數 1就是軸心項。進行換基迭代得新基 因為表...
第4章非線性規劃張
第四章非線性規劃模型 第一節非線性規劃的例項與基本概念 一 非線性規劃的例項 例1 化學反應的平衡組成 設現有原料由種原子組成，各種原子數量依次為共生成種分子 產品 設生產數量 待求 依次為。設第種分子中含各種原子的數量依次為 所有產品中含第種原子數之和為 由熟知的質量守恆定律有 在一定的溫度 壓力...