常用参数说明

• 函数书写声明同Python全局

• 以下常用参数如不特殊注明，按照此解释

Session

• target = ""/str

  • 含义：执行引擎

• graph = None/tf.Graph

  • 含义：Session中加载的图
  • 默认：缺省为当前默认图

• config = None/tf.ConfigProto

  • 含义：包含Session配置的Protocal Buffer
  • 默认：None，默认配置

• fetches = tf.OPs/[tf.OPs]

  • 含义：需要获得/计算的OPs值列表
  • 默认：无

• feed_dict = None/dict

  • 含义：替换/赋值Graph中feedable OPs的tensor字典
  • 默认：无
  • 说明
    • 键为图中节点名称、值为向其赋的值
    • 可向所有可赋值OPs传递值
    • 常配合tf.placeholder（强制要求）

Operators

• name = None/str

  • 含义：Operations名
  • 默认：None/OP类型，后加上顺序后缀
  • 说明
    • 重名时TF自动加上_[num]后缀

• axis = None/0/int

  • 含义：指定张量轴
  • 默认
    • None：大部分，表示在整个张量上运算
    • 0：有些运算难以推广到整个张量，表示在首轴（维）

• keepdims=False/True

  • 含义：是否保持维度数目
  • 默认：False不保持

• dtype=tf.int32/tf.float32/...

  • 含义：数据类型
  • 默认：根据其他参数、函数名推断

• shape/dims=(int)/[int]

  • 含义：各轴维数
  • 默认：None/1???
  • 说明
    • -1表示该轴维数由TF计算得到
    • 有些情况下，此参数可省略，由TF隐式计算得到， 但显式指明方便debug

• start=int

  • 含义：起始位置
  • 默认：0

• stop=int

  • 含义：终点位置
  • 默认：一般无

TensorFlow基本概念

• TensorFlow将计算的定义、执行分开

流程

组合计算图

• 为输入、标签创建placeholder
• 创建weigth、bias
• 指定模型
• 指定损失函数
• 创建Opitmizer

在会话中执行图中操作

• 初始化Variable
• 运行优化器
• 使用FileWriter记录log
• 查看TensorBoard

PyTF 模块

tf.nn

tf.nn：神经网络功能支持模块

• rnn_cell：构建循环神经网络子模块

tf.contrib

tf.contrib：包含易于变动、实验性质的功能

• bayesflow：包含贝叶斯计算
• cloud：云操作
• cluster_resolver：集群求解
• compiler：控制TF/XLA JIT编译器
• copy_graph：在不同计算图之间复制元素
• crf：条件随机场
• cudnn_rnn：Cudnn层面循环神经网络
• data：构造输入数据流水线
• decision_trees：决策树相关模块
• deprecated：已经、将被替换的summary函数
• distributions：统计分布相关操作
• estimator：自定义标签、预测的对错度量方式
• factorization：聚类、因子分解
• ffmpeg：使用FFmpeg处理声音文件
• framework：框架类工具，包含变量操作、命令空间、 checkpoint操作
• gan：对抗生成相关
• graph_editor：计算图操作
• grid_rnn：GridRNN相关
• image：图像操作
• input_pipeline：输入流水线
• integrate：求解常微分方程
• keras：Keras相关API
• kernel_methods：核映射相关方法
• kfac：KFAC优化器
• labeled_tensor：有标签的Tensor
• layers：类似nn里面的函数，经典CNN方法重构
• learn：类似ski-learn的高级API
• legacy_seq2seq：经典seq2seq模型
• linalg：线性代数
• linear_optimizer：训练线性模型、线性优化器
• lookup：构建快速查找表
• losses：loss相关
• memory_stats：设备内存使用情况
• meta_graph_transform：计算图转换
• metrics：各种度量模型表现的方法
• nccl：收集结果的操作
• ndlstm：ndlstm相关
• nn：tf.nn某些方法的其他版本
• opt：某些优化器的其他版本
• predictor：构建预测器
• reduce_slice_ops：切片规约
• remote_fused_graph
• resampler：重抽样
• rnn：某些循环神经网络其他版本
• saved_model：更加易用的模型保存、继续训练、模型转换
• seq2seq：seq2seq相关模型
• session_bundle
• signal：信号处理相关
• slim：contrib主模块交互方式、主要入口
• solvers：贝叶斯计算
• sparsemax：稀疏概率激活函数、相关loss
• specs
• staging：分段输入
• stat_summarizer：查看运行状态
• statless：伪随机数
• tensor_forest：可视化工具
• testing：单元测试工具
• tfprof：查看模型细节工具
• timeseries：时间序列工具
• tpu：TPU配置
• training：训练及输入相关工具
• util：Tensors处理相关工具

tf.train

tf.train：训练模型支持

• 优化器

  • AdadeltaOptimizer：Adadelta优化器
  • AdamOptimizer：Adam优化器
  • GradientDescentOptimizer：SGD优化器
  • MomentumOptimizer：动量优化器
  • RMSPropOptimizer：RMSProp优化器

• 数据处理

  • Coordinator：线程管理器
  • QueueRunner：管理读写队列线程
  • NanTensorHook：loss是否为NaN的捕获器
  • create_global_step：创建global step
  • match_filenames_once：寻找符合规则文件名称
  • start_queue_runners：启动计算图中所有队列

• tfrecord数据

  • Example：tfrecord生成模板
  • batch：生成tensor batch
  • shuffle_batch：创建随机tensor batch

• 模型保存、读取

  • Saver：保存模型、变量类
  • NewCheckpointReader：checkpoint文件读取
  • get_checkpoint_state：从checkpoint文件返回模型状态
  • init_from_checkpoint：从checkpoint文件初始化变量
  • latest_checkpoint：寻找最后checkpoint文件
  • list_variable：返回checkpoint文件变量为列表
  • load_variable：返回checkpoint文件某个变量值

tf.summary

tf.summary：配合tensorboard展示模型信息

• FileWriter：文件生成类
• Summary
• get_summary_description：获取计算节点信息
• histogram：展示变量分布信息
• image：展示图片信息
• merge：合并某个summary信息
• merge_all：合并所有summary信息至默认计算图
• scalar：展示标量值
• text：展示文本信息

安装

CUDA、CUDNN、CUDAtookit、NVCC

• CUDA：compute unified device architecture，通用并行计算 平台和编程模型，方便使用GPU进行通用计算
• cuDNN：深度学习加速库，计算设计的库、中间件
  • C++STL的thrust的实现
  • cublas：GPU版本blas
  • cuSparse：稀疏矩阵运算
  • cuFFT：快速傅里叶变换
  • cuDNN：深度学习网络加速
