一类混合0-1非凸二次约束二次规划问题的近似算法

研究一类混合0-1非凸二次约束二次规划问题的近似算法.该问题是在M个非凸二次约束与一个基数约束下,求解一个n维向量的极小范数,变量包含M个0-1变量与一个n维连续向量.该问题是NP-难的.在求解其半正定规划(SDP)松弛问题的基础上,提出了一种随机舍入算法,能够得到原始的问题的一个可行解.数值仿真实验结果表明该方法是十分有效的.     

非光滑向量均衡问题近似拟全局真有效解的最优性条件

本文研究一类非光滑向量均衡问题(Vector Equilibrium Problem)(VEP)关于近似拟全局真有效解的最优性条件.首先,利用凸集的拟相对内部型分离定理和Clarke次微分的性质,得到了问题(VEP)关于近似拟全局真有效解的最优性必要条件.其次,引入近似伪拟凸函数的概念,并给出具体实例验证其存在性,且在该凸性假设下建立了问题(VEP)关于近似拟全局真有效解的充分条件.最后,利用Tammer函数以及构建满足一定性质的非线性泛函,得到了问题(VEP)近似拟全局真有效解的标量化定理.     

关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题．通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案．     

基于LBFGS的求解最小闭包球的光滑化方法

考虑在n维空间中求m个球的最小闭包球(the Smallest Enclosing Ball,SEB)问题.首先将SEB问题转化为一个含有函数max(0,z)的等价无约束非光滑凸优化问题,然后利用光滑化技巧和有限内存BFGS方法来求解高维空间中的SEB问题,并分析了方法的收敛性.数值实验结果表明文中给出的算法是有效的.     

拉丁超立方体抽样混合遗传算法求解TSP问题

0引 言 旅行商问题(Traveling Salesman Problem：TSP)是十分重要的组合优化问题,它在计算机科学、运筹学及工程等领域都有着广泛的应用.巡回旅行商问题即给定一组N个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短.     

关于隐函数样条的凸性分析

本文讨论由隐函数样条F(x)=αg~h(x)-(1-α)f(x)=0,x∈R~(?),0<α<1定义的函数(Functional spline)的凸性,得到:1)当 g(x)=l_0(x),f(x)=multiply from j to k l_j(x),其中,l_j(x)=sum from i=1 to n a_(ij)x_i+b_j 是线性的,且 (?)(x)≥0围成区域Ω,那么在Ω内,当 h>k 时,F(x)=αg~h(x)-(1-α)f(x)=0是凸的;2)在 R~2内,若 f(x,y)=0,g(x,y)=0定义两条凸曲线,那么隐函数样条不一定是凸的.但可以构造 f_1,g_1,使得 f_1与 f 定义同一条曲线,g_1与 g 也定义同一条曲线,而这时的隐函数样条是凸的.本文还给出了一个凸样条的充分条件.     

具有无界梯度的拟共形调和映照

设f=h+g为单位圆盘U到凸区域上的调和映照,其中h和g为U上的解析函数且满足g(0)=0.本文首先给出f的梯度Λ_f具有控制增长函数1/(1-|x|)~α(其中z∈U,0≤α≤1)时的一个等价刻画,进而得到了v-Bloch调和映照成为拟共形映照的条件.特别地,当v=0时,f即为双向Lipschitz映照.进一步地,本文还给出了当f(U)为一般区域(未必是凸)而h为凸映照时f成为拟共形映照的充分必要条件.     

线性等式与不等式组稀疏解的唯一性条件

近年来,稀疏优化广泛应用在信号处理、机器学习、图像去噪和计算机视觉等方面,得到了深入的研究和快速的发展.本文考虑含有一般线性等式和不等式约束的广义l_(0-)最小化问题.尽管l_(0-)最小化问题是NP-困难的,但已有多种计算方法可以用来克服这一计算上的困难,其中一种常用的方法是,通过一个凸优化问题来近似求解原问题.具体地,用l_(1-)范数代替l_(0-)范数得到l_(0-)最小化问题的一个凸松弛.在这类方法中,研究什么条件可以保证两个问题等价是非常重要的.基于值域空间性质(RSP)的分析方法,本文提出广义l_(0-)最小化问题的RSP性质,并且证明在某些条件下,RSP性质可以保证l_(0-)最小化问题与它的凸松弛l_(1-)最小化问题是等价的.最后,本文对所使用的条件给出一些说明.     

紧流形上的Schrodinger算子的谱间隙估计

M是一个n维紧黎曼流形,具有严格凸边界,且Ricci曲率不小于(n-1)K(其中K≥0为某个常数).假定Schrodinger算子的Dirichlet (或Robin)特征值问题的第一特征函数f1在M上是对数凹的,该文得到了此类Schrodinger算子的前两个Dirichlet(或Robin)特征值之差的下界估计,这推广了最近Andrews等人在R^n中有界凸区域上关于Laplace算子的一个相应结果[4].     

