Subproblem optimization with regression and neural network approximators

Design optimization of large systems can be attempted through a subproblem strategy. In this strategy the original problem is divided into a number of smaller problems that are clustered together to obtain a sequence of subproblems. Solution to the large problem is attempted iteratively through repeated solutions to the modest subproblems. This strategy is applicable to structures and to multidisciplinary systems. For structures, clustering the substructures generates the sequence of subproblems. For a multidisciplinary system, individual disciplines, accounting for coupling, can be considered as subproblems. A subproblem, if required, can be further broken down to accommodate subdisciplines. The subproblem strategy is being implemented into the NASA design optimization test bed, referred to as “CometBoards”. Neural network and regression approximators are employed for reanalysis and sensitivity analysis calculations at the subproblem level. The strategy has been implemented in sequential as well as parallel computational environments. This strategy, which attempts to alleviate algorithmic and reanalysis deficiencies, has the potential to become a powerful design tool. However, several issues have to be addressed before its full potential can be harnessed. This paper illustrates the strategy and addresses some issues.     

CONLIN: An efficient dual optimizer based on convex approximation concepts

The Convex Linearization method (CONLIN) exhibits many interesting features and it is applicable to a broad class of structural optimization problems. The method employs mixed design variables (either direct or reciprocal) in order to get first order, conservative approximations to the objective function and to the constraints. The primary optimization problem is therefore replaced with a sequence of explicit approximate problems having a simple algebraic structure. The explicit subproblems are convex and separable, and they can be solved efficiently by using a dual method approach.In this paper, a special purpose dual optimizer is proposed to solve the explicit subproblem generated by the CONLIN strategy. The maximum of the dual function is sought in a sequence of dual subspaces of variable dimensionality. The primary dual problem is itself replaced with a sequence of approximate quadratic subproblems with non-negativity constraints on the dual variables. Because each quadratic subproblem is restricted to the current subspace of non zero dual variables, its dimensionality is usually reasonably small. Clearly, the Hessian matrix does not need to be inverted (it can in fact be singular), and no line search process is necessary.An important advantage of the proposed maximization method lies in the fact that most of the computational effort in the iterative process is performed with reduced sets of primal variables and dual variables. Furthermore, an appropriate active set strategy has been devised, that yields a highly reliable dual optimizer.     

Biobjective optimization for analytical target cascading: optimality vs. achievability

Analytical target cascading (ATC), a hierarchical, multilevel multidisciplinary methodology, has proved to be an effective solution strategy for complex design problems. ATC decomposition and coordination incorporates compromise between the performance of the system and the demands of the subproblems reflected in their feasibility constraints. Optimal system performance regardless of subproblem feasibility may yield targets that are not achievable by the subproblems. Compromise is needed to accept deterioration of the optimal system performance and to increase the achievability of the targets. Biobjective optimization is used to reconcile system optimality and subproblem achievability of targets while solving the ATC-decomposed problem and generating an overall optimal solution. Three algorithms are proposed for two-level ATC-decomposed problems. The effectiveness of the algorithms is evaluated on mathematical and engineering examples. For a class of ATC problems, the performance of the proposed algorithms is superior to the performance of the ATC methods currently considered to be state of the art.     

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.     

Simulation based optimization of stochastic systems with integer design variables by sequential multipoint linear approximation

Optimization problems are considered for which objective function and constraints are defined as expected values of stochastic functions that can only be evaluated at integer design variable levels via a computationally expensive computer simulation. Design sensitivities are assumed not to be available. An optimization approach is proposed based on a sequence of linear approximate optimization subproblems. Within each search subregion a linear approximate optimization subproblem is built using response surface model building. To this end, N simulation experiments are carried out in the search subregion according to a D-optimal experimental design. The linear approximate optimization problem is solved by integer linear programming using corrected constraint bounds to account for any uncertainty due to the stochasticity. Each approximate optimum is evaluated on the basis of M simulation replications with respect to objective function change and feasibility of the design. The performance of the optimization approach and the influence of parameters N and M is illustrated via two analytical test problems. A third example shows the application to a production flow line simulation model. Received April 28, 2000     

Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems

This paper proposes a framework named multi-objective ant colony optimization based on decomposition (MoACO/D) to solve bi-objective traveling salesman problems (bTSPs). In the framework, a bTSP is first decomposed into a number of scalar optimization subproblems using Tchebycheff approach. To suit for decomposition, an ant colony is divided into many subcolonies in an overlapped manner, each of which is for one subproblem. Then each subcolony independently optimizes its corresponding subproblem using single-objective ant colony optimization algorithm and all subcolonies simultaneously work. During the iteration, each subproblem maintains an aggregated pheromone trail and an aggregated heuristic matrix. Each subcolony uses the information to solve its corresponding subproblem. After an iteration, a pheromone trail share procedure is evoked to realize the information share of those subproblems solved by common ants. Three MoACO algorithms designed by, respectively, combining MoACO/D with AS, MMAS and ACS are presented. Extensive experiments conducted on ten bTSPs with various complexities manifest that MoACO/D is both efficient and effective for solving bTSPs and the ACS version of MoACO/D outperforms three well-known MoACO algorithms on large bTSPs according to several performance measures and median attainment surfaces.     

Aero-structural optimization using adjoint coupled post-optimality sensitivities

A new subspace optimization method for performing aero-structural design is introduced. The method relies on a semi-analytic adjoint approach to the sensitivity analysis that includes post-optimality sensitivity information from the structural optimization subproblem. The resulting coupled post-optimality sensitivity approach is used to guide a gradient-based optimization algorithm. The new approach simplifies the system-level problem, thereby reducing the number of calls to a potentially costly aerodynamics solver. The aero-structural optimization of an aircraft wing is performed using linear aerodynamic and structural analyses, and a performance comparison is made between the new approach and the conventional multidisciplinary feasible method. The new asymmetric suboptimization method is found to be the more efficient approach when it adequately reduces the number of system evaluations or when there is a large enough discrepancy between disciplinary solution times.     

Cooperative particle swarm optimization for multiobjective transportation planning

The paper presents a multiobjective optimization problem that considers distributing multiple kinds of products from multiple sources to multiple targets. The problem is of high complexity and is difficult to solve using classical heuristics. We propose for the problem a hierarchical cooperative optimization approach that decomposes the problem into low-dimensional subcomponents, and applies Pareto-based particle swarm optimization (PSO) method to the main problem and the subproblems alternately. In particular, our approach uses multiple sub-swarms to evolve the sub-solutions concurrently, controls the detrimental effect of variable correlation by reducing the subproblem objectives, and brings together the results of the sub-swarms to construct effective solutions of the original problem. Computational experiment demonstrates that the proposed algorithm is robust and scalable, and outperforms some state-of-the-art constrained multiobjective optimization algorithms on a set of test problems.     

Explicit/multi-parametric model predictive control (MPC) of linear discrete-time systems by dynamic and multi-parametric programming

This work presents a new algorithm for solving the explicit/multi-parametric model predictive control (or mp-MPC) problem for linear, time-invariant discrete-time systems, based on dynamic programming and multi-parametric programming techniques. The algorithm features two key steps: (i) a dynamic programming step, in which the mp-MPC problem is decomposed into a set of smaller subproblems in which only the current control, state variables, and constraints are considered, and (ii) a multi-parametric programming step, in which each subproblem is solved as a convex multi-parametric programming problem, to derive the control variables as an explicit function of the states. The key feature of the proposed method is that it overcomes potential limitations of previous methods for solving multi-parametric programming problems with dynamic programming, such as the need for global optimization for each subproblem of the dynamic programming step.     

$K$ Constrained Shortest Path Problem

Motivated by a real project for a sophisticated automated storage and retrieval system (AS/RS), we study the problem of generating K shortest paths that are required to satisfy a set of constraints. We propose a structural branching procedure that decomposes the problem into at most K|N| subproblems, where |N| is the number of nodes in the network. By using a Network Modification procedure, each subproblem can be transformed into a constrained shortest path problem (CSP). When these constraints satisfy a so called separable property, the subproblem can be further simplified. Based on this branching procedure, we propose a specific algorithm for an application where resource and loopless constraints have to be respected. Numerical results show that our algorithm is very efficient and robust.     

An effective trust-region-based approach for symmetric nonlinear systems

