线性规划和非线性规划是什么？
文章目录
- 线性规划和非线性规划
- 基本概念
- 优化问题
- 数学公式与概念扩充 (Mathematical Formulas and Concept Expansion)
- **1. 无约束优化 (Unconstrained Optimization)**
- **2. 约束优化 (Constrained Optimization)**
- **3. 对偶理论简介 (Introduction to Duality Theory)**
线性规划和非线性规划
基本概念
If both the objective function and the constraint functions are linear, the problem is a linear programming problem; otherwise, it is a nonlinear programming problem. All points that satisfy the constraints are called feasible points, and they constitute a feasible set. If the feasible set of a problem fills the entire space, we call it an unconstrained programming problem.
如果目标函数和约束函数都是线性的，那么该问题是一个线性规划问题；否则，它是一个非线性规划问题。所有满足约束条件的点称为可行点，它们构成可行集。如果一个问题的可行集填满了整个空间，我们称其为无约束规划问题。
-
线性规划问题（Linear Programming, LP）：
minimize c T x subject to A x ≤ b , x ≥ 0 egin{aligned} & ext{minimize} quad c^T x & ext{subject to} quad A x leq b, & quad quad quad quad x geq 0 end{aligned} minimizecTxsubject toAx≤b,x≥0
其中：- c , x ∈ R n c, x in mathbb{R}^n c,x∈Rn，
- A ∈ R m × n A in mathbb{R}^{m imes n} A∈Rm×n，
- b ∈ R m b in mathbb{R}^m b∈Rm。
-
非线性规划问题（Nonlinear Programming, NLP）：
minimize f ( x ) subject to g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p egin{aligned} & ext{minimize} quad f(x) & ext{subject to} quad g_i(x) leq 0, quad i = 1, dots, m & quad quad quad quad h_j(x) = 0, quad j = 1, dots, p end{aligned} minimizef(x)subject togi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p
其中 f , g i , h j f, g_i, h_j f,gi,hj 中至少有一个是非线性的。 -
可行集（Feasible Set）：
F = { x ∈ R n ∣ g i ( x ) ≤ 0 , h j ( x ) = 0 } mathcal{F} = { x in mathbb{R}^n mid g_i(x) leq 0, ; h_j(x) = 0 } F={x∈Rn∣gi(x)≤0,hj(x)=0} -
无约束规划问题（Unconstrained Programming）：
minimize f ( x ) , x ∈ R n ext{minimize} quad f(x), quad x in mathbb{R}^n minimizef(x),x∈Rn
此时可行集 F = R n mathcal{F} = mathbb{R}^n F=Rn。
优化问题
The optimization problem can be divided into two categories: constrained optimization and unconstrained optimization. The fundamental concept in optimization theory is the extremum of a function, namely min f ( x ) min f(x) minf(x), where x ∈ R n x in mathbb{R}^n x∈Rn is called the decision variable, and f ( x ) ∈ R f(x) in mathbb{R} f(x)∈R is called the objective function. The point x ∗ x^* x∗, which makes f ( x ) f(x) f(x) attain the extremum, is called the optimal solution. If the problem must satisfy certain constraints, it becomes a constrained optimization problem.
优化问题可分为两类：约束优化和无约束优化。优化理论的核心是函数的极值问题，即 min f ( x ) min f(x) minf(x)。其中 x ∈ R n x in mathbb{R}^n x∈Rn 称为决策变量， f ( x ) ∈ R f(x) in mathbb{R} f(x)∈R 称为目标函数。使 f ( x ) f(x) f(x) 达到极值的点 x ∗ x^* x∗ 称为最优解。如果问题必须满足某些约束条件，则成为约束优化问题。
数学公式与概念扩充 (Mathematical Formulas and Concept Expansion)
以下将分别阐述两类问题的标准数学形式及其关键原理。
1. 无约束优化 (Unconstrained Optimization)
数学形式 (Mathematical Form):
min
x
∈
R
n
f
(
x
)
min_{x in mathbb{R}^n} f(x)
x∈Rnminf(x)
其中
f
:
R
n
→
R
f: mathbb{R}^n o mathbb{R}
f:Rn→R 是一个可微 (differentiable) 的目标函数。
一阶必要条件 (First-Order Necessary Condition):
如果
x
∗
x^*
x∗ 是一个局部极小点 (local minimizer) 且
f
f
f 在
x
∗
x^*
x∗ 处可微，则梯度必须为零：
∇
f
(
x
∗
)
=
0
abla f(x^*) = 0
∇f(x∗)=0
满足此式的点称为驻点 (stationary point)。
二阶条件 (Second-Order Conditions):
- 二阶必要条件 (Necessary Condition): 若
x
∗
x^*
x∗ 是局部极小点，则其 Hessian 矩阵 (Hessian matrix) 是半正定的：
∇ 2 f ( x ∗ ) ⪰ 0 abla^2 f(x^*) succeq 0 ∇2f(x∗)⪰0 - 二阶充分条件 (Sufficient Condition): 如果
∇
f
(
x
∗
)
=
0
abla f(x^*) = 0
∇f(x∗)=0 且 Hessian 矩阵是正定的，则
x
∗
x^*
x∗ 是一个严格的局部极小点：
∇ 2 f ( x ∗ ) ≻ 0 abla^2 f(x^*) succ 0 ∇2f(x∗)≻0
关键算法 (Key Algorithms):
- 梯度下降法 (Gradient Descent): 沿负梯度方向迭代更新。
x k + 1 = x k − α k ∇ f ( x k ) x_{k+1} = x_k - lpha_k abla f(x_k) xk+1=xk−αk∇f(xk) - 牛顿法 (Newton’s Method): 利用梯度和 Hessian 矩阵信息进行二阶更新。
x k + 1 = x k − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) x_{k+1} = x_k - [ abla^2 f(x_k)]^{-1} abla f(x_k) xk+1=xk−[∇2f(xk)]−1∇f(xk)
2. 约束优化 (Constrained Optimization)
一般数学形式 (General Mathematical Form):
min
x
∈
R
n
f
(
x
)
s.t.
g
i
(
x
)
≤
0
,
i
=
1
,
…
,
m
(不等式约束)
h
j
(
x
)
=
0
,
j
=
1
,
…
,
p
(等式约束)
egin{aligned} min_{x in mathbb{R}^n} &quad f(x) ext{s.t.} &quad g_i(x) leq 0, quad i = 1, dots, m quad ext{(不等式约束)} &quad h_j(x) = 0, quad j = 1, dots, p quad ext{(等式约束)} end{aligned}
x∈Rnmins.t.f(x)gi(x)≤0,i=1,…,m(不等式约束)hj(x)=0,j=1,…,p(等式约束)
其中 s.t. 是 “subject to”（受限于）的缩写。满足所有约束的
x
x
x 的集合称为可行域 (feasible set)。
拉格朗日函数 (Lagrangian Function):
为求解此问题，引入拉格朗日乘子
λ
i
(
≥
0
)
lambda_i (geq 0)
λi (≥0) 和
ν
j
u_j
νj，构造拉格朗日函数：
L
(
x
,
λ
,
ν
)
=
f
(
x
)
+
∑
i
=
1
m
λ
i
g
i
(
x
)
+
∑
j
=
1
p
ν
j
h
j
(
x
)
mathcal{L}(x, lambda,
u) = f(x) + sum_{i=1}^m lambda_i g_i(x) + sum_{j=1}^p
u_j h_j(x)
L(x,λ,ν)=f(x)+i=1∑mλigi(x)+j=1∑pνjhj(x)
KKT 条件 (Karush-Kuhn-Tucker Conditions):
对于可微函数，若
x
∗
x^*
x∗ 是一个局部最优解，并且在
x
∗
x^*
x∗ 处满足一定的约束规范性条件 (constraint qualification)，则存在乘子
λ
∗
lambda^*
λ∗,
ν
∗
u^*
ν∗ 使得以下 KKT 条件 成立：
∇
x
L
(
x
∗
,
λ
∗
,
ν
∗
)
=
0
(平稳性/Stationarity)
g
i
(
x
∗
)
≤
0
,
h
j
(
x
∗
)
=
0
(原始可行性/Primal Feasibility)
λ
i
∗
≥
0
(对偶可行性/Dual Feasibility)
λ
i
∗
g
i
(
x
∗
)
=
0
(互补松弛性/Complementary Slackness)
egin{aligned} &
abla_x mathcal{L}(x^*, lambda^*,
u^*) = 0 quad & ext{(平稳性/Stationarity)} &g_i(x^*) leq 0, quad h_j(x^*) = 0 quad & ext{(原始可行性/Primal Feasibility)} &lambda_i^* geq 0 quad & ext{(对偶可行性/Dual Feasibility)} &lambda_i^* g_i(x^*) = 0 quad & ext{(互补松弛性/Complementary Slackness)} end{aligned}
∇xL(x∗,λ∗,ν∗)=0gi(x∗)≤0,hj(x∗)=0λi∗≥0λi∗gi(x∗)=0(平稳性/Stationarity)(原始可行性/Primal Feasibility)(对偶可行性/Dual Feasibility)(互补松弛性/Complementary Slackness)
对于凸优化问题，KKT条件通常是充分必要条件 (necessary and sufficient conditions)。
线性规划 (Linear Programming) 特例: 当目标函数和所有约束均为线性时：
min
x
c
T
x
s.t.
A
x
≤
b
x
≥
0
egin{aligned} min_{x} &quad c^T x ext{s.t.} &quad A x leq b &quad x geq 0 end{aligned}
xmins.t.cTxAx≤bx≥0
3. 对偶理论简介 (Introduction to Duality Theory)
每一个优化问题（原问题 / Primal Problem）都有一个相伴的对偶问题 (Dual Problem)。
拉格朗日对偶函数 (Lagrangian Dual Function):
d
(
λ
,
ν
)
=
inf
x
∈
R
n
L
(
x
,
λ
,
ν
)
d(lambda,
u) = inf_{x in mathbb{R}^n} mathcal{L}(x, lambda,
u)
d(λ,ν)=x∈RninfL(x,λ,ν)
这个函数给出了原问题最优值
p
∗
p^*
p∗ 的一个下界 (lower bound)。
对偶问题 (Dual Problem):
max
λ
,
ν
d
(
λ
,
ν
)
s.t.
λ
≥
0
egin{aligned} max_{lambda,
u} &quad d(lambda,
u) ext{s.t.} &quad lambda geq 0 end{aligned}
λ,νmaxs.t.d(λ,ν)λ≥0
其对偶最优值记为
d
∗
d^*
d∗。
弱对偶与强对偶 (Weak and Strong Duality):
- 弱对偶 (Weak Duality): 总是成立， d ∗ ≤ p ∗ d^* leq p^* d∗≤p∗。
- 强对偶 (Strong Duality): 若 d ∗ = p ∗ d^* = p^* d∗=p∗，则强对偶成立。对于凸优化问题且在满足 Slater 条件 (存在严格可行内点) 时，通常成立强对偶。此时，原问题与对偶问题的最优值相等。