• CUDA Toolkit：包括以下组件
  • 编译器nvcc：CUDA-C、CUDA-C++编译器，依赖nvvm 优化器 （nvvm本身依赖llvm编译器）
  • ·debuggers、profiler等工具
  • 科学库、实用程序库
    • cudart
    • cudadevrt
    • cupti
    • nvml
    • nvrtc
    • cublas
    • cublas_device
  • 示例
  • 驱动：

TensorBoard

TensorBoard是包括在TensorFlow中可视化组件

• 运行启动了TB的TF项目时，操作都会输出为事件日志文件
• TB能够把这些日志文件以可视化的方式展示出来
  • 模型图
  • 运行时行为、状态

1

$ tensorboard --logdir=/path/to/logdir --port XXXX

问题

指令集

Your CPU supports instructions that this TensorFlow binary was not cmpiled to use: SSE1.4, SSE4.2, AVX AVX2 FMA

• 没从源代码安装以获取这些指令集的支持
  • 从源代码编译安装
  • 或者设置log级别

    1 2 3

    import os os.environ["TF_CPP_MIN_LOG_LEVEL"] = "2" import tensorflow as tf

文件结构规则

拆分文件

Rust一般库中文件名/文件夹都表示mod （测试文件规则比较特殊）

• modfoo在其父modbar中声明
• 如果modfoo没有子mod，将其实现放在foo.rs文件中
• 若modfoo有子mod，创建文件夹foo，将其实现放在 foo/mod.rs中

以上是文件拆分规则，也可以不拆分文件

库Crate

库crate中lib.rs相当于该crate顶层mod（根mod）

• 所有的mod直接或间接（祖先mod）声明于此，否则不能识别
• 从引用库crate的外部crate角度来看，其名称和库crate同名 extern crate crate_name;的同时就use crate_name;， 此时可将引用其的mod视为根mod的父mod

库、二进制Crate

crate中可以同时有lib.rs和main.rs，此时库crate和二进制 crate应该看作相互独立

• 在两处都使用mod关键字声明定义mod（不能在main.rs 中使用use声明使用mod）

• 在main.rs中使用extern crate crate_name引入 “外部”库crate

可见性规则

Mod默认私有

• 默认仅crate内部可见
  • 父mod处直接可用
  • 兄弟mod、子mod可以通过“回溯“声明使用
• pub声明为公用后，对外部crate也可见

Fn默认私有

• 默认仅mod“内部”可见（包括后代mod）
  • 当前mod内直接可用
  • 子mod可以通过“回溯”声明可用
• pub声明为公用后，对外部mod也可见

说明

• 项（mod、fn）的声明使用路径都是相对于当前项，即默认调用 其后代项（mod、fn），通过以下“回溯”方式调用非直接后代项
  • super直接父mod路径起始：super::child_mod
  • ::根mod起始：::child_mod
• fn和mod的可见规则相似的，只是注意：fn是否可见只与mod有关 ，mod是否可见只有crate有关。从这个意义上说，crate不能 看作是“大号“的mod

相关关键字

好像都是单一用途（意义），罕见

• extern：引入外部crate（同时包含use crate_name;）
• crate：标记外部crate
• mod/fn：声明定义（注册）mod/fn（同crate内仅一次 ，位于其父mod处）
• use：声明使用项（mod、fn），用于缩略代码

panic!与不可预期（不可恢复）错误

panic!时程序默认开始展开（unwinding）、回溯栈并清理函数据

如果希望二进制文件尽量小，可以选择“终止（abort）”，此时 程序内存由操作系统进行清理，在Cargo.toml中添加

[profile]
panic='abort'

[profile.release]
panic='abort'

前者是配置debug时，后者配置release版本

Result与潜在（可预期、可恢复）错误

Result枚举类型

Result<T, E>{
    Ok<T>,
    Err<E>,
}

• T：成功时Ok成员中的数据类型
• E：失败时Err成员中返回的数据类型

直接处理

• 对Result值进行模式匹配，分别处理

  let f = File::open(“hello.txt”); let mut f = match f { Ok(file) => file, Err(error) => panic!(“error:{:?}”, error), }

• 使用Result上定义的方法（类似以上）

  • Result.unwrap()

    • T = Ok<T>.unwrap()
    • Err<E>.unwrap()使用默认信息调用panic

  • Result.expect(&str)

    • T = Ok<T>.expect(&str)
    • Err<E>.expect(&str)使用&str调用!panic

  • Result.unwrap_or_else

    Result.unwrap_or_else(|err|{

      clojure...
    

    })

    • T = Ok<T>.unwrap_or_else()
    • Err<E>.unwrap_or_else()将E作为闭包参数调用 闭包

  • Result.is_err()

    • False = Ok<T>.is_err()
    • True = Err<E>.is_err()

传播错误（Propagating）

对Result对象进行匹配，提前返回Err<E>，需要注意返回值 类型问题，尤其是在可能存在多处潜在错误需要返回

let f = File:open("hello.txt");
let mut f match f {
    Ok(file) => file,
    Err(error) => return Err(error),
}

?简略写法（效果同上）

let mut f = File::open("hello.txt")?

• ?会把Err(error)传递给from函数（定义在标准库From trait中），将错误从转换为函数返回值中的类型，潜在 错误类型都实现了from函数
• ?只能用于返回值为Result类型的函数内，因为其”返回值” 就是Err(E)（如果有）

变量、值、所有权

变量、值

• 变量：用来代表值进行操作、没有对应内存空间的字符串， 如：a，b
• 值：在内存中有对应的空间，如：5，”asdf”

变量默认不可变

• var变量绑定的值1不能更改，对应的内存数据不能改变

  • 不允许赋值操作，但是变量的声明和绑定可以分开，即使 声明不可变变量，也可以之后绑定值，注意区分

    1 2 3 4 5 6 7 8

    fn ret_int() -> i32{ 5 } // 以下代码可编译，且正确 let num = &mut ret_int(); *num += 1; // 以下不可 let num; num = &mut ret_int(); *num += 1;

    todo

  • 不允许获取可变引用、所有权转移给可变变量（对函数 即限制参数类型，类似于默认const)

  若其中包含（或就是）引用，引用值是可以更改的

  1 2	let ref = &mut ori; *ref += 1;

• 但是变量var可以重新绑定为其他的值

  • 虽然值1不能更改，但是var变量可以绑定其他值

    1 2	let var = 3; let var = 2;

  • 此时虽然值1虽然无法被访问、使用，但是离开作用域 之前不会被丢弃，只是被“隐藏”

所有权规则

