Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

有向树的部分逆M矩阵完备及其算法设计

1 引言 M矩阵是具有非正非对角元且其逆是非负矩阵的一类矩阵．逆M矩阵是逆为M矩阵的一类非负矩阵．部分矩阵是指一个矩阵中一些元已定,其余未定元还可以自由选择的矩阵．如果在一个部分矩阵中,其每个已定的主子矩阵均为逆M矩阵并且所有已定元均是非负的,称这个部分矩阵是一个部分逆M矩阵．一个部分逆M矩阵的完备式是对     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

SCHWARZ TYPE DOMAIN DECOMPOSITION ALGORITHMS FOR PARABOLIC EQUATIONS AND ERROR ESTIMATES

1.IntroductionTheSchwarzalternatingmethodwasintroducedbyH.A.SchWarz(1870)120yearsagoasatechniqueforprovingtheexistenceofsolutionstocertainellipticproblemsdefinedonadomainofcomplicatedgeometries.Sincethenthemethodhasbeenextendedtononlinearproblemsandhasbeenproventobeasuitabledivideandconquertechniquetosolveawideclassofproblems,forinstance,see[2,3,8--10].Inthispaperweareinterestedinsolvingtheparabolicproblemsbyusingimplicitschemes,suchasbackwardEulerschemeinthetimevariable.Ateachfixedtimeleve…     

Cubic spline method for a class of nonlinear singularly-perturbed boundary-value problems

In this paper, we present a numerical method for solving a class of nonlinear, singularly perturbed two-point boundary-value problems with a boundary layer on the left end of the underlying interval. The original second-order problem is reduced to an asymptotically equivalent first-order problem and is solved by a numerical method using a fourth-order cubic spline in the inner region. The method has been analyzed for convergence and is shown to yield anO(h ⁴) approximation to the solution. Some test examples have been solved to demonstrate the efficiency of the method.The authors thank the referee for his helpful comments.     

Linear elliptic boundary value problems in varying domains

The paper is devoted to the study of solutions to linear elliptic boundary value problems in domains depending smoothly on a small perturbation parameter. To this end we transform the boundary value problem onto a fixed reference domain and obtain a problem in a fixed domain but with differential operators depending on the perturbation parameter. Using the Fredholm property of the underlying operator we show the differentiability of the transformed solution under the assumption that the dimension of the kernel does not depend on the perturbation parameter. Furthermore, we obtain an explicit representation for the corresponding derivative.     

Local a posteriori error estimates and adaptive control of pollution effects

Local a posteriori error estimators are derived for linear elliptic problems over general polygonal domains in 2d. The estimators lead to a sharp upper bound for the energy error in a local region of interest. This upper bound consists of H¹‐type local error indicators in a slightly larger subdomain, plus weighted L²‐type local error indicators outside this subdomain, which account for the pollution effects. This constitutes the basis of a local adaptive refinement procedure. Numerical experiments show a superior performance than the standard global procedure as well as the generation of locally quasi‐optimal meshes. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 421–442, 2003     

Necessary and sufficient conditions of optimality for some classical scheduling problems

A scheduling problem is generally to order the jobs such that a certain objective function f(π) is minimized. For some classical scheduling problems, only sufficient conditions of optimal solutions are concerned in the literature. In this paper, we study the necessary and sufficient conditions by means of the concept of critical ordering (critical jobs and their relations). These results are meaningful in recognition and characterization of optimal solutions of scheduling problems.     

Application of the Proximal Point Method to Nonmonotone Equilibrium Problems

We consider a general equilibrium problem defined on a convex set, whose cost bifunction may not be monotone. We show that this problem can be solved by the inexact proximal point method if there exists a solution to the dual problem. An application of this approach to nonlinearly constrained problems is also suggested.