文章目录
- 线性规划和非线性规划
-
- 基本概念
- 优化问题
- 数学公式与概念扩充 (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
\\begin{aligned} & \\text{minimize} \\quad c^T x \\\\ & \\text{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 \\times 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
\\begin{aligned} & \\text{minimize} \\quad f(x) \\\\ & \\text{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
\\text{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 \\to \\mathbb{R}
f:Rn→R 是一个可微 (differentiable) 的目标函数。
一阶必要条件 (First-Order Necessary Condition): 如果
x
∗
x^*
x∗ 是一个局部极小点 (local minimizer) 且
f
f
f 在
x
∗
x^*
x∗ 处可微，则梯度必须为零：
∇
f
(
x
∗
)
=
0
\\nabla f(x^*) = 0
∇f(x∗)=0 满足此式的点称为驻点 (stationary point)。
二阶条件 (Second-Order Conditions):
- 二阶必要条件 (Necessary Condition): 若
x
∗
x^*
x∗ 是局部极小点，则其 Hessian 矩阵 (Hessian matrix) 是半正定的：∇
2
f
(
x
∗
)
⪰
0
\\nabla^2 f(x^*) \\succeq 0
∇2f(x∗)⪰0 - 二阶充分条件 (Sufficient Condition): 如果
∇
f
(
x
∗
)
=
0
\\nabla f(x^*) = 0
∇f(x∗)=0 且 Hessian 矩阵是正定的，则x
∗
x^*
x∗ 是一个严格的局部极小点：∇
2
f
(
x
∗
)
≻
0
\\nabla^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 – \\alpha_k \\nabla 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 – [\\nabla^2 f(x_k)]^{-1} \\nabla 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
(等式约束)
\\begin{aligned} \\min_{x \\in \\mathbb{R}^n} &\\quad f(x) \\\\ \\text{s.t.} &\\quad g_i(x) \\leq 0, \\quad i = 1, \\dots, m \\quad \\text{(不等式约束)} \\\\ &\\quad h_j(x) = 0, \\quad j = 1, \\dots, p \\quad \\text{(等式约束)} \\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
\\nu_j
νj，构造拉格朗日函数：
L
(
x
,
λ
,
ν
)
=
f
(
x
)
+
∑
i
=
1
m
λ
i
g
i
(
x
)
+
∑
j
=
1
p
ν
j
h
j
(
x
)
\\mathcal{L}(x, \\lambda, \\nu) = f(x) + \\sum_{i=1}^m \\lambda_i g_i(x) + \\sum_{j=1}^p \\nu_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^*
λ∗,
ν
∗
\\nu^*
ν∗ 使得以下 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)
\\begin{aligned} &\\nabla_x \\mathcal{L}(x^*, \\lambda^*, \\nu^*) = 0 \\quad &\\text{(平稳性/Stationarity)} \\\\ &g_i(x^*) \\leq 0, \\quad h_j(x^*) = 0 \\quad &\\text{(原始可行性/Primal Feasibility)} \\\\ &\\lambda_i^* \\geq 0 \\quad &\\text{(对偶可行性/Dual Feasibility)} \\\\ &\\lambda_i^* g_i(x^*) = 0 \\quad &\\text{(互补松弛性/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
\\begin{aligned} \\min_{x} &\\quad c^T x \\\\ \\text{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, \\nu) = \\inf_{x \\in \\mathbb{R}^n} \\mathcal{L}(x, \\lambda, \\nu)
d(λ,ν)=x∈RninfL(x,λ,ν) 这个函数给出了原问题最优值
p
∗
p^*
p∗ 的一个下界 (lower bound)。
对偶问题 (Dual Problem):
max
λ
,
ν
d
(
λ
,
ν
)
s.t.
λ
≥
0
\\begin{aligned} \\max_{\\lambda, \\nu} &\\quad d(\\lambda, \\nu) \\\\ \\text{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 条件 (存在严格可行内点) 时，通常成立强对偶。此时，原问题与对偶问题的最优值相等。
