Difference of convex functions algorithms (DCA) for image restoration via a Markov random field model

In this paper, we introduce a novel approach in the nonconvex optimization framework for image restoration via a Markov random field (MRF) model. While image restoration is elegantly expressed in the language of MRF’s, the resulting energy minimization problem was widely viewed as intractable: it exhibits a highly nonsmooth nonconvex energy function with many local minima, and is known to be NP-hard. The main goal of this paper is to develop fast and scalable approximation optimization approaches to a nonsmooth nonconvex MRF model which corresponds to an MRF with a truncated quadratic (also known as half-quadratic) prior. For this aim, we use the difference of convex functions (DC) programming and DC algorithm (DCA), a fast and robust approach in smooth/nonsmooth nonconvex programming, which have been successfully applied in various fields in recent years. We propose two DC formulations and investigate the two corresponding versions of DCA. Numerical simulations show the efficiency, reliability and robustness of our customized DCAs with respect to the standard GNC algorithm and the Graph-Cut based method—a more recent and efficient approach to image analysis.     

Mean-field annealing for phase unwrapping

Use of mean-field annealing theory is proposed for solving the phase-unwrapping (PU) problem. PU is formulated as a constrained optimization problem for the field of integer corrections to be added to the wrapped gradient field. A deterministic algorithm is described to provide an approximation of the average of the correction field over the global minima of the cost function. The proposed algorithm can be applied for any choice of the cost function. Using a cost function based on second-order differences, we obtain results close to those from simulated annealing and spend less computational time.     

一种超松弛原始对偶不动点算法及其应用

近年来,关于两个凸函数和的优化问题受到极大关注,其中一凸函数可微且其梯度满足 Lipschitz 连续性,另一凸函数包含有界线性算子。提出一种超松弛原始对偶不动点算法求解这一类问题,相比于原始对偶不动点算法,所提算法扩展了松弛参数的选择范围。通过定义合适的范数,运用非扩张算子不动点理论,证明所提迭代算法的收敛性,并证明算法的遍历收敛率。在对目标函数一些强的条件下,证明算法具有全局线性收敛率。最后,为验证算法的有效性和优越性,将所提算法运用于求解全变分图像复原模型,数值结果表明,选择松弛参数大于 $1$ (即超松弛) 的原始对偶不动点算法比松弛参数小于 $1$ 时算法收敛更快。     

Optimization‐based stability analysis of structures under unilateral constraints

This paper discusses an optimization‐based technique for determining the stability of a given equilibrium point of the unilaterally constrained structural system, which is subjected to the static load. We deal with the three problems in mechanics sharing the common mathematical properties: (i) structures containing no‐compression cables; (ii) frictionless contacts; and (iii) elastic–plastic trusses with non‐negative hardening. It is shown that the stability of a given equilibrium point of these structures can be determined by solving a maximization problem of a convex function over a convex set. On the basis of the difference of convex functions optimization, we propose an algorithm to solve the stability determination problem, at each iteration of which a second‐order cone programming problem is to be solved. The problems presented are solved for various structures to determine the stability of given equilibrium points. Copyright © 2008 John Wiley & Sons, Ltd.     

STRUCTURAL OPTIMIZATION USING A NEW LOCAL APPROXIMATION METHOD

A new method for solving structural optimization problems using a local function approximation algorithm is proposed. This new algorithm, called the Generalized Convex Approximation (GCA), uses the design sensitivity information from the current and previous design points to generate a sequence of convex, separable subproblems. The paper contains the derivation of the parameters associated with the approximation and the formulation of the approximated problem. Numerical results from standard test problems solved using this method are presented. It is observed that this algorithm generates local approximations which lead to faster convergence for structural optimization problems.     

Algorithms for separable convex optimization with linear ascending constraints

The paper considers the minimization of a separable convex function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios, and is a special case of an optimization of a separable convex function over the bases of a polymatroid with a certain structure. The paper generalizes a prior algorithm to a wider class of separable convex objective functions that need not be smooth or strictly convex. The paper also summarizes the state-of-the-art algorithms that solve this optimization problem. When the objective function is a so-called \(d{\text {-}}\)separable function, a simpler linear time algorithm solves the problem.     

Optimal joint replenishment policy for multiple non-instantaneous deteriorating items

