Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

In Pang and Fukushima (Comput Manage Sci 2:21–56, 2005), a sequential penalty approach was presented for a quasi-variational inequality (QVI) with particular application to the generalized Nash game. To test the computational performance of the penalty method, numerical results were reported with an example from a multi-leader-follower game in an electric power market. However, due to an inverted sign in the penalty term in the example and some missing terms in the derivatives of the firms’ Lagrangian functions, the reported numerical results in Pang and Fukushima (Comput Manage Sci 2:21–56, 2005) are incorrect. Since the numerical examples of this kind are scarce in the literature and this particular example may be useful in the future research, we report the corrected results. The online version of the original article can be found under doi:.     

Simultaneously inpainting in image and transformed domains

In this paper, we focus on the restoration of images that have incomplete data in either the image domain or the transformed domain or in both. The transform used can be any orthonormal or tight frame transforms such as orthonormal wavelets, tight framelets, the discrete Fourier transform, the Gabor transform, the discrete cosine transform, and the discrete local cosine transform. We propose an iterative algorithm that can restore the incomplete data in both domains simultaneously. We prove the convergence of the algorithm and derive the optimal properties of its limit. The algorithm generalizes, unifies, and simplifies the inpainting algorithm in image domains given in Cai et al. (Appl Comput Harmon Anal 24:131–149, 2008) and the inpainting algorithms in the transformed domains given in Cai et al. (SIAM J Sci Comput 30(3):1205–1227, 2008), Chan et al. (SIAM J Sci Comput 24:1408–1432, 2003; Appl Comput Harmon Anal 17:91–115, 2004). Finally, applications of the new algorithm to super-resolution image reconstruction with different zooms are presented. R. H. Chan’s research was supported in part by HKRGC Grant 400505 and CUHK DAG 2060257. L. Shen’s research was supported by the US National Science Foundation under grant DMS-0712827. Z. Shen’s research was supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

A multiwave approximate Riemann solver for ideal MHD based on relaxation II: numerical implementation with 3 and 5 waves

In the first part of this work Bouchut et al. (J Comput Phys 108:7–41, 2007) we introduced an approximate Riemann solver for one-dimensional ideal MHD derived from a relaxation system. We gave sufficient conditions for the solver to satisfy discrete entropy inequalities, and to preserve positivity of density and internal energy. In this paper we consider the practical implementation, and derive explicit wave speed estimates satisfying the stability conditions of Bouchut et al. (J Comput Phys 108:7–41, 2007). We present a 3-wave solver that well resolves fast waves and material contacts, and a 5-wave solver that accurately resolves the cases when two eigenvalues coincide. A full 7-wave solver, which is highly accurate on all types of waves, will be described in a follow-up paper. We test the solvers on one-dimensional shock tube data and smooth shear waves.     

Remarks on solutions to a nonconvex quadratic programming test problem

A recent paper of Tuy and Hoai-Phuong published in JOGO (2007) 37:557–569 presents an algorithm for nonconvex quadratic programming with quadratic constraints. Performance of this algorithm is illustrated by solving, among others, a test problem from a paper of Audet, Hansen, Jaumard and Savard published in Mathematical Programming, Ser. A (2000) 87:131–152. This test problem is a reformulation of a problem from a paper of Dembo published in Mathematical Programming (1976) 10:192–213. Tuy and Hoai-Phuong observe that the optimal solution reported by Audet et al. is very far from the optimal one for this reformulation. The discrepancy between the reported optimal solutions is not due to selection of an almost feasible solution far from the optimal one nor to cumulation of termwise approximation errors. It is, in fact, simply due to a typographical error.     

Global optimality conditions for cubic minimization problem with box or binary constraints

In this article, we provide optimality conditions for global solutions to cubic minimization problems with box or binary constraints. Our main tool is an extension of the global subdifferential approach, developed by Jeyakumar et al. (J Glob Optim 36:471–481, 2007; Math Program A 110:521–541, 2007). We also derive optimality conditions that characterize global solutions completely in the case where the cubic objective function contains no cross terms. Examples are given to demonstrate that the optimality conditions can effectively be used for identifying global minimizers of certain cubic minimization problems with box or binary constraints.     

Exact Simulation of Jump-Diffusion Processes with Monte Carlo Applications

We introduce a novel algorithm (JEA) to simulate exactly from a class of one-dimensional jump-diffusion processes with state-dependent intensity. The simulation of the continuous component builds on the recent Exact Algorithm (Beskos et al., Bernoulli 12(6):1077–1098, 2006a). The simulation of the jump component instead employs a thinning algorithm with stochastic acceptance probabilities in the spirit of Glasserman and Merener (Proc R Soc Lond Ser A Math Phys Eng Sci 460(2041):111–127, 2004). In turn JEA allows unbiased Monte Carlo simulation of a wide class of functionals of the process’ trajectory, including discrete averages, max/min, crossing events, hitting times. Our numerical experiments show that the method outperforms Monte Carlo methods based on the Euler discretization.     

Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (2005).     