• 每个值（内存）都有一个称为所有者（owner）的变量

• 值（内存）有且只有一个所有者

  • 如果多个变量拥有某值（内存）所有权，有可能会多次释放 同一内存，造成内存二次污染
  • rust中只有一个变量拥有所有权避免内存污染问题

• 所有者（变量）离开作用域，值将被丢弃（内存被回收） （rust为其调用drop函数）

  在生命周期结束时释放资源的方法在C++称为RAII （Resource Aquistion Is Initialization），这里的 initialization是指对资源跟踪、管理初始化，RAII就是 将对象（变量）同资源生命周期相关联，在C++中体现为 析构函数

• rust的所有权管理是编译是进行检查，没有runtime性能损失
• 相较于gc（垃圾回收）性能影响较小
• 相较于手动分配、释放内存不容易代码疏忽导致的内存问题

所有权转移

Drop和Copytrait

• Drop：值离开作用域时rust自动调用
• Copy：赋值时调用，赋值之后原变量仍然可以继续使用

需要分配内存、本身就是某种资源形式不会实现Copy trait，实现 Copy trait类型有

• 存储在stack上的类型，值拷贝速度快，定长
• 整型、bool型、浮点型这样（标量）原生数据类型
• 所有元素都copy的tuple

rust不允许任何类型同时同时实现Drop和Copytrait

所有权转移

对于没有实现Copytrait的类型：赋值（包括函数传参、返回值） 操作会将原变量所有权转移（move）给新变量，之后不允许使用 原变量，编译时即报错，这样就避免了同时释放同一内存造成 二次污染

有些情况下所有权不允许转移，如vec中元素

实现了Copytrait的类型，赋值（包括函数传参）操作将按照 Copytrait复制一个新值，将新值（包括所有权）赋给新变量， 如此原变量可以之后继续使用，没有违反rust的所有权规则，因为 实际上两个值（内存）

Reference（引用）

引用（references，&，获取引用作为函数参数称为借用）

单一所有权情况下，仅仅想使用值而不获取所有权，尤其是函数 传参，虽然可以获取所有权之后再将所有权转移，但是操作麻烦， 而且函数返回值可能有其他用途

引用特点

• 引用允许变量使用值但是不获取所有权
• 引用离开作用域时不会丢弃其指向的值，不会内存二次污染
• 分为可变引用、不可变引用，类似于变量绑定

引用规则

• 任意时间内，特定作用域、特定变量只允许
  • 一个可变引用
  • 任意数量不可变引用
• 引用必须总是有效的

注意：获取可变引用和引用赋值给可变变量的区别

1
2
3
4
5
6

let m = 5;
let mut n = &m;
	//将引用赋值给可变变量
let n = &mut m;
	//获取可变引用赋值给变量，这里会报错，因为`m`是不可变
	//变量，不允许通过其获取可变引用

规则1

第一条规则避免以下情况导致的数据竞争

• 多个指针可以访问同一数据
• 至少有一个指针可以写入数据
• 没有有效的同步数据访问机制

这条规则在显式的赋值、声明易发现、遵守，需要注意的是

• 函数调用创建可变引用
• 自运算符创建可变引用（+=、*=）

规则2

rust会在编译时检查引用是否有效，即引用是否是悬垂指针

悬垂指针：指向的内存已经被分配给其他所有者或值被丢弃， 常见于函数中返回局部变量

对于rust中的“变量（有所有权）”而言则不存此问题

• 赋值操作要么转移所有权，值不会被丢弃
• 要么实现copytrait，返回新值

解引用

rust中引用更像c中的指针

• 引用有对应的解引用（dereferance），且“多层次”引用也需要 ”多层次“解引用

• 教程上的引用附图也是引用“指向”原“变量”，不是“值（内存）”

自动引用和解引用

• 方法中self
• +自己实现了解引用（不知道是否算自动解引用）

  1 2	impl<'a> Add<&'a i32> for i32{} impl Add<i32> for i32{}

• todo

生命周期

• rust每个引用都有生命周期，即引用保持有效的作用域 （避免悬垂引用）

• 大部分情况下，生命周期是隐含、可推断的 （类似于类型可推断）

  • 借用检查器（编译器一部分）可以分析函数代码得到引用的 生命周期，通过作用域确保借用有效
  • 但是函数被调用、被函数之外的代码引用时，每次生命周期 都不一样，rust无法分析

• 有时也会出现引用生命周期以一些不同的方式相关联，此时需要 使用泛型生命周期参数标注关系

生命周期注解语法

• 生命周期参数必须以”’“开头（和一般泛型参数区别）
• 参数名称通常小写
• 位于引用”&“之后，”mut“（如果存在）之前

函数生命周期注解

只存在于函数签名中

1
2
3
4
5
6
7

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str{
	if x.len() > y.len(){
		x
	}else{
		y
	}
}

• 生命周期注解并不改变参数、返回值的生命周期，只是在 函数签名中增加了生命周期“协议”

  • 函数体中返回值不遵守“协议”，函数体编译错误
  • 传参、返回值接收变量不遵守“协议”，调用处编译错误
  • 生命周期注解是用于联系函数不同参数和返回值的生命 周期，一旦形成某种联系，编译器就能获取足够信息判断 引用是否有效（是否内存安全、产生悬垂指针）

• 生命周期注解是为了保证函数返回值引用有效，同函数 用途有关，因此以下签名也可以通过编译

  1 2 3

  fn longest<'a>(x: &'a str, y: &str) -> &a' str{ x }

生命周期注解省略规则

• 每个是引用的参数都有自己的输入生命周期参数
• 如果只有一个输入生命周期参数，会被赋予所有输出生命周期 参数
• 若方法存在多个输入生命周期参数，且首个参数self 为引用（&self、&mut self），将其生命周期参数赋给 所有输出生命周期参数

编译器检查完以上三条规则之后，所有引用均有生命周期参数，则 无需额外生命周期注解，但是若函数体返回值不遵守“协议”，仍 无法编译通过

1
2
3
4
5
6
7

impl<'a> stct<'a>{
	fn other_str(&self, &str1) -> &str{
		str1
	}
}
// 检查完规则之后，所有引用均有注解，但是
// 函数体中的生命周期和签名中不一致

这个例子说明生命周期注解不只是“注解”，是真的需要例子考虑 返回值的生命周期

结构体生命周期注解

在结构体成员为引用时需要增加生命周期注解

1
2
3

struct ImportantExcerpt<'a>{
	part: &'a str,
}

此类结构体在实现方法时不能省略生命周期注解，方法签名可根据 规则省略注解

1
2
3
4

