多重集非凸分裂可行问题的非精确均值投影算法

在本文中,我们引入了非精确均值投影算法来求解多重集非凸分裂可行问题,其中这些非凸集合为半代数邻近正则集合.通过借助著名的Kurdyka-Lojasiewicz不等式理论,我们建立了算法的收敛性.     

一类新的广义非凸集值变分不等式组

本文的主要目的是引入一类广义非凸集值变分不等式.首先,我们把这类广义非凸集值变分不等式等价的转化为不动,点问题,通过构造一种新的扰动投影算法,在一定条件下,我们证明了所给迭代算法是收敛的.     

广义非凸变分不等式解的存在性与投影算法

本文运用Banach压缩映象原理和投影技巧研究一类新的广义非凸变分不等式问题解的存在唯一性,并在非凸集上建立一个逼近广义非凸变分不等式解的三步投影算法,在一定条件下证明了该投影算法所产生的迭代序列的收敛性.     

可分离凸优化问题的非精确平行分裂算法

针对一类可分离凸优化问题提出了一种非精确平行分裂算法.该算法充分利用了所求解问题的可分离结构,并对子问题进行非精确求解.在适当的条件下,证明了所提出的非精确平行分裂算法的全局收敛性,初步的数值实验说明了算法有效性.     

非凸约束优化的随机近似算法

在人工智能、科学计算等领域,众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂,同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来,结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类:基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结,简要地介绍相关算法的设计思想和基本的理论性质,如渐近收敛性理论、复杂度理论等。     

Hilbert空间中的非严格凸情况的Uzawa算法

无穷维空间中目标泛函为严格凸时的Uzawa算法已由Bensoussan等提出.一般说来,对于普通凸泛函,这种算法无效.这是因为在非严格凸情况时,对偶泛函一般是不可微的.本文提出Hilbert空间中的非严格凸情况的Uzawa算法.对于可分离问题,我们就得到了价格分解方法.考虑问题这里,     

一类约束非光滑优化的非单调信赖域算法

提出了求解一类带一般凸约束的复合非光滑优化的信赖域算法 .和通常的信赖域方法不同的是 :该方法在每一步迭代时不是迫使目标函数严格单调递减 ,而是采用非单调策略 .由于光滑函数、逐段光滑函数、凸函数以及它们的复合都是局部Lipschitz函数 ,故本文所提方法是已有的处理同类型问题 ,包括带界约束的非线性最优化问题的方法的一般化 ,从而使得信赖域方法的适用范围扩大了 .同时 ,在一定条件下 ,该算法还是整体收敛的 .数值实验结果表明 :从计算的角度来看 ,非单调策略对高度非线性优化问题的求解非常有效     

图像处理中全变差正则化数据拟合问题算法回顾

全变差正则化数据拟合问题产生于许多图像处理任务,如图像去噪、去模糊、图像修复、磁共振成像、压缩图像感知等.近年来,求解此类问题的快速高效算法发展很快.以最小二乘、最小一乘等为例简要回顾求解此类问题的主要算法,并讨论一个全变差正则化非凸数据拟合模型在脉冲噪声图像去模糊问题中的应用.     

动力下降制导问题的两阶段序列凸化方法

可重复使用火箭技术是近五年来航天工程领域的焦点话题.以三自由度燃料最优控制问题为具体模型,本文研究火箭回收中的关键问题—动力下降制导问题的求解.由于此模型中包含非凸动力学约束(带空气阻力项)、非凸推力大小和方向控制约束等,直接求解方法难以满足工程上实时性的需求.为了消除非凸性带来的困难,本文通过无损凸化、时间离散化和线性化技术将问题转化为一类凸规化问题,即二阶锥规划问题进行求解.此外,为了避免传统的序列凸化策略在求解本文模型时的数值不稳定现象,本文提出一个新的两阶段序列凸化方法.数值结果表明所提方法仅需求解少量的凸规化问题,且拥有比单阶段方法更稳定和高效的数值表现.     

关于非凸的有限理性的稳定性

关于有限理性方面的文献, 大多数都是在满足凸性条件下研究有限理性的相关性质, 在一定程度上限制了其应用范围. 应用Ekeland变分原理, 减弱了有限理性模型的假设条件, 考虑在不满足凸性条件下的有限理性模型的稳定性问题. 具体给出了非凸的Ky Fan点问题解的稳定性, 非凸非紧的Ky Fan点问题解的稳定性, 非凸向量值函数Ky Fan点解的稳定性和非凸非紧向量值函数Ky Fan点解的稳定性. 作为应用, 还给出了非凸的n人非合作博弈有限理性模型解的稳定性和非凸的多目标博弈有限理性模型解的稳定性.     

Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms

Two-phase image segmentation is a fundamental task to partition an image into foreground and background. In this paper, two types of nonconvex and nonsmooth regularization models are proposed for basic two-phase segmentation. They extend the convex regularization on the characteristic function on the image domain to the nonconvex case, which are able to better obtain piecewise constant regions with neat boundaries. By analyzing the proposed non-Lipschitz model, we combine the proximal alternating minimization framework with support shrinkage and linearization strategies to design our algorithm. This leads to two alternating strongly convex subproblems which can be easily solved. Similarly, we present an algorithm without support shrinkage operation for the nonconvex Lipschitz case. Using the Kurdyka-Łojasiewicz property of the objective function, we prove that the limit point of the generated sequence is a critical point of the original nonconvex nonsmooth problem. Numerical experiments and comparisons illustrate the effectiveness of our method in two-phase image segmentation.     

