A new algorithm for computing the convex hull of a planar point set

When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.

The Ellipsoidal Invariant Set of Fractional Order Systems Subject to Actuator Saturation:The Convex Combination Form

The domain of attraction of a class of fractional order systems subject to saturating actuators is investigated in this paper. We show the domain of attraction is the convex hull of a set of ellipsoids. In this paper, the Lyapunov direct approach and fractional order inequality are applied to estimating the domain of attraction for fractional order systems subject to actuator saturation. We demonstrate that the convex hull of ellipsoids can be made invariant for saturating actuators if each ellipsoid with a bounded control of the saturating actuators is invariant. The estimation on the contractively invariant ellipsoid and construction of the continuous feedback law are derived in terms of linear matrix inequalities (LMIs). Two numerical examples illustrate the effectiveness of the developed method. © 2014 Chinese Association of Automation.

基于凸包理论的含风电电力系统负荷恢复方案优化

大停电事故后,合理的负荷恢复策略对加快电力系统恢复、减少停电损失具有重要意义。针对标准交流潮流方程的非凸性导致负荷恢复模型求解效率低的问题,提出了基于凸包理论的含风电电力系统负荷恢复方案优化方法。首先,简要介绍了凸包理论以及非线性函数的凸包构建方法。其次,针对风电出力的不确定性,采用条件风险价值理论处理风电波动带来的风险,进而建立了直角坐标系下基于凸包理论的电力系统负荷恢复二阶锥优化模型,其中,交流潮流方程中的非线性项采用凸包表达。针对无法精确确定凸包参数的问题,提出了基于迭代更新的参数优化方法,减少因凸包引入的松弛误差。所提出的模型为混合整数二阶锥规划模型,可采用商业求解器高效求解。最后,采用IEEE 39节点系统和改进的广东电力系统验证了所提出模型的有效性。

颌骨重建中的图像分割和轮廓对应及分支问题

根据人体颌骨的形状特征 ,提出一系列有针对性的方法 ,在CT断层数据的基础上重建三维表面模型 研究的内容包括医学图像的分割和从轮廓线重建表面两个方面 首先 ,采用一种称为“非种子区域分割”方法提取物体的轮廓线 ;然后 ,建立一条反应颌骨走向的弓形“参照基准线” ,充分利用轮廓线相对于它的“归一化位置”信息解决表面重建中的对应和分支问题 ;同时考虑相邻层的影响 ,使生成的表面更加光滑、自然 最后 ,提出“多阶凸包点对应匹配”的思想 。

序凸集与锥的正规性

研究了序凸集的一些运算性质，得到了紧序凸集的序端点表示定理．定理2紧序凸集是其所有序端点的序凸包．还利用序凸集给出了正规锥的两个特征性质．定理3实Banach空间E的锥P是正规的当且仅当E的任何有界集的序凸包是有界的．定理4实Banach空间E的锥P是正规的当且仅当E是局部序凸的，即E有一个序凸的零点邻域基．

求解大规模机组组合问题的二阶锥规划方法

基于混合整数二阶锥规划(mixed integer second-order cone programming,MI-SOCP)提出一种求解电力系统计及爬坡约束机组组合问题(unit commitment,UC)的新方法。利用UC问题的混合整数二次规划(mixed integer quadratic programming,MI-QP)模型和一个简单混合整数集合的凸包表示,产生UC问题一个更紧的MI-SOCP模型。将最小覆盖不等式作为割平面,应用内点割平面法求解MI-SOCP以获得不计爬坡约束UC问题的机组启停状态。为满足爬坡约束,提出一种简单易行的机组启停状态修正方法。100机组96时段等多个系统的仿真结果表明,利用内点割平面法求解2种模型时,MI-SOCP能比MI-QP获得质量更好的次优解,所提方法能有效处理爬坡约束,适用于大规模的UC问题。

用优化凸包法作B-Spline曲线的求交运算

本文在分析B-Spline曲线所具有的几何特性的基础上,提出了用优化凸包方法,作B-Spline曲线的求交运算,内容包括B-Spline曲线与直线求交、B-Spline曲线与圆弧求交及B-Spline曲线与B-Spline曲线求交。 本算法主要从工程应用的实用性出发,首先将B-Spline曲线作离散处理,然后为了提高求交速度,依据其理论,对B样条曲线的凸包多边形进行了优化处理,使得凸包多边形的包括范围大为减小,在判断该优化凸包是否与直线、圆弧或另一样条曲线段的优化凸包相交的前提下,作求交运算。求交精度随B-Spline曲线离散精度的提高而提高。

一种用于电-气互联系统运行优化的动态收缩凸松弛算法

提出了一种动态收缩凸松弛算法来解决电-气互联系统的运行优化问题。模型建立中,考虑了新能源与储能元件接入以及管存和气流方向等运行约束。所提算法利用了二阶锥松弛和凸包松弛的方法将非凸约束转换为凸约束,并通过动态收缩求解算法将电-气互联系统的运行优化问题转化为精确松弛域内的混合整数二阶规划问题加以求解。算例测试中,分别以修改的IEEE 39节点与IEEE 118节点电力系统和比利时20节点天然气系统组成的2个电-气互联系统为例,通过仿真验证了该算法有较佳的松弛精度和较快的计算速度。