【作者】 申远；

【导师】 何炳生； 张寅；

【作者基本信息】 南京大学 ， 计算数学， 2012， 博士

【摘要】 许多现实世界中的问题可以转化为结构型优化求解,特别是在电子工程,统计,计算机科学等领域,具体的应用包括数字信号处理,信号增强,自然影像处理,矩阵处理,医学影像处理,交通网络分析等等。有效的解决这些问题是这些应用中的关键步骤,因此,为这些有着深刻应用背景的优化问题开发专用的高效算法十分重要。我们所考虑的这些结构型优化,或多或少,存在一些良好的结构可以加以利用,例如,可分性。虽然我们可以使用以内点算法为代表的标准算法来求解这些问题,并且效率通常不错。但是标准算法通常无法利用这些有利的结构。此外,一些标准算法,如内点算法,其固有的高计算复杂度使其并不适合求解大规模问题。因此,我们需要针对所需处理问题的具体结构有针对性地设计专门的算法。近年来,包括”向前向后分裂算法”,”增广拉格朗日乘子法”以及”邻近点算法”在内的一阶算法,已经吸引了越来越多的学者关注。由于只涉及一阶计算,相对于所求问题的规模,这些算法每步的计算量是比较低的,这使它们更适合处理大规模问题。而且这些算法己被广泛地研究,特别是从非线性规划的角度。这些研究提供了丰富的理论结果和大量的改进算法。此外,所求问题的良好结构如果被适当地加以利用,可以大大提高计算效率。然而,这些算法可能仍然有其局限性,例如,在使用增广拉格朗日乘子法的时候,其子问题的求解可能依然困难。一个可能的补救措施是引入不精确极小化准则,或者说放松子问题使其容易求解。特别的,在满足某些条件的时候,放松的子问题可以有显式解,因而是容易求解的。这些改进算法对于求解一部分问题是比较有效的,但是我们依然可以进一步改进它们。一方面,这些算法可能收敛较慢。另一方面,放松的子问题可能没有显式解。此外,子问题即使有显式解,也可能因为其中涉及到计算量较大的操作,如特征值分解,奇异值分解,而大大降低计算速度。因而我们尽量避免算法中出现这种操作。事实上,大多数上述(一阶)算法可以从变分不等式的角度来解释,作收敛性分析,并且可以归纳到一个统一的框架下面。在这一框架下,我们能够比较容易地分析现有算法的收敛性,并根据我们的需要建立新的算法。特别的,为了降低计算量,我们可以要求算法对于某类特定问题是”可以实施的”。或者说子问题是容易求解的,且计算量较低。在这篇论文中,我们考虑四种类型的优化问题,提出了一些新算法。数值试验表明,这些新算法在特定的应用中的计算效率超过了一些当今世界上的最先进算法。由于这些新算法都是专为某一类问题设计的,虽然这些算法被证明是有效和实用的,但它们并非通用的算法,也不是用来取代这些通用的算法。更多还原

【Abstract】 In the real world applications, there are quite a few structured optimizations aris-ing from the fields such as electrical engineering, statistics, and computer science, including digital signal processing, signal enhancement, natural imaging processing, matrix processing, medical imaging processing, and traffic network analysis, and etc. Solving such problem constitutes a critical step in an emerging methodology in these applications, hence, it is important to develop efficient algorithms for it. In this thesis, we consider four types of structured optimizations derived from the above applications.These optimization problems, more or less, have some favorable structures, e.g., separability. If we use the standard methods, such as interior-point methods, to solve these problems, these good structures could be totally ignored. Additionally, the stan-dard methods such as interior point methods are not directly amenable to large prob-lems due to their inherent high computational complexity.As a result, we need to develop dedicated algorithms that are able to handle the specific structure of the problem. In recent years, the first-order algorithms such as "forward-backward splitting method","augmented Lagrangian method", or "proximal point algorithm" have attracted more and more attentions from the researchers. In fact, the low per-iteration cost of these algorithms gives them better ability to handle large-scale problem. These algorithms have been extensively studied in the field of nonlinear programming, providing abundant theory and practical improvements. Additionally, the favorable structure of the problem under consideration can be utilized to simplify the subproblem.However, these algorithms could still have limitations, e.g., their subproblems can be difficult or expensive to solve. One remedy is allowing inexact minimization which is equivalent to solving a relaxed subproblem in each iteration, and we require the relaxed subproblem to be implementable, e.g., when the relaxed subproblem is simple enough to have a closed form solution. Although the algorithms based on above idea can work well for a few types of problems, it is still possible to improve them further. On one hand, the algorithms based on inexact minimization can suffer from the slow convergence. On the other hand, the relaxed subproblem may not always have a closed form solution.In fact, most of the above first-order algorithms can be interpreted from the aspect of variational inequality (VI), and their convergence analysis can be categorized into a unified framework. Under this framework, we are able to develop new algorithms based on our need. Specially, for saving the cost, we can require the algorithms to be implementable for the specific problem by taking the advantage of problem structure.In this thesis, we propose several such algorithms for four types of optimization problems, and demonstrate their efficiencies in the numerical experiments by compar-ing them with some state-of-the-art algorithms. Each of these algorithms is only for one type of problem, hence, they are not general-purpose methods, and not designed to replace the standard methods, however, for the specific problem they are designed for, these dedicated algorithms are proved to be efficient and practical.更多还原