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.     

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.     

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.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.     

ADMM for multiaffine constrained optimization

ABSTRACT

We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka–?ojasiewicz (K–?) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.     

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.     

A gradient-based transformation method in multidisciplinary design optimization

Multidisciplinary design optimization (MDO) has become essential for solving the complex engineering design problems. The most common approach is to “divide and conquer” the MDO problem, that is, to decompose the complex problem into several sub-problems and to collect the local solutions to give a new design point for the original problem. In 1990s, researchers have developed some decomposition strategies to find or synthesize the optimal model of the optimization structure in order to evenly distribute the computational workloads to multiple processors. Several MDO methods, such as Collaborative Optimization (CO) and Analytical Target Cascading (ATC), were then developed to solve the decomposed sub-problems and coordinate the coupling variables among them to find the optimal solution. However, both the synthesis of the decomposition structure and the coordination of the coupling variables require additional function evaluations, in terms of evaluating the functional dependency between each sub-problem and determining the proper weighting coefficients between each coupling functions respectively. In this paper, a new divide-and-conquer strategy, Gradient-based Transformation Method (GTM), is proposed to overcome the challenges in structure synthesis and variable coordination. The proposed method first decomposes the MDO problem into several sub-systems and distributes one constraint from the original problem to each sub-system without evaluating the dependency between each sub-system. Each sub-system is then transformed to the single-variate coordinate along the gradient direction of the constraint. The total function evaluations equal the number of constraints times the number of variables plus one in every iteration. Due to the monotonicity characteristics of the transformed sub-problems, they are efficiently solved by Monotonicity Analyses without any additional function evaluations. Two coordination principles are proposed to determine the significances of the responses based on the feasibility and activity conditions of every sub-problem and to find the new design point at the average point of the most significant responses. The coordination principles are capable of finding the optimal solution in the convex feasible space bounded by the linearized sub-system constraints without additional function evaluations. The optimization processes continue until the convergence criterion is satisfied. The numerical examples show that the proposed methodology is capable of effectively and efficiently finding the optimal solutions of MDO problems.     

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.     

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.     

Dynamic Multiple Fault Diagnosis: Mathematical Formulations and Solution Techniques

Imperfect test outcomes, due to factors such as unreliable sensors, electromagnetic interference, and environmental conditions, manifest themselves as missed detections and false alarms. This paper develops near-optimal algorithms for dynamic multiple fault diagnosis (DMFD) problems in the presence of imperfect test outcomes. The DMFD problem is to determine the most likely evolution of component states, the one that best explains the observed test outcomes. Here, we discuss four formulations of the DMFD problem. These include the deterministic situation corresponding to perfectly observed coupled Markov decision processes to several partially observed factorial hidden Markov models ranging from the case where the imperfect test outcomes are functions of tests only to the case where the test outcomes are functions of faults and tests, as well as the case where the false alarms are associated with the nominal (fault free) case only. All these formulations are intractable NP-hard combinatorial optimization problems. Our solution scheme can be viewed as a two-level coordinated solution framework for the DMFD problem. At the top (coordination) level, we update the Lagrange multipliers (coordination variables, dual variables) using the subgradient method. At the bottom level, we use a dynamic programming technique (specifically, the Viterbi decoding or Max-sum algorithm) to solve each of the subproblems, one for each component state sequence. The key advantage of our approach is that it provides an approximate duality gap, which is a measure of the suboptimality of the DMFD solution. Computational results on real-world problems are presented. A detailed performance analysis of the proposed algorithm is also discussed.      

Enhanced Collaborative Optimization Using Alternating Direction Method of Multipliers

Enhanced collaborative optimization (ECO) is a recently developed multidisciplinary design optimization (MDO) method in the family of collaborative optimization (CO). While ECO achieves better optimization performance than its predecessors, its formulation is much more complex and incurs higher computation and communication costs, mainly due to the use of linear models of nonlocal constraints (LMNC). Consequently, ECO is often not the most desirable MDO method for large-scale and/or highly coupled applications. In this paper, we propose a new method named “ECO-ADMM” by introducing the alternating direction method of multipliers (ADMM) to ECO. With the aid of Lagrangian multipliers, ECO-ADMM increases each discipline’s “awareness” of global constraint conditions and search history at a negligible cost of Lagrangian multipliers updating. We also propose a simplified version of ECO-ADMM which removes LMNC from the original ECO-ADMM. With case studies of two analytic test problems and an industrial vehicle suspension design problem, two main advantages of ECO-ADMM over ECO are observed. First, ECO-ADMM achieves faster convergence and better solutions than ECO in most cases where both methods have comparable settings. Second, in the cases where LMNC are removed, ECO-ADMM maintains a much higher level of optimization performance than ECO. Therefore, ECO-ADMM is expected to outperform ECO in most application scenarios, and its simplified version provides designers with the option of trading a reasonable level of performance for ease of implementation and lower computation and communication costs.     

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.     

Improved Susceptibility Artifact Correction of Echo-Planar MRI using the Alternating Direction Method of Multipliers

