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

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

相关文章

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

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

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

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

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

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

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3