尋求具有約束條件的線性或非線性規劃問題解的數值演算法。假設f(x)，gi(x)(i=1，2，…，m)是n維歐幾裏得空間<Rn中的實值函數。所謂約束優化問題，是指在約束條件gi(x)≤0(i=1，2，…，m)之下求一點
，使
f(
x)≥
f(
)，點
稱為最優解。約束優化問題當
f(
x)、
g
i(
x)(
i=1，2，…，
m)均為凸函數時稱為凸規劃。凸函數有很多已知特性，因此凸規劃算法的研究進展較快。線性規劃是凸規劃的最簡單的情形，可以用單純形方法等求解。約束優化問題當
f(
x)是二次函數而
g
i(
x)(
i=1，2，…，
m)是線性函數時稱為二次規劃。G.B.丹齊克和P.沃爾夫於1963年將單純形方法作瞭修改，用以求解凸二次規劃，得到隻經過有限次迭代即可達到最優解的算法。
對於隻有等式約束的非線性規劃，經典的拉格朗日乘子法指出，在對函數加以一定限制下，最優解可在一組函數方程的解集中去尋求，但是並未指出行之有效的算法。1951年，H.W.庫恩和A.W.塔克爾發表“論非線性規劃”一文後，隨著計算技術的迅速發展，線性約束的非線性規劃出現瞭不少行之有效的算法。在非線性約束規劃的研究上，近十幾年來也有相當的進展。
可行方向法 根據逐次沿可行方向求可行解點的迭代思想構造一點列{xk}，使其滿足某種給定要求的算法稱為可行方向法。假設已知可行解為x(k)，若能找到一個向量
與步長數
λ
k＞0，使
，而當0≤
λ≤
λ
k時，線段
x
(k)+
λ
屬於約束集，則
稱為約束集在
x
(k)處的一個可行方向。可行方向法的關鍵在於適當選取
，點列{
x
(k)}符合一般迭代法的要求。對線性約束的情形，當
f(
x)為可微凸函數時有三種較為有效的求
的算法：G.藻滕代克於1960年提出的可行方向法，取
＝
y
(k)-
x
(k)，其中
y
(k)為
f(
x)在
x
(k)處的線性近似函數
在線性約束下達到最小值的最優解。J.B.羅森於1960年提出的梯度投影法，運用在
x
(k)處投影矩陣
p
k的公式，取最速下降方向－▽
f(
x
(k))在
x
(k)所處的約束邊界面上的投影方向－
p
k▽
f(
x
(k))為
，從而避免瞭每迭代一次就要解一個線性規劃的手續。P.沃爾夫於1963年提出的既約梯度法，他應用消去基變量的方法和
f(
x)的既約梯度的概念，構造出
。這三種方法所產生的點列{
x
(k)}雖然可以使函數值序列{
f(
x
(k)}單調下降，但是它卻不一定收斂於最優解。因此，後來陸續有不少研究工作，對原有方法進行種種修正，如采取攝動和轉軸變換等技巧，而得出具有收斂性的各種新方法。1969年D.戈德福佈結合梯度投影法與變尺度法提出瞭一種可行方向法，對二次凸規劃是有限步收斂的。這些方法都可以推廣用於處理非線性約束的情形。但是，算法程序都比較復雜。J.阿巴迪和J.卡彭特爾於1969年將既約梯度法加以推廣，提出瞭廣義既約梯度法(GRG法)用來求解具有非線性約束的最優化問題。實際計算的效果說明，廣義既約梯度法是一種很好的算法。
上述線性近似型算法的收斂速度，一般都不高於超線性的。對二階可微的函數f(x)，在x(k)處若用二次函數
·
來近似，進而對可微函數
f(
x)又用種種變尺度矩陣
H
k去代替近似式中的矩陣▽
2
f（
x
(k)），將約束問題的求解化為求一系列二次規劃的解，這類方法統稱為序貫二次規劃法，1963年R.B.威爾森對二階可微函數
f(
x)，
g
i(
x)(
i=1，2，…，
m)提出將拉格朗日函數
在已知點（
x
(k)，
u
(k)）處用二次近似函數來逼近，而對約束仍用線性近似函數逼近，並證明瞭在最優解附近，點列{
x
(k)}是二階收斂的。若用二次函數
在
x
(k)處逼近目標函數
f(
x)，其中
H
k是正定函數，同時象無約束最優化方法中的變尺度算法一樣，利用計算過程中得到的信息和變尺度公式來更新
H
k，這種逐次二次規劃算法也稱為約束變尺度算法。它是求解帶非線性約束的最優化問題的重要方法之一。
序貫無約束極小化法 1943年R.庫朗對於僅帶一個約束等式g(x)=0的問題，引入參數t＞0，研究函數f(x)＋t[g(x)]2的平穩點x(t)在t→∞時與原問題的關系。對於具有不等式約束gi(x)≤0(i=1，2，…，m)的非線性規劃問題，則作函數
；
如果將
f(
x)看成“價格”，約束看成某種“規定”，則
為當
x違反“規定”時的罰款項，於是
p(
x，
t)就是應支付的總代價。因此，
p(
x，
t)被稱為罰函數，而
t稱為罰因子。在適當的假設下，
p(
x，
t)在對
x不加約束的情形下的最優解
x(
t)，當
t→∞時趨於原問題的最優解。這種方法稱為罰函數法。由此就可以用逐漸加大
t
k的方法來求得原問題近似解
x(
t
k)。為瞭克服
p(
x，
t)的黑塞矩陣在
t→∞時容易產生病態的缺點，W.I.贊格威爾於1967年提出精確罰函數
E(
x，
t)，證明瞭在適當的假設下，存在
t
0＞0，當
t≥
t
0時
E(
x，
t)的無約束最優解
x(
t)就是原問題的最優解。於是把有約束的最優化問題化為一個無約束的最優化問題。但是這種精確罰函數不是可微的，因而不便於利用一般無約束優化方法。M.R.赫斯泰尼斯和M.J.D.鮑威爾結合拉格朗日乘子法和罰函數法的特點，於1969年對約束為等式的情形提出可微的增廣拉格朗日函數
，並指出在適當的假設下，存在
t
0＞0，對任意取定的
t≥
t
0，在最優乘子
處，
L(
x，
，
t)的無約束最優解
必為原問題的最優解，還給出瞭逐步調整
u和
t的辦法。以後陸續有不少工作對一般可微非線性規劃，構造瞭各種不同的可微增廣拉格朗日函數，並給出瞭算法的迭代程序。這類方法統稱為廣義乘子法。K.R.弗裡希鑒於罰函數法產生的點列 {
x(
t
k)}是從約束集的外部來逼近在約束邊界上的最優解，於1955年提出所謂障礙函數
，可使
B(
x，
r)的無約束最優解
x(
r)在約束集內達到，而當
r→0時，
x(
r)趨於原問題的最優解。1961年，C.W.卡羅爾提出瞭另一種典型的障礙函數
。當
r→0時，
B(
x，
r)的黑塞矩陣也可能出現病態現象。
對兼有等式和不等式約束的最優化問題，可結合使用罰函數與障礙函數而構造出混合型函數來求解；對兼有線性和非線性約束的最優化問題，可僅將非線性約束納入p(x，t)（或B(x，r)，或L(x，u，t)），將問題化為在線性約束下p(x，t)（或B(x，r)，或L(x，u，t)）的極小化問題。
對於不可微的凸規劃，近十多年來有人用次梯度或差分等概念來建立算法。設f為Rn中的凸函數，若矢量
滿足
，則矢量
稱為函數
f在點
x
0處的一個次梯度。不可微凸規劃的最優解在一定條件下滿足以次梯度表示的推廣的庫恩－塔克爾條件(見
非線性規劃)。函數在一點的次梯度不一定是惟一的。可微函數在一點的梯度若不為零，其負梯度方向必是函數在此點的一個下降方向。然而不可微函數在一點的某些負次梯度可以不是函數的下降方向。這將導致上述可微情況的約束優化算法對於不可微凸規劃往往會失敗。不可微凸規劃的次梯度算法類的基本迭代公式是
，這裡
t
k和
(k)分別是按一定規則選定的步長和點
x
(k)的次梯度(或近似次梯度)。在一些適當的條件下可證明，次梯度算法產生的點列{
x
(k)}收斂到問題的最優解。
贊格威爾1969年提出用統一的觀點研究算法。他的基本思想是，將算法看成是一個點到集的映像。在一些假設下由上半連續的點到集映像產生的點列 {x(k)}收斂於最優解。從而統一瞭不少已有算法的收斂性的研究。這方面的工作還在不斷發展。
參考書目
M.阿弗裡爾著，李元熹等譯：《非線性規劃-分析與方法》，上冊，上海科學技術出版社，上海，1979。(M.Avriel，Nonlinear Programming-Analysis and Method，Prentice-hall，Englewood Cliffs，New Jersey，1976.)
A.V.Fiacco and G.P.McCormick，Nonlinear Pro-gramming Sequential Unconstrained Minimization Techiques，John Wiley &Sons，New York，1968.