关于二阶椭圆方程区域分裂法的最优预处理

§0.引言 区域分裂是与微分方程数值解的并行计算的数学基础密切相关的,预处理共轭梯度法是区域分裂的一个主要途径,寻找好的预处理子是关键问题,本文给出一个较一般性的方法,预处理过程包括一个整体小规模问题和若干个独立的局部子问题,整体问题和局部问题的选取均有极大的任意性,预处理条件数的估计是由整体问题和局部问题的一些特     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

Preconditioning of the Stiffness Matrix of Local Refined Triangulation

A preconditioning method for the finite element stiffness matrix is given in this paper. The triangulation is refined in a subregion; the preconditioning process is composed of resolution of two regular subproblems; the condition number of the preconditioned matrix is O(1 logH/h), where H and h are mesh sizes of the unrefined and local refined triangulations respectively.     

A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

Multilevel preconditioning for perturbed finite element matrices

Multilevel preconditioning methods for finite element matricesfor the approximation of second-order elliptic problems areconsidered. Using perturbations of the local finite elementmatrices by zero-order terms it is shown that one can controlthe smallest eigenvalues. In this way in a multilevel methodone can reach a final coarse mesh, where the remaining problemto be solved has a condition number independent of the totaldegrees of freedom, much earlier than if no perturbations wereused. Hence, there is no need in a method of optimal computationalcomplexity to carry out the recursion in the multilevel methodto a coarse mesh with a fixed number of degrees of freedom.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

A general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty

In this paper, a general algorithm for solving Generalized Geometric Programming with nonpositive degree of difficulty is proposed. It shows that under certain assumptions the primal problem can be transformed and decomposed into several subproblems which are easy to solve, and furthermore we verify that through solving these subproblems we can obtain the optimal value and solutions of the primal problem which are global solutions. At last, some examples are given to vindicate our conclusions.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

一种具有非线性约束线性规划全局优化算法

本文提出了一种新的适用于处理非线性约束下线性规划问题的全局优化算法。该算法通过构造子问题来寻找优于当前局部最优解的可行解。该子问题可通过模拟退火算法来解决。通过求解一系列的子问题,当前最优解被不断地更新,最终求得全局最优解。最后,本算法应用于几个典型例题,并与罚函数法相比较,数值结果表明该算法是可行的,有效的。     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

Schwarz methods of neumann-neumann type for three-dimensional elliptic finite element problems

Several domain decomposition methods of Neumann-Neumann type are considered for solving the large linear systems of algebraic equations that arise from discretizations of elliptic problems by finite elements. We will only consider problems in three dimensions. Several new variants of the basic algorithm are introduced in a Schwarz method framework that provides tools which have already proven very useful in the design and analysis of other domain decomposition and multi-level methods. The Neumann-Neumann algorithms have several advantages over other domain decomposition methods. The subregions, which define the subproblems, only share the boundary degrees of freedom with their neighbors. The subregions can also be of quite arbitrary shape and many of the major components of the preconditioner can be constructed from subprograms available in standard finite element program libraries. In its original form, however, the algorithm lacks a mechanism for global transportation of information and its performance therefore suffers when the number of subregions increases. In the new variants of the algorithms, considered in this paper, the preconditioners include global components, of low rank, to overcome this difficulty. Bounds are established for the condition number of the iteration operator, which are independent of the number of subregions, and depend only polylogarithmically on the number of degrees of freedom of individual local subproblems. Results are also given for problems with arbitrarily large jumps in the coefficients across the interfaces separating the subregions. ©1995 John Wiley & Sons, Inc.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Application of the method of multipliers to state space constrained optimal control problems with discrete time

The paper deals with convergence conditions of multiplier algorithms for solving optimal control problems with discrete time suggested by J. Bjbvonek in some earlier papers. In this approach the original state space constrained problem is converted into a control-constrained problem by introducing an additional control variable and an equality constraint which is taken into consideration by a multiplier method. Convergence conditions for the multiplier Iteration of global and local nature are given for exact and inexact solution of the subproblems.     

Unsteady convection and convection-diffusion problems via direct overlapping domain decomposition methods

In solving unsteady problems,domain decomposition methods may be used either for iterative preconditioning each global implicit time-step or directly (noniteratively) within a blockwise implicit time-stepping procedure, in the latter case, the inner boundary values for the subproblems are generated by explicit time-extrapolation. The overlapping variants of this method have been proved to be efficient tools for solving parabolic and first-order hyperbolic problems on modern parallel computers, because they require global communication only once per time-step. The mechanism making this possible is the exponential decay in space of the time-discrete Green's function. We investigate several model problems of convection and convection-diffusion. Favorable optimal and far-reaching estimates of the overlap required have been established in the case of exemplary standard upwind finite-difference schemes. In particular, it has been shown that the overlap for the convection-diffusion problem is the additive function of overlaps for the corresponding convection and diffusion problem to be considered independently. These results have been confirmed with several numerical test examples. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 387–406, 1998     

一类大系统目标规划问题最优解的判别准则

本文将一类大系统目标规划问题分解为若干个子问题,研究了原问题的最优解和各个子问题最优解之间的关系,并讨论了原问题最优解的判别条件．     

The layout problem of two kinds of graph elements with performance constraints and its optimality conditions

This paper presents an optimization model with performance constraints for two kinds of graph elements layout problem. The layout problem is partitioned into finite subproblems by using graph theory and group theory, such that each subproblem overcomes its on-off nature about optimal variable. Furthermore each subproblem is relaxed and the continuity about optimal variable doesn’t change. We construct a min-max problem which is locally equivalent to the relaxed subproblem and develop the first order necessary and sufficient conditions for the relaxed subproblem by virtue of the min-max problem and the theories of convex analysis and nonsmooth optimization. The global optimal solution can be obtained through the first order optimality conditions.     

An algorithm for nonlinear optimization problems with binary variables

One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases. Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage, we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how well the algorithm performs we show the computational results of applying it to problems taken from the literature and new test problems with known optimal solutions.     

Coordinated control of distribution supply chains in the presence of fuzzy customer demand

This paper considers a single product inventory control in a Distribution Supply Chain (DSC). The DSC operates in the presence of uncertainty in customer demands. The demands are described by imprecise linguistic expressions that are modelled by discrete fuzzy sets. Inventories at each facility within the DSC are replenished by applying periodic review policies with optimal order up-to-quantities. Fuzzy customer demands imply fuzziness in inventory positions at the end of review intervals and in incurred relevant costs per unit time interval. The determination of the minimum of defuzzified total cost of the DSC is a complex problem which is solved by applying decomposition; the original problem is decomposed into a number of simpler independent optimisation subproblems, where each retailer and the warehouse determine their optimum periodic reviews and order up-to-quantities. An iterative coordination mechanism is proposed for changing the review periods and order up-to-quantities for each retailer and the warehouse in such a way that all parties within the DSC are satisfied with respect to total incurred costs per unit time interval. Coordination is performed by introducing fuzzy constraints on review periods and fuzzy tolerances on retailers and warehouse costs in local optimisation subproblems.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.