We present an improved technique for susceptibility artifact correction in echo-planar imaging (EPI), a widely used ultra-fast magnetic resonance imaging (MRI) technique. Our method corrects geometric deformations and intensity modulations present in EPI images. We consider a tailored variational image registration problem incorporating a physical distortion model and aiming at minimizing the distance of two oppositely distorted images subject to invertibility constraints. We derive a novel face-staggered discretization of the variational problem that renders the discretized distance function and constraints separable. Motivated by the presence of a smoothness regularizer, which leads to global coupling, we apply the alternating direction method of multipliers (ADMM) to split the problem into simpler subproblems. We prove the convergence of ADMM for this non-convex optimization problem. We show the superiority of our scheme compared to two state-of-the-art methods both in terms of correction quality and time-to-solution for 13 high-resolution 3D imaging datasets.     

Large-scale convex optimal control problems: time decomposition,incentive coordination, and parallel algorithm

A parallel algorithm based on time decomposition and incentive coordination is developed for long-horizon optimal control problems. This is done by first decomposing the original problem into subproblems with shorter time horizon, and then using the incentive coordination scheme to coordinate the interaction of subproblems. For strictly convex problems it is proved that the decomposed problem with linear incentive coordination is equivalent to the original problem, in the sense that each optimal solution of the decomposed problem produces one global optimal solution of the original problem and vice versa. In other words, linear incentive terms are sufficient in this case and impose no additional computation burden on the subproblems. The high-level parameter optimization problem is shown to be nonconvex, despite the uniqueness of the optimal solution and the convexity of the original problem. Nevertheless, the high-level problem has no local minimum, even though it is nonconvex. A parallel algorithm based on a prediction method is developed, and a numerical example is used to demonstrate the feasibility of the approach     

求解复杂耦合问题的多系统优化方法

由于复杂耦合问题具有多系统、多目标、多约束、多尺度和不确定等特点, 急需一种求解此类问题的高效 智能优化方法. 为此, 借鉴多种群进化算法的智能平行特征, 利用种群间进化信息的继承和交互作用, 提出一种多 系统优化方法. 首先以子种群来代表子系统的优化环境, 通过子系统内的进化操作求解各自的优化子问题; 然后通 过子系统间的迁移操作, 即利用变量共享、目标函数和约束条件的相似程度来实现子系统间的信息迁移与反馈, 加 速整个问题的全局优化; 最后将该方法应用到基准函数和具有多系统优化特征的三级供应链网络, 仿真实验表明 所提出的方法可行且有效.     

Discovering inequality conditions in the analytic solution of optimization problems

Necessary and sufficient conditions for the problem of maximizing or minimizing a function subject to inequality constraints are given by a set of equalities and inequalities known as the Kuhn-Tucker conditions. These conditions can provide an analytic solution to the optimization problem if the artificial variables known as Lagrange multipliers can be eliminated. However, this is tedious to do by hand. This paper develops a computer program to assist in the solution process which combines symbolic computation and automated reasoning techniques. The program may also be useful for other problems involving algebraic reasoning with inequalities which employ general functions or symbolic parameters.     

A single front genetic algorithm for parallel multi-objective optimization in dynamic environments

This paper proposes a new parallel evolutionary procedure to solve multi-objective dynamic optimization problems along with some measures to evaluate multi-objective optimization in dynamic environments. These dynamic optimization problems appear in quite different real-world applications with actual socio-economic relevance. In these applications, the objective functions, the constraints, and hence, also the solutions, can change over time and usually demand to be solved online whilst the size of the changes is unknown. Although parallel processing could be very useful in these problems to meet the solution quality requirements and constraints, to date, not many parallel approaches have been reported in the literature. Taking this into account, we introduce a multi-objective optimization procedure for dynamic problems that are based on PSFGA, a parallel evolutionary algorithm previously proposed by us for multi-objective optimization. It uses an island model where a process divides the population among the remaining processes and allows the communication and coordination among the subpopulations in the different islands. The proposed algorithm makes an exclusive use of non-dominating individuals for the selection and variation operator and applies a crowding mechanism to maintain the diversity and the distribution of the solutions in the Pareto front. We also propose a model to understand the benefits of parallel processing in multi-objective problems and the speedup figures obtained in our experiments.     

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.     

Research on Approaches of Multidisciplinary Design Optimization for Non-hierarchic Systems

In complex engineering optimization, multilevel or two-level approaches are often applied. These approaches are carried out in assumption that there are no connections among sub problems at the same level. But it is difficult to construct the models that suit to this assumption. In recent years, the complexity of engineering systems has led to the rapid development in the field of Multidisciplinary Design Optimization (MDO). In MDO, two kinds of coupled factors, coupled variables (or functions) and system (or global) variables, always exist among all disciplines. These variable5 or functions make it disordered to solve the whole system. So, how to handle these variables is one of important studies in MDO. In this paper two approaches are discussed for handling these coupled factors in non-hierarchic system in MDO. And a test engineering example gives a demonstration about the implemeniation of these approaches.