Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Hyperbolic knots spanning accidental Seifert surfaces of arbitrarily high genus

A method for constructing hyperbolic knots each of which bounds accidental incompressible Seifert surfaces of arbitrarily high genus is given. Mathematics Subject Classification (2000):57N10, 57M25.The author was supported in part by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists.     

Branching Brownian Motions on Riemannian Manifolds: Expectation of the Number of Branches Hitting Closed Sets

For a branching Brownian motion on Riemannian manifold, we give an analytic criterion for the expectation of the number of branches hitting a closed set being finite. The author was supported in part by Grant-in-Aid for Scientific Research (No.18340033 (B)), Japan Society for the Promotion of Science.     

On the first homology of automorphism groups of manifolds with geometric structures

Hermann and Thurston proved that the group of diffeomorphisms with compact support of a smooth manifold M which are isotopic to the identity is a perfect group. We consider the case where M has a geometric structure. In this paper we shall survey on the recent results of the first homology of the diffeomorphism groups which preserve a smooth G-action or a foliated structure on M. We also work in Lipschitz category. This research was partially supported by Grant-in-Aid for Scientific Research (No. 16540058), Japan Society for the Promotion of Science. This research was partially supported by Grant-in-Aid for Scientific Research (No. 14540093), Japan Society for the Promotion of Science.     

Identifying an optimal basis in linear programming

We propose a sufficient condition that allows an optimal basis to be identified from a central path point in a linear programming problem. This condition can be applied when there is a gap in the sorted list of slack values. Unlike previously known conditions, this condition is valid for real-number data and does not involve the number of bits in the data.This work is supported in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF Grant DMS-8920550. Also supported in part by an NSF Presidential Young Investigator Award with matching funds received from AT&T and the Xerox Corporation. Part of this work was carried out while the author was visiting the Sandia National Laboratories, supported by the U.S. Department of Energy under Contract DE-AC04-76DP00789.The author is supported in part by NSF Grant DDM-9207347. Part of this work was carried out while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and the IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Some existence results for solutions to SU(3) Toda system

We study SU(3) Toda system in non-abelian relativistic self-dual gauge theory. In the range of parameters where the corresponding Trudinger-Moser inequality fails, we show the existence of the solution by a different variational formulation from Lucia-Nolasco's [15]. This work was supported by a grant of the Japan-Korea Scientific Cooperation Program - Joint Research “Mathematical analysis and mathematical science for self-interacting particles.” The second author was partially supported by Grant-in-Aid for Scientific Research (No. 16740103), Japan Society for the Promotion of Science. Mathematics Subject Classification (2000) 35B40 - 35J50 - 35J60 - 49Q99 - 58E15 - 58J05 - 70S15     

A real algorithm for the Hermitian eigenvalue decomposition

Modifying complex plane rotations, we derive a new Jacobi-type algorithm for the Hermitian eigendecomposition, which uses only real arithmetic. When the fast-scaled rotations are incorporated, the new algorithm brings a substantial reduction in computational costs. The new method has the same convergence properties and parallelism as the symmetric Jacobi algorithm. Computational test results show that it produces accurate eigenvalues and eigenvectors and achieves great reduction in computational time.The work of this author was supported in part by the National Science Foundation grant CCR-8813493 and by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.The work of this author was supported in part by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.     

The Weierstrass semigroup of a pair and moduli inM 3

We classify all the Weierstrass semigroups of a pair of points on a curve of genus 3, by using its canonical model in the plane. Moreover, we count the dimension of the moduli of curves which have a pair of points with a specified Weierstrass semigroup.This work has been supported by the Japan Society for the Promotion of Science and the Korea Science and Engineering Foundation (Project No. 976-0100-001-2). Also the first author is partially supported by Korea Research Foundation Grant (KRF-99-005-D00003).     

A lower bound on the number of iterations of long-step primal-dual linear programming algorithms

Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn ^1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550.This author is supported in part by NSF Grant DDM-9207347. Part of thiw work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Stability of anisotropic capillary surfaces between two parallel planes

We study the stability of capillary surfaces without gravity for anisotropic free surface energies. For a large class of rotationally symmetric energy functionals, it is shown that the only stable equilibria supported on parallel planes are either cylinders or a part of the Wulff shape. The first author is partially supported by Grant-in-Aid for Scientific Research (C) No. 16540195 of the Japan Society for the Promotion of Science.     

Decompositions of Besov–Morrey spaces and Triebel–Lizorkin–Morrey spaces

The aim of this paper is to define the Besov–Morrey spaces and the Triebel– Lizorkin–Morrey spaces and to present a decomposition of functions belonging to these spaces. Our results contain an answer to the conjecture proposed by Mazzucato. The first author is supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. The second author is supported by Fūjyukai foundation and the 21st century COE program at Graduate School of Mathematical Sciences, the University of Tokyo.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

Successive Linearization Methods for Nonlinear Semidefinite Programs

We present a successive linearization method with a trust region-type globalization for the solution of nonlinear semidefinite programs. At each iteration, the method solves a quadratic semidefinite program, which can be converted to a linear semidefinite program with a second order cone constraint. A subproblem of this kind can be solved quite efficiently by using some recent software for semidefinite and second-order cone programs. The method is shown to be globally convergent under certain assumptions. Numerical results on some nonlinear semidefinite programs including optimization problems with bilinear matrix inequalities are reported to illustrate the behaviour of the proposed method.The research of the fourth author was supported in part by a Grant-in-Aid for Scientific Research from Japan Society for the Promotion of Science. The research of the second author was supported by the DFG (Deutsche Forschungsgemeinschaft).     

Superlinear convergence of the affine scaling algorithm

In this paper we show that a variant of the long-step affine scaling algorithm (with variable stepsizes) is two-step superlinearly convergent when applied to general linear programming (LP) problems. Superlinear convergence of the sequence of dual estimates is also established. For homogeneous LP problems having the origin as the unique optimal solution, we also show that 2/3 is a sharp upper bound on the (fixed) stepsize that provably guarantees that the sequence of primal iterates converge to the optimal solution along a unique direction of approach. Since the point to which the sequence of dual estimates converge depend on the direction of approach of the sequence of primal iterates, this result gives a plausible (but not accurate) theoretical explanation for why 2/3 is a sharp upper bound on the (fixed) stepsize that guarantees the convergence of the dual estimates. The work of this author was based on research supported by the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan, 1992. The work of this author was based on research supported by the National Science Foundation (NSF) under grant DDM-9109404 and the Office of Naval Research (ONR) under grant N00014-93-1-0234. This work was done while the second author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

A note on p-supersolvable groups

The notion of Hankel operators associated with analytic crossed products were introduced and researched in [2]. In this paper, we study the adjoint of Hankel operators and give necessary and sufficient condition that the adjoint of a Hankel operator is again a Hankel operator. This work was supported in part by a Grant-in-Aid for Scientific Research, Japan Society for the Promotion of Science.     

On the locally univalent Bloch constant

We give a new lower bound of the locally univalent Bloch constant. Research supported in part by National Natural Science Foundation of China, #10231010, #10171047, and Grant-in-Aid for Scientific Research, Japan Society for the Promotion of Science (B), #1144048.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Some Recent Progress and Applications in Graph Minor Theory

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed. Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number 16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists Supported in part by the Research Grant P1–0297 and by the CRC program On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia     

Anisotropic capillary surfaces with wetting energy

We study the stability of capillary surfaces for anisotropic energies having boundaries supported in horizontal planes. A wetting energy term for the surface to plane interface is included. The first author is partially supported by Grant-in-Aid for Scientific Research (C) No. 16540195 of the Japan Society for the Promotion of Science.