The cyclic Barzilai--Borwein method for unconstrained optimization

^** Email: dyh{at}lsec.cc.ac.cn^*** Email: hager{at}math.ufl.edu^**** Email: klaus.schittkowski{at}uni-bayreuth.de^***** Email: hzhang{at}math.ufl.edu In the cyclic Barzilai–Borwein (CBB) method, the sameBarzilai–Borwein (BB) stepsize is reused for m consecutiveiterations. It is proved that CBB is locally linearly convergentat a local minimizer with positive definite Hessian. Numericalevidence indicates that when m > n/2 3, where n is the problemdimension, CBB is locally superlinearly convergent. In the specialcase m = 3 and n = 2, it is proved that the convergence rateis no better than linear, in general. An implementation of theCBB method, called adaptive cyclic Barzilai–Borwein (ACBB),combines a non-monotone line search and an adaptive choice forthe cycle length m. In numerical experiments using the CUTErtest problem library, ACBB performs better than the existingBB gradient algorithm, while it is competitive with the well-knownPRP+ conjugate gradient algorithm.     

Arbitrary-norm hyperplane separation by variable neighbourhood search

^** Email: alejandro.karam{at}hec.ca^*** Email: gilles.caporossi{at}gerad.ca^**** Email: pierre.hansen{at}gerad.ca We consider the problem of separating two sets of points ina Euclidean space with a hyperplane that minimizes the sum ofp-norm distances to the plane of points lying on the ‘wrong’side of the plane. A variable neighbourhood search heuristicis used to determine the plane coefficients. For a set of exampleswith L₁-norm, L₂-norm and L-norm, for which the exact solutioncan be computed, we show that our algorithm finds it in mostcases and gets good approximations in the others. The use ofour heuristic solutions for problems in these norms can dramaticallyaccelerate exact algorithms. Our method can be applied on verylarge instances that are intractable by exact algorithms. Sincethe proposed approach works for truly arbitrary norms (otherthan the traditional 1, 2 and ), we can explore for the firsttime the effects of the choice of p on the generalization propertiesof p-norm hyperplane separation.     

Electrical coupling in proton exchange membrane fuel cell stacks: mathematical and computational modelling

^** Corresponding author. Email: wetton{at}math.ubc.ca^*** Email: Peter.Berg{at}uoit.ca^**** Email: caglara{at}uwgb.edu^***** Email: kpromisl{at}math.msu.edu^****** Email: jean.st-pierre{at}ballard.com A mathematical model describing the effects of electrical couplingof proton exchange membrane unit fuel cells through shared bipolarplates is developed. Here, the unit cells are described by simple,steady-state, 1D models appropriate for straight reactant gaschannel designs. A linear asymptotic version of the model isused to give analytic insight into the effect of the coupling,including estimates of the extent of the coupling in terms ofthe number of adjacent cells affected. An efficient numericalmethod is developed to solve the non-linear coupled system.Numerical results showing the effects on stack voltage due toa single cell with anomalous oxidant flow rate are given. Theeffects on stack performance due to end plate effects are alsogiven. It is shown that electrical coupling has a significanteffect on fuel cell performance.     

Variable neighbourhood search for redundancy allocation problems

^** Email: ycliang{at}saturn.yzu.edu.tw^*** Email: s929512{at}mail.yzu.edu.tw^**** Email: s927522{at}mail.yzu.edu.tw A variable neighbourhood search (VNS) algorithm has been developedto solve the redundancy allocation problem (RAP). The VNS methodis perfectly suited to those combinatorial problems with potentialneighbourhood structures, as in the case of the RAP. The moststudied configuration of the RAP is a series system of s-independentk-out-of-n:G subsystems the so-called series–parallelsystem. The RAP is to select the optimal combination and redundancylevels of components to meet system-level constraints. Two typesof objectives are considered in this study—system reliabilitymaximization and system cost minimization. The VNS algorithmis tested on sets of benchmark problems and compared to thebest heuristics in the literature such as tabu search, multipleweighted objective heuristic, ant colony optimization and geneticalgorithm. Computational results show the advantages and benefitsof VNS for solving both types of RAP while considering bothsolution quality and computational efficiency.     

