Solution to nonconvex quadratic programming with both inequality and box constraints

This paper presents a canonical dual approach for solving nonconvex quadratic programming problems subjected to both linear inequality constraints and box constrains. It is proved that the constrained nonconvex primal problem can be reformulated as a concave maximization dual problem with zero duality gap, which can be solved under certain conditions. Both global and local extremimality conditions are presented by the triality theory. Several applications are illustrated. The main result of this paper has been announced at the Seventh International Conference on Optimization: Techniques and Applications, Kobe, Japan, Dec. 12–15, 2007.     

Lower bound limit analysis of cohesive‐frictional materials using second‐order cone programming

The formulation of limit analysis by means of the finite element method leads to an optimization problem with a large number of variables and constraints. Here we present a method for obtaining strict lower bound solutions using second‐order cone programming (SOCP), for which efficient primal‐dual interior‐point algorithms have recently been developed. Following a review of previous work, we provide a brief introduction to SOCP and describe how lower bound limit analysis can be formulated in this way. Some methods for exploiting the data structure of the problem are also described, including an efficient strategy for detecting and removing linearly dependent constraints at the assembly stage. The benefits of employing SOCP are then illustrated with numerical examples. Through the use of an effective algorithm/software, very large optimization problems with up to 700 000 variables are solved in minutes on a desktop machine. The numerical examples concern plane strain conditions and the Mohr–Coulomb criterion, however we show that SOCP can also be applied to any other problem of lower bound limit analysis involving a yield function with a conic quadratic form (notable examples being the Drucker–Prager criterion in 2D or 3D, and Nielsen's criterion for plates). Copyright © 2005 John Wiley & Sons, Ltd.     

Joint cell loading and scheduling approach to cellular manufacturing systems

A hierarchical multi-objective heuristic algorithm and pricing mechanism are developed to first determine the cell loading decisions, and then lot sizes for each item and to obtain a sequence of items comprising the group technology families to be processed at each manufacturing cell that minimise the setup, inventory holding, overtime and tardiness costs simultaneously. The linkage between the different levels is achieved using the proposed pricing mechanism through a set of dual variables associated with the resource and inventory balance constraints, and the feasibility status feedback information is passed between the levels to ensure internally consistent decisions. The computational results indicate that the proposed algorithm is very efficient in finding a compromise solution for a set of randomly generated problems compared with a set of competing algorithms.     

An augmented Lagrangian quasi-Newton solver for constrained nonlinear finite element applications

A solution scheme is presented for constrained non-linear equations of evolution that result, for example, from the finite element discretization of mechanical contact problems. The algorithm discussed utilizes a quasi-Newton non-linear equation solving strategy, with constraints enforced by an augmented Lagrangian iteration procedure. Through presentation of a simple model problem and its generalization, it is shown that the iterations associated with both the quasi-Newton algorithm and the augmentation procedure can be interwoven to produce a highly efficient and robust solution strategy.     

Physics-constrained non-Gaussian probabilistic learning on manifolds

An extension of the probabilistic learning on manifolds (PLoM), recently introduced by the authors, has been presented: In addition to the initial data set given for performing the probabilistic learning, constraints are given, which correspond to statistics of experiments or of physical models. We consider a non-Gaussian random vector whose unknown probability distribution has to satisfy constraints. The method consists in constructing a generator using the PLoM and the classical Kullback-Leibler minimum cross-entropy principle. The resulting optimization problem is reformulated using Lagrange multipliers associated with the constraints. The optimal solution of the Lagrange multipliers is computed using an efficient iterative algorithm. At each iteration, the Markov chain Monte Carlo algorithm developed for the PLoM is used, consisting in solving an Itô stochastic differential equation that is projected on a diffusion-maps basis. The method and the algorithm are efficient and allow the construction of probabilistic models for high-dimensional problems from small initial data sets and for which an arbitrary number of constraints are specified. The first application is sufficiently simple in order to be easily reproduced. The second one is relative to a stochastic elliptic boundary value problem in high dimension.     

An efficient approach for reliability-based topology optimization

This article presents an efficient approach for reliability-based topology optimization (RBTO) in which the computational effort involved in solving the RBTO problem is equivalent to that of solving a deterministic topology optimization (DTO) problem. The methodology presented is built upon the bidirectional evolutionary structural optimization (BESO) method used for solving the deterministic optimization problem. The proposed method is suitable for linear elastic problems with independent and normally distributed loads, subjected to deflection and reliability constraints. The linear relationship between the deflection and stiffness matrices along with the principle of superposition are exploited to handle reliability constraints to develop an efficient algorithm for solving RBTO problems. Four example problems with various random variables and single or multiple applied loads are presented to demonstrate the applicability of the proposed approach in solving RBTO problems. The major contribution of this article comes from the improved efficiency of the proposed algorithm when measured in terms of the computational effort involved in the finite element analysis runs required to compute the optimum solution. For the examples presented with a single applied load, it is shown that the CPU time required in computing the optimum solution for the RBTO problem is 15–30% less than the time required to solve the DTO problems. The improved computational efficiency allows for incorporation of reliability considerations in topology optimization without an increase in the computational time needed to solve the DTO problem.     

A Two-Stage Planning Model for Power Scheduling in a Hydro-Thermal System Under Uncertainty

A two-stage stochastic programming model for the short- or mid-term cost-optimal electric power production planning is developed. We consider the power generation in a hydro-thermal generation system under uncertainty in demand (or load) and prices for fuel and delivery contracts. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints that couple power units. It is assumed that the stochastic load and price processes are given (or approximated) by a finite number of realizations (scenarios). Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a specific descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the primal problem is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon of 168 hours. The sizes of the corresponding optimization problems go up to 400.000 binary and 650.000 continuous variables, and more than 1.300.000 constraints.     

Developing a fuzzy proportional–derivative controller optimization engine for engineering design optimization problems

In real world engineering design problems, decisions for design modifications are often based on engineering heuristics and knowledge. However, when solving an engineering design optimization problem using a numerical optimization algorithm, the engineering problem is basically viewed as purely mathematical. Design modifications in the iterative optimization process rely on numerical information. Engineering heuristics and knowledge are not utilized at all. In this article, the optimization process is analogous to a closed-loop control system, and a fuzzy proportional–derivative (PD) controller optimization engine is developed for engineering design optimization problems with monotonicity and implicit constraints. Monotonicity between design variables and the objective and constraint functions prevails in engineering design optimization problems. In this research, monotonicity of the design variables and activities of the constraints determined by the theory of monotonicity analysis are modelled in the fuzzy PD controller optimization engine using generic fuzzy rules. The designer only needs to define the initial values and move limits of the design variables to determine the parameters in the fuzzy PD controller optimization engine. In the optimization process using the fuzzy PD controller optimization engine, the function value of each constraint is evaluated once in each iteration. No sensitivity information is required. The fuzzy PD controller optimization engine appears to be robust in the various design examples tested.     

A reduced basis method for parametrized variational inequalities applied to contact mechanics

We investigate new developments of the reduced-basis method for parametrized optimization problems with nonlinear constraints. We propose a reduced-basis scheme in a saddle-point form combined with the Empirical Interpolation Method to deal with the nonlinear constraint. In this setting, a primal reduced-basis is needed for the primal solution and a dual one is needed for the Lagrange multipliers. We suggest to construct the latter using a cone-projected greedy algorithm that conserves the non-negativity of the dual basis vectors. The reduction strategy is applied to elastic frictionless contact problems including the possibility of using nonmatching meshes. The numerical examples confirm the efficiency of the reduction strategy.     

Computation of limit and shakedown loads using a node‐based smoothed finite element method

This paper presents a novel numerical procedure for computing limit and shakedown loads of structures using a node‐based smoothed FEM in combination with a primal–dual algorithm. An associated primal–dual form based on the von Mises yield criterion is adopted. The primal‐dual algorithm together with a Newton‐like iteration are then used to solve this associated primal–dual form to determine simultaneously both approximate upper and quasi‐lower bounds of the plastic collapse limit and the shakedown limit. The present formulation uses only linear approximations and its implementation into finite element programs is quite simple. Several numerical examples are given to show the reliability, accuracy, and generality of the present formulation compared with other available methods. Copyright © 2011 John Wiley & Sons, Ltd.     

Integrating production-transportation planning decision with fuzzy multiple goals in supply chains

This work presents a novel fuzzy multi-objective linear programming (f-MOLP) model for solving integrated production-transportation planning decision (PTPD) problems in supply chains in a fuzzy environment. The proposed model attempts to simultaneously minimise total production and transportation costs, total number of rejected items, and total delivery time with reference to available capacities, labor level, quota flexibility, and budget constraints at each source, as well as forecast demand and warehouse space at each destination. An industrial case demonstrates that the proposed f-MOLP model achieves an efficient compromise solution and overall decision maker satisfaction with determined goal values. Additionally, the proposed model provides a systematic framework that facilitates decision makers to interactively modify the fuzzy data and parameters until a satisfactory solution is obtained. Overall, the f-MOLP model offers a practical method for solving PTPD problems with fuzzy multiple goals, and can effectively improve producer–distributor relationships within a supply chain.     

Model order reduction with Galerkin projection applied to nonlinear optimization with infeasible primal-dual interior point method

It is not new that model order reduction (MOR) methods are employed in almost all fields of engineering to reduce the processing time of complex computational simulations. At the same time, interior point methods (IPMs), a method to deal with inequality constraint problems (which is little explored in engineering), can be applied in many fields such as plasticity theory, contact mechanics, micromechanics, and topology optimization. In this work, a MOR based in Galerkin projection is coupled with the infeasible primal-dual IPM. Such research concentrates on how to develop a Galerkin projection in one field with the interior point method; the combination of both methods, coupled with Schur complement, permits to solve this MOR similar to problems without constraints, leading to new approaches to adaptive strategies. Moreover, this research develops an analysis of error from the Galerkin projection related to the primal and dual variables. Finally, this work also suggests an adaptive strategy to alternate the Galerkin projection operator, between primal and dual variable, according to the error during the processing of a problem.     

A new impedance accounting for short‐ and long‐range effects in mixed substructured formulations of nonlinear problems

An efficient method for solving large nonlinear problems combines Newton solvers and domain decomposition methods. In the domain decomposition method framework, the boundary conditions can be chosen to be primal, dual, or mixed. The mixed approach presents the advantage to be eligible for the research of an optimal interface parameter (often called impedance), which can increase the convergence rate. The optimal value for this parameter is usually too expensive to be computed exactly in practice: An approximate version has to be sought, along with a compromise between efficiency and computational cost. In the context of parallel algorithms for solving nonlinear structural mechanical problems, we propose a new heuristic for the impedance, which combines short‐ and long‐range effects at a low computational cost.     

A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routes. The problem is considered in the aspect of the natural constraints of real-life production systems such as cell size, separation and co-location constraints. Co-location constraints were added to the proposed model in order to deal with the necessity of grouping certain machines in the same cell for technical reasons, and separation constraints were included to prevent placing certain machines in close vicinity. The objective is to minimise the weighted sum of the voids and the exceptional elements. A hybrid algorithm is proposed to solve this problem. The proposed algorithm hybridises the modified sub-gradient (MSG) algorithm with a genetic algorithm. MSG algorithm solves the sharp augmented Lagrangian dual problems, where zero duality gap property is guaranteed for a wide class of optimisation problems without convexity assumption. Generally, the dual problem is solved by using GAMS solvers in the literature. In this study, a genetic algorithm has been used for solving the dual problem at the first time. The experimental results show the advantage of combining the MSG algorithm and the genetic algorithm. Although the MSG algorithm, whose dual problem is solved by GAMS solver, and the genetic algorithm cannot find feasible solutions, hybrid algorithm generates feasible solutions for all of the test problems.     

A two‐level nonoverlapping Schwarz algorithm for the Stokes problem without primal pressure unknowns

A two‐level nonoverlapping Schwarz algorithm is developed for the Stokes problem. The main feature of the algorithm is that a mixed problem with both velocity and pressure unknowns is solved with a balancing domain decomposition by constraints (BDDC)‐type preconditioner, which consists of solving local Stokes problems and one global coarse problem related to only primal velocity unknowns. Our preconditioner allows to use a smaller set of primal velocity unknowns than other BDDC preconditioners without much concern on certain flux conditions on the subdomain boundaries and the inf–sup stability of the coarse problem. In the two‐dimensional case, velocity unknowns at subdomain corners are selected as the primal unknowns. In addition to them, averages of each velocity component across common faces are employed as the primal unknowns for the three‐dimensional case. By using its close connection to the Dual–primal finite element tearing and interconnecting (FETI‐DP algorithm) (SIAM J Sci Comput 2010; 32 : 3301–3322; SIAM J Numer Anal 2010; 47 : 4142–4162], it is shown that the resulting matrix of our algorithm has the same eigenvalues as the FETI‐DP algorithm except zero and one. The maximum eigenvalue is determined by H/h, the number of elements across each subdomains, and the minimum eigenvalue is bounded below by a constant, which does not depend on any mesh parameters. Convergence of the method is analyzed and numerical results are included. Copyright © 2011 John Wiley & Sons, Ltd.     

Hybrid hyper‐reduced modeling for contact mechanics problems

The model reduction of mechanical problems involving contact remains an important issue in computational solid mechanics. In this article, we propose an extension of the hyper‐reduction method based on a reduced integration domain to frictionless contact problems written by a mixed formulation. As the potential contact zone is naturally reduced through the reduced mesh involved in hyper‐reduced equations, the dual reduced basis is chosen as the restriction of the dual full‐order model basis. We then obtain a hybrid hyper‐reduced model combining empirical modes for primal variables with finite element approximation for dual variables. If necessary, the inf‐sup condition of this hybrid saddle‐point problem can be enforced by extending the hybrid approximation to the primal variables. This leads to a hybrid hyper‐reduced/full‐order model strategy. This way, a better approximation on the potential contact zone is further obtained. A posttreatment dedicated to the reconstruction of the contact forces on the whole domain is introduced. In order to optimize the offline construction of the primal reduced basis, an efficient error indicator is coupled to a greedy sampling algorithm. The proposed hybrid hyper‐reduction strategy is successfully applied to a 1‐dimensional static obstacle problem with a 2‐dimensional parameter space and to a 3‐dimensional contact problem between two linearly elastic bodies. The numerical results show the efficiency of the reduction technique, especially the good approximation of the contact forces compared with other methods.     

Adaptive multigrid method using duality in plane elasticity

This work presents an adaptive multigrid method for the mixed formulation of plane elasticity problems. First, a mixed‐hybrid formulation is introduced where the continuity of the normal components of the stress tensor is indirectly imposed using a Lagrange multiplier. Two different numerical approximations, naturally associated with the primal problem and the dual problem, are then proposed. The Complementary Energy Principle provides an a posteriori error estimate. For the effective solving of both systems of equations, a non‐standard multigrid algorithm has been designed that allows us to solve the two problems, dual and primal, with reasonable cost and in an integrated way. Finally, a significant numerical application is presented to check the efficiency of the error estimator and the good performance of the algorithm. Copyright © 2001 John Wiley & Sons, Ltd.     

A decomposition procedure for large-scale optimum plastic design problems

A decomposition procedure is proposed in this paper for solving a class of large-scale optimum design problems for perfectly-plastic structures under several alternative loading conditions. The conventional finite element method is used to cast the problem into a finite dimensional constrained nonlinear programming problem. Structures of practically meaningful size and complexity tend to give rise to a large number of variables and constraints in the corresponding mathematical model. The difficulty is that the state-of-the-art mathematical programming theory does not provide reliable and efficient ways of solving large-scale constrained nonlinear programming problems. The natural idea to deal with the large-scale structural problem is somehow to decompose the problem into a collection of small-size problems each of which represents an analysis of the behaviour of each finite element under a single loading condition. This paper proposes one such way of decomposition based on duality theory and a recently developed iterative algorithm called the proximal point algorithm.     

FETI‐DP: a dual–primal unified FETI method—part I: A faster alternative to the two‐level FETI method

The FETI method and its two‐level extension (FETI‐2) are two numerically scalable domain decomposition methods with Lagrange multipliers for the iterative solution of second‐order solid mechanics and fourth‐order beam, plate and shell structural problems, respectively.The FETI‐2 method distinguishes itself from the basic or one‐level FETI method by a second set of Lagrange multipliers that are introduced at the subdomain cross‐points to enforce at each iteration the exact continuity of a subset of the displacement field at these specific locations. In this paper, we present a dual–primal formulation of the FETI‐2 concept that eliminates the need for that second set of Lagrange multipliers, and unifies all previously developed one‐level and two‐level FETI algorithms into a single dual–primal FETI‐DP method. We show that this new FETI‐DP method is numerically scalable for both second‐order and fourth‐order problems. We also show that it is more robust and more computationally efficient than existing FETI solvers, particularly when the number of subdomains and/or processors is very large. Copyright © 2001 John Wiley & Sons, Ltd.     

An exact penalty function method for optimising QAP formulation in facility layout problem

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.