An augmented Lagrangian method for VLSI global placement

By ignoring some cell overlaps, global placement computes the best position for each cell to minimize the wirelength. It is an important stage in very large scale integration (VLSI) physical design, since circuit performance heavily depends on the placement results. In this paper, we propose an augmented Lagrangian method to solve the VLSI global placement problem. In the proposed method, a cautious dynamic density weight strategy is used to balance the wirelength objective and the density constraints, and an adaptive step size is used to obtain a trade-off between runtime and solution quality. The proposed method is tested on the IBM mixed-size benchmarks and the International Symposium on Physical Design 2006 placement contest benchmarks. Experimental results show that our global placement method outperforms the state-of-the-art placement approaches in terms of solution quality on most of the benchmarks.     

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.     

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.     

An augmented Lagrangian optimization method for inflatable structures analysis problems

This paper describes the development of an augmented Lagrangian optimization method for the numerical simulation of the inflation process in the design of inflatable space structures. Although the Newton–Raphson scheme was proven to be efficient for solving many nonlinear problems, it can lead to lack of convergence when it is applied to the simulation of the inflation process. As a result, it is recommended to use an optimization algorithm to find the minimum energy configuration that satisfies the equilibrium equations characterizing the final shape of the inflated structure subject to an internal pressure. On top of that, given that some degrees of freedom may be linked, the optimum may be constrained, and specific optimization methods for constrained problems must be considered. The paper presents the formulation and the augmented Lagrangian method (ALM) developed in SAMCEF Mecano for inflatable structures analysis problems. The related quasi-unconstrained optimization problem is solved with a nonlinear conjugate gradient method. The Wolfe conditions are used in conjunction with a cubic interpolation for the line search. Equality constraints are considered and can be easily treated by the ALM formulation. Numerical applications present simulations of unconstrained and constrained inflation processes (i.e., where the motion of some nodes is ruled by a rigid body element restriction and/or problems including contact conditions).Part of this paper was presented at the sixth world congress of Structural and Multidisciplinary Optimization held in Rio de Janeiro, June 2005.     

An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory

We present a new approach to a class of non-convex LMI-constrained problems in robust control theory. The problems we consider may be recast as the minimization of a linear objective subject to linear matrix inequality (LMI) constraints in tandem with non-convex constraints related to rank deficiency conditions. We solve these problems using an extension of the augmented Lagrangian technique. The Lagrangian function combines a multiplier term and a penalty term governing the non-convex constraints. The LMI constraints, due to their special structure, are retained explicitly and not included in the Lagrangian. Global and fast local convergence of our approach is then obtained either by an LMI-constrained Newton type method including line search or by a trust-region strategy. The method is conveniently implemented with available semi-definite programming (SDP) interior-point solvers. We compare its performance to the wellknown D - K iteration scheme in robust control. Two test problems are investigated and demonstrate the power and efficiency of our approach.     

An augmented Lagrangian optimization method for contact analysis problems, 2: numerical evaluation

The ALM2 solution procedure is evaluated by solving two simple contact analysis problems for different friction conditions. These example problems are devised to have closed form solutions. This way there is no uncertainty about the target solution for evaluation of the proposed algorithm as well as existing algorithms. The numerical results with ALM2 are compared with the analytical solutions as well as with the penalty, Lagrange multiplier and existing augmented Lagrangian methods. All the algorithms are analysed for stick and slip friction conditions. The example problems are used to show clearly the dependence of the existing solution methods on the number of load steps and penalty values. It is concluded that convergence of incremental solution schemes employed in these methods does not guarantee accuracy of the contact solution even with the use of solution enhancement schemes such as automatic load stepping and contact load prediction. The example problems are also used to demonstrate solution independence of the proposed ALM2 procedure from penalty values, and from the number of load steps. The proposed formulation for calculation of frictional forces and the ALM solution algorithm have worked quite well for the example problems. However, the algorithm needs to be developed and evaluated for more complex contact analysis problems.     

An augmented Lagrangian relaxation for analytical target cascading using the alternating direction method of multipliers

Analytical target cascading is a method for design optimization of hierarchical, multilevel systems. A quadratic penalty relaxation of the system consistency constraints is used to ensure subproblem feasibility. A typical nested solution strategy consists of inner and outer loops. In the inner loop, the coupled subproblems are solved iteratively with fixed penalty weights. After convergence of the inner loop, the outer loop updates the penalty weights. The article presents an augmented Lagrangian relaxation that reduces the computational cost associated with ill-conditioning of subproblems in the inner loop. The alternating direction method of multipliers is used to update penalty parameters after a single inner loop iteration, so that subproblems need to be solved only once. Experiments with four examples show that computational costs are decreased by orders of magnitude ranging between 10 and 1000.     

An augmented Lagrangian optimization method for contact analysis problems, 1: formulation and algorithm