Improving the accuracy of the mini-element approximation to Navier-Stokes equations

^** Email: blanca{at}imati.cnr.it^*** Email: frutos{at}mac.cie.uva.es^**** Corresponding author. Email: julia.novo{at}uam.es A technique to improve the accuracy of the mini-element approximationto incompressible the Navier–Stokes equations is introduced.Once the mini-element approximation has been computed at a fixedtime, the linear part of this approximation is postprocessedby solving a discrete Stokes problem. The bubble functions neededto stabilize the approximation to the Navier–Stokes equationsare not used at the postprocessing step. This postprocessingprocedure allows us to increase by one unit (up to a logarithmicterm) the H¹ norm rate of convergence of the velocity and correspondinglythe L² norm of the pressure. An error analysis of the algorithmis performed.     

Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood search

^** Corresponding author. Email: mahdi{at}dcc.ufmg.br^*** Email: martin{at}dcc.ufmg.br^**** Email: mateus{at}dcc.ufmg.br^***** Email: pardalos{at}ufl.edu Variable neighbourhood search (VNS) is a modern metaheuristicbased on systematic changes of the neighbourhood structure withina search to solve optimization problems. The aim of this paperis to propose and analyse a VNS algorithm to solve schedulingproblems with parallel machines and sequence-dependent setuptimes, which are of great importance on the industrial context.Three versions of a greedy randomized adaptive search procedurealgorithm are used to compare with the proposed VNS algorithmto highlight its advantages in terms of generality, qualityand speed for large instances.     

Supraconvergence of a finite difference scheme for solutions in Hs(0, L)

^** Email: silvia{at}mat.uc.pt^*** Email: ferreira{at}mat.uc.pt^**** Email: grigo{at}math.tu-berlin.de In this paper we study the convergence of a centred finite differencescheme on a non-uniform mesh for a 1D elliptic problem subjectto general boundary conditions. On a non-uniform mesh, the schemeis, in general, only first-order consistent. Nevertheless, weprove for s (1/2, 2] order O(h^s)-convergence of solution andgradient if the exact solution is in the Sobolev space H^1+s(0,L), i.e. the so-called supraconvergence of the method. It isshown that the scheme is equivalent to a fully discrete linearfinite-element method and the obtained convergence order isthen a superconvergence result for the gradient. Numerical examplesillustrate the performance of the method and support the convergenceresult.     

An adaptive boundary element method for the exterior Stokes problem in three dimensions

^** Email: vjervin{at}clemson.edu^*** Email: norbert.heuer{at}brunel.ac.uk We present an adaptive refinement strategy for the h-versionof the boundary element method with weakly singular operatorson surfaces. The model problem deals with the exterior Stokesproblem, and thus considers vector functions. Our error indicatorsare computed by local projections onto 1D subspaces definedby mesh refinement. These indicators measure the error separatelyfor the vector components and allow for component-independentadaption. Assuming a saturation condition, the indicators giverise to an efficient and reliable error estimator. Also we describehow to deal with meshes containing quadrilaterals which arenot shape regular. The theoretical results are underlined bynumerical experiments. To justify the saturation assumption,in the Appendix we prove optimal lower a priori error estimatesfor edge singularities on uniform and graded meshes.     

Reduced-basis output bound methods for parabolic problems

^** Email: rovas{at}uiuc.edu^*** Email: luc_machiels{at}mckinsey.com^**** Corresponding author. Email: maday{at}ann.jussieu.fr In this paper, we extend reduced-basis output bound methodsdeveloped earlier for elliptic problems, to problems describedby ‘parameterized parabolic’ partial differentialequations. The essential new ingredient and the novelty of thispaper consist in the presence of time in the formulation andsolution of the problem. First, without assuming a time discretization,a reduced-basis procedure is presented to ‘efficiently’compute accurate approximations to the solution of the parabolicproblem and ‘relevant’ outputs of interest. In addition,we develop an error estimation procedure to ‘a posteriorivalidate’ the accuracy of our output predictions. Second,using the discontinuous Galerkin method for the temporal discretization,the reduced-basis method and the output bound procedure areanalysed for the semi-discrete case. In both cases the reduced-basisis constructed by taking ‘snapshots’ of the solutionboth in time and in the parameters: in that sense the methodis close to Proper Orthogonal Decomposition (POD).     

