A globally convergent Newton method for solving strongly monotone variational inequalities

Variational inequality problems have been used to formulate and study equilibrium problems, which arise in many fields including economics, operations research and regional sciences. For solving variational inequality problems, various iterative methods such as projection methods and the nonlinear Jacobi method have been developed. These methods are convergent to a solution under certain conditions, but their rates of convergence are typically linear. In this paper we propose to modify the Newton method for variational inequality problems by using a certain differentiable merit function to determine a suitable step length. The purpose of introducing this merit function is to provide some measure of the discrepancy between the solution and the current iterate. It is then shown that, under the strong monotonicity assumption, the method is globally convergent and, under some additional assumptions, the rate of convergence is quadratic. Limited computational experience indicates the high efficiency of the proposed method.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

Spurious Shell Closures in the Relativistic Mean Field Model

Following a previous systematic theoretical study of the ground-state properties of over 7000 nuclei from the proton drip line to the neutron drip line in the relativistic mean field model [Prog. Theor. Phys. 113 （2005） 785], which is in fair agreement with existing experimental data, we observe a few spurious shell closures, i.e. proton shell closures at Z = 58 and Z = 92. These spurious shell closures are found to persist in all the effective forces of the relativistic mean field model, e.g. TMA, NL3, PKDD and DD-ME2.     

Properties of the πh_(9/2)  νi_(13/2) band in odd-odd ~(188)Au

A new rotational band has been identified and assigned to 188Au for the first time using the 173Yb(19F,4nγ) reaction at the beam energies of 86 and 90 MeV. This band is proposed to be built on the πh9/2  νi13/2 configuration by comparing the band properties with known bands in neighboring nuclei. The prolate-to-oblate shape transition through triaxial shape has been proposed to occur around 188Au for the πh9/2  νi13/2 bands in odd-odd Au isotopes on the basis of total Routhian surface (TRS) calculations.     

Detection of parametric resonance of trapped ions for micromotion compensation

We have detected excess micromotion of trapped ions by modulating the trapping voltage. This radio-frequency (rf) modulation induces parametric resonance and excites secular motion of the trapped ions when they possess excess motion. This technique has been applied to laser-cooled ions in a linear rf trap and it provides optimum values for compensating the trapping field. We found that the technique has sensitivity equal to or greater than the conventional method for detecting excess micromotion. Because any laser propagation direction can be used, this method is expected to be applied to surface-electrode traps.     

A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations

be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem. Received: March 24, 1997     

Implementing an efficient minimum capacity cut algorithm

In this paper, we present an efficient implementation of theO(mn + n ² logn) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration. To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved.Corresponding author.     

Dynamic Generalized Assignment Problems with Stochastic Demands and Multiple Agent--Task Relationships

The assignment problem is a well-known operations research model. Its various extensions have been applied to the design of distributed computer systems, job assignment in telecommunication networks, and solving diverse location, truck routing and job shop scheduling problems.This paper focuses on a dynamic generalization of the assignment problem where each task consists of a number of units to be performed by an agent or by a limited number of agents at a time. Demands for the task units are stochastic. Costs are incurred when an agent performs a task or a group of tasks and when there is a surplus or shortage of the task units with respect to their demands. We prove that this stochastic, continuous-time generalized assignment problem is strongly NP-hard, and reduce it to a number of classical, deterministic assignment problems stated at discrete time points. On this basis, a pseudo-polynomial time combinatorial algorithm is derived to approximate the solution, which converges to the global optimum as the distance between the consecutive time points decreases. Lower bound and complexity estimates for solving the problem and its special cases are found.     

Notes on the Problem of the Allocation of Resources to Activities in Discrete Quantities

The simple resource allocation problem (also called the distribution of effort problem) is generalized by allowing more than one resource constraint. It is shown that the generalized problem can be reduced to the simple one if the coefficients in the objective function are all unity. In general, however, the problem seems to become much more difficult; the difficulty is evidenced by the failure of the incremental method which is valid for the simple problem, and the NP-hardness of the generalized problem.     

Scheduling of corrugated paper production

Corrugated paper is produced by gluing three types of papers of the same breadth. Given a set of orders, we first assign each order to one of the standard breadths, and then sequence those assigned to each standard breadth so that they are continuously manufactured from the three rolls of the specified standard breadth equipped in the machine called corrugator. Here we are asked to achieve multi-goals of minimizing total length of roll papers, total loss of papers caused by the differences between standard breadths and real breadths of the orders, and the number of machine stops needed during production. We use integer programming to assign orders to standard breadths, and then develop a special purpose algorithm to sequence the orders assigned to each standard breadth. This is a first attempt to handle scheduling problems of the corrugator machine.