A review of existing augmented Lagrangian methods (ALM) for contact analysis problems reveals that they have not been implemented with automatic penalty updates as intended in their original development. Therefore, although the methods are an improvement over the penalty methods, solution with them still depends on the user-specified penalty values for the contact constraints. To overcome this drawback, an ALM is developed and discussed for contact analysis problems that automatically update the user-specified penalty values to obtain the final appropriate values. Further, to solve the frictional contact analysis problem accurately, a two-phase formulation is proposed. Solution of the Phase 1 problem removes penetration of the contacting nodes and brings them exactly to their initial contact points. In addition, a new contact constraint is introduced which allows determination of the precise friction force at the contacting nodes. Phase 2 of the formulation checks the friction conditions and solves the friction problem to bring the structure to an equilibrium state. Phases 1 and 2 are then combined to provide a general algorithm for multi-node frictional contact problems. The two-phase procedure also removes dependence of the contact solution on the number of load steps for the elastostatic problem. Numerical evaluation of the formulation and the algorithm is presented in Part 2 of the paper.     

Coevolutionary augmented Lagrangian methods for constrainedoptimization

This paper introduces a coevolutionary method developed for solving constrained optimization problems. This algorithm is based on the evolution of two populations with opposite objectives to solve saddle-point problems. The augmented Lagrangian approach is taken to transform a constrained optimization problem to a zero-sum game with the saddle point solution. The populations of the parameter vector and the multiplier vector approximate the zero-sum game by a static matrix game, in which the fitness of individuals is determined according to the security strategy of each population group. Selection, recombination, and mutation are done by using the evolutionary mechanism of conventional evolutionary algorithms such as evolution strategies, evolutionary programming, and genetic algorithms. Four benchmark problems are solved to demonstrate that the proposed coevolutionary method provides consistent solutions with better numerical accuracy than other evolutionary methods     

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.     

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.     

Lagrangian particle model for multiphase flows

A Lagrangian particle model for multiphase multicomponent fluid flow, based on smoothed particle hydrodynamics (SPH), was developed and used to simulate the flow of an emulsion consisting of bubbles of a non-wetting liquid surrounded by a wetting liquid. In SPH simulations, fluids are represented by sets of particles that are used as discretization points to solve the Navier-Stokes fluid dynamics equations. In the multiphase multicomponent SPH model, a modified van der Waals equation of state is used to close the system of flow equations. The combination of the momentum conservation equation with the van der Waals equation of state results in a particle equation of motion in which the total force acting on each particle consists of many-body repulsive and viscous forces, two-body (particle-particle) attractive forces, and body forces such as gravitational forces. Similar to molecular dynamics, for a given fluid component the combination of repulsive and attractive forces causes phase separation. The surface tension at liquid-liquid interfaces is imposed through component dependent attractive forces. The wetting behavior of the fluids is controlled by phase dependent attractive interactions between the fluid particles and stationary particles that represent the solid phase. The dynamics of fluids away from the interface is governed by purely hydrodynamic forces. Comparison with analytical solutions for static conditions and relatively simple flows demonstrates the accuracy of the SPH model.     

Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables

We propose a new splitting augmented Lagrangian method (SALM) for solving a class of optimization problems with both cardinality constraint and semicontinuous variables constraint. The proposed approach, inspired by the penalty decomposition method in [Z.S. Lu and Y. Zhang, Sparse approximation via penalty decomposition methods, SIAM J. Optim. 23(4) (2013), pp. 2448–2478], splits the problem into two subproblems using auxiliary variables. SALM solves two subproblems alternatively. Furthermore, we prove the convergence of SALM, under certain assumptions. Finally, SALM is implemented on the portfolio selection problem and the compressed sensing problem, respectively. Numerical results show that SALM outperforms the well-known tailored approach in CPLEX 12.6 and the penalty decomposition method, respectively.     

Newton-conjugate gradient （CG） augmented Lagrangian method for path constrained dynamic process optimization

In this paper, a Newton-conjugate gradient (CG) augmented Lagrangian method is proposed for solving the path constrained dynamic process optimization problems. The path constraints are simplified as a single final time constraint by using a novel constraint aggregation function. Then, a control vector parameterization (CVP) approach is applied to convert the constraints simplified dynamic optimization problem into a nonlinear programming (NLP) problem with inequality constraints. By constructing an augmented Lagrangian function, the inequality constraints are introduced into the augmented objective function, and a box constrained NLP problem is generated. Then, a linear search Newton-CG approach, also known as truncated Newton (TN) approach, is applied to solve the problem. By constructing the Hamiltonian functions of objective and constraint functions, two adjoint systems are generated to calculate the gradients which are needed in the process of NLP solution. Simulation examples demonstrate the effectiveness of the algorithm.     

An augmented Lagrangian approach to non-convex SAO using diagonal quadratic approximations

