Adaptive augmented Lagrangian methods: algorithms and practical numerical experience

In this paper, we consider augmented Lagrangian (AL) algorithms for solving large-scale nonlinear optimization problems that execute adaptive strategies for updating the penalty parameter. Our work is motivated by the recently proposed adaptive AL trust region method by Curtis et al. [An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 (2015), pp. 201–245.]. The first focal point of this paper is a new variant of the approach that employs a line search rather than a trust region strategy, where a critical algorithmic feature for the line search strategy is the use of convexified piecewise quadratic models of the AL function for computing the search directions. We prove global convergence guarantees for our line search algorithm that are on par with those for the previously proposed trust region method. A second focal point of this paper is the practical performance of the line search and trust region algorithm variants in Matlab software, as well as that of an adaptive penalty parameter updating strategy incorporated into the Lancelot software. We test these methods on problems from the CUTEst and COPS collections, as well as on challenging test problems related to optimal power flow. Our numerical experience suggests that the adaptive algorithms outperform traditional AL methods in terms of efficiency and reliability. As with traditional AL algorithms, the adaptive methods are matrix-free and thus represent a viable option for solving large-scale problems.     

An Alternating Augmented Lagrangian method for constrained nonconvex optimization

ABSTRACT

We consider the problem of minimizing a smooth nonconvex function over a structured convex feasible set, that is, defined by two sets of constraints that are easy to treat when considered separately. In order to exploit the structure of the problem, we define an equivalent formulation by duplicating the variables and we consider the augmented Lagrangian of this latter formulation. Following the idea of the Alternating Direction Method of Multipliers (ADMM), we propose an algorithm where a two-blocks decomposition method is embedded within an augmented Lagrangian framework. The peculiarities of the proposed algorithm are the following: (1) the computation of the exact solution of a possibly nonconvex subproblem is not required; (2) the penalty parameter is iteratively updated once an approximated stationary point of the augmented Lagrangian is determined. Global convergence results are stated under mild assumptions and without requiring convexity of the objective function. Although the primary aim of the paper is theoretical, we perform numerical experiments on a nonconvex problem arising in machine learning, and the obtained results show the practical advantages of the proposed approach with respect to classical ADMM.     

An augmented Lagrangian decomposition method for quasi-separable problems in MDO

Several decomposition methods have been proposed for the distributed optimal design of quasi-separable problems encountered in Multidisciplinary Design Optimization (MDO). Some of these methods are known to have numerical convergence difficulties that can be explained theoretically. We propose a new decomposition algorithm for quasi-separable MDO problems. In particular, we propose a decomposed problem formulation based on the augmented Lagrangian penalty function and the block coordinate descent algorithm. The proposed solution algorithm consists of inner and outer loops. In the outer loop, the augmented Lagrangian penalty parameters are updated. In the inner loop, our method alternates between solving an optimization master problem and solving disciplinary optimization subproblems. The coordinating master problem can be solved analytically; the disciplinary subproblems can be solved using commonly available gradient-based optimization algorithms. The augmented Lagrangian decomposition method is derived such that existing proofs can be used to show convergence of the decomposition algorithm to Karush–Kuhn–Tucker points of the original problem under mild assumptions. We investigate the numerical performance of the proposed method on two example problems.     

Fixed‐order H∞ control design via a partially augmented Lagrangian method

In this paper we develop an augmented Lagrangian method to determine local optimal solutions of the reduced‐ and fixed‐order H_∞ synthesis problems. We cast these synthesis problems as optimization programs with a linear cost subject to linear matrix inequality (LMI) constraints along with nonlinear equality constraints representing a matrix inversion condition. The special feature of our algorithm is that only equality constraints are included in the augmented Lagrangian, while LMI constraints are kept explicitly in order to exploit currently available semi definite programming (SDP) codes. The step computation in the tangent problem is based on a Gauss–Newton model, and a specific line search and a first‐order Lagrange multiplier update rule are used to enhance efficiency. A number of computational results are reported and underline the strong practical performance of the algorithm. Copyright © 2003 John Wiley & Sons, Ltd.     

