半定矩阵秩极小的非凸精确松弛

本文主要研究半定矩阵秩极小问题(P)的非凸精确松弛及其性质.首先,为求解问题(P),我们引入其Schatten p-范数(0＜p＜1)松弛,记为(Sp).其次,通过定义半定限制等距常数和半定限制正交常数,我们给出了问题(P)有唯—解的充分条件.最后,利用半定限制等距性质,我们给出了问题(P)和(Sp)有相同唯一解的充分条件.特别地,对任意0＜p＜1,我们还得到—个一致的精确恢复条件.     

稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。     

基于DC规划方法的稀疏临近支持向量机

为了提高临近支持向量机(PSVM)的数值表现,在PSVM的模型中引入了l_0-范数正则项,提出了稀疏临近支持向量机模型(SPSVM),从而提高分类器的特征选择能力。然而带有l_0-范数正则项的问题往往是NP-难问题,为了克服这一问题,采用非凸连续函数近似l_0-范数,并通过适当的DC分解将问题转化成DC规划问题进行求解,同时还讨论了算法的收敛性。数值实验结果表明不论是在仿真数据还是在实际数据中,所提出的方法是比较有效稳定的。     

锥-次预不变凸集值优化问题近似解的最优性条件[英文]

本文讨论相依上图导数形式下广义锥-预不变集值优化近似解的最优性条件问题. 首先, 引入锥-次预不变凸集值映射的概念, 并举例说明次类广义锥-凸性是锥-预不变凸性的推广. 其次, 得到了锥-次预不变凸集值映射的两个有用性质. 最后, 在锥-次预不变凸性条件下, 分别建立了集值优化问题强近似极小元和弱近似有效元的充分最优性条件.     

锥-次预不变凸集值优化问题近似解的最优性条件(英文)

本文讨论相依上图导数形式下广义锥-预不变集值优化近似解的最优性条件问题.首先,引入锥-次预不变凸集值映射的概念,并举例说明次类广义锥-凸性是锥-预不变凸性的推广.其次,得到锥-次预不变凸集值映射的两个有用性质.最后,在锥-次预不变凸性条件下,分别建立集值优化问题强近似极小元和弱近似有效元的充分最优性条件.     

地震时频分析的加权l_1范数稀疏正则化及交替方向乘子算法

地震时频分析在地震信号处理中具有重要意义.本文研究一种基于反演的稀疏算法来对反射地震记录进行时频分析.首先使用窗口逆Fourier变换来形成正演问题,然后建立一个加权l_1范数约束的最小化模型,用于求解未知模型参数向量(Fourier频率域系数).为了实现最小化问题,本文提出应用加权交替方向乘子法(ADMM)进行求解.数值试验部分针对短时Fourier变换(STFT)、连续小波变换(CWT)和本文提出的算法进行了对比结果分析.从比较结果可以看出,本文提出的优化模型和相关算法可以得到比STFT和CWT更高分辨率的地震数据的频谱分解.     

稀疏优化在数独中的应用

