版权声明：私募工场致力于全新服务专业投资者，及时分享精华、精选、精读内容。除原创文章外，文章所有观点不代表私募工场的观点，所有版权归原作者所有。部分未标注原作者以及原始出处的文章，请原文作者联系506743560@qq.com或15034081448或直接在公众号留言，我们会按照要求在第一时间删除或者作其他正确处理。多谢！
欢迎个人微信转发，谢绝任何媒体、第三方网站、微信公众号不经授权转载。
作者 | immanuel
来源 | 金融投资智库
什么是最优化方法
最优化方法与运筹学
最优化方法是在所有的可行方案中找出最优方案的方法；也称为运筹学方法。
最优化方法与数据分析
最优化方法与统计学、机器学习等数据分析方法不同，并不是从历史数据中发现规律和建立模型；最优化方法与数据分析方法的相似之处在于流程，都需要从实际问题中抽象出数学模型，然后根据数据和问题来建模，并使用计算机求解；最优化方法是数据科学中不可或缺的关键一环，很多统计模型和机器学习算法的理解与实现都需要仰仗最优化方法。
线性规划
lpSolve 是R 中最常用的线性规划工具，基于C 语言；
Rglpk、Rmosek、Rcplex 等是其他工具的R 语言接口。
非线性规划
无约束的非线性规划问题比较简单，R 基础包中包含一些很
方便的函数；
Rsolnp 和alabama 用来求解约束非线性规划的问题；
对于二次规划问题，有quadprog 等专门的R 包可以解决。
整数规划
简单的整数规划问题可以使用线性规划工具解决；
混合线性整数规划可以使用Rsymphony 包来解决，该包基于
COIN-OR 上的SYMPHONY 项目；
非线性混合整数规划问题暂无方便的R 包可以直接使用。
图优化
igraph 是sna 常用的图与网络优化的工具包；
这也是进来流行的社交网络分析的基础方法。
一个标准的最优化模型
两变量的问题可以直观地在直角坐标性中理解:
lpSolve 包的lp 函数
direction：优化的方向，默认是“min”，也可以是“max”
objective.in：目标函数的系数，向量的长度必须等于变量的
个数
const.mat：约束条件的系数矩阵
const.dir：约束的方向
const.rhs：不等式右边的数值向量
Rglpk 包
AMPL 的子集
Rglpk_read_file 可以读入模型
Rglpk_solve_LP 可以求解模型
代码示例：
library(lpSolve)
f.obj <- c(-2, -1)
f.con <- matrix (c(-3, -4, -1, 2, 1, 0, 0, 1), nrow = 4,
byrow = TRUE)
f.dir <- c(">=", ">=", ">=", ">=")
f.rhs <- c(-12, -2, 0, 0)
res <- lp("min", f.obj, f.con, f.dir, f.rhs)
res
## Success: the objective function is -7
class(res)
## [1] "lp"
res$solution
## [1] 3.2 0.6
IP
纯粹的整数规划
所有变量都必须取值为整数
所有变量都为0-1 时称为0-1 规划
MILP
混合整数线性规划
部分变量为整数
MINLP
混合整数规划
目标函数和约束条件可能同时包含整数项和非线性项
Rglpk 包示例
library(Rglpk)
mod.file <- system.file("examples", "optimization",
"sudoku.mod", package = "rinds")
mod <- Rglpk_read_file(mod.file, type = "MathProg")
class(mod)
## [1] "MP_data_from_file" "MILP"
res <- Rglpk_solve_LP(obj = mod$objective,
mat = mod$constraints[[1]],
dir = mod$constraints[[2]],
rhs = mod$constraints[[3]], bounds = mod
无约束的非线性规划
f(x1, x2) = (1 x1)2 + 100(x2 x21)2 .
Rosenbrock 香蕉函数
函数参数
par：表示各变量的初始值，通过向量传入
fn：目标函数
gr：梯度函数
method：优化方法，通过字符串的形式传入
control：一个列表，包含优化中的各种设置，包括最大迭代次
数maxit、绝对收敛容忍度abstol、相对收敛容忍度reltol 等
hessian：表示是否返回海塞矩阵，默认是FALSE
Nelder-Mead
一种单纯型法
非常稳健，效率也不低
CG
一种共轭梯度法
最速下降
容易陷入局部最优
BFGS
一种拟牛顿法，也称为变尺度法
具备牛顿法搜索快的特性的基础上又能有效地搜索全局最优
解
L-BFGS-B 是对该方法的一个优化，能够在优化的同时增加
箱型的约束条件
代码示例
obj.rosenbrock <- function(x) {
x1 <- x[1]
x2 <- x[2]
100 * (x2 - x1 * x1)^2 + (1 - x1)^2
}
optim(par = c(0, 3), fn = obj.rosenbrock)
## $par
## [1] 1.000300 1.000562
##
## $value
## [1] 2.301092e-07
##
## $counts
## function gradient
## 83 NA
##
## $convergence
## [1] 0
带约束的非线性规划
constrOptim 函数
f 表示目标函数
grad 表示梯度函数
theta 表示初始值
ui 和ci 表示线性约束条件
所有不等式的方向都是“>=”
第三方包
alabama
Rsolnp
代码示例
library(alabama)
hin.rosenbrock <- function(x) {
x1 <- x[1]
x2 <- x[2]
c(-x1^2 - x2^2 + 4, x1 / x2 -2)
}
constrOptim.nl(par=c(1,0.3), fn=obj.rosenbrock,
gr=gr.rosenbrock, hin=hin.rosenbrock)
## $par
## [1] 0.5174369 0.2587185
##
## $value
## [1] 0.2410077
##
## $counts
## function gradient
## 365 56
##
## $convergence
## [1] 0
遗传算法简介
一种随机算法，基于进化论的思想，模拟物种的世代，优胜劣汰
步骤
随机模拟初始物种作为初始值
目标函数代表个体的优秀程度
通过轮盘法决定繁殖，优秀的个体容易找到配偶
基因交换
基因突变机制
世代更替
代码实现
gene.reproduce <- function(ind) {
pop.val <- sapply(ind, gene.obj)
pop.prob <- 1 / (pop.val - min(pop.val) + 1)^0.2
pop.prob <- pop.prob/sum(pop.prob) #构造轮盘概率
pop.idx <- sample(seq_along(ind), 2,
prob = pop.prob) #抽样选出亲代
ind.gene.len <- sample(1:13, 1)
ind.gene.i <- sample(1:14, ind.gene.len)
new1 <- ind[[pop.idx[1]]]
new2 <- ind[[pop.idx[2]]]
new1[ind.gene.i]<-ind[[pop.idx[2]]][ind.gene.i]
new2[ind.gene.i]<-ind[[pop.idx[1]]][ind.gene.i]
ind.new <- new1 # 染色体交换
# 选择存活的子代与淘汰最弱的亲代：
if (gene.obj(new2)<gene.obj(new1)) ind.new <- new2
ind.old.i <- which.min(pop.prob)
if (gene.obj(ind.new)<gene.obj(ind[[ind.old.i]]))
ind[[ind.old.i]] <- ind.new
return(ind)
}
