A Damped Gauss-Newton Method for the Second-Order Cone Complementarity Problem

We investigate some properties related to the generalized Newton method for the Fischer-Burmeister (FB) function over second-order cones, which allows us to reformulate the second-order cone complementarity problem (SOCCP) as a semismooth system of equations. Specifically, we characterize the B-subdifferential of the FB function at a general point and study the condition for every element of the B-subdifferential at a solution being nonsingular. In addition, for the induced FB merit function, we establish its coerciveness and provide a weaker condition than Chen and Tseng (Math. Program. 104:293–327, 2005) for each stationary point to be a solution, under suitable Cartesian P-properties of the involved mapping. By this, a damped Gauss-Newton method is proposed, and the global and superlinear convergence results are obtained. Numerical results are reported for the second-order cone programs from the DIMACS library, which verify the good theoretical properties of the method. S. Pan’s work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. J.-S. Chen is member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. J.-S. Chen’s work is partially supported by National Science Council of Taiwan.     

Exponentially and Trigonometrically Fitted Methods for the Solution of the Schrödinger Equation

In the present paper we compare the two methodologies for the development of exponentially and trigonometrically fitted methods. One is based on the exact integration of the functions of the form: {1,x,x ²,…,x ^p ,exp?(±wx),xexp?(±wx),…,x ^m exp?(±w x)} and the second is based on the exact integration of the functions of the form: {1,x,x ²,…,x ^p ,exp?(±wx),exp?(±2wx),…,exp?(±mwx)}. The above functions are used in order to improve the efficiency of the classical methods of any kind (i.e. the method (5) with constant coefficients) for the numerical solution of ordinary differential equations of the form of the Schrödinger equation. We mention here that the above sets of exponential functions are the two most common sets of exponential functions for the development of the special methods for the efficient solution of the Schrödinger equation. It is first time in the literature in which the efficiency of the above sets of functions are studied and compared together for the approximate solution of the Schrödinger equation. We present the error analysis of the above two approaches for the numerical solution of the one-dimensional Schrödinger equation. Finally, numerical results for the resonance problem of the radial Schrödinger equation are presented.     

A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem

In this paper, we investigate a DC (Difference of Convex functions) programming technique for solving large scale Eigenvalue Complementarity Problems (EiCP) with real symmetric matrices. Three equivalent formulations of EiCP are considered. We first reformulate them as DC programs and then use DCA (DC Algorithm) for their solution. Computational results show the robustness, efficiency, and high speed of the proposed algorithms.     

Eigenvalues Estimate for the Neumann Problem of a Bounded Domain

In this note, we investigate upper bounds of the Neumann eigenvalue problem for the Laplacian of a domain Ω in a given complete (not compact a priori) Riemannian manifold (M,g). For this, we use test functions for the Rayleigh quotient subordinated to a family of open sets constructed in a general metric way, interesting for itself. As applications, we prove that if the Ricci curvature of (M,g) is bounded below Ric  ^g ≥−(n−1)a ², a≥0, then there exist constants A _n >0,B _n >0 only depending on the dimension, such that

A Graph-based Equilibrium Problem for the Limiting Distribution of Nonintersecting Brownian Motions at Low Temperature

We consider n nonintersecting Brownian motion paths with p prescribed starting positions at time t=0 and q prescribed ending positions at time t=1. The positions of the paths at any intermediate time are a determinantal point process, which in the case p=1 is equivalent to the eigenvalue distribution of a random matrix from the Gaussian unitary ensemble with external source. For general p and q, we show that if a temperature parameter is sufficiently small, then the distribution of the Brownian paths is characterized in the large n limit by a vector equilibrium problem with an interaction matrix that is based on a bipartite planar graph. Our proof is based on a steepest descent analysis of an associated (p+q)×(p+q) matrix-valued Riemann–Hilbert problem whose solution is built out of multiple orthogonal polynomials. A new feature of the steepest descent analysis is a systematic opening of a large number of global lenses.     

The Global Classical Solution of the Initial Boundary Value Problem for Generalized KdV Equation

ＴｈｅＧｌｏｂａｌＣｌａｓｓｉｃａｌＳｏｌｕｔｉｏｎｏｆｔｈｅＩｎｉｔｉａｌＢｏｕｎｄａｒｙＶａｌｕｅＰｒｏｂｌｅｍｆｏｒＧｅｎｅｒａｌｉｚｅｄＫｄＶＥｑｕａｔｉｏｎ￥ＭｉａｏＣｈｅｎｘｉａ（苗晨霞）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＰｈｙｓｉｃ...     

A Modica–Mortola approximation for the Steiner Problem

In this note we present a way to approximate the Steiner Problem by a family of elliptic energies of Modica–Mortola type, with an additional term relying on a weighted geodesic distance which takes care of the connectedness constraint.     