Parametric approximation of isotropic and anisotropic elastic flow for closed and open curves

Deckelnick and Dziuk (Math. Comput. 78(266):645–671, 2009) proved a stability bound for a continuous-in-time semidiscrete parametric finite element approximation of the elastic flow of closed curves in \mathbbR^d, d 3 2{\mathbb{R}^d, d\geq2} . We extend these ideas in considering an alternative finite element approximation of the same flow that retains some of the features of the formulations in Barrett et al. (J Comput Phys 222(1): 441–462, 2007; SIAM J Sci Comput 31(1):225–253, 2008; IMA J Numer Anal 30(1):4–60, 2010), in particular an equidistribution mesh property. For this new approximation, we obtain also a stability bound for a continuous-in-time semidiscrete scheme. Apart from the isotropic situation, we also consider the case of an anisotropic elastic energy. In addition to the evolution of closed curves, we also consider the isotropic and anisotropic elastic flow of a single open curve in the plane and in higher codimension that satisfies various boundary conditions.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).     

Iterative algorithms for variational inequality and equilibrium problems with applications

In this paper, we introduce an iterative method for finding a common element of the set of solutions of equilibrium problems, of the set of variational inequalities and of the set of common fixed points of an infinite family of nonexpansive mappings in the framework of real Hilbert spaces. Strong convergence of the proposed iterative algorithm is obtained. As an application, we utilize the main results which improve the corresponding results announced in Chang et al. (Nonlinear Anal, 70:3307–3319, 2009), Colao et al. (J Math Anal Appl, 344:340–352, 2008), Plubtieng and Punpaeng (Appl Math Comput, 197:548–558, 2008) to study the optimization problem.     

Optimal Meshes for Finite Elements of Arbitrary Order

Given a function f defined on a bounded domain Ω⊂ℝ² and a number N>0, we study the properties of the triangulation T_N\mathcal{T}_{N} that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the norm X=L ^p for 1≤p≤∞, and we consider Lagrange finite elements of arbitrary polynomial degree m−1. We establish sharp asymptotic error estimates as N→+∞ when the optimal anisotropic triangulation is used, recovering the results on piecewise linear interpolation (Babenko et al. in East J. Approx. 12(1), 71–101, 2006; Babenko, submitted; Chen et al. in Math. Comput. 76, 179–204, 2007) and improving the results on higher degree interpolation (Cao in SIAM J. Numer. Anal. 45(6), 2368–2391, 2007, SIAM J. Sci. Comput. 29, 756–781, 2007, Math. Comput. 77, 265–286, 2008). These estimates involve invariant polynomials applied to the m-th order derivatives of f. In addition, our analysis also provides practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. We partially extend our results to higher dimensions for finite elements on simplicial partitions of a domain Ω⊂ℝ ^d .     

Lorentz Gas with Thermostatted Walls

In a planar periodic Lorentz gas, a point particle (electron) moves freely and collides with fixed round obstacles (ions). If a constant force (induced by an electric field) acts on the particle, the latter will accelerate, and its speed will approach infinity (Chernov and Dolgopyat in J Am Math Soc 22:821–858, 2009; Phys Rev Lett 99, paper 030601, 2007). To keep the kinetic energy bounded one can apply a Gaussian thermostat, which forces the particle’s speed to be constant. Then an electric current sets in and one can prove Ohm’s law and the Einstein relation (Chernov and Dolgopyat in Russian Math Surv 64:73–124, 2009; Chernov et al. Comm Math Phys 154:569–601, 1993; Phys Rev Lett 70:2209–2212, 1993). However, the Gaussian thermostat has been criticized as unrealistic, because it acts all the time, even during the free flights between collisions. We propose a new model, where during the free flights the electron accelerates, but at the collisions with ions its total energy is reset to a fixed level; thus our thermostat is restricted to the surface of the scatterers (the ‘walls’). We rederive all physically interesting facts proven for the Gaussian thermostat in Chernov, Dolgopyat (Russian Math Surv 64:73–124, 2009) and Chernov et al. (Comm Math Phys 154:569–601, 1993; Phys Rev Lett 70:2209–2212, 1993), including Ohm’s law and the Einstein relation. In addition, we investigate the superconductivity phenomenon in the infinite horizon case.     

A note on the prior parameter choice in finite mixture models of distributions from exponential families

This work presents a new scheme to obtain the prior distribution parameters in the framework of Rufo et al. (Comput Stat 21:621–637, 2006). Firstly, an analytical expression of the proposed Kullback–Leibler divergence is derived for each distribution in the considered family. Therefore, no previous simulation technique is needed to estimate integrals and thus, the error related to this procedure is avoided. Secondly, a global optimization algorithm based on interval arithmetic is applied to obtain the prior parameters from the derived expression. The main advantage by using this approach is that all solutions are found and rightly bounded. Finally, an application comparing this strategy with the previous one illustrates the proposal.     

