Semilinear Mixed Problems on Hilbert Complexes and Their Numerical Approximation

Arnold, Falk, and Winther recently showed (Bull. Am. Math. Soc. 47:281–354, 2010) that linear, mixed variational problems, and their numerical approximation by mixed finite element methods, can be studied using the powerful, abstract language of Hilbert complexes. In another recent article (arXiv:), we extended the Arnold–Falk–Winther framework by analyzing variational crimes (à la Strang) on Hilbert complexes. In particular, this gave a treatment of finite element exterior calculus on manifolds, generalizing techniques from surface finite element methods and recovering earlier a priori estimates for the Laplace–Beltrami operator on 2- and 3-surfaces, due to Dziuk (Lecture Notes in Math., vol. 1357:142–155, 1988) and later Demlow (SIAM J. Numer. Anal. 47:805–827, 2009), as special cases. In the present article, we extend the Hilbert complex framework in a second distinct direction: to the study of semilinear mixed problems. We do this, first, by introducing an operator-theoretic reformulation of the linear mixed problem, so that the semilinear problem can be expressed as an abstract Hammerstein equation. This allows us to obtain, for semilinear problems, a priori solution estimates and error estimates that reduce to the Arnold–Falk–Winther results in the linear case. We also consider the impact of variational crimes, extending the results of our previous article to these semilinear problems. As an immediate application, this new framework allows for mixed finite element methods to be applied to semilinear problems on surfaces.     

On the Parametric Cubic Spline Approach for Solving Second Order Boundary Value Problems

In this article some comments on the paper “parametric cubic spline approach to the solution of a system of second order boundary value problems” in (Khan and Aziz, J. Optim. Theory Appl. 118:45–54, 2003) are given. This paper concerns with a numerical method for solving a second order boundary value problem associated with obstacle, unilateral and contact problems. Corrections are given for the convergence analysis of the numerical method and the computational experiments.     

A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation

We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297–320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances, which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal solution for some test problems.     

The three dimensional inverse scattering problem for acoustic waves

We consider the inverse scattering problem for an acoustically soft obstacle in R³. By assuming a priori that the unknown scattering obstacle is starlike and has its boundary lying in a compact family of Hölder continuously differentiable surfaces, it is shown that an optimal solution can be constructed which depends continuously on the measured far field data. Remarks are made on the numerical approximation of the optimal solution.     

Finite Time Merton Strategy under Drawdown Constraint: A Viscosity Solution Approach

We consider the optimal consumption-investment problem under the drawdown constraint, i.e. the wealth process never falls below a fixed fraction of its running maximum. We assume that the risky asset is driven by the constant coefficients Black and Scholes model and we consider a general class of utility functions. On an infinite time horizon, Elie and Touzi (Preprint, [2006]) provided the value function as well as the optimal consumption and investment strategy in explicit form. In a more realistic setting, we consider here an agent optimizing its consumption-investment strategy on a finite time horizon. The value function interprets as the unique discontinuous viscosity solution of its corresponding Hamilton-Jacobi-Bellman equation. This leads to a numerical approximation of the value function and allows for a comparison with the explicit solution in infinite horizon.     

Verified computation of solutions for obstacle problems with guaranteed L∞ error bound

In this paper, we consider a numerical enclosure method with guaranteed L^∞ error bound for the solutions of obstacle problems. Using the finite-element approximations and the explicit a priori error estimates for obstacle problems, we present an effective verification procedure that automatically generates on a computer a set which includes the exact solution. A particular emphasis is that our method needs no assumption of the existence of the solution of the original obstacle problems, but it follows as the result of computation itself. A numerical example for an obstacle problem is presented.     

A new smoothing Newton-type algorithm for semi-infinite programming

We consider a semismooth reformulation of the KKT system arising from the semi-infinite programming (SIP) problem. Based upon this reformulation, we present a new smoothing Newton-type method for the solution of SIP problem. The main properties of this method are: (a) it is globally convergent at least to a stationary point of the SIP problem, (b) it is locally superlinearly convergent under a certain regularity condition, (c) the feasibility is ensured via the aggregated constraint, and (d) it has to solve just one linear system of equations at each iteration. Preliminary numerical results are reported.     

Feasible Semismooth Newton Method for a Class of Stochastic Linear Complementarity Problems

We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high safety for SLCPs.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

Piecewise polynomial collocation for linear boundary value problems of fractional differential equations

We consider a class of boundary value problems for linear multi-term fractional differential equations which involve Caputo-type fractional derivatives. Using an integral equation reformulation of the boundary value problem, some regularity properties of the exact solution are derived. Based on these properties, the numerical solution of boundary value problems by piecewise polynomial collocation methods is discussed. In particular, we study the attainable order of convergence of proposed algorithms and show how the convergence rate depends on the choice of the grid and collocation points. Theoretical results are verified by two numerical examples.     