数独是一个难以求解的整数规划问题,可以通过实数编码的方式去除整数约束的限制,将整数规划模型转化为一个l0范数极小化模型.已有算法大多是求解松弛的l1范数极小化模型,只能求解部分数独问题.本文证明对于数独这样一个特殊的问题,lq(0＜q＜1)范数极小化模型等价于l0范数极小化模型,同时用l1/2-SLP(sequenti...     

具有线性化技术的三块非凸不可分优化问题BregmanADMM收敛性分析

交替方向乘子法是求解两块可分离凸优化问题的有效方法,但是对于三块不可分的非凸优化问题的交替方向乘子法的收敛性可能无法保证.该文主要研究的是用线性化广义Bregman交替方向乘子法(L-G-BADMM)求解目标函数是三块不可分的非凸极小化问题的收敛性分析.在适当假设条件下,对算法中子问题进行求解并构建满足Kurdyka-Lojasiewicz性质的效益函数,经过理论证明可以得到该算法的收敛性.     

带自由变量的广义几何规划全局求解的新算法

带自由变量的广义几何规划(FGGP)问题广泛出现在证券投资和工程设计等实际问题中.利用等价转换及对目标函数和约束函数的凸下界估计,提出一种求(FGGP)问题全局解的凸松弛方法.与已有方法相比,方法可处理符号项中含有更多变量的(FGGP)问题,且在最后形成的凸松弛问题中含有更少的变量和约束,从而在计算上更容易实现.最后数值实验表明文中方法是可行和有效的.     

线性方程组l_1范数问题的松弛投影算法及其应用

考虑线性方程组l_1范数问题的求解,在分别将其转化为一个分裂可行问题和凸可行问题的基础上,设计了几种松弛投影算法,然后将所设计的求解方法用于信号处理问题的求解上.     

带自由变量的广义几何规划问题的全局优化

对带自由变量的广义几何规划问题(FGGP)给出一全局优化算法.该算法先利用等价转换把(FGGP)中的自由变量转化为正变量,再通过凸化方案建立了(FGGP)的松弛凸规划(RCP).通过对(RCP)可行域的细分以及一系列(RCP)的求解过程,提出的算法收敛到(FGGP)的全局最优解,且数值例子表明了算法的可行性.     

co-radiant集的等价表示及其在向量优化问题中的应用

作为特殊的抽象凸(凹)集,radiant集和co-radiant集在抽象凸分析和多目标优化问题理论中发挥着重要作用.首先建立radiant集co-radiant集的等价刻画,从而推导出它们的重要性质.然后,将重要性质应用到向量优化问题近似解的刻画中,得到关于近似解集的等价刻画.     

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

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

近似锥-次类凸集值优化的严有效性

在Hausdorff局部凸拓扑线性空间中考虑约束集值优化问题(VP)的严有效性.在近似锥-次类凸假设下,利用凸集分离定理,分别得到了Kuhn-Tucker型和Lagrange型最优性条件,建立了与(VP)等价的两种形式的无约束优化.     

矫正低秩相关系数矩阵的松弛序列凸近似方法

本文主要讨论带有秩约束以及简单上下界约束的相关系数矩阵矫正问题的求解方法.该问题可以写成一个含有DC(两个凸函数之差)约束的优化问题,于是考虑利用求解DC优化问题的序列凸近似(SCA)方法求解.然而对本文讨论的问题,经典的序列凸近似方法收敛所需的约束规范不成立,于是,本文提出一种松弛的序列凸近似方法.本文证明当松弛参数趋于零时,松弛的DC问题的稳定点趋于原问题的稳定点.另一方面,可以利用序列凸近似方法求解松弛的DC问题.可以证明,序列凸近似方法生成的一系列凸子问题的解的聚点就是该松弛DC问题的稳定点.数值实验验证了该方法的有效性.     

基于最优D.C.分解的单二次约束非凸二次规划精确算法

本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果.     

拟凸向量值映射次微分性质及优化问题的最优性条件

本文研究了拟凸向量值映射的次微分及其拟凸向量优化问题的最优性条件.首先,引进恰当K-拟凸的概念,并利用△函数对其进行标量化,得到恰当K-拟凸的等价刻画.然后,给出拟凸向量值映射的四种次微分的定义,并研究了它们的性质.最后,利用拟凸向量值映射的次微分研究拟凸向量优化问题弱有效解的最优性条件,并用例子说明其合理性.     

一类半可微优化问题的解集

本文考虑线性约束条件下连续与半可微的伪线性(既伪凸又伪凹)函数的优化问题.使用伪线性函数的性质推导了解集的一般表达式,并基于用右侧导数代替既约梯度的广义凸单纯形法,给出了唯一解的条件以及当唯一性条件不满足时求出解集的计算步骤,最后给出了算例.     

广义模糊子半环的广义模糊双(内)理想

给出了广义模糊子半环的广义模糊双(内)理想的概念.运用截集、模糊子集的和与积得到了广义模糊子半环的广义模糊双(内)理想的等价条件及性质,同时还得到了在半环的同态映射下同态像及同态原像的性质.当λ=0,μ=1时,得到一般意义下的模糊子半环的模糊双(内)理想的相应结果.     

求线性比式和问题全局解的输出空间分枝定界算法

基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.