impl<'a> ImportantExcerpt<'a>{
	fn (&self){
	}
}

泛型结构体（枚举）作为函数参数、返回值类型时，替换泛型参数 为引用时也需要添加生命周期注解

1
2

fn new(args: &[String]) -> Result<Config, &'a str>{}
fn search<'a>(query: &str, contents: &'a str) -> Vec<&'a str>{}

静态生命周期（'static）

• 存活于整个程序生命期间
• 所有的&str（字符串字面值）都拥有'static生命周期
• 可以用于指定引用的生命周期，但是使用之前三思，应先考虑 悬垂引用、生命周期不匹配的问题

高级生命周期

Lifetime Subtyping

生命周期子类型：确保某个生命周期长于另一个生命周期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

struct Context<'s>(&'s str);
struct Parser<'c, 's: 'c>{
	//`'s: 'c`声明一个不短于`'c`的生命周期`'s`
	context: &'c Context<'s>;
}
impl<'c, 's: 'c> Parser<'c, 's: 'c>{
	fn parse(&self) -> Result<(), &'s str>{
		//根据生命周期省略规则，若`'s`省略，则赋予`&self`的
		//生命周期
		//使用生命周期子类型语法，指定（要求）`&str`生命周期
		//长于`&Context`
		Err(&self.context.0[1..]
		//这里没有考虑字符串切片的有效性，如果这个切片不是
		//有效的unicode字符串（utf8字节序列），会panic
	}
}
fn parse_context(context: Context) -> Result<(), &str>{
	//方法获取`context`的所有权
	Parser{ context: &Context }.parse()
	//`&Context`的生命周期只有整个函数内
	//函数体中的返回值是`context.0[1..]`，为保证返回值有效，
	//其生命周期必须长于整个函数
	//返回值中的`&str`类型的生命周期是`'s`，长于context`'c`
	//满足返回值的生命周期长于函数的要求，能编译通过
}

Lifetime Bounds

生命周期bounds：帮助Rust验证泛型引用不会比其引用的数据存在 更久

1
2
3
4
5

struct Ref<'a, T: 'a> { &'a T };
	//为`T`增加生命周期bound，指定`T`引用的生命周期不短于
	//`'a`，保证结构体成员有效
struct StaticRef<T: 'static> { &'static T };
	//限制`T`为只拥有`'static`生命周期的引用或没有引用的类型

trait对象生命周期推断

1
2
3
4
5
6
7
8
9

trait Red {}
struct Ball<'a> {
	diameter: &'a i32,
}
impl<'a> Red for Ball<'a> {}
fn main(){
	let num = 5;
	let obj = Box::new(Ball {diameter: &num}) as Box<Red>;
}

以上代码能编译通过，因为生命周期和trait对象必须遵守：

• trait对象默认的生命周期为'static
• 若有&'a X或&'a mut x，则默认生命周期为'a
• 如有T: 'a从句，则默认生命周期为'a
• 若有多个类似T: 'a从句，则需明确指定trait对象生命周期， Box<Red + 'a>或Box<Red + 'static>

  todo

正如其他bound，任何Redtrait的实现内部包含引用，必须拥有和 trait对象bound中所指定的相同的生命周期

测试常用宏、属性注解

宏

• assert!(exp,...)
• assert_eq!(val1, val2,...)
• assert_ne!(val1, val2,...) 以上宏均可以传入自定义信息，所有的...中参数都将传递给 format!宏

属性注解

• #[test]：$>cargo test时将测试此函数

• #[ignore]：除非指定，否则$>cargo test默认不测试此 函数（仍需和#[test]注解）

• #[should_panic(expected=&str)]：测试中出现panic测试 通过，可以传递expected参数，当参数为panic信息的起始 子串才通过

cargo test命令

命令行参数和可执行文件参数用“—”分隔

1

$>cargo test cargo_params -- bin_params 

可执行文件常用参数

• 控制测试线程数目

  1	$>cargo test -- --test-thread=1（不使用任何并行机制）

• 禁止捕获输出（测试函数中的标准输出）

  1	$>cargo test -- --nocapture

• 测试#[ignore]标注的测试函数

  1	$>cargo test -- --ignore

命令行常用参数

• 指定部分测试函数

  1	$>cargo test function_name（cargo匹配以此开头的函数）

• 指定部分集成测试文件

  1	$>cargo test --test test_filename

单元测试、集成测试

单元测试

在隔离环境中一次测试一个模块，可以测试私有接口，常用做法是 在每个文件中创建包含测试函数的tests模块，并使用 #[cfg(test)]标注，告诉rust仅在cargo test时才编译该mod

集成测试

相当于外部库，和用户使用代码的方式相同，只能测试公有接口， 可以同时测试多个模块

新建/project/tests目录（和src同级），cargo自动寻找此目录 中集成测试文件

• cargo将每个文件当作单独的crate编译（模仿用户） 其中的文件也不能共享相同的行为（fn、mod）

  • 需要像外部用户一样extern crate引入外部文件，因此 如果二进制库没有lib.rs文件，无法集成测试，推荐 采用main.rs调用lib.rs的逻辑结构

  • 不需要添加任何#[cfg(test)]注解，cargo会自动将 tests中文件只在cargo test时编译

  • 即使文件中不存在任何#[test]注解的测试函数，仍然会 对其进行测试，只是结果永远是通过

• 而文件夹则不会当作测试crate编译

  • cargo test不会将文件夹视为测试crate，而是看作 一个mod

  • 所以可以创建tests/common/mod.rs，并在测试文件中 通过mod common;声明定义common mod共享行为 （相当于所有的测试crate = 测试文件 + common mod）

代码省略

• for i in i.iter()
• array[m..n]

问题明确

• rust中slice也是左闭右开区间

其他技巧

• 随便定义变量数据类型，编译后通过编译器给出的信息得到 某个函数返回值类型

不安全的Rust存在原因

• Rust在编译时强制执行内存安全保证，但这样的静态分析是 保守的，有些代码编译器认为不安全，但其实合法
• 底层计算机硬件的固有的不安全性，必须进行某些不安全操作 才能完成任务

因此需要通过unsafe关键字切换到不安全的Rust，开启存放 不安全代码的块，只能在不安全Rust中进行的操作如下

• 解引用裸指针，
• 调用不安全的函数、方法
• 访问或修改可变静态变量
• 实现不安全trait

需要注意的是，unsafe不会关闭借用检查器或其它Rust安全检查， 在不安全Rust中仍然会检查引用，unsafe关键字只告诉编译器忽略 上述4中情况的内存安全检查，此4种的内存安全由用户自己保证， 这就保证出现内存安全问题只需要检查unsafe块。可以将不安全 代码封装进安全的抽象并提供API，隔离不安全代码。

