A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices

A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product spaceS of unit simplices. The triangulation which underlies the algorithm differs from the triangulations ofS used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrarily chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex ofS. In caseS is the product ofn one-dimensional unit simplices the alogrithm is similar to the octahedral algorithm onR ⁿ having 2 ⁿ rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms onS. Computational results will show that the number of iterations for the new algorithm is much less. The examples concern the computation of equilibria in noncooperative games, exchange economies and trade models. This author is financially supported by the Netherlands Organisation for the Advancement of Pure Research (ZWO), Grant 46-98. This research is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply” which has been approved by the Netherlands ministry of education and sciences.     

Complete characterization of almost Moore digraphs of degree three

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005     

On the cauchy problem for a class of degenerate differential equations with Lipschitz right-hand side

This note deals with an application of the fixed point theorem for multivalued contraction mappings to the study of degenerate differential equations with Lipschitz right-hand side and with degeneration determined by a closed surjective linear operator.     

Analysis of an industrial component commonality problem

We discuss a case study of an industrial production-marketing coordination problem involving component commonality. For the product line considered, the strategic goal of the company is to move from the current low volume market to a high volume market. The marketing department believes that this can be achieved by substantially lowering the end products’ prices. However, this requires a product redesign to lower production costs in order to maintain profit margins. The redesign decision involves grouping end products into families. All products within one family use the same version of some components. This paper fits in the stream of recent literature on component commonality where the focus has shifted from inventory cost savings to production and development cost savings. Further, we consider both costs and revenues, leading to a profit maximization approach. The price elasticity of demand determines the relationship between the price level and number of units sold. Consequently, we integrate information from different functional areas such as production, marketing and accounting. We formulate the problem as a net-present-value investment decision. We propose a mixed integer nonlinear optimization model to find the optimal commonality decision. The recommendation based on our analysis has been implemented in the company. In addition, the application allows us to experimentally validate some claims made in the literature and obtain managerial insights into the trade-offs.     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

George Boole and the origins of invariant theory

Historians have repeatedly asserted that invariant theory was born in two papers of George Boole (1841 and 1842). Although several themes and techniques of 19th-century invariant theory are enunciated in this work, in reacting to it (and thereby founding the British school of invariant theory), Arthur Cayley shifted Boole's research program.     

MONOTONIZATION IN GLOBAL OPTIMIZATION

A general monotonization method is proposed for converting a constrained programming problem with non-monotone objective function and monotone constraint functions into a monotone programming problem. An equivalent monotone programming problem with only inequality constraints is obtained via this monotonization method. Then the existing convexification and concavefication methods can be used to convert the monotone programming problem into an equivalent better-structured optimization problem.     

A VARIATIONAL EXPECTATION-MAXIMIZATION METHOD FOR THE INVERSE BLACK BODY RADIATION PROBLEM

The inverse black body radiation problem, which is to reconstruct the area temperature distribution from the measurement of power spectrum distribution, is a well-known ill-posed problem. In this paper, a variational expectation-maximization （EM） method is developed and its convergence is studied. Numerical experiments demonstrate that the variational EM method is more efficient and accurate than the traditional methods, including the Tikhonov regularization method, the Landweber method and the conjugate gradient method.     

Representation for the Green’s function of the Dirichlet problem for polyharmonic equations in a ball

We explicitly construct the Green’s function for the Dirichlet problem for polyharmonic equations in a ball in a space of arbitrary dimension. The formulas for the Green’s function are of interest in their own right. In particular, the explicit representations for a solution to the Dirichlet problem for the biharmonic equation are important in elasticity.     

A simple 1D model of inviscid fluid-solid interaction

We analyze a one-dimensional fluid-particle interaction model, composed by the Burgers equation for the fluid velocity and an ordinary differential equation which governs the particle movement. The coupling is achieved through a friction term. One of the novelties is to consider entropy weak solutions involving shock waves. The difficulty is the interaction between these shock waves and the particle. We prove that the Riemann problem with arbitrary data always admits a solution, which is explicitly constructed. Besides, two asymptotic behaviors are described: the long-time behavior and the behavior for large friction coefficients.