无约束坐标下降法
坐标下降法即在目标函数每一次迭代沿着一个坐标分量方向最小化。这不仅简化了搜索方向的计算，而且经常使得步长选择变得容易，因为沿着分量方向的线性最小化相对容易求得。在这个算法中，坐标的顺序是变化的。由下图所示，给定
x
k
,
x
k
+
1
x^k,x^{k+1}
xk,xk+1的第
i
i
i个分量由下式给出
x
i
k
+
1
∈
arg
min
ξ
∈
ℜ
f
(
x
1
k
+
1
,
⋯
,
x
i
−
1
k
+
1
,
ξ
,
x
i
+
1
k
,
⋯
,
x
n
k
)
x_i^{k+1}\in \arg \min_{\xi \in \Re} f(x_1^{k+1},\cdots,x_{i-1}^{k+1},\xi,x_{i+1}^{k},\cdots,x_n^k)
xik+1∈argξ∈ℜminf(x1k+1,⋯,xi−1k+1,ξ,xi+1k,⋯,xnk)这个方法也可以用于变量
x
i
x^i
xi有上下界的
f
f
f的最小化（上式中的
ξ
∈
ℜ
\xi \in \Re
ξ∈ℜ改为合适的区间即可）。
坐标下降法的一个重要优势是它很合适用于并行计算，假设存在分量
x
i
1
,
x
i
2
,
⋯
,
x
i
m
x_{i_1},x_{i_2},\cdots,x_{i_m}
xi1,xi2,⋯,xim的子集，这个分量子集与目标函数是非耦合的，即
f
(
x
)
f(x)
f(x)能表达为
∑
r
=
1
m
f
i
r
(
x
)
\sum\limits_{r=1}^{m}f_{i_r}(x)
r=1∑mfir(x)，对于每一个
r
r
r，
f
i
r
(
x
)
f_{i_r}(x)
fir(x)的取值与所有
s
≠
r
s\ne r
s=r的
x
i
s
x_{i_s}
xis无关，此时可以实现
m
m
m个分量的下降迭代
x
i
r
k
+
1
∈
arg
min
ξ
f
i
r
(
x
k
+
ξ
e
i
r
)
,
r
=
1
,
⋯
,
m
x_{i_r}^{k+1} \in \arg\min\limits_{\xi} f_{i_r}(x^k+\xi e_{i_r}),\quad r=1,\cdots,m
xirk+1∈argξminfir(xk+ξeir),r=1,⋯,m独立并行。
坐标块下降法
上一节简单的讨论了无约束优化问题的坐标下降方法，这一节讨论的是有约束的坐标下降法即坐标块下降法，求解如下问题
m
i
n
f
(
x
)
s
.
t
.
x
∈
X
\begin{array}{ll}\mathrm{min}&f(x)\\ \mathrm{s.t.}& x \in X\end{array}
mins.t.f(x)x∈X其中
X
X
X是闭凸集
X
1
,
⋯
,
X
m
X_1,\cdots,X_m
X1,⋯,Xm的笛卡尔积
X
=
X
1
×
X
2
×
⋯
×
X
m
X=X_1 \times X_2 \times \cdots \times X_m
X=X1×X2×⋯×Xm假设
X
i
X_i
Xi是
ℜ
n
i
\Re^{n_i}
ℜni的闭凸子集，并且
n
=
n
1
+
⋯
+
n
m
n=n_1+\cdots+n_m
n=n1+⋯+nm，将向量
x
x
x分块为
x
=
(
x
1
,
x
2
,
⋯
,
x
m
)
x=(x_1,x_2,\cdots,x_m)
x=(x1,x2,⋯,xm)其中分块向量
x
i
x_i
xi属于
ℜ
n
i
\Re^{n_i}
ℜni，所以约束
x
∈
X
x\in X
x∈X等价于
x
i
∈
X
i
,
i
=
1
,
⋯
,
m
.
x_i \in X_i, \quad i=1,\cdots,m.
xi∈Xi,i=1,⋯,m.
假设对每一个
x
∈
X
x \in X
x∈X及每一个
i
=
1
,
⋯
,
m
i=1,\cdots,m
i=1,⋯,m，约束优化问题
m
i
n
f
(
x
1
,
⋯
,
x
i
−
1
,
ξ
,
x
i
+
1
,
⋯
,
x
m
)
s
.
t
.
ξ
∈
X
i
\begin{array}{ll}\mathrm{min}&f(x_1,\cdots,x_{i-1},\xi,x_{i+1},\cdots,x_m)\\\mathrm{s.t.} & \xi\in X_i\end{array}
mins.t.f(x1,⋯,xi−1,ξ,xi+1,⋯,xm)ξ∈Xi至少存在一个最优解，可以在给定当前迭代
x
k
=
(
x
1
k
,
⋯
,
x
m
k
)
x^k = (x_1^k,\cdots,x_m^k)
xk=(x1k,⋯,xmk)的条件下，产生新的迭代
x
k
+
1
=
(
x
1
k
+
1
,
⋯
,
x
m
k
+
1
)
x^{k+1}=(x_1^{k+1},\cdots,x_{m}^{k+1})
xk+1=(x1k+1,⋯,xmk+1)，其中迭代关系为
x
i
k
+
1
∈
arg
min
ξ
∈
X
i
f
(
x
i
k
+
1
,
⋯
,
x
i
−
1
k
+
1
,
ξ
,
x
i
+
1
k
,
⋯
,
x
m
k
)
,
i
=
1
,
⋯
,
m
x_i^{k+1}\in \arg \min\limits_{\xi \in X_i}f(x_i^{k+1},\cdots,x_{i-1}^{k+1},\xi,x_{i+1}^k,\cdots,x_m^k),\quad i=1,\cdots,m
xik+1∈argξ∈Ximinf(xik+1,⋯,xi−1k+1,ξ,xi+1k,⋯,xmk),i=1,⋯,m因此，每一次迭代中，算法将按次序分别在每个“坐标块”向量
x
i
k
x^k_i
xik对目标函数进行优化，然后循环进行。
命题（坐标块下降法的收敛性）：假设 f f f在 X X X上连续可微，并且进一步假设对每一个 x = ( x 1 , ⋯ , x m ) ∈ X x=(x_1,\cdots,x_m)\in X x=(x1,⋯,xm)∈X及 i i i，如果将 f ( x 1 , ⋯ , x i − 1 , ξ , x i + 1 , ⋯ , x m ) f(x_1,\cdots,x_{i-1},\xi,x_{i+1},\cdots,x_m) f(x1,⋯,xi−1,ξ,xi+1,⋯,xm)看作 ξ \xi ξ的函数，在 X i X_i Xi上有唯一极小值点 ξ ˉ \bar{\xi} ξˉ，并且在从 x i x_i xi到 ξ ˉ \bar{\xi} ξˉ的区间上该函数是单调非增的。设 { x k } \{x^k\} {xk}是坐标块下降方法产生的序列，那么 { x k } \{x^k\} {xk}的每一个极限点都是驻点。
优化问题的分层分解
考虑优化问题
m
i
n
∑
i
=
1
m
f
i
(
x
,
y
i
)
s
.
t
.
x
∈
X
,
y
i
∈
Y
i
,
i
=
1
,
⋯
,
m
\begin{array}{ll}\mathrm{min}&\sum\limits_{i=1}^mf_i(x,y_i)\\\mathrm{s.t.}&x\in X,y_i\in Y_i,i=1,\cdots,m\end{array}
mins.t.i=1∑mfi(x,yi)x∈X,yi∈Yi,i=1,⋯,m其中
X
X
X和
Y
i
,
i
=
1
,
⋯
,
m
Y_i,i=1,\cdots,m
Yi,i=1,⋯,m，是给定欧式空间的闭凸子集，函数
f
i
f_i
fi为连续可微函数。这是一个包含
m
m
m个子系统的优化问题，其中
f
i
f_i
fi为第
i
i
i个子系统的目标函数。
y
i
y_i
yi是只对第
i
i
i个子系统的目标函数产生影响的局部决策变量，而
x
x
x是影响整个系统的全局决策变量。
利用该问题可分解的结构特点，坐标下降方法具有下面的形式
y
i
k
+
1
∈
arg
min
y
i
∈
Y
i
f
i
(
x
k
,
y
i
)
,
i
=
1
,
⋯
,
m
x
k
+
1
∈
arg
min
x
∈
X
∑
i
=
1
m
f
i
(
x
,
y
i
k
+
1
)
\begin{aligned}&y_i^{k+1}\in \arg\min\limits_{y_i \in Y_i} f_i(x^k,y_i),\quad i=1,\cdots,m\\&x^{k+1}\in \arg\min\limits_{x \in X}\sum\limits_{i=1}^mf_i(x,y_i^{k+1})\end{aligned}
yik+1∈argyi∈Yiminfi(xk,yi),i=1,⋯,mxk+1∈argx∈Xmini=1∑mfi(x,yik+1)该方法的直接解释是：在每一次迭代中，首先在给定全局变量值的情况下，每个子系统都进行内部优化，然后给定局部变量值，再进行全局优化。