解引用裸指针（raw pointer）

• *const T：T类型不可变裸指针
• *mut T：T类型可变裸指针

裸指针的上下文中，裸指针意味着指针解引用后不能直接赋值， 裸指针和引用、智能指针的区别

• 允许忽略借用规则，允许同时拥有不可变和可变指针，或者 多个相同位置（值）的可变指针
• 不保证指向有效的内存
• 允许为空
• 不能实现任何自动清理功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let mut num = 5;
let r1 = &num as *const i32;
let r2 = &num as *mut i32;
	//`as`将不可变引用和可变引用强转为对应的裸指针类型
	//同时创建`num`的可变裸指针和不可变裸指针
	//创建裸指针是安全的
unsafe{
	println!("r1 is: {}", *r1);
	println!("r2 is: {}", *r2);
		//解引用裸指针是不安全的，需要放在`unsafe`块中
}

let address = 0x012345usize;
	//创建任意地址
let r = address  as *const i32;
	//创建指向任意内存地址的裸指针

调用不安全的函数或方法

不安全函数和方法类似常规，在开头有unsafe关键字标记，表示 函数含有内存不安全的内容，Rust不再保证此函数内存安全，需要 程序员保证。

但是包含不安全代码并不意味着整个函数都需要标记为不安全，相反 将不安全代码封装于安全函数中是隔离unsafe代码的方法。应该 将不安全代码与调用有关的函数标记为unsafe。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

unsafe fn dangerous() {}
	//`unsafe`关键字表示此函数为不安全函数，含有内存不安全
	//内容，需要程序员自身保证其内存安全
	//但是，包含不安全代码的函数不意味着整个函数都需要标记为
	//不安全，相反的，将不安全代码封装进安全函数是常用的

	//不安全函数体也是`unsafe`块，在其中进行不安全操作时，
	//不需要包裹于`unsafe`块

unsafe{
	dangerous();
	//调用不安全函数也需要在`unsafe`块中，表示调用者确认此
	//“不安全”函数在此上下文中是*内存安全*
}

调用不安全的函数时也需要放在unsafe中，表示程序员确认此函数 在调用上下文中是内存安全的。

split_at_mut的实现

1
2
3
4
5
6
7

let mut v = vec![1, 2, 3, 4, 5, 6];
let r = &mut v[..];
let (a, b)  r.split_at_mut(3);
	//以index=3分隔为两个列表引用（左开右闭）

assert_eq!(a, &mut [1, 2, 3]);
assert_eq!(b, &mut [4, 5, 6]);

split_at_mut方法无法指通过安全Rust实现，一个大概的“函数” 实现可以如此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::slice;