In this paper, we deal with the problem of determining the optimal economic operating policy when a number of non-instantaneous deteriorating items are jointly replenished. We establish a multi-item joint replenishment model for non-instantaneous deteriorating items under constant demand rate allowing full backlogging. This problem is challenging, in particular, the cost function is a piecewise function with exponential parts, which makes the problem more complicated. To solve this problem, an approximation method is used to simplify the objective function and a bound-based heuristic algorithm is developed to solve the model. Numerical examples illustrate the effectiveness of the proposed method and the quality of the approximation. Experimental results on a real-life case study show that the proposed model can achieve substantial cost savings compared to the individual replenishment policy for non-instantaneous deteriorating items. Furthermore, sensitivity analysis of key parameters is carried out and the implications are discussed in detail.     

Order batching to minimize total travel time in a parallel-aisle warehouse

Although the picking of items may make up as much as 60% of all labor activities in a warehouse and may account for as much as 65% of all operating expenses, many order picking problems are still not well understood. Indeed, usually simple rules of thumb or straightforward constructive heuristics are used in practice, even in state-of-the-art warehouse management systems, however, it might well be that more attractive algorithmic alternatives could be developed. We address one such a fundamental materials handling problem: the batching of orders in a parallel-aisle warehouse so as to minimize the total traveling time needed to pick all items. Many heuristics have been proposed for this problem, however, a fundamental analysis of the problem is still lacking. In this paper, we first address the computational complexity of the problem. We prove that this problem is NP-hard in the strong sense but that it is solvable in polynomial time if no batch contains more than two orders. This result is not really surprising but it justifies the development of approximation and/or enumerative optimization algorithms for the general case. Our primary goal is to develop a branch-and-price optimization algorithm for the problem. To this end, we model the problem as a generalized set partitioning problem and present a column generation algorithm to solve its linear programming relaxation. Furthermore, we develop a new approximation algorithm for the problem. Finally, we test the performance of the branch-and-price algorithm and the approximation algorithm on a comprehensive set of instances. The computational experiments show the compelling performance of both algorithms.     

Lie group method: A new approach to image matching with arbitrary orientations

In this article, we develop a new method for image matching of any two images with arbitrary orientations. The idea comes from the workpiece localization in machining industry. We first describe an image as a 3D point set other than the common 2D function f(x, y), then, making the sets corresponding to the compared images form solid surfaces, we equivalently translate the matching problem into an optimization problem on the Lie group SE(3). Through developing a kind of steepest descent algorithms on a general Lie group, we present an practical algorithm for matching problem. Simulations of eye detection and face detection are presented to show the feasibility and efficiency of the proposed algorithm. © 2010 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 20, 245–252, 2010.     

约束全局优化问题的一个单参数填充函数方法

类似于无约束全局优化问题,本文给出了求解约束全局优化问题的一个填充函数方法,首先给出了约束全局优化问题的填充函数定义,在此定义的基础上提出了一个单参数填允函数.讨论了该函数的性质,并设计了一个填充函数算法,数值计算结果显示该算法是有效的和可行的.     

An Algorithm for the Proximity Operator in Hybrid TV-Wavelet Regularization,with Application to MR Image Reconstruction

Total variation (TV) and wavelet $L_1$ norms have often been used as regularization terms in image restoration and reconstruction problems. However, TV regularization can introduce staircase effects and wavelet regularization some ringing artifacts, but hybrid TV and wavelet regularization can reduce or remove these drawbacks in the reconstructed images. We need to compute the proximal operator of hybrid regularizations, which is generally a sub-problem in the optimization procedure. Both TV and wavelet $L_1$ regularisers are nonlinear and non-smooth, causing numerical difficulty. We propose a dual iterative approach to solve the minimization problem for hybrid regularizations and also prove the convergence of our proposed method, which we then apply to the problem of MR image reconstruction from highly random under-sampled k-space data. Numerical results show the efficiency and effectiveness of this proposed method.     

A quadratic approximation for structural topology optimization

In topology optimization, it is customary to use reciprocal‐like approximations, which result in monotonically decreasing approximate objective functions. In this paper, we demonstrate that efficient quadratic approximations for topology optimization can also be derived, if the approximate Hessian terms are chosen with care. To demonstrate this, we construct a dual SAO algorithm for topology optimization based on a strictly convex, diagonal quadratic approximation to the objective function. Although the approximation is purely quadratic, it does contain essential elements of reciprocal‐like approximations: for self‐adjoint problems, our approximation is identical to the quadratic or second‐order Taylor series approximation to the exponential approximation. We present both a single‐point and a two‐point variant of the new quadratic approximation. Copyright © 2009 John Wiley & Sons, Ltd.     

A method for simulation based optimization using radial basis functions