A Dynamic Programming Algorithm for the κ-Haplotyping Problem

The Minimum Fragments Removal （MFR） problem is one of the haplotyping problems： given a set of fragments, remove the minimum number of fragments so that the resulting fragments can be partitioned into k classes of non-conflicting subsets. In this paper, we formulate the κ-MFR problem as an integer linear programming problem, and develop a dynamic programming approach to solve the κ-MFR problem for both the gapless and gap eases.     

A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem

In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes the probability of the event “this arc is located on the shortest tour.” Those probabilities are then updated as in cross entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However, for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear program).     

A presentation for the singular part of the full transformation semigroup

The (full) transformation semigroup T_n\mathcal{T}_{n} is the semigroup of all functions from the finite set {1,…,n} to itself, under the operation of composition. The symmetric group S_n í T_n{\mathcal{S}_{n}\subseteq \mathcal{T}_{n}} is the group of all permutations on {1,…,n} and is the group of units of T_n\mathcal{T}_{n}. The complement T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n} is a subsemigroup (indeed an ideal) of T_n\mathcal{T}_{n}. In this article we give a presentation, in terms of generators and relations, for T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n}, the so-called singular part of T_n\mathcal{T}_{n}.     

Pointwise Estimates for Laplace Equation. Applications to the Free Boundary of the Obstacle Problem with Dini Coefficients

In this paper we are interested in pointwise regularity of solutions to elliptic equations. In a first result, we prove that if the modulus of mean oscillation of Δu at the origin is Dini (in L ^p average), then the origin is a Lebesgue point of continuity (still in L ^p average) for the second derivatives D ² u. We extend this pointwise regularity result to the obstacle problem for the Laplace equation with Dini right hand side at the origin. Under these assumptions, we prove that the solution to the obstacle problem has a Taylor expansion up to the order 2 (in the L ^p average). Moreover we get a quantitative estimate of the error in this Taylor expansion for regular points of the free boundary. In the case where the right hand side is moreover double Dini at the origin, we also get a quantitative estimate of the error for singular points of the free boundary. Our method of proof is based on some decay estimates obtained by contradiction, using blow-up arguments and Liouville Theorems. In the case of singular points, our method uses moreover a refined monotonicity formula.      

On Classical Solutions to the First Mixed Problem for the Vlasov–Poisson System in an Infinite Cylinder

Doklady Mathematics - The first mixed problem for the Vlasov–Poisson system in an infinite cylinder is considered. This problem describes the kinetics of charged particles in a...     

A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

A comparison of problem decomposition techniques for the FAP

This paper proposes a problem decomposition approach to solve hard Frequency Assignment Problem instances with standard meta-heuristics. The proposed technique aims to divide the initial problem into a number of easier subproblems, solve them and then recompose the partial solutions into one of the original problem. We consider the COST-259 MI-FAP instances and other Cardiff University test problems in order to simulate larger and more realistic networks. For both benchmarks the standard implementations of meta-heuristics do not generally produce a satisfactory performance within reasonable times of execution. However, the decomposed assignment approach can improve their results, both in terms of solution quality and runtime.     

Classical and Impulse Control for the Optimization of Dividend and Proportional Reinsurance Policies with Regime Switching

We consider the optimal proportional reinsurance and dividend strategy. The surplus process is modeled by the classical compound Poisson risk model with regime switching. Considering a class of utility functions, the object of the insurer is to select the reinsurance and dividend strategy that maximizes the expected total discounted utility of the shareholders until ruin. By adapting the techniques and methods of stochastic control, we study the quasi-variational inequality for this classical and impulse control problem and establish a verification theorem. We show that the optimal value function is characterized as the unique viscosity solution of the corresponding quasi-variational inequality.     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

The Entries of Haar-Invariant Matrices from the Classical Compact Groups

Let Γ _n =(γ _ij ) _n×n be a random matrix with the Haar probability measure on the orthogonal group O(n), the unitary group U(n), or the symplectic group Sp(n). Given 1≤m<n, a probability inequality for a distance between (γ _ij ) _n×m and some mn independent F-valued normal random variables is obtained, where F=ℝ, ℂ, or ℍ (the set of real quaternions). The result is universal for the three cases. In particular, the inequality for Sp(n) is new.     

A multiresolution method for fitting scattered data on the sphere

In this work, we propose an efficient multiresolution method for fitting scattered data functions on a sphere S, using a tensor product method of periodic algebraic trigonometric splines of order 3 and quadratic polynomial splines defined on a rectangular map of S. We describe the decomposition and reconstruction algorithms corresponding to the polynomial and periodic algebraic trigonometric wavelets. As application of this method, we give an algorithm which allows to compress scattered data on spherelike surfaces. In order to illustrate our results, some numerical examples are presented.