On embedding the volume algorithm in a variable target value method

We employ the volume algorithm as a subgradient deflection strategy in a variable target value method for solving nondifferentiable optimization problems. Focusing on Lagrangian duals for LPs, we exhibit primal nonconvergence of the original method, establish convergence of the proposed algorithm in the dual space, and present related computational results.     

Decay mode solution of nonlinear boundary–initial value problems for the cylindrical (spherical) Boussinesq–Burgers equations

The major target of this paper is to construct new nonlinear boundary–initial value problems for Boussinesq–Burgers Equations, and derive the solutions of these nonlinear boundary–initial value problems by the simplified homogeneous balance method. The nonlinear transformation and its inversion between the Boussinesq–Burgers Equations and the linear heat conduction equation are firstly derived; then a new nonlinear boundary–initial value problem for the Boussinesq–Burgers equations with variable damping on the half infinite straight line is put forward for the first time, and the solution of this nonlinear boundary–initial value problem is obtained, especially, the decay mode solution of nonlinear boundary–initial value problem for the cylindrical (spherical) Boussinesq–Burgers equations is obtained.     

The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches

We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure.     

Nonlocal boundary value problems in differential and difference settings

We study nonlocal boundary value problems of the first and second kind for the heat equation with variable coefficients in the differential and difference settings. By the method of energy inequalities, we find a priori estimates for the differential and difference problems.     

On the stability and convergence of nonlocal difference schemes

We study nonlocal boundary value problems of the first and second kind for the heat equation with variable coefficients in the differential and finite-difference settings. By using the method of energy inequalities, we obtain a priori estimates for the corresponding differential and finite-difference problems.     

Bayesian shrinkage in mixture-of-experts models: identifying robust determinants of class membership

Advances in Data Analysis and Classification - A method for implicit variable selection in mixture-of-experts frameworks is proposed. We introduce a prior structure where information is taken from...     

Backward stochastic differential equations on manifolds

The problem of finding a martingale on a manifold with a fixed random terminal value can be solved by considering BSDEs with a generator with quadratic growth. We study here a generalization of these equations and we give uniqueness and existence results in two different frameworks, using differential geometry tools. Applications to PDEs are given, including a certain class of Dirichlet problems on manifolds.     

Families of exact solutions for linear and nonlinear wave equations with a variable speed of sound and their use in solving initial boundary value problems

We propose a procedure for multiplying solutions of linear and nonlinear one-dimensional wave equations, where the speed of sound can be an arbitrary function of one variable. We obtain exact solutions. We show that the functional series comprising these solutions can be used to solve initial boundary value problems. For this, we introduce a special scalar product.     

Strong solution of boundary value problems in cylindrical domains for a fourth-order equation of composite type

We use the method of energy inequalities and averaging operators with variable step to prove the existence and uniqueness of a strong solution of boundary value problems for a fourth-order equation of composite type.     

A global optimization algorithm for generalized semi-infinite,continuous minimax with coupled constraints and bi-level problems

We propose an algorithm for the global optimization of three problem classes: generalized semi-infinite, continuous coupled minimax and bi-level problems. We make no convexity assumptions. For each problem class, we construct an oracle that decides whether a given objective value is achievable or not. If a given value is achievable, the oracle returns a point with a value better than or equal to the target. A binary search is then performed until the global optimum is obtained with the desired accuracy. This is achieved by solving a series of appropriate finite minimax and min-max-min problems to global optimality. We use Laplace’s smoothing technique and a simulated annealing approach for the solution of these problems. We present computational examples for all three problem classes.     

一阶双曲型方程组初边值问题的差分格式及其稳定性

本文比较系统地讨论了有关数值求解两个自变量的一阶双曲型方程组初边值问题的某些问题,给出了几种能用于任何类型的初边值问题的差分格式,并在很宽的条件下证明了其中的某些变系数的初边值问题的差分格式对初值和边值是稳定的、差分格式所立出的方程组是良态的.其中的某些格式已用于解决某些复杂的实际问题(应用部分见[16]).     

Probabilistic decision graphs for optimization under uncertainty

This paper provides a survey on probabilistic decision graphs for modeling and solving decision problems under uncertainty. We give an introduction to influence diagrams, which is a popular framework for representing and solving sequential decision problems with a single decision maker. As the methods for solving influence diagrams can scale rather badly in the length of the decision sequence, we present a couple of approaches for calculating approximate solutions. The modeling scope of the influence diagram is limited to so-called symmetric decision problems. This limitation has motivated the development of alternative representation languages, which enlarge the class of decision problems that can be modeled efficiently. We present some of these alternative frameworks and demonstrate their expressibility using several examples. Finally, we provide a list of software systems that implement the frameworks described in the paper.     

Probabilistic decision graphs for optimization under uncertainty

This paper provides a survey on probabilistic decision graphs for modeling and solving decision problems under uncertainty. We give an introduction to influence diagrams, which is a popular framework for representing and solving sequential decision problems with a single decision maker. As the methods for solving influence diagrams can scale rather badly in the length of the decision sequence, we present a couple of approaches for calculating approximate solutions. The modeling scope of the influence diagram is limited to so-called symmetric decision problems. This limitation has motivated the development of alternative representation languages, which enlarge the class of decision problems that can be modeled efficiently. We present some of these alternative frameworks and demonstrate their expressibility using several examples. Finally, we provide a list of software systems that implement the frameworks described in the paper.     

