A Smoothing Newton-Type Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming

In this paper we propose a smoothing Newton-type algorithm for the problem of minimizing a convex quadratic function subject to finitely many convex quadratic inequality constraints. The algorithm is shown to converge globally and possess stronger local superlinear convergence. Preliminary numerical results are also reported. Mathematics Subject Classification (1991): 90C33, 65K10 This author’s work was also partially supported by the Scientific Research Foundation of Tianjin University for the Returned Overseas Chinese Scholars and the Scientific Research Foundation of Liu Hui Center for Applied Mathematics, Nankai University-Tianjin University.     

Order and disorder in algebraic combinatorics

Text of a plenary address given to the Canadian Mathematical Society at their annual meeting at the University of Waterloo in December 1990. The author’s work is partially supported by grants from the National Science Foundation.     

A convergence theorem of Rosen’s gradient projection method

Since Rosen’s gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence theorem is given in this paper. Part of this author’s work was done while he studied at the Department of Mathematics, University of California at Santa Barbara, and was supported by the National Science Foundation under Grant No. MCS83-14977. Part of this author’s work was done while he visited the Computer Science Department, University of Minnesota, Minneapolis, and was supported by the National Science Foundation under Grant No. MCS81-01214.     

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.     

Parallelizable Preprocessing Method for Multistage Stochastic Programming Problems

Stochastic programming has extensive applications in practical problems such as production planning and portfolio selection. Typically, the model has very large size and some techniques are often used to exploit the special structure of the programs. It has been noticed that the coefficient matrix may not be of full rank in the well-known scenario formulation of stochastic programming; thus, the preprocessing is often necessary in developing rapid decomposition methods. In this paper, we propose a parallelizable preprocessing method, which exploits effectively the structure of the formulation. Although the underlying idea is simple, the method turns out to be very useful in practice, since it may help us to select the nonanticipativity constraints efficiently. Some numerical results are reported confirming the usefulness of the method.This work was partially supported by the Informatics Research Center for Development of Knowledge Society Infrastructure, Graduate School of Informatics, Kyoto University, Kyoto, Japan. The work of the first author was also supported in part by the National Science Foundation of China, Grant 10571039. The work of the second author was also supported in part by the Scientific Research Grant-in-Aid from the Japan Society for the Promotion of Science. The authors are grateful to the referees for careful reading of the paper and helpful comments.This author’s work was done while he was visiting Kyoto University.     

On critical orientations in the kedem-sharir motion planning algorithm

We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome it without increasing the asymptotic complexity of the algorithm The first author was supported by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The second author was partly supported by the Fund for Basic Research administered by the Israeli Academy of Sciences, by National Science Foundation Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. The third author was partly supported by the Interdisciplinary Program at Tel-Aviv University. The third author’s current address is: Department of Computer Science, MIT, Boston, MA, USA.     

Amalgamation,interpolation and epimorphisms in algebraic logic

In his landmark paper on amalgamation published in Algebra Universalis in 1971, Don Pigozzi posed some open questions in connection with amalgamation of subclasses of cylindric algebras. Some of these questions were originally raised by Comer, Daigneault, Johnson, McKenzie and others. In this paper we give answers to all these as well as a number of other related questions. Most of the solutions were found by the authors of this paper. However, a few were contributed by others who will of course be given due credit at the appropriate points. This paper is dedicated to Don Pigozzi on his retirement. Presented by R. W. Quackenbush. The first author’s research was supported by the Hungarian National Foundation for Scientific Research grants no T30314 and T23234. The second author’s research was supported by the Hungarian National Foundation for Scientific Reserach OKTA grant no T30314. All the new results in this article were announced by Judit Madarász in the Workshop on Abstract Algebraic Logic, held in Centre de Recerca Matematica Bellaterra, Spain July 1–5, 1997. Received December 15, 2002; accepted in final form January 3, 2006.     

Quantum groups of dimensionpq 2

In this paper we construct two families of non-trivial self-dual semisimple Hopf algebras of dimensionpq ² and investigate closely their (quasi) triangular structures. The paper contains also general results on finite-dimensional triangular Hopf algebras, unimodularity, semisimplicity and ribbon structures of finite-dimensional semisimple Hopf algebras. Dedicated to the memory of Professor S. A. Amitsur This work was partially supported by the Basic Research Foundation administrated by the Israel Academy of Sciences and Humanities. The paper consists of part of the author’s doctoral dissertation written at Ben Gurion University under the supervision of Prof. M. Cohen and Prof. D. E. Radford whom the author wishes to thank for their valuable guidance.     

Proper holomorphic self-maps of smooth bounded Reinhardt domains in ?2

It is proved that every proper holomorphic self-map of a smooth bounded Reinhardt domain in ℂ² is an automorphism. The first author’s work was supported in part by the National Natural Science Foundation of China (Grant No. 10571135) and the Doctoral Program Foundation of the Ministry of Education of China (Grant No. 20050240711)     

Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

Parabolic Harnack inequality and heat kernel estimates for random walks with long range jumps

