机器学习 - 凸优化
· 7 min read
定义
凸优化问题 (OPT,convex optimization problem
) 指定义在凸集中的凸函数最优化的问题。
数学概念
凸集
定义
假设 是向量空间的集。若对于任意 和任意的 ,满足 时, 恒成立。则称 为 凸集
1
从几何上来看,就是 中的任意两点之间的直线段都属于 。
下面举几个例子:
info
- 是凸集 (集合中的任意两个点连线段中的所有点,都在集合中)
- 不是凸集,有空隙
- 不是凸集,有些边不在集合中
凸函数
定义
定义在 上的函数 是凸函数,如果它的定义域 是一个凸集且对任意的 和 恒成 立 2
直观来看:
info
在函数图形上,任意两点连成的线段,皆位于图形的上方
凸函数的一阶充要条件
tip
假设定义在 上的函数 可微 (对于定义域,梯度 均存在)。则函数 是凸函数当且仅当函数定义域 是一个 凸集
,且对于所有 均满足
info
从几何上来看,即定义域内图形都大于等于该点的切线 (切平面)
公式的理解
凸函数的二阶充要条件
记函数的一阶导数和二阶导数分别为 和 :
假设定义在 上的函数 二阶可微(即海赛矩阵 存在)。则函数 是凸函数当且仅当函数定义域 是一个凸集,且对于所有 均满足:
info
这里的 表示是半正定的
见 正定矩阵(This page is not published)
凸优化问题
定义
当 和 均为凸函数,而 均为 仿射变换与仿射函数 时,上述的优化问题即凸优化问题
常见的凸优化问题
线性规划(LP,Linear Program)
其中的目标函数和不等式约束都是仿射函数,且 表示按元素小于等于
二次规划(QP,Quadratic Program)
其中目标函数为凸二次型,不等式约束为仿射函数
利用 Python 进行凸优化
下面是几段例程
给定一个普通的线性规划问题
- Scipy
- pulp
import numpy as np
z = np.array([2, 3, 1])
a = np.array([[1, 4, 2], [3, 2, 0]])
b = np.array([8, 6])
x1_bound = x2_bound = x3_bound =(0, None)
from scipy import optimize
res = optimize.linprog(z, A_ub=-a, b_ub=-b,bounds=(x1_bound, x2_bound, x3_bound))
print(res)
#output:
# fun: 7.0
# message: 'Optimization terminated successfully.'
# nit: 2
# slack: array([0., 0.])
# status: 0
# success: True
# x: array([0.8, 1.8, 0. ])
import pulp
#目标函数的系数
z = [2, 3, 1]
#约束
a = [[1, 4, 2], [3, 2, 0]]
b = [8, 6]
#确定最大化最小化问题,最大化只要把Min改成Max即可
m = pulp.LpProblem(sense=pulp.LpMinimize)
#定义三个变量放到列表中
x = [pulp.LpVariable(f'x{i}', lowBound=0) for i in [1,2,3]]
#定义目标函数,lpDot可以将两个列表的对应位相乘再加和
#相当于z[0]*x[0]+z[1]*x[0]+z[2]*x[2]
m += pulp.lpDot(z, x)
#设置约束条件
for i in range(len(a)):
m += (pulp.lpDot(a[i], x) >= b[i])
#求解
m.solve()
#输出结果
print(f'优化结果:{pulp.value(m.objective)}')
print(f'参数取值:{[pulp.value(var) for var in x]}')
#output:
#优化结果:7.0
#参数取值:[2.0, 0.0, 3.0]