优化基础
优化问题
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