Optimization of financial and energy structure of productive capital

^** Email: nahritonenko{at}pvamu.edu^*** Email: yyatsenko{at}hbu.edu Optimal control of special non-linear Volterra integral equationsis used to optimize the structure and lifetime of age-dependentproductive capital at an individual enterprise level. The equationsdescribe a multifactor vintage capital model. The optimizationproblem is to select investment, specific capital cost, specificenergy consumption and capital lifetime that maximize net profiton finite and infinite horizons. The structure of optimal trajectoriesis investigated and relevant relations among technological andfinancial parameters of the productive capital are established.     

A cell-centred finite-volume approximation for anisotropic diffusion operators on unstructured meshes in any space dimension

^** Email: eymard{at}math.univ-mlv.fr^*** Email: gallouet{at}cmi.univ-mrs.fr^**** Corresponding author. Email: herbin{at}cmi.univ-mrs.fr Finite-volume methods for problems involving second-order operatorswith full diffusion matrix can be used thanks to the definitionof a discrete gradient for piecewise constant functions on unstructuredmeshes satisfying an orthogonality condition. This discretegradient is shown to satisfy a strong convergence property forthe interpolation of regular functions, and a weak one for functionsbounded in a discrete H¹-norm. To highlight the importance ofboth properties, the convergence of the finite-volume schemefor a homogeneous Dirichlet problem with full diffusion matrixis proven, and an error estimate is provided. Numerical testsshow the actual accuracy of the method.     

Wave-front solution behaviour for continuous neural networks with lateral inhibition

^** Email: rsittipong{at}yahoo.com^*** Corresponding author. Email: jbell{at}math.umbc.edu^**** Email: scylb{at}mahidol.ac.th In this paper we discuss the shape of travelling wave-frontsolutions to a model for a single continuous layer of nervecells originally introduced by Amari (1977, Dynamics of patternformation in lateral inhibition-type neural fields. Biol. Cybern.,27, 77–87). The neural field is homogeneous and isotropic,and the connection function is one of lateral inhibition type,meaning that nearby connecting cells have an excitatory influence,while more spatially distant cells impose an inhibitory influence.We give results on the shape of the wave-front solutions, whichare non-monotone and exhibit different shapes depending on thesize of a threshold parameter. For a layer of excitatory cellsindirectly inhibited by a second layer of cells, we derive resultson the qualitative behaviour of wave-fronts for changes in parametersrepresenting the inhibitory firing threshold and the time-scaleof the inhibition process. This study shows how intrinsic celland network parameter can interact to shape global responseproperties.     

A Lobatto interpolation grid over the triangle

^** Email: m.blyth{at}uea.ac.uk^*** Email: cpozrikidis{at}ucsd.edu A sequence of increasingly refined interpolation grids overthe triangle is proposed, with the goal of achieving uniformconvergence and ensuring high interpolation accuracy. The numberof interpolation nodes, N, corresponds to a complete mth-orderpolynomial expansion with respect to the triangle barycentriccoordinates, which arises by the horizontal truncation of thePascal triangle. The proposed grid is generated by deployingLobatto interpolation nodes along the three edges of the triangle,and then computing interior nodes by averaged intersectionsto achieve three-fold rotational symmetry. Numerical computationsshow that the Lebesgue constant and interpolation accuracy ofthe proposed grid compares favorably with those of the best-knowngrids consisting of the Fekete points. Integration weights correspondingto the set of Lobatto triangle base points are tabulated.     

An a posteriori error indicator for discontinuous Galerkin discretizations of H(curl)-elliptic partial differential equations

^** Email: paul.houston{at}nottingham.ac.uk^*** Corresponding author. Email: ilaria.perugia{at}unipv.it^**** Email: schoetzau{at}math.ubc.ca We introduce a residual-based a posteriori error indicator fordiscontinuous Galerkin discretizations of H(curl; )-ellipticboundary value problems that arise in eddy current models. Weshow that the indicator is both reliable and efficient withrespect to the approximation error measured in terms of a naturalenergy norm. We validate the performance of the indicator withinan adaptive mesh refinement procedure and show its asymptoticexactness for a range of test problems.     

