数学基础W15:优化

阅读数: 4次 2020-06-18

优化基础

优化问题

Minimize $f_0(x)$ 使 $f_i(x)\le b_i,i=1,2,…,m$

带不等式约束的优化问题；

大部分机器学习的训练参数的过程都可以用一个优化问题来描述。

$x=(x_1,x_2,…,x_n)$ 为优化变量

$f_0:R^n->R$ 目标函数

优化问题的应用

投资组合

变量：不同资产上的投资额
约束：预算，每份资产投资额(最大/最小)限制，最小收益值
目标：总风险值或投资回报方差

第一次华尔街革命标志性成果，马科维茨均方投资组合。

数据拟合

变量：模型参数
约束：先验知识、参数限制
目标：拟合或预测误差

全局最优问题

求解困难

但最小二乘/线性规划/凸优化问题都可以在理论上有最优解

无法找到最优解的，想办法近似成可以找到最优解的问题类型。

最小二乘： $||Ax-b||_2^2$

求解最小二乘：解析解 $(A^TA)^{-1}A^Tb$

使用最小二乘：判别/一些技术增加了灵活性

最小二乘的变体：加权与正则化

线性规划

Minimize: $c^Tx,s.t. a_i^Tx\le b_i$

线性规划问题不如最小二乘问题容易判别

凸优化

Minimize $f_0(x)$

目标函数和限制函数都是凸函数

最小二乘问题和线性规划问题实质上都是凸优化问题的特殊形式。

故优化课程的核心为凸优化

凸优化问题的识别较困难

数据科学常见的凸优化问题

逻辑回归模型，在C类中的概率表示

决策变量 $x_0$ 和斜率向量 $x^n$

稀疏数据拟合

Minimize $||x||_0=|j:x_j\neg 0|$

非0 分量的个数

NP-hard

用LASSO来近似求解(1范数的好的性质)

添加正则化项防止过拟合，其中0<p<1, $\mu>0$ 是正则化参数

SVM：支持向量机

寻找到一个超平面进行类别的分割。

设施位置

Minimize $\sum||y-c_j||_p$

$y_j-x_j=c_j,||c_j||\le \theta_j,minimize \theta_j$

图形实现与传感器网络定位

SDP：半定规划

产业互联网的发展

产业检测，产业过程的优化需要布置传感器，捕捉到线下传感的过程，故此涉及到了传感器定位的问题。

Mobile phone c.f. transistior