关于凸像共形映照的掩蔽性质

<正> 1.设G是复数W平面上的一个凸形区域.假如通过G的一个境界点有一个圆周把G合在它的内部,那末这个圆周是 G 在此境界点的支持圆周.设在 G 的每一个境界点都有一个半径不超过ρ(ρ>0)的支持圆周,并且有一个点,其支持圆周的半径不能小于ρ,那末称 G 是一由半径为ρ的圆所支持的凸形区域.我们又简称这种区域为支持半径为ρ的区域.当ρ=∞时圆周化成直线,每一凸形区域都为一个半平面所支持.     

The smallest triangular cover for triangles of diameter one

A convex region covers a family of curves if it contains a congruent copy of each curve in the family, and a “worm problem” for that family is to find the convex region of smallest area. In this paper, we find the smallest triangular cover of any prescribed shape for the familyS of all triangles of diameter 1.     

The Worm Problem of Leo Moser

One of Leo Moser's geometry problems is referred to as the Worm Problem [10]: “What is the (convex) region of smallest area which will accommodate (or cover) every planar arc of length 1?” For example, it is easy to show that the circular disk with diameter 1 will cover every planar arc of length 1. The area of the disk is approximately 0.78539. Here we show that a solution to the Worm Problem of Moser is a region with area less than 0.27524.     

A Small Cover for Convex Unit Arcs

An arc in the plane is convex if it is simple (i.e., one–one except that its endpoints may coincide) and lies on the boundary of its convex hull. We describe a compact convex plane set of area about 0.2466 that contains a congruent copy of each convex plane arc of unit length, a reduction of about 1.1% from the smallest such set previously known.     

凸集的广义Reuleaux三角形

常宽凸集的面积最小者为Reulaux三角形，而非常宽凸集的面积最小者为何呢？它就是本文将给出的广义Reuleaux三角形△R。     

The perimeter of rounded convex planar sets

A convex set is inscribed into a rectangle with sides a and 1/a so that the convex set has points on all four sides of the rectangle. By “rounding” we mean the composition of two orthogonal linear transformations parallel to the edges of the rectangle, which makes a unit square out of the rectangle. The transformation is also applied to the convex set, which now has the same area, and is inscribed into a square. One would expect this transformation to decrease the perimeter of the convex set as well. Interestingly, this is not always the case. For each a we determine the largest and smallest possible increase of the perimeter.      

平面凸集存在最小凸生成集的充要条件

本文在平面上解决了StevenRLay在 [1 ]中提出的开放性问题“什么样的凸集存在唯一的最小凸生成子集” ,给出并证明了“平面上的凸集存在唯一的最小凸生成子集”的一个充要条件 .同时证明了En 中的开集一定不存在最小凸生成集 .     

The convex dimension of a graph

The convex dimension of a graph G=(V,E) is the smallest dimension d for which G admits an injective map f:V?R^d of its vertices into d-space, such that the barycenters of the images of the edges of G are in convex position. The strong convex dimension of G is the smallest d for which G admits a map as above such that the images of the vertices of G are also in convex position. In this paper we study the convex and strong convex dimensions of graphs.     

Linear Inequalities for Rank 3 Geometric Lattices

The flag Whitney numbers (also referred to as the flag f-numbers) of a geometric lattice count the number of chains of the lattice with elements having specified ranks. We give a collection of inequalities which imply all the linear inequalities satisfied by the flag Whitney numbers of rank 3 geometric lattices. We further describe the smallest closed convex set containing the flag Whitney numbers of rank 3 geometric lattices as well as the smallest closed convex set containing the flag Whitney numbers of those lattices corresponding to oriented matroids.     

Planar Location Problems with Block Distance and Barriers

This paper considers one facility planar location problems using block distance and assuming barriers to travel. Barriers are defined as generalized convex sets relative to the block distance. The objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. The problem is solved by modifying the barriers to obtain an equivalent problem and by decomposing the feasible region into a polynomial number of convex subsets on which the objective function is convex. It is shown that solving a planar location problem with block distance and barriers requires at most a polynomial amount of additional time over solving the same problem without barriers.     

Iteration-complexity of first-order penalty methods for convex programming

This paper considers a special but broad class of convex programming problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. It studies the computational complexity of quadratic penalty based methods for solving the above class of problems. An iteration of these methods, which is simply an iteration of Nesterov’s optimal method (or one of its variants) for approximately solving a smooth penalization subproblem, consists of one or two projections onto the simple convex set. Iteration-complexity bounds expressed in terms of the latter type of iterations are derived for two quadratic penalty based variants, namely: one which applies the quadratic penalty method directly to the original problem and another one which applies the latter method to a perturbation of the original problem obtained by adding a small quadratic term to its objective function.