凸优化3:几种重要凸集

2023-10-23 07:50
文章标签 优化 几种 重要 凸集

本文主要是介绍凸优化3:几种重要凸集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、几种简单的凸集

仿射集凸集
R n R^n Rn空间、 R n R^n Rn空间子空间、直线任意线段、${x_0+\theta v

2、超平面与半空间

超平面(Hyperplane): { x ∣ a T x = b } \{x|a^T x=b\} {xaTx=b} x , a ∈ R n , b ∈ R , a ≠ 0 x,a \in R^n,b \in R, a \neq 0 x,aRn,bR,a=0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eLDUUwgC-1642769035169)(D:\StudyFiles\ConvexOptimization\note\3.几种重要凸集\3-1.png)]

半空间(Halfspace): { x ∣ a T x ≤ b } \{x|a^T x \leq b\} {xaTxb} x , a ∈ R n , b ∈ R , a ≠ 0 x,a \in R^n,b \in R, a \neq 0 x,aRn,bR,a=0

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-j0ZHOlbD-1642769035170)(D:\StudyFiles\ConvexOptimization\note\3.几种重要凸集\3-2.png)]

2、球和椭球


球 : 我 们 所 提 的 球 指 欧 几 里 得 球 ( E u c l i d e a n b a l l ) B ( x c , r ) = { x ∣ ∣ ∣ x − x c ∣ ∣ 2 ≤ r } = { x ∣ ( x − x c ) T ( x − x c ) ≤ r } 球:我们所提的球指欧几里得球(Euclidean \space ball) \\ B(x_c,r)=\{x \mid ||x-x_c||_2 \leq r\} \\ =\{x \mid \sqrt{{(x-x_c)}^T(x-x_c)} \leq r\} \\ (Euclidean ball)B(xc,r)={xxxc2r}={x(xxc)T(xxc) r}
椭球(ellipsoids)
ε ( x c , p ) = { x ∣ ( x − x c ) T p − 1 ( x − x c ) ≤ 1 } x , x c ∈ R n , P ∈ S + + n P 的 奇 异 值 对 应 椭 球 的 半 周 长 , S + + n 为 n × n 的 对 称 正 定 矩 阵 \varepsilon(x_c,p)=\{x \mid (x-x_c)^Tp^{-1}(x-x_c) \leq 1\} \\ x,x_c \in R^n, P \in S^n_{++}\\ P的奇异值对应椭球的半周长,S^n_{++}为 n \times n的对称正定矩阵 ε(xc,p)={x(xxc)Tp1(xxc)1}x,xcRn,PS++nPS++nn×n

3、多面体和单纯形

多面体(Polyhedron)
P = { x ∣ a j T x ≤ b j , j = 1 , . . . , m c j T x = d j , j = 1 , . . . , r } P=\{x \mid a^T_jx \leq b_j,j=1,...,m\\ \space\space\space\space\ c^T_jx=d_j,j=1,...,r\} P={xajTxbj,j=1,...,m     cjTx=dj,j=1,...,r}
**单纯形(Simplex)**定义较为复杂
R n 空 间 中 选 择 v 0 , . . . , v k 共 k + 1 个 点 , v 1 − v 0 , . . . , v k − v 0 线 性 无 关 , 则 与 上 述 点 相 关 的 单 纯 形 为 : C = c o n v { v 0 , . . . , v k } = { θ 0 v 0 + . . . + θ k v k , θ ≥ 0 , 1 T θ = 1 } , θ ∈ R n R^n空间中选择v_0,...,v_k共k+1个点,\\ v_1-v_0,...,v_k-v_0线性无关,\\ 则与上述点相关的单纯形为:\\ C=conv\{v_0,...,v_k\}=\{\theta_0 v_0+...+\theta_k v_k, \theta \geq 0, 1^T \theta=1\},\theta \in R^n Rnv0,...,vkk+1v1v0,...,vkv0线C=conv{v0,...,vk}={θ0v0+...+θkvk,θ0,1Tθ=1},θRn
证明:一个单纯形是一种多面体
x ∈ C ∈ R n , C 为 s i m p l e x ⇔ x = θ 0 v 0 + . . . + θ k v k , 1 T θ = 1 , θ ≥ 0 , v 1 − v 0 , . . . , v k − v 0 线 性 无 关 x\in C \in R^n, C为simplex \\ \Leftrightarrow x=\theta_0 v_0+...+\theta_k v_k,1^T \theta=1,\theta \geq 0,\\v_1-v_0,...,v_k-v_0线性无关\\ xCRn,Csimplexx=θ0v0+...+θkvk,1Tθ=1,θ0,v1v0,...,vkv0线

