凸优化基础之计算几何、凸集、凸函数、凸规划

2023-10-30 21:00

本文主要是介绍凸优化基础之计算几何、凸集、凸函数、凸规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、计算几何
    • 1.什么是计算几何
    • 2.计算几何理论中过两点的一条直线的表达式,是如何描述的?
  • 二、凸集
    • 1.什么是凸集
    • 2.如何表达三维空间中的一个平面
    • 3.如何表达超平面
    • 4.什么是凸函数及如何判别
    • 5.什么是凸规划及如何判别

一、计算几何

1.什么是计算几何

计算几何是计算机理论科学的一个重要分支.自20世纪70年代末从算法设计与分析中独立出来起,不到30年,该学科已经有了巨大的发展,不仅产生了一系列重要的理论成果,也在众多实际领域中得到了广泛的应用.
计算几何基本概念和常用算法包括如下内容:
矢量的概念
矢量加减法
矢量叉积
折线段的拐向判断
判断点是否在线段上
判断两线段是否相交
判断线段和直线是否相交
判断矩形是否包含点
判断线段、折线、多边形是否在矩形中
判断矩形是否在矩形中
判断圆是否在矩形中
判断点是否在多边形中
判断线段是否在多边形内
判断折线是否在多边形内
判断多边形是否在多边形内
判断矩形是否在多边形内
判断圆是否在多边形内
判断点是否在圆内
判断线段、折线、矩形、多边形是否在圆内
判断圆是否在圆内
计算点到线段的最近点
计算点到折线、矩形、多边形的最近点
计算点到圆的最近距离及交点坐标
计算两条共线的线段的交点
计算线段或直线与线段的交点
求线段或直线与折线、矩形、多边形的交点
求线段或直线与圆的交点
凸包的概念
凸包的求法

想要深入了解这些内容可参考这个博客

2.计算几何理论中过两点的一条直线的表达式,是如何描述的?

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内。前者保证Q点在直线P1P2上,后者是保证Q点不在线段P1P2的延长线或反向延长线上,对于这一步骤的判断可以用以下过程实现:

ON-SEGMENT(pi,pj,pk)

if min(xi,xj) <= xk <= max(xi,xj) and min(yi,yj) <= yk <= max(yi,yj)

then return true;

else return false;

特别要注意的是,由于需要考虑水平线段和垂直线段两种特殊情况,min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。

二、凸集

1.什么是凸集

集合C中任两点之间的点仍在C中,称C为凸集。
即x.x∈C,成+(1-0)xq∈C, 其中θ∈[:1]b 显然仿射集是凸集。
凸组合 ∑ θ i X i \sum^{}_{}\theta_iX_i θiXi,其中 ∑ θ i \sum^{}_{}θ_i θi,的值为1。
集合C是凸集<=>C包含其任意点的凸组合
凸包,C为任意集合,
c n o v C = ∑ θ i X i ∣ X i ∈ C z , θ i ≥ 0 , θ i = 1 cnov C= {\sum^{}_{}\theta_iX_i |X_i\in C_z, \theta_i \geq0 ,\theta_i=1 } cnovC=θiXiXiCz,θi0,θi=1
凸包是包含集合C的最小的凸集

直线的表示: y = θ x 1 + ( 1 − θ ) x 2 , θ ∈ R , y= \theta x_1 + (1-\theta)x_2, \theta \in R, y=θx1+(1θ)x2,θR,
直线是仿射集,而仿射集一定是凸集,所以直线是凸集。

2.如何表达三维空间中的一个平面

三维空间中的平面由两个量确定:
① 一个法向量(垂直于该平面的向量)
② 一个已知点(位于该平面上的一个点)
平面法向量为: n → = { 1 2 3 } ⊤ (3) \overrightarrow{n}= \begin{Bmatrix} 1 & 2 & 3 \end{Bmatrix} \tag{3}\top n ={1<

这篇关于凸优化基础之计算几何、凸集、凸函数、凸规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

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