Successful gradient-based sequential approximate optimization (SAO) algorithms in simulation-based optimization typically use convex separable approximations. Convex approximations may however not be very efficient if the true objective function and/or the constraints are concave. Using diagonal quadratic approximations, we show that non-convex approximations may indeed require significantly fewer iterations than their convex counterparts. The nonconvex subproblems are solved using an augmented Lagrangian (AL) strategy, rather than the Falk-dual, which is the norm in SAO based on convex subproblems. The results suggest that transformation of large-scale optimization problems with only a few constraints to a dual form via convexification need sometimes not be required, since this may equally well be done using an AL formulation.     

Live three-dimensional content for augmented reality

We describe an augmented reality system for superimposing three-dimensional (3-D) live content onto two-dimensional fiducial markers in the scene. In each frame, the Euclidean transformation between the marker and the camera is estimated. The equivalent virtual view of the live model is then generated and rendered into the scene at interactive speeds. The 3-D structure of the model is calculated using a fast shape-from-silhouette algorithm based on the outputs of 15 cameras surrounding the subject. The novel view is generated by projecting rays through each pixel of the desired image and intersecting them with the 3-D structure. Pixel color is estimated by taking a weighted sum of the colors of the projections of this 3-D point in nearby real camera images. Using this system, we capture live human models and present them via the augmented reality interface at a remote location. We can generate 384/spl times/288 pixel images of the models at 25 fps, with a latency of <100 ms. The result gives the strong impression that the model is a real 3-D part of the scene.     

Ghost-cell method for analysis of inviscid three-dimensional flows on Cartesian-grids

The present paper deals with the implementation of non-penetration boundary conditions at solid walls for three-dimensional inviscid flow computations on Cartesian grids. The crux of the method is the curvature-corrected symmetry technique (CCST) developed by the present authors for body-fitted grids. The method introduces ghost cells near the boundaries whose values are developed from an assumed flow-field model in vicinity of the wall consisting of a vortex flow, with locally symmetric distribution of entropy and total enthalpy. In three dimensions this procedure is implemented in the so-called “osculating plane”. This method was shown to be substantially more accurate than traditional surface boundary condition approaches. This improved boundary condition is adapted to a Cartesian mesh formulation, which we have termed the “ghost-cell method”. In this approach, all cell centers exterior to the body are computed with fluxes at the six surrounding cell faces, without any cut cell. A multiple-valued point technique is used to compute sharp edges. The merits of the ghost-cell method for three-dimensional inviscid flow computations are established by computing compressible and transonic flows about a sphere, an oblate and a prolate spheroid, a cylindrical wing with an end-plate, the ONERA M6 wing and detailed comparison to body-fitted grid computations and to published data. The computed results show the surface non-penetration condition to be satisfied in the limit of vanishing cell size and the method to be second-order accurate in space. The comparison with body-fitted results proves that the accuracy is comparable to the accuracy of CCST computations on body-fitted grids and remarkably superior to body-fitted computations based on traditional pressure extrapolation, non-penetration boundary conditions. In addition, we prove that the results are independent of the position of the body with respect to the grid. Finally, we show that the ONERA M6 wing results compare very well with published data.     

A separable augmented Lagrangian algorithm for optimal structural design

Structural and Multidisciplinary Optimization - We propose an iterative separable augmented Lagrangian algorithm (SALA) for optimal structural design, with SALA being a subset of the alternating...     

Multi-modality in augmented Lagrangian coordination for distributed optimal design

This paper presents an empirical study of the convergence characteristics of augmented Lagrangian coordination (ALC) for solving multi-modal optimization problems in a distributed fashion. A number of test problems that do not satisfy all assumptions of the convergence proof for ALC are selected to demonstrate the convergence characteristics of ALC algorithms. When only a local search is employed at the subproblems, local solutions to the original problem are often attained. When a global search is performed at subproblems, global solutions to the original, non-decomposed problem are found for many of the examples. Although these findings are promising, ALC with a global subproblem search may yield only local solutions in the case of non-convex coupling functions or disconnected feasible domains. Results indicate that for these examples both the starting point and the sequence in which subproblems are solved determines which solution is obtained. We illustrate that the main cause for this behavior lies in the alternating minimization inner loop, which is inherently of a local nature.     

Block-separable linking constraints in augmented Lagrangian coordination

Augmented Lagrangian coordination (ALC) is a provably convergent coordination method for multidisciplinary design optimization (MDO) that is able to treat both linking variables and linking functions (i.e. system-wide objectives and constraints). Contrary to quasi-separable problems with only linking variables, the presence of linking functions may hinder the parallel solution of subproblems and the use of the efficient alternating directions method of multipliers. We show that this unfortunate situation is not the case for MDO problems with block-separable linking constraints. We derive a centralized formulation of ALC for block-separable constraints, which does allow parallel solution of subproblems. Similarly, we derive a distributed coordination variant for which subproblems cannot be solved in parallel, but that still enables the use of the alternating direction method of multipliers. The approach can also be used for other existing MDO coordination strategies such that they can include block-separable linking constraints.