Numerical investigation of non-hierarchical coordination for distributed multidisciplinary design optimization with fixed computational budget

This paper presents a numerical investigation of the non-hierarchical formulation of Analytical Target Cascading (ATC) for coordinating distributed multidisciplinary design optimization (MDO) problems. Since the computational cost of the analyses can be high and/or asymmetric, it is beneficial to understand the impact of the number of ATC iterations required for coordination and the number of iterations required for disciplinary feasibility on the quality of the obtained MDO solution. At each “outer” ATC iteration, the disciplinary optimization subproblems are solved for a predefined maximum number of “inner” loop iterations. The numerical experiments consider different numbers of maximum outer iterations while keeping the total computational budget of analyses constant. Solution quality is quantified by optimality (objective function value) and consistency (violation of coordination-related consistency constraints). Since MDO problems are typically simulation-based (and often blackbox) problems, we compare implementations of the mesh-adaptive direct search optimization algorithm (a derivative-free method with convergence properties) to the gradient-based interior-point algorithm implementation of the popular Matlab optimization toolbox. The impact of the values of two parameters involved in the alternating directions updating scheme of the augmented Lagrangian penalty functions (aka method of multipliers) on solution quality is also investigated. Numerical results are provided for a variety of MDO test problems. The results indicate consistently that a balanced modest number of outer and inner iterations is more effective; moreover, there seems to be a specific combination of parameter value ranges that yield better results.     

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.     

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.     

一种求解约束优化问题的混合算法

提出一种基于修改增广Lagrange函数和PSO的混合算法用于求解约束优化问题。将约束优化问题转化为界约束优化问题,混合算法由两层迭代结构组成,在内层迭代中,利用改进PSO算法求解界约束优化问题得到下一个迭代点。外层迭代主要修正Lagrange乘子和罚参数,检查收敛准则是否满足,重构下次迭代的界约束优化子问题,检查收敛准则是否满足。数值实验结果表明该混合算法的有效性。     

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.     

A sharp augmented Lagrangian-based method in constrained non-convex optimization

In this paper, a novel sharp Augmented Lagrangian-based global optimization method is developed for solving constrained non-convex optimization problems. The algorithm consists of outer and inner loops. At each inner iteration, the discrete gradient method is applied to minimize the sharp augmented Lagrangian function. Depending on the solution found the algorithm stops or updates the dual variables in the inner loop, or updates the upper or lower bounds by going to the outer loop. The convergence results for the proposed method are presented. The performance of the method is demonstrated using a wide range of nonlinear smooth and non-smooth constrained optimization test problems from the literature.     

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.     

Solving multiobjective optimization problems using quasi-separable MDO formulations and analytical target cascading

One approach to multiobjective optimization is to define a scalar substitute objective function that aggregates all objectives and solve the resulting aggregate optimization problem (AOP). In this paper, we discern that the objective function in quasi-separable multidisciplinary design optimization (MDO) problems can be viewed as an aggregate objective function (AOF). We consequently show that a method that can solve quasi-separable problems can also be used to obtain Pareto points of associated AOPs. This is useful when AOPs are too hard to solve or when the design engineer does not have access to the models necessary to evaluate all the terms of the AOF. In this case, decomposition-based design optimization methods can be useful to solve the AOP as a quasi-separable MDO problem. Specifically, we use the analytical target cascading methodology to formulate decomposed subproblems of quasi-separable MDO problems and coordinate their solution in order to obtain Pareto points of the associated AOPs. We first illustrate the approach using a well-known simple geometric programming example and then present a vehicle suspension design problem with three objectives related to ground vehicle ride and handling.     

A classification of methods for distributed system optimization based on formulation structure

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. This work is funded by MicroNed, grant number 10005898.     

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.     

Simultaneous structural analysis and design based on augmented Lagrangian duality

Solution procedures in structural optimization are commonly based on a nested approach where approximations of the analysis and design problems are solved alternately in an iterative scheme. In this paper, we study a simultaneous approach based on an integrated formulation of the analysis and design problems. An advantage of the simultaneous approach, when compared to the nested one, is that the dependence between the analysis and design variables is imposed explicitly. In the nested approach, this dependence is implicitly determined through the solution of the analysis problem. Earlier simultaneous approaches mostly utilize various penalty function reformulations. In this paper, we make use of two augmented Lagrangian schemes, which avoid the numerical ill-conditioning inherent in penalty reformulations. These schemes give rise to Lagrangian subproblems with somewhat different properties, and two efficient techniques are adapted for their solution. The first is a projected Newton method, and the second is a simplicial decomposition scheme. Computational results for bar-truss structures show that the proposed schemes are viable approaches for solving the integrated formulation, and that they are promising for future developments.     

Lagrangian duality applied to the vehicle routing problem with time windows