fn split_at_mut(slice: &mut [i32], mid: usize) -> (&mut [i32], &mut [i32]) {
	//这里根据生命周期省略规则省略了生命周期注解

	//在所有权里就有提到，这里不也是可变引用吗，为啥这样
	//还可以通过编译，是对方法中的`self`有特殊的处理吗

	let len = slice.len();
	let ptr = slice.as_mut_ptr();
		//`as_mut_ptr`返回`*mut T`可变裸指针
	
	assert!(mid <= len);
	
	unsafe{
		(slice::from_raw_parts_mut(ptr, mid),
			//`from_raw_parts_mut`根据裸指针和长度两个参数
			//创建slice，其是不安全的，因为其参数是一个
			//裸指针，无法保证内存安全，另外长度也不总是有效
		slice::from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
			//`offset`同样是不安全的，其参数地址偏移量无法
			//保证始终有效
	}
}

使用extern函数调用外部代码

extern关键字用于创建、使用外部函数接口

• 外部函数接口FFI：foreign function interface，编程语言 用以定义函数的方式，允许不同（外部）编程语言调用这些 函数
• 应用程序接口ABI：application binary interface，定义了 如何在汇编层面调用函数

1
2
3
4
5
6
7
8
9
10

extern "C" {
	//`"C"`定义了外部函数所使用的ABI
	fn abs(input: i32) -> i32;
	//希望调用的其他语言中的（外部）函数签名
}
fn main(){
	unsafe{
		println!("absolute value of -3 according to C: {}", abs(-3));
	}
}

extern块中声明的函数总是不安全的，因为其他语言并不强制执行 Rust的内存安全规则，且Rust无法检查，因此调用时需要放在 unsafe块中，程序员需要确保其安全

通过其他语言调用Rust函数

1
2
3
4
5
6

#[no_mangle]
	//告诉Rust编译器不要mangle此函数名称
pub extern "C" fn call_from_c(){
	//此函数编译器为动态库并从C语言中链接，就可在C代码中访问
	println!("just called a Rust function from C!");
}

mangle发生于编译器将函数名修改为不同的名称，这会增加 用于其他编译器过程中的额外信息，但是会使其名称难以阅读 而不同的编程语言的编译器mangle函数名的方式可能不同

访问或修改可变静态变量

全局变量：Rust中称为静态（static）变量

1
2
3
4
5

static HELLO_WORLD: &str = "Hello, world!";
	//静态变量（不可变）
fn main(){
	println!("name is: {}", HELLO_WORLD);
}

• 名称采用SCREAMING_SNAKE_CASE写法，必须标注变量类型
• 只能存储‘static生命周期的引用，因此无需显著标注
• 不可变静态变量和常量（不可变变量）有些类似
  • 静态变量值有固定的内存地址，使用其总会访问相同地址
  • 常量则允许在任何被用到的时候复制数据

访问不可变静态变量是安全的，但访问、修改不可变静态变量都是 不安全的，因为可全局访问的可变数据难以保证不存在数据竞争， 因此在任何可能情况，优先使用智能指针，借助编译器避免数据竞争

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

static mut COUNTER： u32 = 0;
	//可变静态变量

fn add_to_count(inc: u32){
	unsafe {
		COUNTER += inc;
		//修改可变静态变量
	}
}

fn main(){
	add_to_count(3);

	unsafe{
		println!("COUNTER: {}", COUNTER);
		//访问可变静态变量
	}
}

实现不安全trait

存在方法中包含编译器不能验证的不变量的trait时不安全的，可以 在trait前增加unsafe将trait生命为unsafe，且实现trait 也需要标记为unsafe

1
2
3
4

unsafe trait Foo{
}
unsafe impl Foo for i32{
}

如为裸指针类型实现（标记）Send、Synctrait时需要标记 unsafe，因为Rust不能验证此类型可以安全跨线程发送或多线程 访问，需要自行检查

共轭方向

• 设G为$n * n$阶正定对称矩阵，若$d^{(1)}, d^{(2)}$满足

  $$(d^{(1)})^T G d^{(2)} = 0$$

  则称$d^{(1)}, d^{(2)}$关于G共轭

• 类似正交方向，若$d^{(1)},\cdots,d^{(k)}(k \leq n)$关于 G两两共轭，则称其为G的k个共轭方向

• 特别的，$G=I$时，共轭方向就是正交方向

定理1

• 设目标函数为 $$f(w) = \frac 1 2 w^T w + r^T w + \sigma$$ $q^{(1)}, \cdots, q^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$w^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$w^{(1)}, \cdots, w^{(k+1)}$， 则$w^{(k+1)}$是$f(w)$在线性流形 $$\bar W_k = \{w = w^{(1)} + \sum_{i=1}^k \alpha_i q^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$w^{(n+1)}$是$f(w)$在整个 空间上的唯一极小点

• $\bar W_k$上的存在唯一极小点$\hat w^{(k)}$，在所有方向 都是极小点，所以有

  $$<\triangledown f(\hat w^{(k)}), q^{(i)}> = 0, i=1,2,..$$

• 将$\hat w^{(k)}$由正交方向表示带入梯度，求出系数表达式

• 解精确搜索步长，得到$w^{(k+1)}$系数表达式

扩展子空间定理

• 设目标函数为 $$f(w) = \frac 1 2 x^T G x + r^T x + \sigma$$ $d^{(1)}, \cdots, d^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$x^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$x^{(1)}, \cdots, x^{(k+1)}$， 则$x^{(k+1)}$是$f(x)$在线性流形 $$\bar x_k = \{x = x^{(1)} + \sum_{i=1}^k \alpha_i d^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$x^{(n+1)}$是$f(x)$在整个 空间上的唯一极小点

• 引进变换$w = \sqrt G x$即可证

• 在以上假设下，有 $$<\triangledown f(x^{(k+1)}), d^{(i)}> = 0, i=1,2...$$

Conjugate Gradient Method

共轭梯度法

对正定二次函数函数

• 任取初始点$x^{(1)}$，若$\triangledown f(x^{(1)}) = 0$， 停止计算，得到极小点$x^{(1)}$，否则取

  $$d^{(1)} = -\triangledown f(x^{(1)})$$

• 沿着$d^{(1)}$方向进行精确一维搜索得到$x^{(2)}$，若 $\triangledown f(x^{(2)}) \neq 0$，令

  $$d^{(2)} = -\triangledown f(x^{(2)}) + \beta_1^{(2)} d^{(1)}$$

  且满足$(d^{(1)})^T G d^{(2)} = 0$，即二者共轭，可得

  $$\beta_1^{(2)} = \frac {(d^{(1)})^T G \triangledown f(x^{(2)})} {((d^{(1)})^T G d^{(1)})}$$
  • 这里$d^{(2)}$方向的构造方式是为类似构造后面$d^{(k)}$ ，得到能方便表示的系数
  • 类似于将向量组$\triangledown f(x^{(i)})$正交化

• 如此重复搜索，若$\triangledown f^(x^{i)}) \neq 0$，构造 $x^{(k)}$处搜索方向$d^{(k)}$如下

  $$\begin{align*} 0 & = (d^{(i)})^T G d^{(k)} \\ & = -(d^{(i)})T G \triangledown f(x^{(k)}) + \sum_{j=1}^{k-1} \beta_j^{(k)} (d^{(i)})^T G d^{(j)} \\ & = -(d^{(i)})^T G \triangledown f(x^{(k)}) + \beta_i^{(k)} (d^{(i)})^T G d^{(i)} \end{align*}$$

  可得

  $$\beta_i^{(k)} = \frac {(d^{(i)})^T G \triangledown f(x^{(k)})} {(d^{(i)})^T G d^{(i)}}$$

  此时$d^{(k)}$与前k-1个方向均关于G共轭，此k个方向是G的k个 共轭方向，由扩展空间子定理，$x^{(k+1)}$是整个空间上极小

计算公式简化

期望简化$d^{(k)}$的计算公式

• 由扩展子空间定理推论有 $\triangledown f(x^{(k)})^T d^{(i)} = 0, i=1,2…,k-1$ 结合以上$d^{(k)}$的构造公式，有

  $$\begin{align*} & \triangledown f(x^{(k)})^T \triangledown f(x^{(i)}) \\ = & \triangledown f(x^{(k)})^T ( -d^{(i)} + \beta_1^{(i)} d^{(1)} + \cdots + \beta_{i-1}^{(i)} d^{(i-1)} ) \\ = & 0, i=1,2,...,k-1 \end{align*}$$

• 则有

  $$\begin{align*} (d^{(i)})^T G \triangledown f(x^{(k)}) & = \triangledown f(x^{(k)})^T G d^{(i)} \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T G (x^{(i+1)} - x^{(i)}) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(i+1)}) - \triangledown f(x^{(i)})) \\ & = 0, i=1,2,\cdots,k-2 \end{align*}$$

  • $d^{(k)} = \frac 1 {\alpha_i} x^{(i+1)} - x^{(i)}$

• 所以上述$d^{(k)}$构造公式可以简化为

  $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1} d^{(k-1)}$$

• 类似以上推导有

  $$\begin{align*} (d^{(k-1)})^T G \triangledown f(x^{(k)}) & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T \triangledown f(x^{(k)}) \\ \end{align*}$$ $$\begin{align*} (d^{(k-1)})^T G d^{(k-1)} & = \frac 1 {\alpha_i} (d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = -\frac 1 {\alpha_i} (d^{(k-1)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} (\triangledown f(x^{(k-1)}) - \beta_{k-2}d^{(k-2)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} \triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)}) \end{align*}$$

  最终的得到简化后系数$\beta_{k-1}, k>1$的PRP公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {\triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

  或FR公式

  $$\beta_{k-1} = \frac {\|\triangledown f(x^{(k)})\|^2} {\|\triangledown f(x^{(k-1)}) \|^2}$$

• 以上推导虽然是根据正定二次函数得出的推导，但是仍适用于 一般可微函数

• $\beta _ {k-1}$给出两种计算方式，应该是考虑到目标函数 可能不是标准正定二次函数、一维搜索数值计算不精确性

• 将$\beta _ {k-1}$分子、分母推导到不同程度可以得到其他 公式

• Growder-Wolfe公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {(d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))}$$

