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).