A “Nonconvex+Nonconvex” approach for image restoration with impulse noise removal

In this paper, we propose a new method for image restoration problems, which are degraded by impulsive noise, with nonconvex data fitting term and nonconvex regularizer.The proposed method possesses the advantages of nonconvex data fitting and nonconvex regularizer simultaneously, namely, robustness for impulsive noise and efficiency for restoring neat edge images.Further, we propose an efficient algorithm to solve the “Nonconvex+Nonconvex” structure problem via using the alternating direction minimization, and prove that the algorithm is globally convergent when the regularization parameter is known. However, the regularization parameter is unavailable in general. Thereby, we combine the algorithm with the continuation technique and modified Morozov’s discrepancy principle to get an improved algorithm in which a suitable regularization parameter can be chosen automatically. The experiments reveal the superior performances of the proposed algorithm in comparison with some existing methods.     

Non-Convex Global Minimization and False Discovery Rate Control for the TREX

The TREX is a recently introduced method for performing sparse high-dimensional regression. Despite its statistical promise as an alternative to the lasso, square-root lasso, and scaled lasso, the TREX is computationally challenging in that it requires solving a nonconvex optimization problem. This article shows a remarkable result: despite the nonconvexity of the TREX problem, there exists a polynomial-time algorithm that is guaranteed to find the global minimum. This result adds the TREX to a very short list of nonconvex optimization problems that can be globally optimized (principal components analysis being a famous example). After deriving and developing this new approach, we demonstrate that (i) the ability of the preexisting TREX heuristic to reach the global minimum is strongly dependent on the difficulty of the underlying statistical problem, (ii) the new polynomial-time algorithm for TREX permits a novel variable ranking and selection scheme, (iii) this scheme can be incorporated into a rule that controls the false discovery rate (FDR) of included features in the model. To achieve this last aim, we provide an extension of the results of Barber and Candes to establish that the knockoff filter framework can be applied to the TREX. This investigation thus provides both a rare case study of a heuristic for nonconvex optimization and a novel way of exploiting nonconvexity for statistical inference.     

Minimization of the sum of three linear fractional functions

In this paper, we will propose an efficient and reliable heuristic algorithm for minimizing and maximizing the sum of three linear fractional functions over a polytope. These problems are typical nonconvex minimization problems of practical as well as theoretical importance. This algorithm uses a primal-dual parametric simplex algorithm to solve a subproblem in which the value of one linear function is fixed. A subdivision scheme is employed in the space of this linear function to obtain an approximate optimal solution of the original problem. It turns out that this algorithm is much more efficient and usually generates a better solution than existing algorithms. Also, we will develop a similar algorithm for minimizing the product of three linear fractional functions.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.     

A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis

We consider the problem of subspace clustering with data that is potentially corrupted by both dense noise and sparse gross errors. In particular, we study a recently proposed low rank subspace clustering approach based on a nonconvex modeling formulation. This formulation includes a nonconvex spectral function in the objective function that makes the optimization task challenging, e.g., it is unknown whether the alternating direction method of multipliers (ADMM) framework proposed to solve the nonconvex model formulation is provably convergent. In this paper, we establish that the spectral function is differentiable and give a formula for computing the derivative. Moreover, we show that the derivative of the spectral function is Lipschitz continuous and provide an explicit value for the Lipschitz constant. These facts are then used to provide a lower bound for how the penalty parameter in the ADMM method should be chosen. As long as the penalty parameter is chosen according to this bound, we show that the ADMM algorithm computes iterates that have a limit point satisfying first-order optimality conditions. We also present a second strategy for solving the nonconvex problem that is based on proximal gradient calculations. The convergence and performance of the algorithms is verified through experiments on real data from face and digit clustering and motion segmentation.     

Nonconvex Piecewise-Quadratic Underestimation for Global Minimization

Motivated by the fact that important real-life problems, such as the protein docking problem, can be accurately modeled by minimizing a nonconvex piecewise-quadratic function, a nonconvex underestimator is constructed as the minimum of a finite number of strictly convex quadratic functions. The nonconvex underestimator is generated by minimizing a linear function on a reverse convex region and utilizes sample points from a given complex function to be minimized. The global solution of the piecewise-quadratic underestimator is known exactly and gives an approximation to the global minimum of the original function. Successive shrinking of the initial search region to which this procedure is applied leads to fairly accurate estimates, within 0.0060%, of the global minima of synthetic nonconvex functions for which the global minima are known. Furthermore, this process can approximate a nonconvex protein docking function global minimum within four-figure relative accuracy in six refinement steps. This is less than half the number of refinement steps required by previous models such as the convex kernel underestimator (Mangasarian et al., Computational Optimization and Applications, to appear) and produces higher accuracy here.     

泊松化图像复原的交替最小化算法

为了快速地去除图像中的泊松噪声,本文在传统的交替方向算法基础上,结合松弛算法提出了一个改进的快速交替最小化算法.与经典的数值算法相比,数值试验表明提出的新算法不但能有效地实现泊松化图像复原,还能大幅度地提高数值计算的速率,并显著地减少电脑的CPU运行时间.     

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikin’s affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

包含FR方法的一类无约束极小化方法的全局收敛性

本文对包含Fletcher-Reeves共轭梯度法的一类无约束最优化方法的全局收敛性进行了研究．Fletcher-Reeves方法的某些性质在收敛性分析中起着重要的作用．我们以一种简单的方式证明了这类方法在一种Wolfe型非精确线搜索条件下对光滑的非凸函数具有下降性和全局收敛性．全局收敛性结果也被推广到了一种广义Wolfe型非精确线搜索．