• Dixon公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T \triangledown f(x^{(k)})} {(d^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

FR/PRP算法

1. 初始点$x^{(1)}$、精度要求$\epsilon$，置k=1

2. 若$|\triangledown f(x^{(k)}) | \leq \epsilon$，停止 计算，得到解$x^{(k)}$，否则置

   $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1}d^{(k-1)}$$

   其中$\beta_{k-1}=0, k=1$，或由上述公式计算

3. 一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} - \alpha d^{(k)})$$

   得$\alpha_k$，置$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$

4. 置k=k+1，转2

• 实际计算中，n步重新开始的FR算法优于原始FR算法
• PRP算法中 $\triangledown f(x^{(k)}) \approx \triangledown f(x^{(k-1)})$ 时，有$\beta_{k-1} \approx 0$，即 $d^{(k)} \approx -\triangledown f(x^{(k)})$，自动重新开始
• 试验表明，对大型问题，PRP算法优于FR算法

共轭方向下降性

• 设$f(x)$具有连续一阶偏导，假设一维搜索是精确的，使用共轭 梯度法求解无约束问题，若$\triangledown f(x^{(k)}) \neq 0$ 则搜索方向$d^{(k)}$是$x^{(k)}$处的下降方向

• 将$d^{(k)}$导入即可

算法二次终止性

• 若一维搜索是精确的，则共轭梯度法具有二次终止性

• 对正定二次函数，共轭梯度法至多n步终止，否则

  • 目标函数不是正定二次函数
  • 或目标函数没有进入正定二次函数区域，

• 此时共轭没有意义，搜索方向应该重新开始，即令

  $$d^{(k)} = -\triangledown f(x^{(k)})$$

  即算法每n次重新开始一次，称为n步重新开始策略

综述

一维搜索/线搜索：单变量函数最优化，即求一维问题

最优解的$\alpha_k$的数值方法

• exact line search：精确一维搜索，求得最优步长 $\alpha_k$使得目标函数沿着$d^{(k)}$方向达到极小，即

• inexact line search：非精确一维搜索，求得$\alpha_k$ 使得

  $$\begin{align*} f(x^{(k)} + \alpha_k d^{(k)}) & < f(x^{(k)}) \\ \phi(\alpha_k) & < \phi(0) \end{align*}$$

一维搜索基本结构

• 确定搜索区间
• 用某种方法缩小搜索区间
• 得到所需解

搜索区间

• 搜索区间：设$\alpha^{ }$是$\phi(\alpha)$极小点，若存在 闭区间$[a, b]$使得$\alpha^{ } \in [a, b]$，则称 $[a, b]$是$phi(\alpha)$的搜索区间

确定搜索区间的进退法

1. 取初始步长$\alpha$，置初始值

   $$\mu_3 = 0, \phi_3 = \phi(\mu_3), k = 0$$

2. 置

   $$\mu = \mu_3 + \alpha, \phi = \phi(\mu), k = k+1$$

3. 若$\phi < \phi_3$，置

   $$\mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi \\ \alpha = 2\alpha, k = k+1$$

4. 若k =1，置

   $$\mu_2 = mu, \phi_2 = \phi, \alpha = -\alpha$$

   转2，否则置

   $$\mu_1 = \mu_2, \phi_1 = \phi_2 \\ \mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi$$

   并令$a=min{\mu_1,\mu_3}, b=max{\mu_1,\mu_3}$，停止搜索

• 通常认为目标函数此算法得到搜索区间就是单峰函数

试探法

• 在搜索区间内选择两个点，计算目标函数值
  • 需要获得两个点取值才能判断极值点的所属区间
• 去掉函数值较大者至离其较近端点段

0.618法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，计算左右 试探点

   $$\begin{align*} a_l & = a + (1 - \tau)(b - a) \\ a_r & = a + \tau(b - a) \end{align*}$$

   其中$\tau = \frac {\sqrt 5 - 1} 2$，及相应函数值

   $$\begin{align*} \phi_l & = \phi(a_l) \\ \phi_r & = \phi(a_r) \end{align*}$$

2. 若$\phi_l<\phi_r$，置

   $$b= a_r, a_r = a_l, \phi_l = \phi_l$$

   并计算

   $$a_l = a + (1 - \tau)(b - a), \phi_l = \phi(a_l)$$

   否则置

   $$a = a_l, a_l = a_r, \phi_l = \phi_r$$

   并计算

   $$a_r = a + \tau(b - a), \phi_r = \phi(a_r)$$

3. 若$|b - a| \geq \epsilon$

   • 若$\phi_l < \phi_r$，置$\mu = a_l$
   • 否则置$\mu = \alpha_r$ 得到问题解$\mu$，否则转2

• 0.618法除第一次外，每次只需要计算一个新试探点、一个新 函数值，大大提高了算法效率
• 收敛速率线性，收敛比为$\tau = \frac {\sqrt 5 - 1} 2$常数

Fibonacci方法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，选取分离 间隔$\sigma < \epsilon$，求最小正整数n，使得 $F_n > \frac {b - a} \epsilon$，计算左右试探点

   $\begin{align} al & = a + \frac {F{n-2}} {Fn} (b - a)\ a_r & = a + \frac {F{n-1}} {F_n} (b - a) \end{align}

2. 置n=n-1

3. 若$\phi_l < \phi_r$，置

   $$b = a_r, a_r = a_l , \phi_r = \phi_l$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-2}} {F_n} (b - a) \\ \phi_r & = \phi(a_l) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_l & = a_r - \sigma \\ \phi_l & = \phi(a_l) \end{align*}$$

4. 若$\phi_l \geq \phi_r$，置

   $$a = a_l, a_l = a_r , \phi_l = \phi_r$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-1}} {F_n} (b - a) \\ \phi_r & = \phi(a_r) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_r & = a_l + \sigma \\ \phi_r & = \phi(a_r) \end{align*}$$

5. 若n=1

   • 若$\phi_l < \phi_r$，置$\mu = a_r$
   • 否则置$\mu = a_r$

   得到极小点$\mu$，停止计算，否则转2

• Finonacci方法是选取实验点的最佳策略，即在实验点个数相同 情况下，最终的极小区间最小的策略

• Finonacci法最优性质可通过设最终区间长度为1，递推使得原始 估计区间最大的取实验点方式，得出

插值法

• 利用搜索区间上某点的信息构造插值多项式（通常不超过3次） $\hat \phi(\alpha)$
• 逐步用$\hat \phi(\alpha)$的极小点逼近$\phi(\alpha)$ 极小点$\alpha^{*}$

• $\phi^{ * }$解析性质比较好时，插值法较试探法效果好

三点二次插值法

思想

以过三个点$(\mu_1,\phi_1), (\mu_2,\phi_2), (\mu_3,\phi_3)$ 的二次插值函数逼近目标函数