A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization

We present a new hybrid method for solving constrained numerical and engineering optimization problems in this paper. The proposed hybrid method takes advantage of the differential evolution (DE) ability to find global optimum in problems with complex design spaces while directly enforcing feasibility of constraints using a modified augmented Lagrangian multiplier method. The basic steps of the proposed method are comprised of an outer iteration, in which the Lagrangian multipliers and various penalty parameters are updated using a first-order update scheme, and an inner iteration, in which a nonlinear optimization of the modified augmented Lagrangian function with simple bound constraints is implemented by a modified differential evolution algorithm. Experimental results based on several well-known constrained numerical and engineering optimization problems demonstrate that the proposed method shows better performance in comparison to the state-of-the-art algorithms.     

An augmented Lagrangian approach to Bingham fluid flows in a lid-driven square cavity with piecewise linear equal-order finite elements

We study an augmented Lagrangian approach to Bingham fluid flows in a lid-driven square cavity. The piecewise linear equal-order finite element spaces for both the velocity and the pressure approximations, proposed and analyzed by Latché and Vola [18], are applied. Based on the resulting regularity of the numerical solutions, a mesh adaptive strategy is proposed to render the yield surfaces of desired resolution. The corresponding numerical scheme is formulated for general Herschel–Bulkley models, and its validity is verified on the benchmark model: Bingham fluid flows in a lid-driven square cavity.     

隐式低秩稀疏表示的多视角子空间聚类

针对多视角子空间聚类问题,提出基于隐式低秩稀疏表示的多视角子空间聚类算法(LLSMSC).算法构建多个视角共享的隐式结构,挖掘多视角之间的互补性信息.通过对隐式子空间的表示施加低秩约束和稀疏约束,捕获数据的局部结构和稀疏结构,使聚类结果更准确.同时,使用基于增广拉格朗日乘子交替方向最小化算法高效求解优化问题.在6个不同数据集上的实验验证LLSMSC的有效性和优越性.     

Neural-network-based stochastic linear quadratic optimal tracking control scheme for unknown discrete-time systems using adaptive dynamic programming

In this paper, a stochastic linear quadratic optimal tracking scheme is proposed for unknown linear discrete-time (DT) systems based on adaptive dynamic programming (ADP) algorithm. First, an augmented system composed of the original system and the command generator is constructed and then an augmented stochastic algebraic equation is derived based on the augmented system. Next, to obtain the optimal control strategy, the stochastic case is converted into the deterministic one by system transformation, and then an ADP algorithm is proposed with convergence analysis. For the purpose of realizing the ADP algorithm, three back propagation neural networks including model network, critic network and action network are devised to guarantee unknown system model, optimal value function and optimal control strategy, respectively. Finally, the obtained optimal control strategy is applied to the original stochastic system, and two simulations are provided to demonstrate the effectiveness of the proposed algorithm.     

基于磁感应的油藏裂缝内地下无线传感网络定位

针对在油藏裂缝中地下无线传感网络节点定位问题,提出一种基于可变方向增强拉格朗日方法和粒子群优化相结合的定位算法。锚节点布置在井筒固定位置,传感器节点随压裂过程进入裂缝具有位置随机分布特性,节点间采用三线圈磁感应方式通信。推导了基于接收信号磁感应强度的节点间距离估计公式,据此获得全部节点与锚节点及与其邻居节点的距离集合。然后将定位问题转化为半定规划问题,并采用可变方向增强拉格朗日方法求解上述凸优化问题,获得初步定位,再将其作为粒子群优化算法的初始值,在上述初始值小邻域内局部搜索获得最优解作为最终定位。仿真结果表明该算法相对定位误差低于0.6,且定位精度受测量噪声变化影响较小。     

An efficient augmented Lagrangian method for support vector machine