An ADI Petrov–Galerkin method with quadrature for parabolic problems

We propose and analyze a fully discrete Laplace modified alternating direction implicit quadrature Petrov–Galerkin (ADI‐QPG) method for solving parabolic initial‐boundary value problems on rectangular domains. We prove optimal order convergence results for a restricted class of the associated elliptic operator and demonstrate accuracy of our scheme with numerical experiments for some parabolic problems with variable coefficients.© 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

A survey of dual-feasible and superadditive functions

Dual-feasible functions are valuable tools that can be used to compute both lower bounds for different combinatorial problems and valid inequalities for integer programs. Several families of functions have been used in the literature. Some of them were defined explicitly, and others not. One of the main objectives of this paper is to survey these functions, and to state results concerning their quality. We clearly identify dominant subsets of functions, i.e. those which may lead to better bounds or stronger cuts. We also describe different frameworks that can be used to create dual-feasible functions. With these frameworks, one can get a dominant function based on other ones. Two new families of dual-feasible functions obtained by applying these methods are proposed in this paper.     

Variable target value subgradient method

Polyak's subgradient algorithm for nondifferentiable optimization problems requires prior knowledge of the optimal value of the objective function to find an optimal solution. In this paper we extend the convergence properties of the Polyak's subgradient algorithm with a fixed target value to a more general case with variable target values. Then a target value updating scheme is provided which finds an optimal solution without prior knowledge of the optimal objective value. The convergence proof of the scheme is provided and computational results of the scheme are reported.Most of this research was performed when the first author was visiting Decision and Information Systems Department, College of Business, Arizona State University.     

On a free interface problem for linear ordinary differential equations and the one-phase Stefan problem

A numerical method for the solution of the one-phase Stefan problem is discussed. By discretizing the time variable the Stefan problem is reduced to a sequence of free boundary value problems for ordinary differential equations which are solved by conversion to initial value problems. The numerical solution is shown to converge to the solution of the Stefan problem with decreasing time increments. Sample calculations indicate that the method is stable provided the proper algorithm is chosen for integrating the initial value problems.     

Efficient Implementation of a Spectral-Tau Method for a Class of Two-Point Boundary-Value and Initial-Boundary-Value Problems

A simple and efficient spectral method for solving the second, third order and fourth order elliptic equations with variable coefficients and nonlinear differential equations is presented. It is different from spectral-collocation method which leads to dense, ill-conditioned matrices. The spectral method in this paper solves for the coefficients of the solution in a Chebyshev series, leads to discrete systems with special structured matrices which can be factorized and solved efficiently. We also extend the method to boundary value problems in two space dimensions and solve 2-D separable equation with variable coefficients. As an application, we solve Cahn-Hilliard equation iteratively via first-order implicit time discretization scheme. Ample numerical results indicate that the proposed method is extremely accurate and efficient.     

Limited Memory Space Dilation and Reduction Algorithms

In this paper, we present variants of Shor and Zhurbenko's r-algorithm, motivated by the memoryless and limited memory updates for differentiable quasi-Newton methods. This well known r-algorithm, which employs a space dilation strategy in the direction of the difference between two successive subgradients, is recognized as being one of the most effective procedures for solving nondifferentiable optimization problems. However, the method needs to store the space dilation matrix and update it at every iteration, resulting in a substantial computational burden for large-sized problems. To circumvent this difficulty, we first propose a memoryless update scheme, which under a suitable choice of parameters, yields a direction of motion that turns out to be a convex combination of two successive anti-subgradients. Moreover, in the space transformation sense, the new update scheme can be viewed as a combination of space dilation and reduction operations. We prove convergence of this new method, and demonstrate how it can be used in conjunction with a variable target value method that allows a practical, convergent implementation of the method. We also examine a memoryless variant that uses a fixed dilation parameter instead of varying degrees of dilation and/or reduction as in the former algorithm, as well as another variant that examines a two-step limited memory update. These variants are tested along with Shor's r-algorithm and also a modified version of a related algorithm due to Polyak that employs a projection onto a pair of Kelley's cutting planes. We use a set of standard test problems from the literature as well as randomly generated dual transportation and assignment problems in our computational experiments. The results exhibit that the proposed space dilation and reduction method and the modification of Polyak's method are competitive, and offer a substantial advantage over the r-algorithm and over the other tested limited memory variants with respect to accuracy as well as effort.     

The numerical solution of an evolution problem of second order in time on a closed smooth boundary

We consider an initial value problem for the second-order differential equation with a Dirichlet-to-Neumann operator coefficient. For the numerical solution we carry out semi-discretization by the Laguerre transformation with respect to the time variable. Then an infinite system of the stationary operator equations is obtained. By potential theory, the operator equations are reduced to boundary integral equations of the second kind with logarithmic or hypersingular kernels. The full discretization is realized by Nyström's method which is based on the trigonometric quadrature rules. Numerical tests confirm the ability of the method to solve these types of nonstationary problems.