• 求导，得到$\hat \phi(\alpha)$的极小点

  $$\mu = \frac {2[\phi_1(\mu_2-\mu_3) + \phi_2(\mu_3-\mu_1) + \phi_3(\mu_1 - \mu_2)]} {[\phi_1 (\mu_2^2-\mu_3^2) + \phi_2(\mu_3^2-\mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)]}$$

• 若插值结果不理想，继续构造插值函数求极小点近似值

算法

1. 取初始点$\mu_1<\mu_2<\mu_3$，计算$\phi_i=\phi(\mu_i)$， 且满足$\phi_1 > \phi_2, \phi_3 > \phi_2$，置精度要求 $\epsilon$

2. 计算

   $$A = 2[\phi_1(\mu_2 - \mu_3) + \phi_2(\mu_3 - \mu_1) + \phi_3(\mu_1 - \mu_2)]$$
   • 若A=0，置$\mu = \mu_2, \phi = \phi_2$，停止计算， 输出$\mu, \phi$

3. 计算

   $$\mu = [\phi_1 (\mu_2^2 - \mu_3^2) + \phi_2(\mu_3^2 - \mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)] / A$$
   • 若$\mu<\mu_1 或 \mu>\mu_3,\mu \notin (\mu_1,\mu_3)$ ，停止计算，输出$\mu, \phi$

4. 计算$\phi = \phi(\mu)$，若$|\mu - \mu_2| < \epsilon$， 停止计算，得到极小点$\mu$

5. 若$\mu \in (\mu_2, \mu_3)$

   • 若$\phi < \phi_2$，置 $$\mu_1=\mu_2, \phi_1=\phi_2, \mu_2=\mu, \phi_2=\phi$$
   • 否则置 $$\mu_3 = \mu, \phi_3 = \phi$$

   否则

   • 若$\phi < \phi_2$，置

     $$\mu_3=\mu_2, \phi_3=\phi_2, \mu_2=\mu, \phi_2=\phi$$

   • 否则置

     $$\mu_1 = \mu, \phi_1 = \phi$$

6. 转2

两点二次插值法

思想

以$\phi(\alpha)$在两点处$\mu_1, \mu_2$函数值 $\phi_1=\phi(\mu_1)$、一点处导数值 $\phi_1^{‘}=\phi^{‘}(\mu_1) < 0$构造二次函数逼近原函数

• 为保证$[\mu_1, \mu_2]$中极小点，须有 $\phi_2 > \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$

• 求解，得到$\hat \phi (\mu)$极小值为

  $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]}$$

• 若插值不理想，继续构造插值函数求极小点的近似值

算法

1. 初始点$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_2 = \phi_(\mu_2)$$

2. 若$\phi_1^{‘} < 0$，置$d = |d|$，否则置$d = -|d|$

3. 计算

   $$\mu_2 = \mu_1 + d, \phi_2 = \phi(\mu_2)$$

4. 若$\phi_2 \leq \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$，置 $d = 2d$，转3

5. 计算

   $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]} \\ \phi = \phi(\mu), \phi^{'} = \phi^{'}(\mu)$$

6. 若$|phi^{‘}| \leq \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$\mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}, \alpha = \rho \alpha$$

• 其中通常取$d = 1, \rho = 0.1$

两点三次插值法

原理

以两点$\mu_1, \mu_2$处函数值$\phi_i = \phi(\mu_i)$和其导数值 $\phi_i^{‘} = \phi^{‘}(\mu_i)$，由Himiter插值公式可以构造 三次插值多项式$\hat \phi(\alpha)$

• 求导置0，得到$\hat \phi(\alpha)$极小点

  $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \end{align*}$$

算法

1. 初始值$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_1^{'} = \phi^{'}(\mu_1)$$

2. 若$\phi_1^{‘} > 0$，置$d = -|d|$，否则置$d = |d|$

3. 置$\mu_2 = \mu_1 + \alpha$，计算

   $$\phi_2 = \phi(\mu_2), \phi_2^{'} = \phi^{'}(\mu_2)$$

4. 若$\phi_1^{‘} \phi_2{‘} > 0$，置

   $$d = 2d, \mu_1 = \mu_2, \phi_1 = \phi_2, \phi_1^{'} = \phi_2^{'}$$

   转3

5. 计算

   $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \\ \phi & = \phi(\mu) \\ \phi^{'} = \phi^{'}(\mu) \end{align*}$$

6. 若$|\phi^{‘}| < \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$d = \rho d, \mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}$$

   转2

• 通常取$d = 1, \rho = 0.1$

非精确一维搜索

• 对无约束问题整体而言，又是不要求得到极小点，只需要一定 下降量，缩短一维搜索时间，使整体效果最好

• 求满足$\phi(\mu) < \phi(0)$、大小合适的$\mu$

  • $\mu$过大容易不稳定
  • $\mu$过小速度慢

GoldStein方法

原理

• 预先指定精度要求$0< \beta_1 < \beta_2 < 1$

• 以以下不等式限定步长

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu\beta_1 \phi^{'}(0) \\ \phi(\mu) & \geq \phi(0) + \mu\beta_2 \phi^{'}(0) \end{align*}$$

算法

1. 初始试探点$\mu$，置$\mu{min} = 0, \mu{max} = \infty$， 置精度要求$0 < \beta_1 < \beta_2 < 1$

2. 对$\phi(mu)$

   • 若$\phi(\mu) > \phi(0) + \beta1 \phi^{‘}(0) \mu$， 置$\mu{max} = \mu$

   • 否则若$\phi(\mu) > \phi(0) + \beta_2 \phi^{‘}(0)\mu$ ，则停止计算，得到非精确最优解$\mu$

   • 否则置$\mu_{min} = \mu$

3. 若$\mu{max} < \infty$，置 $\mu = \frac 1 2 (\mu{min} + \mu{max})$，否则置 $\mu = 2 \mu{min}$

4. 转2

Armijo方法

Armijo方法是Goldstein方法的变形

• 预先取$M > 1, 0 < \beta_1 < 1$

• 选取$\mu$使得其满足以下，而$M\mu$不满足

  $$\phi(\mu) \leq \phi(0) + \mu \beta_1 \phi^{'}(0)$$

• M通常取2至10

Wolfe-Powell方法

• 预先指定参数$0 < \beta_1 < \beta_2 <1$

• 选取$\mu$满足

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu \beta_1 \phi^{'}(0) \\ \phi^{'}(\mu) & \geq \beta_2 \phi^{'}(0) \end{align*}$$

• 能保证可接受解中包含最优解，而Goldstein方法不能保证