This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are introduced and it leads to faster multiplier convergence due to a stabilization of the dual variables. We have embedded the stabilized cutting-plane algorithm in a branch-and-bound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branch-and-cut-and-price (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speed-up compared to algorithms in the literature based on traditional column generation. We have solved two test problems introduced in 2001 by Gehring and Homberger with 400 and 1000 customers respectively, which to date are the largest problems ever solved to optimality. We have implemented the LBCP algorithm using the ABACUS open-source framework for solving mixed-integer linear-programs by branch, cut, and price.     

A penalty PALM method for sparse portfolio selection problems

In this paper, we propose a penalty proximal alternating linearized minimization method for the large-scale sparse portfolio problems in which a sequence of penalty subproblems are solved by utilizing the proximal alternating linearized minimization framework and sparse projection techniques. For exploiting the structure of the problems and reducing the computation complexity, each penalty subproblem is solved by alternately solving two projection problems. The global convergence of the method to a Karush-Kuhn-Tucker point or a local minimizer of the problem can be proved under the characteristic of the problem. The computational results with practical problems demonstrate that our method can find the suboptimal solutions of the problems efficiently and is competitive with some other local solution methods.     

A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles

We address a bilevel decomposition algorithm for solving the simultaneous scheduling and conflict-free routing problems for automated guided vehicles. The overall objective is to minimize the total weighted tardiness of the set of jobs related to these tasks. A mixed integer formulation is decomposed into two levels: the upper level master problem of task assignment and scheduling; and the lower level routing subproblem. The master problem is solved by using Lagrangian relaxation and a lower bound is obtained. Either the solution turns out to be feasible for the lower level or a feasible solution for the problem is constructed, and an upper bound is obtained. If the convergence is not satisfied, cuts are generated to exclude previous feasible solutions before solving the master problem again. Two types of cuts are proposed to reduce the duality gap. The effectiveness of the proposed method is investigated from computational experiments.     

A nonlinear programming algorithm for hydro-thermal generation scheduling

This paper presents an efficient decomposition technique for optimal generation scheduling of hydro-thermal systems. Interval-wise decomposition has been carried out so as to reduce the complexity of the problem. The decomposed subproblems have been converted into unconstrained nonlinear programming subproblems using augmented penalty function approach. Each subproblem is separately solved using Fletcher's modified metric algorithm.     

稀疏MR图像重构的快速算法

提出小波稀疏的MR图像重构的交替最小化方法,分析证明了这一方法的收敛性。利用半二次罚函数方法将小波稀疏的MR图像重构最优化问题分裂成两个子最优化问题：X-子问题和Y-子问题,通过对两个子问题的交替最小化得到原问题的最优解。利用1维软阈值收缩方法求解Y-子问题,利用Fourier变换的方法求解X-子问题解,进而给出原问题求解的分裂算法。利用Phantom图像和一些实际的MR图像与最新的算子分裂算法进行数值实验比较,其结果是交替最小化方法重构的图像的信噪比比算子分裂算法的高,而相对误差和CPU时间较低,从而表明交替最小化方法是稀疏MR图像重构的一种快速算法。     

Multiparametric optimization for multidisciplinary engineering design

The area of Multiparametric Optimization (MPO) solves problems that contain unknown problem data represented by parameters. The solutions map parameter values to optimal design and objective function values. In this paper, for the first time, MPO techniques are applied to improve and advance Multidisciplinary Design Optimization (MDO) to solve engineering problems with parameters. A multiparametric subgradient algorithm is proposed and applied to two MDO methods: Analytical Target Cascading (ATC) and Network Target Coordination (NTC). Numerical results on test problems show the proposed parametric ATC and NTC methods effectively solve parametric MDO problems and provide useful insights to designers. In addition, a novel Two-Stage ATC method is proposed to solve nonparametric MDO problems. In this new approach elements of the subproblems are treated as parameters and optimal design functions are constructed for each one. When the ATC loop is engaged, steps involving the lengthy optimization of subproblems are replaced with simple function evaluations.     

FETI based algorithms for contact problems: scalability,large displacements and 3D Coulomb friction

Theoretical and experimental results concerning FETI based algorithms for contact problems of elasticity are reviewed. A discretized model problem is first reduced by the duality theory of convex optimization to the quadratic programming problem with bound and equality constraints. The latter is then optionally modified by means of orthogonal projectors to the natural coarse space introduced by Farhat and Roux in the framework of their FETI method. The resulting problem is then solved either by special algorithms for bound constrained quadratic programming problems combined with penalty that imposes the equality constraints, or by an augmented Lagrangian type algorithm with the inner loop for the solution of bound constrained quadratic programming problems. Recent theoretical results are reported that guarantee certain optimality and scalability of both algorithms. The results are confirmed by numerical experiments. The performance of the algorithm in solution of more realistic engineering problems by basic algorithm is demonstrated on the solution of 3D problems with large displacements or Coulomb friction.     

Stochastic optimisation with inequality constraints using simultaneous perturbations and penalty functions

We present a stochastic approximation algorithm based on penalty function method and a simultaneous perturbation gradient estimate for solving stochastic optimisation problems with general inequality constraints. We present a general convergence result that applies to a class of penalty functions including the quadratic penalty function, the augmented Lagrangian, and the absolute penalty function. We also establish an asymptotic normality result for the algorithm with smooth penalty functions under minor assumptions. Numerical results are given to compare the performance of the proposed algorithm with different penalty functions.