Robin型离散Schwarz波形松弛算法的收敛性分析

Schwarz波形松弛(Schwarz waveform relaxation,SWR)是一种新型区域分解算法,是当今并行计算研究领域的焦点之一,但针对该算法的收敛性分析基本上都停留在时空连续层面.从实际计算角度看,分析离散SWR算法的收敛性更重要.本文考虑SWR研究领域中非常流行的Robin型人工边界条件,分析时空离散参数t和x、模型参数等因素对算法收敛速度的影响.Robin型人工边界条件中含有一个自由参数p,可以用来优化算法的收敛速度,但最优参数的选取却需要求解一个非常复杂的极小-极大问题.本文对该极小-极大问题进行深入分析,给出最优参数的计算方法.本文给出的数值实验结果表明所获最优参数具有以下优点:(1)相比连续情形下所获最优参数,利用离散情形下获得的参数可以进一步提高Robin型SWR算法在实际计算中的收敛速度,当固定t或x而令另一个趋于零时,利用离散情形下所获参数可以使算法的收敛速度具有鲁棒性(即收敛速度不随离散参数的减小而持续变慢).(2)相比连续情形下所获收敛速度估计,离散情形下获得的收敛速度估计可以更加准确地预测算法的实际收敛速度.     

Online Surrogate Problem Methodology for Stochastic Discrete Resource Allocation Problems

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers. We propose and analyze an online control scheme which transforms the problem into a surrogate continuous optimization problem and proceeds to solve the latter using standard gradient-based approaches, while simultaneously updating both the actual and surrogate system states. It is shown that the solution of the original problem is recovered as an element of the discrete state neighborhood of the optimal surrogate state. For the special case of separable cost functions, we show that this methodology becomes particularly efficient. Finally, convergence of the proposed algorithm is established under standard technical conditions; numerical results are included in the paper to illustrate the fast convergence of this approach.     

Global optimization by random perturbation of the gradient method with a fixed parameter

The paper deals with the global minimization of a differentiable cost function mapping a ball of a finite dimensional Euclidean space into an interval of real numbers. It is established that a suitable random perturbation of the gradient method with a fixed parameter generates a bounded minimizing sequence and leads to a global minimum: the perturbation avoids convergence to local minima. The stated results suggest an algorithm for the numerical approximation of global minima: experiments are performed for the problem of fitting a sum of exponentials to discrete data and to a nonlinear system involving about 5000 variables. The effect of the random perturbation is examined by comparison with the purely deterministic gradient method.     

Nonlinear Lagrangians for Nonlinear Programming Based on Modified Fischer-Burmeister NCP Functions

This paper proposes nonlinear Lagrangians based on modified Fischer-Burmeister NCP functions for solving nonlinear programming problems with inequality constraints. The convergence theorem shows that the sequence of points generated by this nonlinear Lagrange algorithm is locally convergent when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions, and the error bound of solution, depending on the penalty parameter, is also established. It is shown that the condition number of the nonlinear Lagrangian Hessian at the optimal solution is proportional to the controlling penalty parameter. Moreover, the paper develops the dual algorithm associated with the proposed nonlinear Lagrangians. Numerical results reported suggest that the dual algorithm based on proposed nonlinear Lagrangians is effective for solving some nonlinear optimization problems.     

Analyzing the performance of simultaneous generalized hill climbing algorithms

Simultaneous generalized hill climbing (SGHC) algorithms provide a framework for using heuristics to simultaneously address sets of intractable discrete optimization problems where information is shared between the problems during the algorithm execution. Many well-known heuristics can be embedded within the SGHC algorithm framework. This paper shows that the solutions generated by an SGHC algorithm are a stochastic process that satisfies the Markov property. This allows problem probability mass functions to be formulated for particular sets of problems based on the long-term behavior of the algorithm. Such results can be used to determine the proportion of iterations that an SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient conditions that guarantee that the algorithm spends an equal number of iterations in each discrete optimization problem are provided. SGHC algorithms can also be formulated such that the overall performance of the algorithm is independent of the initial discrete optimization problem chosen. Sufficient conditions are obtained guaranteeing that an SGHC algorithm will visit the globally optimal solution for each discrete optimization problem. Lastly, rates of convergence for SGHC algorithms are reported that show that given a rate of convergence for the embedded GHC algorithm, the SGHC algorithm can be designed to preserve this rate.     

Global optimization of truss topology with discrete bar areas—Part I: theory of relaxed problems