A Characterization of Cubic Graphs with Paired-Domination Number Three-Fifths Their Order

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166–170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order.     

Comments on purification in continuum games

It is pointed out that Corollary 1 in a recent paper by Khan et al. (Int J Game Theory 34:91–104, 2006), presented there as an extension of the Dvoretzky–Wald–Wolfowitz theorem, is a special case of Lyapunov’s theorem for Young measures (Balder in Rend Instit Mat Univ Trieste 31 Suppl. 1:1–69) It is also pointed out that Theorems 1–4 in Khan et al. (Int J Game Theory 34:91–104, 2006) follow from a single strong purification per se result that is already contained, as an implementation of that Lyapunov theorem for Young measures, in the proof of Theorem 2.2.1 in Balder (J Econ Theory 102:437–470, 2002).     

Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation,convergence and numerical results

An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser et al. (Optim Methods Softw 22(3):413–431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective function is determined, and this ensures a significant improvement in the objective so long as the Hessian of the objective is locally Lipschitz continuous. The new method uses an adaptive estimation of the local Lipschitz constant and approximations to the global model-minimizer which remain computationally-viable even for large-scale problems. We show that the excellent global and local convergence properties obtained by Nesterov and Polyak are retained, and sometimes extended to a wider class of problems, by our ARC approach. Preliminary numerical experiments with small-scale test problems from the CUTEr set show encouraging performance of the ARC algorithm when compared to a basic trust-region implementation.     

Crisp and fuzzy <Emphasis Type="Italic">k</Emphasis>-means clustering algorithms for multivariate functional data

Functional data analysis, as proposed by Ramsay (Psychometrika 47:379–396, 1982), has recently attracted many researchers. The most popular approach taken in recent studies of functional data has been the extension of statistical methods for the analysis of usual data to that of functional data (e.g., Ramsay and Silverman in Functional data Analysis Springer, Berlin Heidelberg New York, 1997, Applied functional data analysis: methods and case studies. Springer, Berlin Heidelberg New York, 2002; Mizuta in Proceedings of the tenth Japan and Korea Joint Conference of Statistics, pp 77–82, 2000; Shimokawa et al. in Japan J Appl Stat 29:27–39, 2000). In addition, several methods for clustering functional data have been proposed (Abraham et al. in Scand J Stat 30:581–595, 2003; Gareth and Catherine in J Am Stat Assoc 98:397–408, 2003; Tarpey and kinateder in J Classif 20:93–114, 2003; Rossi et al. in Proceedings of European Symposium on Artificial Neural Networks pp 305–312, 2004). Furthermore, Tokushige et al. (J Jpn Soc Comput Stat 15:319–326, 2002) defined several dissimilarities between functions for the case of functional data. In this paper, we extend existing crisp and fuzzy k-means clustering algorithms to the analysis of multivariate functional data. In particular, we consider the dissimilarity between functions as a function. Furthermore, cluster centers and memberships, which are defined as functions, are determined at the minimum of a certain target function by using a calculus-of-variations approach.     

Second-order Optimality Conditions for Optimal Control of the Primitive Equations of the Ocean with Periodic Inputs

We investigate in this article the Pontryagin’s maximum principle for control problem associated with the primitive equations (PEs) of the ocean with periodic inputs. We also derive a second-order sufficient condition for optimality. This work is closely related to Wang (SIAM J. Control Optim. 41(2):583–606, 2002) and He (Acta Math. Sci. Ser. B Engl. Ed. 26(4):729–734, 2006), in which the authors proved similar results for the three-dimensional Navier-Stokes (NS) systems.     

Duality and optimality conditions for generalized equilibrium problems involving DC functions

We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg (Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371, 2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008), Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences of the main results, we obtain some new optimality conditions for DC and convex problems.     

Local and parallel algorithms for fourth order problems discretized by the Morley–Wang–Xu element method

This paper systematically studies numerical solution of fourth order problems in any dimensions by use of the Morley–Wang–Xu (MWX) element discretization combined with two-grid methods (Xu and Zhou (Math Comp 69:881–909, 1999)). Since the coarse and fine finite element spaces are nonnested, two intergrid transfer operators are first constructed in any dimensions technically, based on which two classes of local and parallel algorithms are then devised for solving such problems. Following some ideas in (Xu and Zhou (Math Comp 69:881–909, 1999)), the intrinsic derivation of error analysis for nonconforming finite element methods of fourth order problems (Huang et al. (Appl Numer Math 37:519–533, 2001); Huang et al. (Sci China Ser A 49:109–120, 2006)), and the error estimates for the intergrid transfer operators, we prove that the discrete energy errors of the two classes of methods are of the sizes O(h + H ²) and O(h + H ²(H/h)^(d−1)/2), respectively. Here, H and h denote respectively the mesh sizes of the coarse and fine finite element triangulations, and d indicates the space dimension of the solution region. Numerical results are performed to support the theory obtained and to compare the numerical performance of several local and parallel algorithms using different intergrid transfer operators.