• Newton方法的缺点
  1. 复杂性估计包含 m, M, L 这三个实践中几乎不可能知道的常数。
  2. 尽管Newton方法是仿射不变的，Newton方法的经典分析过多的依赖于所采用的坐标系，如果改变坐标系，参数 m, M, L 均会发生改变。
  • 因此，要寻找下述假设的替代内容

自和谐

• 自和谐函数的重要性

  1. 包含很多对数障碍函数（内点法）
  2. 自和谐函数的Newton方法分析不依赖任何未知常数
  3. 自和谐具有仿射不变性（对一个自和谐函数的变量进行线性变换，仍然得到一个自和谐函数）（将Newton方法应用于自和谐函数时，导出的复杂性估计独立于坐标的仿射变换）

• R中的自和谐函数

  • 定义：如果一个凸函数 f : R → R 对所有 x ∈ dom f 满足 ，它就是自和谐的。
  • 例子：
    1. 线性和（凸的）二次函数
    2. 负对数
    3. 负熵加负对数（负熵函数本身不是自和谐的）
  • 注释：
    1. 常数 “2” 是为了方便简化后面的公式，它可以被任何其他的正数所替代。
    2. 自和谐函数是仿射不变的。
    • 自和谐条件是限制函数的三阶导数的一种方式，该方式独立于仿射坐标变换

• R^n中的自和谐函数

  • 定义：

自和谐计算

1. 比例 Scaling
2. 求和 Sum
3. 仿射函数的复合 Composition with affine function

   • 例子：

     
     
     
     
4. 对数复合 Composition with logarithm

   该条件是齐次的，并且对加法保持不变。它被所有（凸的）二次函数所满足。

   • 例子：

     
     
     

自和谐函数的性质

• Newton减量

  
  
  
  

• 二阶导数的上下界

  
  

• 次优性边界

  
  
  

自和谐函数的Newton方法分析

针对严格凸的自和谐函数 f 分析采用回溯直线搜索的Newton方法

• 回溯直线搜索

  
  

• 分析过程

  
  
  
  

  • 阻尼Newton阶段

    
    
    

  • 二次收敛阶段

    
    

  • 最终的复杂性上界

    
    

自和谐的实际重要性

对于自和谐函数，有一个完全明确的复杂性上界，它不依赖任何未知常数。
但我们仍不清楚实践中自和谐函数是否比非自和谐函数更容易被Newton方法所优化。