ABSTRACT

Support vector machine (SVM) has proved to be a successful approach for machine learning. Two typical SVM models are the L1-loss model for support vector classification (SVC) and ε-L1-loss model for support vector regression (SVR). Due to the non-smoothness of the L1-loss function in the two models, most of the traditional approaches focus on solving the dual problem. In this paper, we propose an augmented Lagrangian method for the L1-loss model, which is designed to solve the primal problem. By tackling the non-smooth term in the model with Moreau–Yosida regularization and the proximal operator, the subproblem in augmented Lagrangian method reduces to a non-smooth linear system, which can be solved via the quadratically convergent semismooth Newton's method. Moreover, the high computational cost in semismooth Newton's method can be significantly reduced by exploring the sparse structure in the generalized Jacobian. Numerical results on various datasets in LIBLINEAR show that the proposed method is competitive with the most popular solvers in both speed and accuracy.     

基于非局部相似模型的压缩感知图像恢复算法

针对压缩感知(Compressed sensing, CS)图像恢复问题, 提出了一种基于非局部相似模型的压缩感知恢复算法, 该算法将传统意义上二维图像块的稀疏性扩展到相似图像块组在三维空间上的稀疏性, 在提高图像表示稀疏度的同时进一步提高了压缩感知图像恢复效率, 恢复图像在纹理和结构保持方面都得到了很大的提升. 在该算法模型求解过程中, 使用增广拉格朗日方法将受限优化问题转换为非受限优化问题, 为减少计算复杂度, 还使用了基于泰勒展开的线性化技术来加速算法求解. 实验结果表明, 该算法的图像恢复性能优于目前主流的压缩感知图像恢复算法.     

Augmented Lagrangian Method for Generalized TV-Stokes Model

In this paper, we propose a general form of TV-Stokes models and provide an efficient and fast numerical algorithm based on the augmented Lagrangian method. The proposed model and numerical algorithm can be used for a number of applications such as image inpainting, image decomposition, surface reconstruction from sparse gradient, direction denoising, and image denoising. Comparing with properties of different norms in regularity term and fidelity term, various results are investigated in applications. We numerically show that the proposed model recovers jump discontinuities of a data and discontinuities of the data gradient while reducing stair-case effect.     

Modified augmented Lagrangian coordination and alternating direction method of multipliers with parallelization in non-hierarchical analytical target cascading

Analytical Target Cascading (ATC) is a decomposition-based optimization methodology that partitions a system into subsystems and then coordinates targets and responses among subsystems. Augmented Lagrangian with Alternating Direction method of multipliers (AL-AD), one of efficient ATC coordination methods, has been widely used in both hierarchical and non-hierarchical ATC and theoretically guarantees convergence under the assumption that all subsystem problems are convex and continuous. One of the main advantages of distributed coordination which consists of several non-hierarchical subproblems is that it can solve subsystem problems in parallel and thus reduce computational time. Therefore, previous studies have proposed an augmented Lagrangian coordination strategy for parallelization by eliminating interactions among subproblems. The parallelization is achieved by introducing a master problem and support variables or by approximating a quadratic penalty function to make subproblems separable. However, conventional AL-AD does not guarantee convergence in the case of parallel solving. Our study shows that, in parallel solving using targets and responses of the current iteration, conventional AL-AD causes mismatch of information in updating the Lagrange multiplier. Therefore, the Lagrange multiplier may not reach the optimal point, and as a result, increasing penalty weight causes numerical difficulty in the augmented Lagrangian coordination approach. To solve this problem, we propose a modified AL-AD with parallelization in non-hierarchical ATC. The proposed algorithm uses the subgradient method with adaptive step size in updating the Lagrange multiplier and also maintains penalty weight at an appropriate level not to cause oscillation. Without approximation or introduction of an artificial master problem, the modified AL-AD with parallelization can achieve similar accuracy and convergence with much less computational cost compared with conventional AL-AD with sequential solving.     

