文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

Linear Equations

发布于 2025-01-31 22:20:44 字数 17777 浏览 0 评论 0 收藏 0

Linear Equation

“线性方程式”。仅由变数的加法、变数的倍率组成的方程式。

1 x + 2 y - 5 z = 5

System of Linear Equations

“线性方程组”。许多道线性方程式同时成立。

{ 1 x + 2 y - 5 z = 5
{ 2 x + 4 y + 6 z = 1
{ 3 x + 1 y + 7 z = 4

线性方程组求解，等同矩阵求解。儘管标题是 Linear Equations，但是接下来要谈的都是矩阵求解。

{ 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
{ 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
{ 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                 A        x⃗       y⃗

求根、求不动点、求特徵点、求解是等价的，使得矩阵求解有著各式各样的演算法。

Linear Equations: Gaussian Elimination

Linear Equations 与等量公理

这裡预设大家已经相当熟悉线性方程组的计算手法：利用等量公理，由上往下把变数消光光，变成阶梯状；然后由下往上解出每个变数。还不太熟悉的读者，先回忆一下吧！这个计算手法就叫做“高斯消去法”。

演算法（Gaussian Elimination）

现在，以矩阵的相关术语，重新解释“高斯消去法”。

把一个矩阵，化成对角线元素皆为一的上三角矩阵。

按照字典顺序穷举一对一对的 row，每穷举出一对 row，就处理这两个 row──求出首项係数的倍率，以上方 row 消去下方 row，使下方 row 的首项係数变成零。

有一个特殊情况是，当上方 row 的首项係数是零的时候，就要考虑与下方 row 交换，让上方 row 的首项係数尽量不是零。

这个交换 row 的动作称作 pivoting，不为零的那一个首项係数称作 pivot，包含 pivot 的那一个 row 称作 pivot row。

高斯消去法的过程，以 row 的角度来看，只有三种 row 运算：倍率、相减、交换。但是实作时，我们通常不会特地写一个 row 的资料结构、定义这三种运算，因为程式结构太过複杂的话，程式执行时间也会变长。实作时，通常是自己慢慢数索引值，小心的从二维阵列中取得元素，逐步完成 row 运算。

时间複杂度是 O(N^2 * M)，N×M 为矩阵的大小。由于一般情况都是讨论方阵较多，N 与 M 相等，所以会把时间複杂度写成 O(N^3)。

下面提供方阵的高斯消去法程式码；至于一般矩阵的高斯消去法，就留给大家自行练习。

Linear Equations: Eigendecomposition

Linear Equations 与 Linear Transform

线性方程组可以写成矩阵乘法的形式。

{ 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
{ 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
{ 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                 A        x⃗       y⃗

线性方程组得视作线性变换（函数），解线性方程组得视作逆向线性变换（反函数）。

                                                 -1
[ 1 2 -5 ] [ x ]   [ 5 ]        [ x ]   [ 1 2 -5 ] [ 5 ]
[ 2 4  6 ] [ y ] = [ 1 ]  ===>  [ y ] = [ 2 4  6 ] [ 1 ]
[ 3 1  7 ] [ z ]   [ 4 ]        [ z ]   [ 3 1  7 ] [ 4 ]
    A        x⃗       y⃗           x⃗         A⁻¹      y⃗

一旦求得反矩阵，即可轻鬆解线性方程组。

solve Ax⃗ = y⃗  ===>  find A⁻¹, then x⃗ = A⁻¹y⃗

计算反矩阵，使用高斯乔登消去法，时间複杂度 O(N^3)。

不过与其採用高斯乔登消去法求反矩阵、再用反矩阵解线性方程组，不如直接採用高斯消去法解线性方程组。就当作是学个想法吧。

Eigendecomposition

线性变换的精髓：求得在特徵向量上的分量，分别伸缩，伸缩倍率是特徵值。逆向线性变换的精髓：逆向缩放，缩放倍率变成倒数。

             -1          T
A   = Q  Λ  Q   = Q  Λ  Q 

 -1       -1 -1       -1 T
A   = Q  Λ  Q   = Q  Λ  Q

矩阵实施特徵分解，求反矩阵，再拿来解线性方程组。

以特徵值来判断是否存在反矩阵。特徵值皆不为零，则有反矩阵。就这样子。

不过与其採用特徵分解求反矩阵、再用反矩阵解线性方程组，不如直接採用高斯消去法解线性方程组。就当作是学个想法吧。

Linear Equations: Cramer's Rule

Linear Equations 与 Geometry

线性方程式得视作几何元件：点、线、面、……。

ContourPlot3D[1 x + 2 y - 5 z == 5, {x, -5, 5}, {y, -5, 5}, {z, -5, 5}, Boxed -> False, Axes -> False, Mesh -> None]

线性方程组得视作一堆几何元件的交集。

f := 1 x + 2 y - 5 z - 5; g := 2 x + 4 y + 6 z - 1; h := 3 x + 1 y + 7 z - 4; ContourPlot3D[{f == 0, g == 0, h == 0}, {x, -5, 5}, {y, -5, 5}, {z, -5, 5}, Boxed -> False, Axes -> False, Mesh -> None, ContourStyle -> Directive[Opacity[0.5]]]

数学公式（Cramer's Rule）

两线交点的演算法：求得平行四边形的面积，以面积比例求得交点位置。请参考本站文件“ Intersection ”。

“克拉玛公式”则是此演算法的高维度版本，形成了非常漂亮的公式解！求得超平行体的容积，以容积比例求得解。

linear equations:
  Ax⃗ = y⃗

solution:
  { x = det(Aˣ) / det(A)
  { y = det(Aʸ) / det(A)
  { z = det(Aᶻ) / det(A)

unisolvance:
   Ax⃗ = y⃗ has a unique solution   iff   det(A) ≠ 0

example:
  { 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
  { 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
  { 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                   A        x⃗       y⃗
         _ y⃗                  _ y⃗                  _ y⃗
       [|5| 2 -5 ]       [ 1 |5|-5 ]       [ 1  2 |5|]
  Aˣ = [|1| 4  6 ]  Aʸ = [ 2 |1| 6 ]  Aᶻ = [ 2  4 |1|]
       [|4| 1  7 ]       [ 3 |4| 7 ]       [ 3  1 |4|]
         ‾                    ‾                    ‾

determinant 是矩阵当中所有向量所构成的超平行体的容积。时间複杂度等于 N+1 次 determinant 的时间複杂度，O(N^4)。

Determinant

determinant 起初用来判定一个线性方程组是否有解、解是多少，因而称作“决定因子”。古人没有意识到 determinant 是容积。

虽然字面意义是“决定因子”，不过中文教科书译作“行列式”。真是异想天开的翻译啊！

http://mathworld.wolfram.com/DeterminantExpansionbyMinors.html

行列式的计算过程是：先删除一横行，接著分别删除每一直行，形成 N-1 个(N-1)×(N-1) 子矩阵，添上正负号。原矩阵的行列式，等于这些子矩阵的行列式总和。每个子矩阵各自递迴下去，直到 N=1。1×1 矩阵的行列式，等于矩阵元素。时间複杂度 O(N!)。

N = 2 or 3 的时候比较特别，可以直接累加所有“左上右下斜线”的乘积、累减“右上左下斜线”的乘积。中学数学课程有教。

计算行列式，也可以使用高斯消去法，时间複杂度 O(N^3)。

不过与其採用高斯消去法求行列式、再用行列式解线性方程组，不如直接採用高斯消去法解线性方程组。就当作是学个想法吧。

Linear Equations: Preconditioner

演算法（Jacobi Method）

运用 Fixed Point Iteration 求解。

[ 4  3 ] [ x ] = [ 1 ]
[ 2  5 ] [ y ]   [ 2 ]

{ 4x + 3y = 1  => { x = (1 - 3y) / 4
{ 2x + 5y = 2     { y = (2 - 2x) / 5

[ x₀ ] = [ 0 ] 随便设定一个初始值
[ y₀ ]   [ 0 ]
    
[ x₁ ] = [ (1 - 3y₀) / 4 ]
[ y₁ ]   [ (2 - 2x₀) / 5 ]
    
[ x₂ ] = [ (1 - 3y₁) / 4 ]
[ y₂ ]   [ (2 - 2x₁) / 5 ]

三维版本。

[ 4  3 -1 ] [ x ]   [ 1 ]
[ 2  5  1 ] [ y ] = [ 2 ]
[-2 -2  6 ] [ z ]   [ 3 ]

{  4x + 3y -  z = 1     { x = (1 - 3y +  z) / 4
{  2x + 5y +  z = 2  => { y = (2 - 2x -  z) / 5
{ -2x - 2y + 6z = 3     { z = (3 + 2x + 2y) / 6

[ x₀ ]   [ 0 ]
[ y₀ ] = [ 0 ] 随便设定一个初始值
[ z₀ ]   [ 0 ]

[ x₁ ]   [ (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (2 - 2x₀ -  z₀) / 5 ]
[ z₁ ]   [ (3 + 2x₀ + 2y₀) / 6 ]

任意维度。

      Ax = b
(D+L+U)x = b             D 是对角线、L 是下三角、U 是上三角
      Dx = b - (L+U)x
       x = D⁻¹ [b - (L+U)x]

x₀ = 随便设定一个初始值
xₖ₊₁ = D⁻¹ [b - (L+U)xₖ]

时间複杂度是 O(N^2 * T)，N 是方阵维度，T 是递推次数。

判断收敛，检查 D⁻¹(L+U) 的特徵值的绝对值是不是都小于 1。

x = D⁻¹ [b - (L+U)x]
x = D⁻¹b - D⁻¹(L+U)x

满足 strictly diagonally dominant 就保证收敛。不满足时，可能收敛、也可能不收敛。

for each row, |Aii| > ∑ |Aij|
                     j≠i

演算法（Gauss-Seidel Method）

每回合依序计算 x、y、z，刚出炉的数字，马上拿来使用，加快收敛速度。

[ 4  3 -1 ] [ x ]   [ 1 ]
[ 2  5  1 ] [ y ] = [ 2 ]
[-2 -2  6 ] [ z ]   [ 3 ]

{  4x + 3y -  z = 1     { x = (1 - 3y +  z) / 4
{  2x + 5y +  z = 2  => { y = (2 - 2x -  z) / 5
{ -2x - 2y + 6z = 3     { z = (3 + 2x + 2y) / 6

[ x₀ ]   [ 0 ]
[ y₀ ] = [ 0 ] 随便设定一个初始值
[ z₀ ] = [ 0 ]

[ x₁ ]   [ (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (2 - 2x₁ -  z₀) / 5 ]
[ z₁ ]   [ (3 + 2x₁ + 2y₁) / 6 ]
依序计算 x₁、y₁、z₁，刚出炉的数字，马上拿来使用，加快收敛速度。

xₖ₊₁ = D⁻¹ (b - Uxₖ - Lxₖ₊₁)

演算法（Successive Over Relaxation）

原数值、新数值，以固定比例混合。

[ x₁ ]   [ (1-w) * x₀ + w * (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (1-w) * y₀ + w * (2 - 2x₁ -  z₀) / 5 ]
[ z₁ ]   [ (1-w) * z₀ + w * (3 + 2x₁ + 2y₁) / 6 ]

Linear Equations: Least Squares

Least Squares

本章节的先备知识是“ Optimization ”。

唯一解是稀奇的，无解、多解是普遍的。无解、多解时，可以改为找到平方误差最小的解。

solve Ax = b

 overdetermined system: 等式太多 -> 无解 -> 改求‖Ax - b‖²最小的解
underdetermined system: 等式太少 -> 多解 -> 改求‖x‖²最小的解

等式太多、等式太少（中学数学的讲法是：变数少于等号、变数多于等号），两种情况分别处理。严格来说，必须预先消去所有等价的、多馀的等式，以 rank 大小、矩阵大小来区分这两种情况。

一、等式太多因而无解：方程组每一道等式，求得等号左右两边的差的平方；累计所有等式，总和越小越好。

二、等式太少因而多解：解的每一项的平方，总和越小越好。

Least 意指“尽量小”，Squares 意指“平方和”。

平方误差的优势是：循规蹈矩，成为一个参考指标，误差高低可以拿来比较，科学多了。缺陷是：计算速度慢。

平方误差比起绝对值误差，有两个好处：一、让每道等式的误差保持均匀，不会有某道等式误差特别高。二、“一次微分等于零”容易推导数学公式。

三种数学公式

MATLAB 按一按，答案就出来了，大可不必深究细节。

solve overdetermined system Ax = b   minimize ‖Ax - b‖²

       T    -1  T          T       T
x = ( A  A )   A  b     ( A A x = A b )   Normal Equation

     -1 T
x = R  Q  b             ( A = Q R )       QR Decomposition

        +  T                       T
x = V  Σ  U  b          ( A = U Σ V )     Singular Value Decomposition

     +
x = A  b                                  Pseudoinverse

solve underdetermined system Ax = b   minimize ‖x‖²

     T      T -1  
x = A  ( A A )   b                        Normal Equation

         T -1              T
x = Q ( R )   b         ( A = Q R )       QR Decomposition

        +  T               T       T
x = U  Σ  V  b          ( A = U Σ V )     Singular Value Decomposition

数学公式（Normal Equation）

http://people.csail.mit.edu/bkph/articles/Pseudo_Inverse.pdf

线性代数经典公式！视作最佳化问题，以微分求极值。

“一次微分等于零”的地方是极值、鞍点。因为平方误差是开口向上的抛物面，所以“一次微分等于零”的地方必是最小值，而非最大值、鞍点。

以下只证明等式太多的情况。时间複杂度 O(N^3)。

solve  Ax = b
                 2
minimize ‖Ax - b‖

∂          2
―― ‖Ax - b‖ = 0                     “一次微分等于零”的地方是最小值
∂x
  ∂
[ ―― (Ax - b) ] [ 2(Ax - b) ] = 0   微分连锁律
  ∂x
 T
A  [ 2(Ax - b) ] = 0                微分

 T       T
A A x = A b                         同除以 2、展开、移项

       T    -1  T  
x = ( A  A )   A  b                 移项。注意到 A 的向量们必须线性独立！

注意到最后一步，A 的向量们必须线性独立（事先清除冗馀的、无意义的变数），AᵀA 才有反矩阵。

数学公式（QR Decompostion）

http://www.cs.cornell.edu/courses/cs322/2007sp/notes/qr.pdf

A = QR。将矩阵拆开成正规正交矩阵 Q、零馀部分 R。正规正交矩阵 Q 不影响最小值，最小值取决于零馀部分 R。

以下只证明等式太多的情况。等式太少的情况，改为分解 A 的转置矩阵 Aᵀ = QR。

时间複杂度 O(N^3)。但是计算量比 Normal Equation 少。

solve  Ax = b

              2
min ‖ Ax - b ‖

       T          2
min ‖ Q (Ax - b) ‖         正规正交矩阵，变换后长度不变

       T       T   2
min ‖ Q A x - Q b ‖        展开

             T   2          T     T
min ‖ R x - Q b ‖          Q A = Q Q R = R

                 T     2
    ‖ [ R₁ x - Q₁ b ] ‖    R = [ R₁ ]  区分出零，让 R₁是方阵
min ‖ [          T  ] ‖        [ 0  ]  区分上段和下段
    ‖ [    0 - Q₂ b ] ‖ 

            T
令 R₁ x - Q₁ b = 0         此式有唯一解，可为零
               T   2
令最小值是 ‖ Q₂ b ‖ 

         T
R₁ x = Q₁ b                移项

     -1  T
x = R₁ Q₁ b                移项

Timus 1668

数学公式（Singular Value Decompostion）

和 QR 分解的手法如出一辙。

以下只证明等式太多的情况。等式太少的情况，改为分解 A 的转置矩阵 Aᵀ = UΣVᵀ。

时间複杂度 O(N^3 + NK)。我不确定实务上是否比较快。

solve  Ax = b

              2
min ‖ Ax - b ‖

       T          2
min ‖ U (Ax - b) ‖       正规正交矩阵，变换后长度不变

       T       T   2
min ‖ U A x - U b ‖      展开

         T     T   2      T     T     T      T
min ‖ Σ V x - U b ‖      U A = U U Σ V  = Σ V 

      T     T
令 Σ V x - U b = 0       此式有唯一解，可为零

   T     T
Σ V x = U b              移项

        +  T
x = V  Σ  U  b           移项

Linear Equations: Optimization（Under Construction!）

演算法（Conjugate Gradient Method）

本章节的先备知识是“ Optimization ”。

採用最佳化演算法 Gradient Method，针对平方误差进行改良，速度更快。

平方误差的矩阵形式，即是对称正定矩阵。

http://www.cs.ucsb.edu/~gilbert/cs219/cs219Spr2013/Slides/cs219-CgIntro.pptx
http://graphics.stanford.edu/courses/cs205a-15-spring/assets/lecture_slides/cg_i.pdf

演算法（Gauss-Newton Algorithm）

採用最佳化演算法 Newton Method，针对平方误差进行改良，速度更快。

演算法（Levenberg-Marquardt Algorithm）

视情况使用 Conjugate Gradient Method 或者 Gauss-Newton Algorithm，两害相权取其轻。

Linear Equations: Regularization

Regularization

本章节的先备知识是“ Constrained Optimization ”。

线性方程组，无解、多解时，我们增加限制条件，以得到唯一解。以下以无解为例。

                                  2
solve Ax = b     minimize ‖Ax - b‖

我们可以再添加其他限制条件。

                                  2
solve Ax = b     minimize ‖Ax - b‖      subject to f(x) ≥ 0

运用 Regularization，限制条件併入最佳化的对象。

                                  2
solve Ax = b     minimize ‖Ax - b‖ + α f(x)   (α ≥ 0)

α理应是未知数，不过此处改成了一个自订数值。我们视问题需要，订立适当数值。数值越小，限制条件的影响力就越小，类似于加权平均的概念。

求最小值，权重的绝对大小不重要，考虑相对大小即可。我们习惯把第一个限制的权重定为 1，节省一个权重数值。

Tikhonov Regularization

线性方程组，有许多式子和变数。可能有其中一群变数与式子构成无解、另一群构成唯一解、剩下一群构成多解。更有甚者，切割一些群结果无解变多解、整併某些群结果多解变无解。

无法釐清是无解、多解的时候，那就两个限制一起上吧。

                                   2        2
solve Ax = b      minimize ‖Ax - b‖  + α ‖x‖    (α ≥ 0)

∂            2        2        
―― [ ‖Ax - b‖  + α ‖x‖  ] = 0    “一次微分等于零”的地方是极值、鞍点
∂x                               二次函数、恆正，必得最小值
   T         T
2 A A x - 2 A b + 2 α x = 0      展开

   T               T                             T
( A A + α I ) x = A b            移项，左式即是 A A 的对角线加上 α

左式是实数对称正定方阵，有唯一解。时间複杂度 O(N^3)。

Homogeneous Linear Equations

讨论特例 b = 0 的情况。当 b = 0，则 x = 0，缺乏讨论意义。于是添加限制“x 长度（的平方）为 1”，增进讨论意义。

solve Ax = 0
             2
minimize ‖Ax‖
              2
subject to ‖x‖ = 1

             2         2
minimize ‖Ax‖ - λ ( ‖x‖ - 1 )     Lagrange multiplier

∂        2         2
―― [ ‖Ax‖ - λ ( ‖x‖ - 1 ) ] = 0   “一次微分等于零”的地方是极值、鞍点
∂x                                 二次函数，必得极值
   T
2 A A x - 2 λ x = 0               展开

 T
A A x = λ x                       移项，此即特徵向量的格式

答案是 AᵀA 的最小的特徵值的特徵向量！又因为 AᵀA 是实数对称正半定方阵，所以特徵值都是正数、零。

欲求最小的特徵值，可以採用 QR Iteration 或 Lanczos Iteration 演算法求得所有特徵值，再挑出最小的，时间複杂度 O(N^3 + N^2 * K)。亦可採用 Singular Value Decomposition 的演算法，不必计算 AᵀA，节省一点时间。

Basis Pursuit（Lasso）

改成 L¹ norm，讨论多解的情况。NP-hard。

solve Ax = b      minimize ‖x‖₁     [underdetermined system]

http://en.wikipedia.org/wiki/Matching_pursuit

Basis Pursuit Denoising

两个限制一起上，无解採用 L² norm、多解採用 L¹ norm。走火入魔。

                                   2        2
solve Ax = b      minimize ‖Ax - b‖  + α ‖x‖₁    (α ≥ 0)

Linear Inequalities

线性不等式组。许多道线性不等式同时成立。

正是计算几何“ Half-plane Intersection ”推广到高维度，所有解形成一个凸多胞形，也可能形成开放区间、退化、空集合。

目前没有演算法。大家习惯採用“Linear Programming”，将凸多胞形硬是位移至第一象限（各个变数加上一个足够大的数值，代换成新变数），以符合线性规划的格式。

也有人适度乘上负号，调整成 Ax > b 的格式，套用高斯消去法，但是不知道正不正确。

Linear Programming（Under Construction!）

Linear Programming

本章节的先备知识是“ Constrained Optimization ”。

“线性规划”。目标函数、约束条件都是线性函数，只考虑第一象限。

几何意义，请参考计算几何“ Half-plane Intersection ”。目标函数：一个方向向量。约束条件：半平面。可行解：半平面交集。最佳解：半平面交集的顶点、边、面。

因为解是凸函数，所以可以设计极快的演算法！

https://reference.wolfram.com/language/ref/RegionPlot3D.html

Linear Programming 与 Basis Pursuit 等价

Equivalence of Linear Programming and Basis Pursuit
http://www.mathematik.tu-darmstadt.de/~tillmann/docs/YRMS4-Tillmann.pdf

Linear Programming 相关应用

线性规划是现代社会经常使用的知识，也是商管类科系的必修专业。许多现实问题都能大致化作线性规划问题，举凡经济、交通、工业生产、……，都能看到线性规划的应用。

一些经典数学领域，例如组合最佳化、排程理论，也能用线性规划解决，比起传统的组合算法有过之而无不及。

《Understanding and Using Linear Programming》

演算法（Simplex Algorithm）

http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-410-principles-of-autonomy-and-decision-making-fall-2010/lecture-notes/MIT16_410F10_lec17.pdf

一、变成线性方程组。目标函数，预设答案，视作等式。约束条件，不等式添加变数，成为等式。

二、求可行解。取原点做为可行解：原始变数设为 0，添加变数设为 b。如果原点不是可行解：添加变数为负数，有两种解法。

二甲、两阶段法。添加变数为负值者，替其添加暂时变数。奢望暂时变数是 0，故新增目标函数：最小化暂时变数加总。以高斯消去法消去暂时变数，使之为 0，令新目标函数变成约束条件。最后删去暂时变数。

二乙、大 M 法。添加变数为负值者，替其添加暂时变数。目标函数，减去暂时变数，并且乘上巨大係数，使得最佳解的暂时变数必为零。

三、求最佳解。贪心法，藉由高斯消去法，等价调整约束条件，逐步提高目标函数值。几何意义是：可行解，沿边走，朝向目标函数的方向。

三甲、高维度的情况下，运气非常不好时，可能走进一大片鞍点，在山腰平原上鬼打牆。解法是小小扰动 b，摧毁鞍点。

【待补程式码】

每步需时 O(N(M+N))。

N 个变数（维度）、M 道不等式（刻面），可行解至多 C(M,N) 个顶点。根据“ Upper Bound Theorem ”，可行解至多 M^floor(N/2) 个顶点。

单形法至多走 M^floor(N/2) 步，最差时间複杂度是指数时间。

单形法平均走 M 步，平均时间複杂度是多项式时间。

一种很差的情况是“ Klee-Minty Cube ”，需要走 2^N - 1 步，但是遭遇机率极低。

UVa 10498 ICPC 7584

Quadratic Programming

“二次规划”。目标函数是二次式。

http://en.wikipedia.org/wiki/Sequential_minimal_optimization
http://www.foreyou.net/2015/05/27/SVM 之 SMO 算法笔记（之一）

LP ⊂ QP ⊂ SOCP ⊂ SDP

quadratic programming
min 1/2 xᵀQx + cᵀx   s.t. Ax = b, l <= x="" <="u" second="" order="" cone="" programming="" min="" fᵀx="" s.t.="" ‖aᵢx="" +="" bᵢ‖²="" dᵢ,="" fx="g" semidefinite="" tr(cx)="" tr(aᵢx)="bᵢ,">= 0

演算法（Interior Algorithm）（Barrier Method）

梯度下降法。约束条件取 log，以 Regularization 添入原式，效果是挤压边界、调整路径。