凸优化-概述

2019-05-13 本文已影响0人微斯人_吾谁与归

参考教材《凸优化》，参考视频2011中科大凌青《最优化理论》

一.数学优化

最优化问题不同算法的有效性取决于诸多不同因素，如目标函数与约束函数、优化问题所含变量与约束个数以及一些特殊结构如稀疏矩阵

定义：最小二乘问题是这样一类问题，它没有约束条件（m=0）,目标函数是若干项平方和，每一项具有形式 $a_{i}^{T} x-b_{i}$ ，其具体形式表示如下：
$\quad f_{0}(x)=\|A x-b\|_{2}^{2}=\sum_{i=1}^{k}\left(a_{i}^{T} x-b_{i}\right)$
其中A是k*n矩阵， $a_{i}^{T}$ 是A的行向量， $x \in \mathbf{R}^{n}$ 是优化变量。

定义：线性规划及其目标函数都是线性的（ $f_{i}(\alpha x+\beta y)=\alpha f_{i}(x)+\beta f_{i}(y)$ ），线性规划可以表述为 $\begin{array}{ll}{\text { minimize }} & {c^{T} x} \\ {\text { subject to }} & {a_{i}^{T} x \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}$ 其中， $c, a_{1}, \cdots, a_{m} \in \mathbf{R}^{n}, b_{1}, \cdots, b_{m} \in \mathbf{R}$ 是问题参数。
求解：
- 单纯型法
- 内点法
使用：
- 逼近问题

定义：凸优化具有以下形式
$\begin{array}{ll}{\text { minimize }} & {f_{0}(x)} \\ {\text { subject to }} & {f_{i}(x) \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}$
其中 $f_{0}, \cdots, f_{m} : \mathbf{R}^{n} \rightarrow \mathbf{R}$ 为凸函数。所谓凸函数即对任意的 $x, y \in \mathbf{R}^{n}, \alpha, \beta \in \mathbf{R}$ 且 $\alpha+\beta=1, \alpha \geqslant 0, \beta \geqslant 0$ 这些函数满足 $f_{i}(\alpha x+\beta y) \leqslant \alpha f_{i}(x)+\beta f_{i}(y)$ 。
- 线性规划是一种特殊的凸优化问题，
求解：
使用：