An Optimization Model for the Strip-packing Problem and Its Augmented Lagrangian Method

This paper formulates a two-dimensional strip packing problem as a non- linear programming （NLP） problem and establishes the first-order optimality conditions for the NLP problem. A numerical algorithm for solving this NLP problem is given to find exact solutions to strip-packing problems involving up to 10 items. Approximate solutions can be found for big-sized problems by decomposing the set of items into small-sized blocks of which each block adopts the proposed numerical algorithm. Numerical results show that the approximate solutions to big-sized problems obtained by this method are superior to those by NFDH, FFDH and BFDH approaches.

The Rate of Convergence of Augmented Lagrangian Method for Minimax Optimization Problems with Equality Constraints

The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints.We prove that,under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem,for a given multiplier vectorμ,the rate of convergence of the augmented Lagrangian method is linear with respect to||μu-μ^(*)||and the ratio constant is proportional to 1/c when the ratio|μ-μ^(*)||/c is small enough,where c is the penalty parameter that exceeds a threshold c_(*)>O andμ^(*)is the multiplier corresponding to a local minimizer.Moreover,we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters(ck)is bounded and the convergence rate is superlinear if(ck)is increasing to infinity.Finally,we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.

A Fast Augmented Lagrangian Method for Euler’s Elastica Models

In this paper,a fast algorithm for Euler’s elastica functional is proposed,in which the Euler’s elastica functional is reformulated as a constrained minimization problem.Combining the augmented Lagrangian method and operator splitting techniques,the resulting saddle-point problem is solved by a serial of subproblems.To tackle the nonlinear constraints arising in the model,a novel fixed-point-based approach is proposed so that all the subproblems either is a linear problem or has a closed-form solution.We show the good performance of our approach in terms of speed and reliability using numerous numerical examples on synthetic,real-world and medical images for image denoising,image inpainting and image zooming problems.

Fast Linearized Augmented Lagrangian Method for Euler’s Elastica Model

Recently,many variational models involving high order derivatives have been widely used in image processing,because they can reduce staircase effects during noise elimination.However,it is very challenging to construct efficient algo-rithms to obtain the minimizers of original high order functionals.In this paper,we propose a new linearized augmented Lagrangian method for Euler’s elastica image denoising model.We detail the procedures of finding the saddle-points of the aug-mented Lagrangian functional.Instead of solving associated linear systems by FFTor linear iterative methods(e.g.,the Gauss-Seidel method),we adopt a linearized strat-egy to get an iteration sequence so as to reduce computational cost.In addition,we give some simple complexity analysis for the proposed method.Experimental results with comparison to the previous method are supplied to demonstrate the efficiency of the proposed method,and indicate that such a linearized augmented Lagrangian method is more suitable to deal with large-sized images.

Augmented Lagrangian Methods for p-Harmonic Flows with the Generalized Penalization Terms and Application to Image Processing

In this paper,we propose a generalized penalization technique and a convex constraint minimization approach for the p-harmonic flow problem following the ideas in[Kang&March,IEEE T.Image Process.,16(2007),2251–2261].We use fast algorithms to solve the subproblems,such as the dual projection methods,primal-dual methods and augmented Lagrangian methods.With a special penalization term,some special algorithms are presented.Numerical experiments are given to demonstrate the performance of the proposed methods.We successfully show that our algorithms are effective and efficient due to two reasons:the solver for subproblem is fast in essence and there is no need to solve the subproblem accurately(even 2 inner iterations of the subproblem are enough).It is also observed that better PSNR values are produced using the new algorithms.

Augmented Lagrangian Methods for Convex Matrix Optimization Problems

In this paper,we provide some gentle introductions to the recent advance in augmented Lagrangian methods for solving large-scale convex matrix optimization problems(cMOP).Specifically,we reviewed two types of sufficient conditions for ensuring the quadratic growth conditions of a class of constrained convex matrix optimization problems regularized by nonsmooth spectral functions.Under a mild quadratic growth condition on the dual of cMOP,we further discussed the R-superlinear convergence of the Karush-Kuhn-Tucker(KKT)residuals of the sequence generated by the augmented Lagrangian methods(ALM)for solving convex matrix optimization problems.Implementation details of the ALM for solving core convex matrix optimization problems are also provided.