Statistical Causality,Extremal Measures and Weak Solutions of Stochastic Differential Equations with Driving Semimartingales

In this paper we consider different concepts of causality in filtered probability spaces. Especially, we consider a generalization of a causality relationship “G is a cause of J within H ” which was first given by Mykland (1986) and which is based on Granger’s definition of causality (Granger, Econometrica 37:424–438, 1969). Then we apply this concept on weak solutions of stochastic differential equations with driving semimartingales. We also show that the given causality concept is closely connected to the concept of extremality of measures and links Granger’s causality with the concept of adapted distribution. Finally, the concept of causality is applied on solution of martingale problem.     

A Dynamical Method for Solving the Obstacle Problem

In this paper, we consider the unilateral obstacle problem, trying to find the numerical solution and coincidence set. We construct an equivalent format of the original problem and propose a method with a second-order in time dissipative system for solving the equivalent format. Several numerical examples are given to illustrate the effectiveness and stability of the proposed algorithm. Convergence speed comparisons with existent numerical algorithm are also provided and our algorithm is fast.     

Implicit solution function of P0 and Z matrix linear complementarity constraints

Using the least element solution of the P₀ and Z matrix linear complementarity problem (LCP), we define an implicit solution function for linear complementarity constraints (LCC). We show that the sequence of solution functions defined by the unique solution of the regularized LCP is monotonically increasing and converges to the implicit solution function as the regularization parameter goes down to zero. Moreover, each component of the implicit solution function is convex. We find that the solution set of the irreducible P₀ and Z matrix LCP can be represented by the least element solution and a Perron?CFrobenius eigenvector. These results are applied to convex reformulation of mathematical programs with P₀ and Z matrix LCC. Preliminary numerical results show the effectiveness and the efficiency of the reformulation.     

Exact computational approaches to a stochastic uncapacitated single allocation p-hub center problem

The stochastic uncapacitated single allocation p-hub center problem is an extension of the deterministic version which aims to minimize the longest origin-destination path in a hub and spoke network. Considering the stochastic nature of travel times on links is important when designing a network to guarantee the quality of service measured by a maximum delivery time for a proportion of all deliveries. We propose an efficient reformulation for a stochastic p-hub center problem and develop exact solution approaches based on variable reduction and a separation algorithm. We report numerical results to show effectiveness of our new reformulations and approaches by finding global solutions of small-medium sized problems. The combination of model reformulation and a separation algorithm is particularly noteworthy in terms of computational speed.     

A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints

We consider distributionally robust two-stage stochastic linear optimization problems with higher-order (say \(p\ge 3\) and even possibly irrational) moment constraints in their ambiguity sets. We suggest to solve the dual form of the problem by a semi-infinite programming approach, which deals with a much simpler reformulation than the conic optimization approach. Some preliminary numerical results are reported.     

Continuous dependence on obstacles for the double obstacle problem on metric spaces

Let X be a complete metric space equipped with a doubling Borel measure supporting a p-Poincaré inequality. We obtain various convergence results for solutions of double obstacle problems on open subsets of X. In particular, we consider a sequence of double obstacle problems with converging obstacles and show that the corresponding solutions converge as well. We use the convergence properties to define and study a generalized solution of the double obstacle problem.     

On multi-grid methods for variational inequalities

Summary We consider here a general class of algorithms for the numerical solution of variational inequalities. A convergence proof is given and in particular a multi-grid method is described. Numerical results are presented for the finite-difference discretization of an obstacle problem for minimal surfaces     

Variational discretization of Lavrentiev-regularized state constrained elliptic optimal control problems

In the present work, we apply a variational discretization proposed by the first author in (Comput. Optim. Appl. 30:45–61, 2005) to Lavrentiev-regularized state constrained elliptic control problems. We extend the results of (Comput. Optim. Appl. 33:187–208, 2006) and prove weak convergence of the adjoint states and multipliers of the regularized problems to their counterparts of the original problem. Further, we prove error estimates for finite element discretizations of the regularized problem and investigate the overall error imposed by the finite element discretization of the regularized problem compared to the continuous solution of the original problem. Finally we present numerical results which confirm our analytical findings.     

A frictionless contact problem for elastic–viscoplastic materials with normal compliance: Numerical analysis and computational experiments

Summary. In this paper we consider a frictionless contact problem between an elastic–viscoplastic body and an obstacle. The process is assumed to be quasistatic and the contact is modeled with normal compliance. We present a variational formulation of the problem and prove the existence and uniqueness of the weak solution, using strongly monotone operators arguments and Banach's fixed point theorem. We also study the numerical approach to the problem using spatially semi-discrete and fully discrete finite elements schemes with implicit and explicit discretization in time. We show the existence of the unique solution for each of the schemes and derive error estimates on the approximate solutions. Finally, we present some numerical results involving examples in one, two and three dimensions. Received May 20, 2000 / Revised version received January 8, 2001 / Published online June 7, 2001