凸优化-概述

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

一.数学优化

1.定义

  • 数学优化问题或者说是优化问题可以写成如下形式：
    \begin{array}{ll}{\text { minimize }} & {f_{0}(x)} \\ {\text { subject to }} & {f_{i}(x) \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}

    • 优化变量：x=\left(x_{1}, \cdots, x_{n}\right)

    • 目标函数：f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}

    • 约束函数：f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, \quad i=1, \cdots, m

    • 可行解z：f_{1}(z) \leqslant b_{1}, \cdots, f_{m}(z) \leqslant b_{m}

    • 最优解 x^*:f_{0}(z) \geqslant f_{0}\left(x^{*}\right),可行解域内的最小值。

2.应用

  • 投资组合优化
  • 器件尺寸
  • 数据拟合：图像处理
  • 嵌入式优化

3.求解最优化问题

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

二.最小二和线性规划

1.最小二乘

  • 定义：最小二乘问题是这样一类问题，它没有约束条件（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}是优化变量。
  • 求解：
  • 使用：
    • 加权最小二乘
    • 正则化

2.线性规划

  • 定义：线性规划及其目标函数都是线性的（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)。

    • 线性规划是一种特殊的凸优化问题，

  • 求解：

  • 使用：

四.非线性规划

五.优化问题分类

  • 凸优化和非凸优化（本质）
  • 线性规划和非线性规划
  • 光滑优化和非光滑优化
  • 可行域连续和离散
  • 单目标优化和多优目标化问题

五.本课程的主要内容

  • 凸集、凸函数、凸优化
  • 凸优化的理论
  • 凸优化的算法
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容