This two part paper considers the classical problem of finding a truss design with minimal compliance subject to a given external force and a volume bound. The design variables describe the cross-section areas of the bars. While this problem is well-studied for continuous bar areas, we treat here the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single bar area, i.e., a 0/1-problem. In contrast to heuristic methods considered in other approaches, Part I of the paper together with Part II present an algorithmic framework for the calculation of a global optimizer of the underlying large-scaled mixed integer design problem. This framework is given by a convergent branch-and-bound algorithm which is based on solving a sequence of nonconvex continuous relaxations. The main issue of the paper and of the approach lies in the fact that the relaxed nonlinear optimization problem can be formulated as a quadratic program (QP). Here the paper generalizes and extends the available theory from the literature. Although the Hessian of this QP is indefinite, it is possible to circumvent the non-convexity and to calculate global optimizers. Moreover, the QPs to be treated in the branch-and-bound search tree differ from each other just in the objective function. In Part I we give an introduction to the problem and collect all theory and related proofs for the treatment of the original problem formulation and the continuous relaxed problems. The implementation details and convergence proof of the branch-and-bound methodology and the large-scale numerical examples are presented in Part II.     

A Learning Algorithm for the Control of Continuous Action Set-Point Regulator Systems

The convergence properties for reinforcement learning approaches, such as temporal differences and Q-learning, have been established under moderate assumptions for discrete state and action spaces. In practice, however, many systems have either continuous action spaces or a large number of discrete elements. This paper presents an approximate dynamic programming approach to reinforcement learning for continuous action set-point regulator problems, which learns near-optimal control policies based on scalar performance measures. The continuous-action space (CAS) algorithm uses derivative-free line search methods to obtain the optimal action in the continuous space. The theoretical convergence properties of the algorithm are presented. Several heuristic stopping criteria are investigated and practical application is illustrated by two example problems—the inverted pendulum balancing problem and the power system stabilization problem.     

Conjugate gradient techniques for the optimal control evolution dam problem

This paper considers the numerical simulation of optimal control evolution dam problem by using conjugate gradient method.The paper considers the free boundary value problem related to time dependent fluid flow in a homogeneous earth rectangular dam.The dam is taken to be sufficiently long that the flow is considered to be two dimensional.On the left and right walls of the dam there is a reservoir of fluid at a level dependent on time.This problem can be transformed into a variational inequality on a fixed domain.The numerical techniques we use are based on a linear finite element method to approximate the state equations and a conjugate gradient algorithm to solve the discrete optimal control problem.This algorithm is based on Armijo's rule in the unconstrained optimization theory.The convergence of the discrete optimal solutions to the continuous optimal solutions,and the convergence of the conjugate gradient algorithm are proved.A numerical example is given to determine the location of the minimum surface     

A predictor-corrector smoothing method for second-order cone programming

In this paper, the second order cone programming problem is studied. By introducing a parameter into the Fischer-Burmeister function, a predictor-corrector smoothing Newton method for solving the problem is presented. The proposed algorithm does neither have restrictions on its starting point nor need additional computation which keep the iteration sequence staying in the given neighborhood. Furthermore, the global and the local quadratic convergence of the algorithm are obtained, among others, the local quadratic convergence of the algorithm is established without strict complementarity. Preliminary numerical results indicate that the algorithm is effective.     

Sparse approximation of functions using sums of exponentials and AAK theory

We consider the problem of approximating functions by sums of few exponentials functions, either on an interval or on the positive half-axis. We study both continuous and discrete cases, i.e. when the function is replaced by a number of equidistant samples. Recently, an algorithm has been constructed by Beylkin and Monzón for the discrete case. We provide a theoretical framework for understanding how this algorithm relates to the continuous case.     

An Algorithm for Continuous Type Optimal Location Problem

In this paper, we extend the ordinary discrete type facility location problems to continuous type ones. Unlike the discrete type facility location problem in which the objective function isn't everywhere differentiable, the objective function in the continuous type facility location problem is strictly convex and continuously differentiable. An algorithm without line search for solving the continuous type facility location problems is proposed and its global convergence, linear convergence rate is proved. Numerical experiments illustrate that the algorithm suggested in this paper have smaller amount of computation, quicker convergence rate than the gradient method and conjugate direction method in some sense.     

SOLUTION OF OPTIMAL TRANSPORTATION PROBLEMS USING A MULTIGRID LINEAR PROGRAMMING APPROACH