A Second-Order Image Denoising Model for Contrast Preservation

In this work,we propose a second-order model for image denoising by employing a novel potential function recently developed in Zhu(J Sci Comput 88:46,2021)for the design of a regularization term.Due to this new second-order derivative based regularizer,the model is able to alleviate the staircase effect and preserve image contrast.The augmented Lagrangian method(ALM)is utilized to minimize the associated functional and convergence analysis is established for the proposed algorithm.Numerical experiments are presented to demonstrate the features of the proposed model.

An Augmented Lagrangian Deep Learning Method for Variational Problems with Essential Boundary Conditions

This paper is concerned with a novel deep learning method for variational problems with essential boundary conditions.To this end,wefirst reformulate the original problem into a minimax problem corresponding to a feasible augmented La-grangian,which can be solved by the augmented Lagrangian method in an infinite dimensional setting.Based on this,by expressing the primal and dual variables with two individual deep neural network functions,we present an augmented Lagrangian deep learning method for which the parameters are trained by the stochastic optimiza-tion method together with a projection technique.Compared to the traditional penalty method,the new method admits two main advantages:i)the choice of the penalty parameter isflexible and robust,and ii)the numerical solution is more accurate in the same magnitude of computational cost.As typical applications,we apply the new ap-proach to solve elliptic problems and(nonlinear)eigenvalue problems with essential boundary conditions,and numerical experiments are presented to show the effective-ness of the new method.

IMAGE SUPER-RESOLUTION RECONSTRUCTION BY HUBER REGULARIZATION AND TAILORED FINITE POINT METHOD

In this paper,we propose using the tailored finite point method(TFPM)to solve the resulting parabolic or elliptic equations when minimizing the Huber regularization based image super-resolution model using the augmented Lagrangian method(ALM).The Hu-ber regularization based image super-resolution model can ameliorate the staircase for restored images.TFPM employs the method of weighted residuals with collocation tech-nique,which helps get more accurate approximate solutions to the equations and reserve more details in restored images.We compare the new schemes with the Marquina-Osher model,the image super-resolution convolutional neural network(SRCNN)and the classical interpolation methods:bilinear interpolation,nearest-neighbor interpolation and bicubic interpolation.Numerical experiments are presented to demonstrate that with the new schemes the quality of the super-resolution images has been improved.Besides these,the existence of the minimizer of the Huber regularization based image super-resolution model and the convergence of the proposed algorithm are also established in this paper.

An Augmented Lagrangian Uzawa IterativeMethod for Solving Double Saddle-Point Systems with Semidefinite(2,2)Block and its Application to DLM/FDMethod for Elliptic Interface Problems

.In this paper,an augmented Lagrangian Uzawa iterative method is developed and analyzed for solving a class of double saddle-point systems with semidefinite(2,2)block.Convergence of the iterativemethod is proved under the assumption that the double saddle-point problem exists a unique solution.An application of the iterative method to the double saddle-point systems arising from the distributed Lagrange multiplier/fictitious domain(DLM/FD)finite element method for solving elliptic interface problems is also presented,in which the existence and uniqueness of the double saddle-point system is guaranteed by the analysis of the DLM/FD finite element method.Numerical experiments are conducted to validate the theoretical results and to study the performance of the proposed iterative method.

Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming

In this paper,we accomplish the unified convergence analysis of a second-order method of multipliers(i.e.,a second-order augmented Lagrangian method)for solving the conventional nonlinear conic optimization problems.Specifically,the algorithm that we investigate incorporates a specially designed nonsmooth(generalized)Newton step to furnish a second-order update rule for the multipliers.We first show in a unified fashion that under a few abstract assumptions,the proposed method is locally convergent and possesses a(nonasymptotic)superlinear convergence rate,even though the penalty parameter is fixed and/or the strict complementarity fails.Subsequently,we demonstrate that for the three typical scenarios,i.e.,the classic nonlinear programming,the nonlinear second-order cone programming and the nonlinear semidefinite programming,these abstract assumptions are nothing but exactly the implications of the iconic sufficient conditions that are assumed for establishing the Q-linear convergence rates of the method of multipliers without assuming the strict complementarity.