定 义 : y = [ θ 1 , . . . , θ k ] T , y i ≥ 0 , 1 T y ≤ 1 B = [ v 1 − v 0 , . . . , v k − v 0 ] T ∈ R n × k x ∈ C ⇔ x = θ 0 v 0 + . . . + θ k v k = v 0 + θ 1 ( v 1 − v 0 ) + . . . + θ k ( v k − v 0 ) = v 0 + B y 定义:y=[\theta_1,...,\theta_k]^T,y_i \geq 0, 1^T y \leq 1 \\ B=[v_1-v_0,...,v_k-v_0]^T \in R^{n \times k} \\ x \in C \Leftrightarrow x=\theta_0 v_0+...+\theta_k v_k \\ = v_0+\theta_1(v_1-v_0)+...+\theta_k(v_k-v_0) \\ = v_0 + By y=[θ1,...,θk]T,yi0,1Ty1B=[v1v0,...,vkv0]TRn×kxCx=θ0v0+...+θkvk=v0+θ1(v1v0)+...+θk(vkv0)=v0+By

引入如下结论:
B = [ v 1 − v 0 , . . . , v k − v 0 ] 线 性 无 关 , 故 r a n k ( B ) = k ≤ n 对 于 非 奇 异 矩 阵 B , 一 定 存 在 一 个 矩 阵 A = [ I k 0 ] ∈ [ R k × k 0 ( n − k ) × k ] 使 得 A B = [ A 1 A 2 ] B = [ I k 0 ] B=[v_1-v_0,...,v_k-v_0]线性无关,故rank(B) = k \leq n \\ 对于非奇异矩阵B,一定存在一个矩阵\\ A=\left[ \begin{matrix} I_k \\ 0 \end{matrix} \right] \in \left[ \begin{matrix} R^{k \times k} \\ 0^{(n-k) \times k} \end{matrix} \right]\\ 使得 AB=\left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]B=\left[ \begin{matrix} I_k \\ 0 \end{matrix} \right] \\ B=[v1v0,...,vkv0]线,rank(B)=knBA=[Ik0][Rk×k0(nk)×k]使AB=[A1A2]B=[Ik0]
则对于前面得到的等式我们可以做如下变换:
x = v 0 + B y ⇒ A x = A v 0 + A B y ⇔ [ A 1 A 2 ] x = [ A 1 A 2 ] v 0 + [ A 1 B A 2 B ] y ⇔ { A 1 x = A 1 v 0 + y A 2 x = A 2 v 0 ⇔ { A 1 x ≥ A 1 v 0 1 T A 1 x ≤ 1 + 1 T A 1 v 0 A 2 x = A 2 v 0 ⇒ 由 不 等 式 和 等 式 构 成 , 是 多 面 体 x=v_0+By \\ \Rightarrow Ax=Av_0+ABy\\ \Leftrightarrow \left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]x=\left[ \begin{matrix} A_1 \\ A_2 \end{matrix} \right]v_0+\left[ \begin{matrix} A_1B \\ A_2B \end{matrix} \right]y\\ \Leftrightarrow \left\{ \begin{matrix} A_1x=A_1v_0+y\\ A_2x=A_2v_0 \end{matrix} \right.\\ \Leftrightarrow \left\{ \begin{matrix} A_1x \geq A_1v_0\\ 1^TA_1x \leq 1+1^TA_1v_0\\ A_2x=A_2v_0 \end{matrix} \right. \\ \Rightarrow 由不等式和等式构成,是多面体\\ x=v0+ByAx=Av0+ABy[A1A2]x=[A1A2]v0+[A1BA2B]y{A1x=A1v0+yA2x=A2v0A1xA1v01TA1x1+1TA1v0A2x=A2v0

4、一些对称矩阵

对称矩阵集合 S n = { x ∈ R n × n ∣ x = x T } S^n=\{x \in R^{n \times n} \mid x=x^T\} Sn={xRn×nx=xT}

对称半正定矩阵集合 S + n = { x ∈ R n × n ∣ x = x T , x ⪰ 0 } S^n_+=\{x \in R^{n \times n} \mid x=x^T,x \succeq 0\} S+n={xRn×nx=xT,x0}

对称正定矩阵集合 S + + n = { x ∈ R n × n ∣ x = x T , x ≻ 0 } S^n_{++}=\{x \in R^{n \times n} \mid x=x^T, x \succ 0\} S++n={xRn×nx=xT,x0}

证明: S + n S^n_+ S+n C o n v e x C o n e Convex \space Cone Convex Cone,即:
∀ θ 1 , θ 2 ≥ 0 , ∀ A , B ∈ S + n , 证 明 θ 1 A + θ 2 B ∈ S + n \forall \space\space \theta_1,\theta_2 \geq 0, \forall \space\space A,B \in S^n_+,证明 \space \theta_1A+\theta_2B \in S^n_+ \\   θ1,θ20,  A,BS+n, θ1A+θ2BS+n
证:
∀ x ∈ R n , x ≠ 0 , x T A x ≥ 0 , x T B x ≥ 0 x T ( θ 1 A + θ 2 B ) x = θ 1 x T A x + θ 2 x T B x ≥ 0 ⇒ 正 定 得 证 ( θ 1 A + θ 2 B ) T = ( θ 1 A T + θ 2 B T ) = ( θ 1 A + θ 2 B ) ⇒ 对 称 得 证 故 : θ 1 A + θ 2 B ∈ S + n \forall \space\space x \in R^n,x \neq 0, x^TAx \geq 0,x^TBx \geq 0 \\ x^T(\theta_1A+\theta_2B)x =\theta_1x^TAx+\theta_2x^TBx \geq 0 \Rightarrow 正定得证\\ (\theta_1A+\theta_2B)^T=(\theta_1A^T+\theta_2B^T)=(\theta_1A+\theta_2B)\Rightarrow 对称得证 \\ 故:\theta_1A+\theta_2B \in S^n_+   xRn,x=0,xTAx0,xTBx0xT(θ1A+θ2B)x=θ1xTAx+θ2xTBx0(θ1A+θ2B)T=(θ1AT+θ2BT)=(θ1A+θ2B)θ1A+θ2BS+n
S + + n S^n_{++} S++n不是 C o n v e x C o n e Convex \space Cone Convex Cone,是凸集
∀ x ∈ R n , x ≠ 0 , x T A x ≥ 0 , x T B x ≥ 0 x T ( θ 1 A + θ 2 B ) x = θ 1 x T A x + θ 2 x T B x ≯ 0 因 为 θ 1 , θ 2 = 0 时 θ 1 x T A x + θ 2 x T B x = 0 , 不 符 合 凸 锥 定 义 \forall \space\space x \in R^n,x \neq 0, x^TAx \geq 0,x^TBx \geq 0 \\ x^T(\theta_1A+\theta_2B)x =\theta_1x^TAx+\theta_2x^TBx \ngtr 0 \\ 因为\theta_1,\theta_2=0时\space \theta_1x^TAx+\theta_2x^TBx = 0,不符合凸锥定义   xRn,x=0,xTAx0,xTBx0xT(θ1A+θ2B)x=θ1xTAx+θ2xTBx0θ1,θ2=0 θ1xTAx+θ2xTBx=0

这篇关于凸优化3:几种重要凸集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/266523

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案