We investigate the relationships between the parabolic Harnack inequality, heat kernel estimates, some geometric conditions, and some analytic conditions for random walks with long range jumps. Unlike the case of diffusion processes, the parabolic Harnack inequality does not, in general, imply the corresponding heat kernel estimates. M. T. Barlow’s research was partially supported by NSERC (Canada), the twenty-first century COE Program in Kyoto University (Japan), and by EPSRC (UK). R. F. Bass’s research was partially supported by NSF Grant DMS-0601783. T. Kumagai’s research was partially supported by the Grant-in-Aid for Scientific Research (B) 18340027 (Japan).     

On-line Tracking of a Smooth Regression Function

We construct an on-line estimator with equidistant design for tracking a smooth function from Stone–Ibragimov–Khasminskii’s class. This estimator has the optimal convergence rate of risk to zero in sample size. The procedure for setting coefficients of the estimator is controlled by a single parameter and has a simple numerical solution. The off-line version of this estimator allows to eliminate a boundary layer. Simulation results are given. This work is partially supported by a fellowship from the Yitzhak and Chaya Weinstein Research Institute for Signal Processing at Tel Aviv University.     

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

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Proximal-Like Algorithm Using the Quasi D-Function for Convex Second-Order Cone Programming

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ℝ₊₊. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538–543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem. Research of Shaohua Pan was partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. Jein-Shan Chen is a member of the Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work was partially supported by National Science Council of Taiwan.     

Solving elliptical equations with high-contrast coefficients in an unbounded region

An approximation model is proposed for an elliptical equation with complex rapidly varying coefficients. An efficient numerical method is developed and implemented. A problem of geoelectricity requiring solution of an equation in this setting is investigated. This research was partially supported by the Russian Foundation for Basic Research (grant No. 96-05-64340) and by the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 37–45, 1998.     

On some developments in the representation theory of cylindric-like algebras

In this survey paper we recall the representation problem of certain classes of algebras of relations. Two specific recent research directions in algebraic logic are surveyed: the one is connected with the representation theory of cylindric relativized set algebras including Resek’s representation theorem and merry-go-round axioms, the other discusses the representation problem in some non-well-founded set theories where the axiom of foundation is replaced by Boffa’s weak anti-foundation axiom. This paper is dedicated to Walter Taylor. Received September 8, 2005; accepted in final form January 12, 2006. The first author was supported by Hungarian National Foundation for Scientific Research grants T43242 and T035192. The second author was supported by Hungarian National Foundation for Scientific Research grants D042177, T43242 and T035192.     

On the Distributions of Two Classes of Multiple Dependent Aggregate Claims

In this paper we examine two classes of correlated aggregate claims distributions, with univariate claim counts and multivariate claim sizes. Firstly, we extend the results of Hesselager [ASTIN Bulletin, 24： 19-32（1994）] and Wang ＆ Sobrero＇s [ASTIN Bulletin, 24：161-166 （1994）] concerning recursions for compound distributions to a multivariate situation where each claim event generates a random vector. Then we give a multivariate continuous version of recursive algorithm for calculating a family of compound distribution. Especially, to some extent, we obtain a continuous version of the corresponding results in Sundt [ASTIN Bulletin, 29：29-45 （1999）] and Ambagaspitiya [Insurance： Mathematics and Economics, 24：301-308 （1999）]. Finally, we give an example and show how to use the algorithm for aggregate claim distribution of first class to compute recursively the compound distribution.     

Graph theoretic method for determining hurwitz equivalence in the symmetric group

Motivated by the problem of Hurwitz equivalence of Δ² factorization in the braid group, we address the problem of Hurwitz equivalence in the symmetric group, of 1s _n factorizations with transposition factors. Looking at the transpositions as the edges in a graph, we show that two factorizations are Hurwitz equivalent if and only if their graphs have the same weighted connected components. The graph structure allows us to compute Hurwitz equivalence in the symmetric group. Using this result, one can compute non-Hurwitz equivalence in the braid group. This paper is part of the author’s PhD thesis. This work was partially supported by the Emmy Noether Research Institute for Mathematics (center of the Minerva Foundation of Germany), the Excellency Center “Group Theoretic Methods in the Study of Algebraic Varieties” of the Israel Science Foundation, and by EAGER (EU network, HPRN-CT-2009-00099). Received December 31, 2001 and in revised form August 6, 2002     

Feedback Stackelberg equilibrium strategies when the private label competes with the national brand

We consider a noncooperative differential game where a retailer sells her own private label in addition to the manufacturer’s brand. We assume that each brand’s goodwill evolves according to a modified Nerlove-Arrow dynamics, in such a way that the advertising effort of one brand hurts the competitor’s goodwill stock. We characterize Feedback-Stackelberg pricing and advertising strategies and employ simulations to analyze their sensitivity to the main model parameters. We thank an anonymous Reviewer for very helpful comments. Research supported by NSERC, Canada, and FQRSC, Quebec. Research completed when the second author was a visiting professor at GERAD, HEC Montréal. The second author’s research was partially supported by MEC and JCYL under projects SEJ2005-03858/ECON and VA045A06, co-financed by FEDER funds.     

A Half-Space Approach to Order Dimension

The aim of the present paper is to investigate the half-spaces in the convexity structure of all quasiorders on a given set and to use them in an alternative approach to classical order dimension. The main result states that linear orders can almost always be replaced by half-space quasiorders in the definition of the dimension of a partially ordered set. The work of the first named author was partially supported by the European Community’s Marie Curie Program (contract MTKD-CT-2004-003006). The second named author’s work was supported by OTKA of Hungary No. T043034.