IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 人工智能 -> 《凸优化》二读之杂言6 -> 正文阅读

[人工智能]《凸优化》二读之杂言6

本部分内容介绍一些特殊的凸优化问题,包括线性规划、二次规划等。

线性规划(LP)(目标和约束函数都是仿射函数):

\begin{matrix} \text{minimize} & c^Tx+d \\ \text{subject to} & Gx\preceq h\\ & Ax=b \end{matrix}

因为约束函数是线性函数,线性规划问题的可行集是多面体,几何意义如下图所示:

线性规划问题的可行集是多面体,由阴影表示;因为目标函数是线性的,所以等值曲线是
垂直于c的 超平面

?二次规划(QP)(目标函数是(凸)二次函数,约束函数是仿射函数):

\begin{matrix} \text{minimize} & 1/2x^TPx+q^Tx+r \\ \text{subject to} & Gx\preceq h\\ & Ax=b \end{matrix}

因为约束函数是线性函数,二次规划问题的可行集是多面体,几何意义如下图所示:

凸二次函数的等值曲线如虚线所示。

?线性规划问题是二次规划问题的特例,令P=0著名的例子是最小二乘问题。

二次约束二次规划(QCQP)(目标函数是二次函数,不等式约束函数是二次函数,等式约束函数是仿射函数):

\begin{matrix} \text{minimize} & 1/2x^TP_0x+q_0^Tx+r_0 \\ \text{subject to} & 1/2x^TP_ix+q_i^Tx+r_i,i=1,\dots,m\\ & Ax=b \end{matrix}

二次约束二次规划问题的可行集是m个椭球的交集。(这是因为我们可以通过消除等式得到等价的凸优化问题,该问题只含有不等式约束,其中约束函数是二次函数。)

二次规划问题是二次约束二次规划问题的特例,令P_i=0,i=1,\dots,m

二阶锥规划(SOCP)(目标函数是仿射函数,不等式约束是二阶锥约束):

\begin{matrix} \text{minimize} & f^Tx \\ \text{subject to} & \|A_ix+b_i\|_2\leq c_i^Tx+d_i,i=1,\dots,m\\ & Fx=g \end{matrix}

下面简单介绍下二阶锥。二阶锥是关于欧几里得范数范数锥\{(x,t)|\|x\|_2\leq t \}。二阶锥约束要求仿射函数(Ax+b,c^Tx+d)位于二阶锥中。因为仿射函数是保凸运算,所以二阶锥约束确定的x可行集也是凸集。

c_i=0,i=1,\dots,m,二阶锥规划问题变为(目标函数是仿射函数的)二次约束二次规划问题;线性规划问题是二阶锥规划问题的特例,令A_i=0,i=1,\dots,m。著名的例子是鲁棒线性规划问题。


?广义不等式约束的凸优化问题(在不等式约束中使用广义不等式):

\begin{matrix} \text{minimize} & f_0(x) & \\ \text{subject to} & f_i(x) \preceq_{K_i} 0 & i=1,\dots,m\\ & Ax=b & \end{matrix}

和普通凸优化问题不同,广义不等式约束的凸优化问题中的不等式约束函数f_i:\mathbf{R}^n\to \mathbf{R}^{K_i}的函数值是向量,是K_i-凸的。

普通凸优化问题的一些结果对于广义不等式约束的凸优化问题同样成立,例如可行集和最优集是凸集、局部最优解也是全局最优解等。和普通凸优化问题一样,我们可以轻松求解广义不等式约束的凸优化问题。

锥规划问题(目标函数是仿射函数,不等式约束函数是仿射函数且K-凸的)是一种特殊的广义不等式约束的凸优化问题:

\begin{matrix} \text{minimize} & c^Tx\\ \text{subject to} & Fx+g \preceq_K0\\ & Ax=b \end{matrix}

线性规划问题是锥规划问题的一种特例,令K=\mathbf{R}^n_{+}非负象限

半定规划问题是锥规划问题的一种特例,令K=\mathbf{S}^n_{+}对称正半定矩阵

\begin{matrix} \text{minimize} & c^Tx\\ \text{subject to} & x_1F_1+\cdots+x_nF_n+G \preceq 0\\ & Ax=b \end{matrix}

二阶锥规划问题是锥规划问题的一种特例,令K=\{(y,t)~|~\|y\|_2\leq t\}\mathbf{R}^{n+1}上的二阶锥

\begin{matrix} \text{minimize} & c^Tx\\ \text{subject to} & (-A,-c^T)x+(-b,-d) \preceq_K0\\ & Ax=b \end{matrix}

  人工智能 最新文章
2022吴恩达机器学习课程——第二课(神经网
第十五章 规则学习
FixMatch: Simplifying Semi-Supervised Le
数据挖掘Java——Kmeans算法的实现
大脑皮层的分割方法
【翻译】GPT-3是如何工作的
论文笔记:TEACHTEXT: CrossModal Generaliz
python从零学(六)
详解Python 3.x 导入(import)
【答读者问27】backtrader不支持最新版本的
上一篇文章      下一篇文章      查看所有文章
加:2022-03-13 21:47:25  更:2022-03-13 21:52:14 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 16:05:58-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码