Interactive decision procedure for watershed nutrient load reduction: An integrated chance-constrained programming model with risk–cost tradeoff

Nutrient load reduction is a well-recognized requirement for aquatic ecosystem restoration. However, decision making is difficult due to challenges related to uncertainty and the interaction between decision makers and modelers, including (a) the quantitative relationship between risks arising from different aspects and the fact that cost is not usually revealed and (b) the fact that decision makers are not significantly involved in the modeling process. In this study, an interactive optimal-decision procedure with risk–cost tradeoff is proposed to overcome these limitations. It consists of chance-constrained programming (CCP) models, risk scenario analysis using the Taguchi method, risk–cost tradeoff and feedback for model adaption. A hybrid intelligent algorithm (HIA) integrating Monte Carlo simulation, artificial neural networks, and an augmented Lagrangian genetic algorithm was developed and applied to solve the CCP model. The proposed decision procedure and HIA are illustrated through a case study of uncertainty-based optimal nutrient load reduction in the Lake Qionghai Watershed, China. The CCP model has four constraints associated with risk levels indicating the possibility of constraint violation. Sixteen risk scenarios were designed with the Taguchi method to recognize the interactions between multiple constraint risks and total cost. The results were analyzed using the signal-to-noise ratio, analysis of variance, and multivariate regression. The model results demonstrate how cost is affected by risk for the four constraints and show that the proposed approach can provide effective support for decision making on risk–cost tradeoffs.     

A new constrained independent component analysis method.

Constrained independent component analysis (cICA) is a general framework to incorporate a priori information from problem into the negentropy contrast function as constrained terms to form an augmented Lagrangian function. In this letter, a new improved algorithm for cICA is presented through the investigation of the inequality constraints, in which different closeness measurements are compared. The utility of our proposed algorithm is demonstrated by the experiments with synthetic data and electroencephalogram (EEG) data.     

A modified augmented Lagrangian with improved grey wolf optimization to constrained optimization problems

This paper presents a novel constrained optimization algorithm named MAL-IGWO, which integrates the benefit of the improved grey wolf optimization (IGWO) capability for discovering the global optimum with the modified augmented Lagrangian (MAL) multiplier method to handle constraints. In the proposed MAL-IGWO algorithm, the MAL method effectively converts a constrained problem into an unconstrained problem and the IGWO algorithm is applied to deal with the unconstrained problem. This algorithm is tested on 24 well-known benchmark problems and 3 engineering applications, and compared with other state-of-the-art algorithms. Experimental results demonstrate that the proposed algorithm shows better performance in comparison to other approaches.

     

An alternating direction method for second-order conic programming

An alternating direction dual augmented Lagrangian method for second-order cone programming (SOCP) problems is proposed. In the algorithm, at each iteration it first minimizes the dual augmented Lagrangian function with respect to the dual variables, and then with respect to the dual slack variables while keeping the other two variables fixed, and then finally it updates the Lagrange multipliers. Convergence result is given. Numerical results demonstrate that our method is fast and efficient, especially for the large-scale second-order cone programming.     

Plug-and-Play Based Optimization Algorithm for New Crime Density Estimation

Different from a general density estimation, the crime density estimation usually has one important factor: the geographical constraint. In this paper, a new crime density estimation model is formulated, in which the regions where crime is impossible to happen, such as mountains and lakes, are excluded. To further optimize the estimation method, a learning-based algorithm, named Plug-and-Play, is implanted into the augmented Lagrangian scheme, which involves an off-the-shelf filtering operator. Different selections of the filtering operator make the algorithm correspond to several classical estimation models. Therefore, the proposed Plug-and-Play optimization based estimation algorithm can be regarded as the extended version and general form of several classical methods. In the experiment part, synthetic examples with different invalid regions and samples of various distributions are first tested. Then under complex geographic constraints, we apply the proposed method with a real crime dataset to recover the density estimation. The state-of-the-art results show the feasibility of the proposed model.