We compute and visualize solutions to the Optimal Transportation (OT) problem for a wide class of cost functions. The standard linear programming (LP) discretization of the continuous problem becomes intractable for moderate grid sizes. A grid refinement method results in a linear cost algorithm. Weak convergence of solutions is established and barycentric projection of transference plans is used to improve the accuracy of solutions. Optimal maps between nonconvex domains, partial OT free boundaries, and high accuracy barycenters are presented.     

Local parameter identifiability for one class of hybrid systems

We consider the problem of local parameter identifiability for a hybrid system with components that are continuous and discrete in time. The set of observations is the vector-solution (depending on the parameter that is continuous in time) of the discrete component. Sufficient conditions of local parameter identifiability have been formulated using the earlier introduced notion of normalized separability of the set of parameters from the kernel of a special functional. An example where the condition of normed separability is reduced to some rank criterion is given.     

一种单位化的增量梯度算法

研究目标函数是若干光滑函数和的可分离优化问题,提出了一种单位化增量梯度算法.该算法每次子迭代只需要计算一个(或几个)分量函数的单位负梯度方向作为迭代方向.在一定条件下,证明了采用发散步长的单位化增量梯度算法的收敛性.作为应用,新算法和Bertsekas D P,Tsitsikils J N提出的(没有单位化)增量梯度算...     

Iterative learning consensus control with initial state learning for fractional order distributed parameter models multi-agent systems

This paper considers the consensus control problem of multi-agent systems (MAS) with distributed parameter models. Based on the framework of network topologies, a second-order PI-type iterative learning control (ILC) protocol with initial state learning is proposed by using the nearest neighbor knowledge. A discrete system for proposed ILC is established, and the consensus control problem is then converted to a stability problem for such a discrete system. Furthermore, by using generalized Gronwall inequality, a sufficient condition for the convergence of the consensus errors between any two agents is obtained. Finally, the validity of the proposed method is verified by two numerical examples.     

A STOCHASTIC MOVING BALLS APPROXIMATION METHOD OVER A SMOOTH INEQUALITY CONSTRAINT

We consider the problem of minimizing the average of a large number of smooth component functions over one smooth inequality constraint. We propose and analyze a stochastic Moving Balls Approximation (SMBA) method. Like stochastic gradient (SG) methods, the SMBA method's iteration cost is independent of the number of component functions and by exploiting the smoothness of the constraint function, our method can be easily implemented. Theoretical and computational properties of SMBA are studied, and convergence results are established. Numerical experiments indicate that our algorithm dramatically outperforms the existing Moving Balls Approximation algorithm (MBA) for the structure of our problem.     

A block coordinate variable metric linesearch based proximal gradient method

In this paper we propose an alternating block version of a variable metric linesearch proximal gradient method. This algorithm addresses problems where the objective function is the sum of a smooth term, whose variables may be coupled, plus a separable part given by the sum of two or more convex, possibly nonsmooth functions, each depending on a single block of variables. Our approach is characterized by the possibility of performing several proximal gradient steps for updating every block of variables and by the Armijo backtracking linesearch for adaptively computing the steplength parameter. Under the assumption that the objective function satisfies the Kurdyka-?ojasiewicz property at each point of its domain and the gradient of the smooth part is locally Lipschitz continuous, we prove the convergence of the iterates sequence generated by the method. Numerical experience on an image blind deconvolution problem show the improvements obtained by adopting a variable number of inner block iterations combined with a variable metric in the computation of the proximal operator.     

Convergence properties of an algorithm for solving non-differentiable optimal control problems

An algorithm for solving the open-loop optimal control problem proposed by Y. Sakawa and Y. Shindo is analysed. The algorithm is essentially based on the use of the Pontriagin maximum principle. The convergence properties of the algorithm are investigated. It is established here, under weaker assumptions, that i) the algorithm is well-defined, ii) the cost functional monotonically decreases, iii) a weak necessary optimality condition is asymptotically verified, if the sequence of computational control parameters is bounded from above and from below.     

Adaptive memory in multistart heuristics for multicommodity network design

This paper focuses on the use of different memory strategies to improve multistart methods. A network design problem in which the costs are given by discrete stepwise increasing cost functions of the capacities installed in the edges is used to illustrate the contributions of adaptive memory and vocabulary building strategies. Heuristics based on shortest path and maximum flow algorithms are combined with adaptive memory in order to obtain an approximate solution to the problem in the framework of a multistart algorithm. Furthermore, a vocabulary building intensification mechanism supported by the resolution of a linear program is also explored. Numerical experiments have shown that the proposed algorithm obtained the best known solutions for some instances in the literature. These results show the contribution of each memory component and the effectiveness of their combination.     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.