This paper presents a new trust-region procedure for solving symmetric nonlinear systems of equations having several variables. The proposed approach takes advantage of the combination of both an effective adaptive trust-region radius and a non-monotone strategy. It is believed that the selection of an appropriate adaptive radius and the application of a suitable non-monotone strategy can improve the efficiency and robustness of the trust-region framework as well as decrease the computational costs of the algorithm by decreasing the required number of subproblems to be solved. The global convergence and the quadratic convergence of the proposed approach are proved without the non-degeneracy assumption of the exact Jacobian. The preliminary numerical results of the proposed algorithm indicating the promising behaviour of the new procedure for solving nonlinear systems are also reported.     

Multidisciplinary modeling and surrogate assisted optimization for satellite constellation systems

Satellite constellation system design is a challenging and complicated multidisciplinary design optimization (MDO) problem involving a number of computation-intensive multidisciplinary analysis models. In this paper, the MDO problem of a constellation system consisting of small observation satellites is investigated to simultaneously achieve the preliminary design of constellation configuration and the satellite subsystems. The constellation is established based on Walker-δ configuration considering the coverage performance. Coupled with the constellation configuration, several disciplines including payload, power, thermal control, and structure are taken into account for satellite subsystems design subject to various constraints (i.e., ground resolution, power usage, natural frequencies, etc.). Considering the mixed-integer and time-consuming behavior of satellite constellation system MDO problem, a novel sequential radial basis function (RBF) method using the support vector machine (SVM) for discrete-continuous mixed variables notated as SRBF-SVM-DC is proposed. In this method, a discrete-continuous variable sampling method is utilized to handle the discrete variables, i.e., the number of orbit planes and number of satellites, in the satellite constellation system MDO problem. RBF surrogates are constructed and gradually refined to represent the time-consuming simulations during optimization, which can efficiently lead the search to the optimum. Finally, the proposed SRBF-SVM-DC utilized to solve the satellite constellation system MDO problem is compared with a conventional integer coding based genetic algorithm (ICGA). The results show that SRBF-SVM-DC significantly decreases the system mass by about 28.63% subject to all the constraints, which greatly reduces the cost of the satellite constellation system. Moreover, the computational budget of SRBF-SVM-DC is saved by over 85% compared with ICGA, which demonstrates the effectiveness and practicality of the proposed surrogate assisted optimization approach for satellite constellation system design.     

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.     

Cross-layer optimization policy for QoS scheduling in computational grid

This paper presents a cross-layer quality of service (QoS) optimization policy for computational grid. Efficient QoS management is critical for computational grid to meet heterogeneity and dynamics of resources and users’ requirements. There are different QoS metrics at different layers of computational grid. To improve perceived QoS by end users over computational grid, QoS supports can be addressed in different layers, including application layer, collective layer, fabric layer and so forth. The paper tackles cross-layer grid QoS optimization as optimization decomposition, each layer corresponds to a decomposed subproblem. The proposed policy produces an optimal set of grid resources, service compositions and user's payments at the fabric layer, collective layer and application layer respectively to maximize global grid QoS. The cross-layer optimization problem decomposes into three subproblems: grid resource allocation problem, service composing and user satisfaction degree maximization problem, all of which interact through the optimal variables for capacities of grid resources and service demand. In order to coordinate the subproblems, cross-layer QoS feedback mechanism is established to ensure different layer interactions. The simulations are conducted to validate the efficiency of the proposed policy.     

布局优化子问题的改进遗传神经网络算法

带性能约束的航天舱布局问题可分解为有限多个子问题,每个子问题克服了关于优化变量的时断时续性。本文针对子问题(关于同构布局等价类),首先构造了用于产生与已知布局方案同构的布局方案的优化算法,然后在给出组合变异策略的基础上,设计了连续空间上基于实数编码的改进遗传神经网络算法。将该算法应用于二维布局优化子问题,数值实验表明该遗传神经网络进行布局逼近是有效的。这种方法是对布局问题求解的有效探索。     

Partitioned but strongly coupled iteration schemes for nonlinear fluid–structure interaction

We look at the computational procedure of computing the response of a coupled fluid–structure interaction problem. We use the so-called strong fluid–structure coupling––a totally implicit formulation. At each time step in an implicit formulation, new values for the solution variables have to be computed by solving a nonlinear system of equations, where we assume that we have solvers for the subproblems. This is often the case, when we have existing software to solve each subproblem separately, and want to couple both. We show how to solve the overall nonlinear system by using only the solvers for the subproblems. This is achieved not by considering the equilibrium equations, but the fixed-point problem resulting from the solution iteration for each of the subproblems.     