Study on the Splitting Methods for Separable Convex Optimization in a Unified Algorithmic Framework

It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality.Recently,we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities.In this work,we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago.In particular,exploiting this framework,we are able to give a very clear and elementary proof of the convergence of these solution methods.

Binary Level Set Methods for Dynamic Reservoir Characterization by Operator Splitting Scheme

In this paper,operator splitting scheme for dynamic reservoir characterization by binary level set method is employed.For this problem,the absolute permeability of the two-phase porous medium flow can be simulated by the constrained augmented Lagrangian optimization method with well data and seismic time-lapse data.By transforming the constrained optimization problem in an unconstrained one,the saddle point problem can be solved by Uzawas algorithms with operator splitting scheme,which is based on the essence of binary level set method.Both the simple and complicated numerical examples demonstrate that the given algorithms are stable and efficient and the absolute permeability can be satisfactorily recovered.

Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization

Orthogonal nonnegative matrix factorization(ONMF)is widely used in blind image separation problem,document classification,and human face recognition.The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method.When the given matrix is huge,the cost of computation and communication is too high.Therefore,ONMF becomes challenging in the large-scale setting.The random projection is an efficient method of dimensionality reduction.In this paper,we apply the random projection to ONMF and propose two randomized algorithms.Numerical experiments show that our proposed algorithms perform well on both simulated and real data.

A Boosting Procedure for Variational-Based Image Restoration

Variational methods are an important class of methods for general image restoration.Boosting technique has been shown capable of improving many image denoising algorithms.This paper discusses a boosting technique for general variation-al image restoration methods.It broadens the applications of boosting techniques to a wide range of image restoration problems,including not only denoising but also deblur-ring and inpainting.In particular,we combine the recent SOS technique with dynamic parameter to variational methods.The dynamic regularization parameter is motivated by Meyer’s analysis on the ROF model.In each iteration of the boosting scheme,the variational model is solved by augmented Lagrangian method.The convergence analy-sis of the boosting process is shown in a special case of total variation image denoising with a“disk”input data.We have implemented our boosting technique for several im-age restoration problems such as denoising,inpainting and deblurring.The numerical results demonstrate promising improvement over standard variational restoration mod-els such as total variation based models and higher order variational model as total generalized variation.

Stroke-Based Surface Reconstruction

In this paper,we present a surface reconstruction via 2D strokes and a vector field on the strokes based on a two-step method.In the first step,from sparse strokes drawn by artists and a given vector field on the strokes,we propose a nonlinear vector interpolation combining total variation(TV)and H1 regularization with a curl-free constraint for obtaining a dense vector field.In the second step,a height map is obtained by integrating the dense vector field in the first step.Jump discontinuities in surface and discontinuities of surface gradients can be well reconstructed without any surface distortion.We also provide a fast and efficient algorithm for solving the proposed functionals.Since vectors on the strokes are interpreted as a projection of surface gradients onto the plane,different types of strokes are easily devised to generate geometrically crucial structures such as ridge,valley,jump,bump,and dip on the surface.The stroke types help users to create a surface which they intuitively imagine from 2D strokes.We compare our results with conventional methods via many examples.

Segmentation by Elastica Energy with L^(1) and L^(2) Curvatures: a Performance Comparison

In this paper,we propose an algorithm based on augmented Lagrangian method and give a performance comparison for two segmentation models that use the L^(1)-and L^(2)-Euler’s elastica energy respectively as the regularization for image seg-mentation.To capture contour curvature more reliably,we develop novel augmented Lagrangian functionals that ensure the segmentation level set function to be signed dis-tance functions,which avoids the reinitialization of segmentation function during the iterative process.With the proposed algorithm and with the same initial contours,we compare the performance of these two high-order segmentation models and numerically verify the different properties of the two models.