The Z-transform and linear multistep stability

^** Email: mapjjc{at}maths.bath.ac.uk^*** Corresponding author. Email: ath{at}maths.bath.ac.uk^**** Email: hl{at}maths.bath.ac.uk This paper makes systematic use of control-theoretic methodssuch as the -transform, small-gain theorems and frequency-domainstability criteria in the analysis of the stability behaviourof linear multistep methods. Some of the results in Nevanlinna'swork are recovered and a number of new boundedness and asymptoticproperties of solutions of numerical schemes are obtained. Inparticular, we give a careful and detailed analysis of the nonlinearstability properties of strictly zero-stable methods.     

A note on the design of hp-version interior penalty discontinuous Galerkin finite element methods for degenerate problems

^** Email: emmanuil.georgoulis{at}mcs.le.ac.uk^*** Email: al{at}maths.strath.ac.uk We consider a variant of the hp-version interior penalty discontinuousGalerkin finite element method (IP-DGFEM) for second-order problemsof degenerate type. We do not assume uniform ellipticity ofthe diffusion tensor. Moreover, diffusion tensors of arbitraryform are covered in the theory presented. A new, refined recipefor the choice of the discontinuity-penalization parameter (thatis present in the formulation of the IP-DGFEM) is given. Makinguse of the recently introduced augmented Sobolev space framework,we prove an hp-optimal error bound in the energy norm and anh-optimal and slightly p-suboptimal (by only half an order ofp) bound in the L² norm (the latter, for the symmetric versionof the IP-DGFEM), provided that the solution belongs to an augmentedSobolev space.     

The Helmholtz equation in a locally perturbed half-plane with passive boundary

^** Email: mduran{at}ing.puc.cl^*** Email: ignacio.muga{at}ucv.cl^**** Email: nedelec{at}cmapx.polytechnique.fr In this article, we study the existence and uniqueness of outgoingsolutions for the Helmholtz equation in locally perturbed half-planeswith passive boundary. We establish an explicit outgoing radiationcondition which is somewhat different from the usual Sommerfeld'sone due to the appearance of surface waves. We work with thehelp of Fourier analysis and a half-plane Green's function framework.This is an extended and detailed version of the previous articleDurán et al. (2005, The Helmholtz equation with impedancein a half-plane. C. R. Acad. Sci. Paris, Ser. I, 340, 483–488).     

Error estimates for stochastic differential games: the adverse stopping case

^** Email: frederic.bonnans{at}inria.fr^*** Email: stefania.maroso{at}inria.fr^**** Email: zidani{at}ensta.fr We obtain error bounds for monotone approximation schemes ofa particular Isaacs equation. This is an extension of the theoryfor estimating errors for the Hamilton–Jacobi–Bellmanequation. To obtain the upper error bound, we consider the ‘Krylovregularization’ of the Isaacs equation to build an approximatesub-solution of the scheme. To get the lower error bound, weextend the method of Barles & Jakobsen (2005, SIAM J. Numer.Anal.) which consists in introducing a switching system whosesolutions are local super-solutions of the Isaacs equation.     

On computing eigenvalues of second-order linear pencils

^** Email: mhannaby{at}yahoo.com^*** Email: zahraa26{at}yahoo.com In this paper, we use sinc techniques to compute the eigenvaluesof a second-order operator pencil of the form Q – P approximately.Here Q and P are self-adjoint differential operators of thesecond and first order, respectively. Also the eigenparameterappears in the boundary conditions linearly.     

Null Riemannian cubics in tension in SO(3)

^** Email: lyle{at}maths.uwa.edu.au^*** Email: popiet01{at}maths.uwa.edu.au Riemannian cubics in tension in the rotation group SO(3) arevariational curves with applications to interpolation problemsin computer graphics and rigid-body trajectory planning. Theyare related by a linking equation to Lie quadratics in tension(LQT) in the Lie algebra so(3). This paper provides a qualitativeanalysis of the null case of LQT in so(3).