We propose an algorithm for the global optimization of expensive and noisy black box functions using a surrogate model based on radial basis functions (RBFs). A method for RBF-based approximation is introduced in order to handle noise. New points are selected to minimize the total model uncertainty weighted against the surrogate function value. The algorithm is extended to multiple objective functions by instead weighting against the distance to the surrogate Pareto front; it therefore constitutes the first algorithm for expensive, noisy and multiobjective problems in the literature. Numerical results on analytical test functions show promise in comparison to other (commercial) algorithms, as well as results from a simulation based optimization problem.     

基于凸包优化的盲源分离在图像去噪中的研究

目的针对高斯-脉冲混合噪声图像中难以有效去除大量奇异点或离群数据的问题,提出一种基于凸包优化的盲源分离方法来去除图像中的混合噪声。方法该方法把混合噪声和原图均看作未知的源信号,依据噪声图像中混合噪声与原图内容的加性关系建立盲源分离的模型,并利用凸包优化的方法构建源信号(凸包极点)的仿射包,然后通过最小化仿射包到凸包(噪声图像)上的投影误差,求解混合噪声和原图2个源信号,实现去噪混合噪声、复原原图的目的。结果实验结果发现,无论高斯-脉冲混合噪声强弱,该方法去噪复原后的峰值信噪比和平均结构相似性分别在39.9129 d B和0.9以上。结论由实验数据证实该方法可有效地从盲源分离的角度去除图像中高斯-脉冲混合噪声、复原原始图像。     

求解约束优化问题的退火遗传算法

针对基于罚函数遗传算法求解实际约束优化问题的困难与缺点,提出了求解约束优化问题的退火遗传算法。对种群中的个体定义了不可行度,并设计退火遗传选择操作。算法分三阶段进行,首先用退火算法搜索产生初始种群体,随后利用遗传算法使搜索逐渐收敛于可行的全局最优解或较优解,最后用退火优化算法对解进行局部优化。两个典型的仿真例子计算结果证明该算法能极大地提高计算稳定性和精度。     

Optimization of segmented constrained layer damping with mathematical programming using strain energy analysis and modal data

A new method for enhancement of damping capabilities of segmented constrained layer damping material is proposed. Constrained layer damping has been extensively used since many years to damp flexural vibrations. The shear deformation occurring in the viscoelastic core is mainly responsible for the dissipation of energy. Cutting both the constraining and the constrained layer, which leads to segmentation, increases the shear deformation at that position. This phenomenon is called edge effect. A two-dimensional model of a cantilever beam has been realized for further investigations. An optimization algorithm using mathematical programming is developed in order to identify a cuts arrangement that optimizes the loss factor. The damping efficiency is estimated using the modal strain energy method. The Nelder–Mead simplex method is used to find the best distribution of cuts. In order to take into account geometrical limitations, the exterior point penalty method is used to transform the constrained objective function into an unconstrained objective function. As the optimization problem is not convex, a modal analysis is performed at each mode in order to identify initial cuts positions that lead to a global minimum. Over a large frequency range, the algorithm is able to identify a distribution of cuts that optimizes the loss factor of each mode under consideration.     

线性约束LC1凸优化问题的内点信赖域算法

本文提出一种解线性约束凸规划的数值方法。通过将问题的KKT系统转化成一个约束方程,算法在每步迭代只需解一个线性方程组即可得到搜索方向。算法运用了信赖域方法利内点技术。在较弱的条件下,我们证明了算法的全局收敛性。     

A Bayesian Approach to Sequential Optimization based on Computer Experiments

Computer experiments are used frequently for the study and improvement of a process under study. Optimizing such process based on a computer model is costly, so an approximation of the computer model, or metamodel, is used. Efficient global optimization (EGO) is a sequential optimization method for computer experiments based on a Gaussian process model approximation to the computer model response. A long‐standing problem in EGO is that it does not consider the uncertainty in the parameter estimates of the Gaussian process. Treating these estimates as if they are the true parameters leads to an improper assessment of the precision of the approximation, a precision that is crucial to assess not only in optimization but in metamodeling in general. One way to account for these uncertainties is to use bootstrapping, studied by previous authors. Alternatively, some other authors have mentioned how a Bayesian approach may be the best way to incorporate the parameter uncertainty in the optimization, but no fully Bayesian approach for EGO has been implemented in practice. In this paper, we present a fully Bayesian implementation of the EGO method. The proposed Bayesian EGO algorithm is validated through simulation of noisy nonlinear functions and compared with the standard EGO method and the bootstrapped EGO. We also apply the Bayesian EGO algorithm to the optimization of a stochastic computer model. It is shown how a Bayesian approach to EGO allows one to optimize any function of the posterior predictive density. Copyright © 2014 John Wiley & Sons, Ltd.