一种基于智能调度的可扩展并行强化学习方法

针对强化学习在大状态空间或连续状态空间中存在的“维数灾”问题,提出一种基于智能调度的可扩展并行强化学习方法——IS-SRL,并从理论上进行分析,证明其收敛性.该方法采用分而治之策略对大状态空间进行分块,使得每个分块能够调入内存独立学习.在每个分块学习了一个周期之后交换到外存上,调入下一个分块继续学习.分块之间在换入换出的过程中交换信息,以使整个学习任务收敛到最优解.同时针对各分块之间的学习顺序会显著影响学习效率的问题,提出了一种新颖的智能调度算法,该算法利用强化学习值函数更新顺序的分布特点,基于多种调度策略加权优先级的思想,把学习集中在能产生最大效益的子问题空间,保障了IS-SRL方法的学习效率.在上述调度算法中融入并行调度框架,利用多Agent同时学习,得到了IS-SRL方法的并行版本——IS-SPRL方法.实验结果表明,IS-SPRL方法具有较快的收敛速度和较好的扩展性能.     

A method for structural optimization which combines secondorder approximations and dual techniques

A structural optimization problem is usually solved iteratively as a sequence of approximate design problems. Traditionally, a variety of approximation concepts are used, but lately second-order approximation strategies have received most interest since high quality approximations can be obtained in this way. Furthermore, difficulties in choosing tuning parameters such as step-size restrictions may be avoided in these approaches. Methods that utilize second-order approximations can be divided into two groups; in the first, a Quadratic Programming (QP) subproblem including all available second-order information is stated, after which it is solved with a standard QP method, whereas the second approach uses only an approximate QP subproblem whose underlying structure can be efficiently exploited. In the latter case, only the diagonal terms of the second-order information are used, which makes it possible to adopt dual methods that require separability. An advantage of the first group of methods is that all available second-order information is used when stating the approximate problem, but a disadvantage is that a rather difficult QP subproblem must be solved in each iteration. The second group of methods benefits from the possibility of using efficient dual methods, but lacks in not using all available information. In this paper, we propose an efficient approach to solve the QP problems, based on the creation of a sequence of fully separable subproblems, each of which is efficiently solvable by dual methods. This procedure makes it possible to combine the advantages of each of the two former approaches. The numerical results show that the proposed solution procedure is a valid approach to solve the QP subproblems arising in second-order approximation schemes.Presented at NATO ASI Optimization of Large Structural Systems, Berchtesgaden, Germany, Sept. 23 – Oct. 4, 1991     

A Combinatorial Benders׳ decomposition for the lock scheduling problem

The Lock Scheduling Problem (LSP) is a combinatorial optimization problem that represents a real challenge for many harbours and waterway operators. The LSP consists of three strongly interconnected subproblems: scheduling lockages, assigning ships to chambers, and positioning the ships inside the chambers. These should be interpreted respectively as a scheduling, an assignment, and a packing problem. By combining the first two problems into a master problem and using the packing problem as a subproblem, a decomposition is achieved that can be solved efficiently by a Combinatorial Benders׳ approach. The master problem is solved first, thereby sequencing the ships into a number of lockages. Next, for each lockage, a packing subproblem is checked for feasibility, possibly returning a number of combinatorial inequalities (cuts) to the master problem. The result is an exact approach to the LSP. Experiments are conducted on a set of instances that were generated in correspondence with real world data. The results indicate that the decomposition approach significantly outperforms other exact approaches presented in the literature, in terms of solution quality and computation time.     

A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing

The purpose of this paper is to develop a novel hybrid optimization method (HRABC) based on artificial bee colony algorithm and Taguchi method. The proposed approach is applied to a structural design optimization of a vehicle component and a multi-tool milling optimization problem.A comparison of state-of-the-art optimization techniques for the design and manufacturing optimization problems is presented. The results have demonstrated the superiority of the HRABC over the other techniques like differential evolution algorithm, harmony search algorithm, particle swarm optimization algorithm, artificial immune algorithm, ant colony algorithm, hybrid robust genetic algorithm, scatter search algorithm, genetic algorithm in terms of convergence speed and efficiency by measuring the number of function evaluations required.