Distributed nonlinear optimization algorithms for general network problems

There are a number of large networks which occur in many problems dealing with the flow of power, communication signals, water, gas, transportable goods, etc. Both design and planning of these networks involve optimization problems. The first part of this paper introduces the common characteristics of a nonlinear network (the network may be linear, the objective function may be non linear, or both may be nonlinear). The second part develops a mathematical model trying to put together some important constraints based on the abstraction for a general network. The third part deals with solution procedures; it converts the network to a matrix based system of equations, gives the characteristics of the matrix and suggests two solution procedures, one of them being a new one. The fourth part handles spatially distributed networks and evolves a number of decomposition techniques so that we can solve the problem with the help of a distributed computer system. Algorithms for parallel processors and spatially distributed systems have been described.There are a number of common features that pertain to networks. A network consists of a set of nodes and arcs. In addition at every node, there is a possibility of an input (like power, water, message, goods etc) or an output or none. Normally, the network equations describe the flows amoungst nodes through the arcs. These network equations couple variables associated with nodes. Invariably, variables pertaining to arcs are constants; the result required will be flows through the arcs. To solve the normal base problem, we are given input flows at nodes, output flows at nodes and certain physical constraints on other variables at nodes and we should find out the flows through the network (variables at nodes will be referred to as across variables).The optimization problem involves in selecting inputs at nodes so as to optimise an objective function; the objective may be a cost function based on the inputs to be minimised or a loss function or an efficiency function. The above mathematical model can be solved using Lagrange Multiplier technique since the equalities are strong compared to inequalities. The Lagrange multiplier technique divides the solution procedure into two stages per iteration. Stage one calculates the problem variables % and stage two the multipliers lambda. It is shown that the Jacobian matrix used in stage one (for solving a nonlinear system of necessary conditions) occurs in the stage two also.A second solution procedure has also been imbedded into the first one. This is called total residue approach. It changes the equality constraints so that we can get faster convergence of the iterations.Both solution procedures are found to coverge in 3 to 7 iterations for a sample network.The availability of distributed computer systems — both LAN and WAN — suggest the need for algorithms to solve the optimization problems. Two types of algorithms have been proposed — one based on the physics of the network and the other on the property of the Jacobian matrix. Three algorithms have been deviced, one of them for the local area case. These algorithms are called as regional distributed algorithm, hierarchical regional distributed algorithm (both using the physics properties of the network), and locally distributed algorithm (a multiprocessor based approach with a local area network configuration). The approach used was to define an algorithm that is faster and uses minimum communications. These algorithms are found to converge at the same rate as the non distributed (unitary) case.

Toeplitz Operators with Special Symbols on Segal-Bargmann Spaces

We study the boundedness of Toeplitz operators on Segal-Bargmann spaces in various contexts. Using Gutzmer's formula as the main tool we identify symbols for which the Toeplitz operators correspond to Fourier multipliers on the underlying groups. The spaces considered include Fock spaces, Hermite and twisted Bergman spaces and Segal-Bargmann spaces associated to Riemannian symmetric spaces of compact type.

Tatonnement Mechanisms for Combinatorial Exchanges

Combinatorial exchanges are double sided marketplaces with multiple sellers and multiple buyers trading with the help of combinatorial bids. The allocation and other associated problems in such exchanges are known to be among the hardest to solve among all economic mechanisms. It has been shown that the problems of surplus maximization or volume maximization in combinatorial exchanges are inapproximable even with free disposal. In this paper, the surplus maximization problem is formulated as an integer linear programming problem and we propose a Lagrangian relaxation based heuristic to find a near optimal solution. We develop computationally efficient tâtonnement mechanisms for clearing combinatorial exchanges where the Lagrangian multipliers can be interpreted as the prices of the items set by the exchange in each iteration. Our mechanisms satisfy Individual-rationality and Budget-nonnegativity properties. The computational experiments performed on representative data sets show that the proposed heuristic produces a feasible solution with negligible optimality gap.

Energy absorption behaviours of CSM-based GFRC plates with hemispherical features

In the present study, the mechanical behaviour of CSM (chopped strand mat)-based GFRC (glass fibre-reinforced composite) plates with single and multiple hemispheres under compressive loads has been investigated both experimentally and numerically. The basic stress-strain behaviours arc identified with quasi-static tests on two-ply coupon laminates and short cylinders, and these are followed up with compressive tests in a UTM (universal testing machine) on single- and multiple-hemisphere plates. The ability of an explicit LS-DYNA solver in predicting the complex material behaviour of composite hemispheres, including failure, is demonstrated. The relevance and scalability of the present class of structural components as `force-multipliers' and `energy-multipliers' have been justified by virtue of findings that as the number of hemispheres in a panel increased from one to four, peak load and average absorbed energy rose by factors of approximately four and six, respectively. The performance of a composite hemisphere has been compared to similar-sized steel and aluminium hemispheres, and the former is found to be of distinctly higher specific energy than the steel specimen. A simulation-based study has also been carried out on a composite 2 x 2-hemisphere panel under impact loads and its behaviour approaching that of an ideal energy absorber has been predicted. In summary, the present investigation has established the efficacy of composite plates with hemispherical force multipliers as potential energy-absorbing countermeasures and the suitability of CAE (computer-aided engineering) for their design.

Revisiting Riesz transforms on Heisenberg groups

We characterise higher order Riesz transforms on the Heisenberg group and also show that they satisfy dimension-free bounds under some assumptions on the multipliers. Using transference theorems, we deduce boundedness theorems for Riesz transforms on the reduced Heisenberg group and hence also for the Riesz transforms associated to multiple Hermite and Laguerre expansions.

The defect sequence for contractive tuples

We introduce the defect sequence for a contractive tuple of Hilbert space operators and investigate its properties. The defect sequence is a sequence of numbers, called defect dimensions associated with a contractive tuple. We show that there are upper bounds for the defect dimensions. The tuples for which these upper bounds are obtained, are called maximal contractive tuples. The upper bounds are different in the non-commutative and in the commutative case. We show that the creation operators on the full Fock space and the coordinate multipliers on the Drury-Arveson space are maximal. We also study pure tuples and see how the defect dimensions play a role in their irreducibility. (C) 2012 Elsevier Inc. All rights reserved.

Stochastic optimization for adaptive labor staffing in service systems

Service systems are labor intensive. Further, the workload tends to vary greatly with time. Adapting the staffing levels to the workloads in such systems is nontrivial due to a large number of parameters and operational variations, but crucial for business objectives such as minimal labor inventory. One of the central challenges is to optimize the staffing while maintaining system steady-state and compliance to aggregate SLA constraints. We formulate this problem as a parametrized constrained Markov process and propose a novel stochastic optimization algorithm for solving it. Our algorithm is a multi-timescale stochastic approximation scheme that incorporates a SPSA based algorithm for ‘primal descent' and couples it with a ‘dual ascent' scheme for the Lagrange multipliers. We validate this optimization scheme on five real-life service systems and compare it with a state-of-the-art optimization tool-kit OptQuest. Being two orders of magnitude faster than OptQuest, our scheme is particularly suitable for adaptive labor staffing. Also, we observe that it guarantees convergence and finds better solutions than OptQuest in many cases.

Simultaneous perturbation methods for adaptive labor staffing in service systems

We consider the problem of optimizing the workforce of a service system. Adapting the staffing levels in such systems is non-trivial due to large variations in workload and the large number of system parameters do not allow for a brute force search. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. Our aim is to find the optimum staffing levels from a discrete high-dimensional parameter set, that minimizes the long run average of the single-stage cost function, while adhering to the constraints relating to queue stability and service-level agreement (SLA) compliance. The single-stage cost function balances the conflicting objectives of utilizing workers better and attaining the target SLAs. We formulate this problem as a constrained parameterized Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA)-based algorithms for solving the above problem. The algorithms include both first-order as well as second-order methods and incorporate SPSA-based gradient/Hessian estimates for primal descent, while performing dual ascent for the Lagrange multipliers. Both algorithms are online and update the staffing levels in an incremental fashion. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by our algorithms onto the discrete set. The smoothness is necessary to ensure that the underlying transition dynamics of the constrained Markov cost process is itself smooth (as a function of the continuous-valued parameter): a critical requirement to prove the convergence of both algorithms. We validate our algorithms via performance simulations based on data from five real-life service systems. For the sake of comparison, we also implement a scatter search based algorithm using state-of-the-art optimization tool-kit OptQuest. From the experiments, we observe that both our algorithms converge empirically and consistently outperform OptQuest in most of the settings considered. This finding coupled with the computational advantage of our algorithms make them amenable for adaptive labor staffing in real-life service systems.

A hybrid finite element formulation for flexible multibody dynamics

This work deals with the transient analysis of flexible multibody systems within a hybrid finite element framework. Hybrid finite elements are based on a two-field variational formulation in which the displacements and stresses are interpolated separately yielding very good coarse mesh accuracy. Most of the literature on flexible multibody systems uses beam-theory-based formulations. In contrast, the use of hybrid finite elements uses continuum-based elements, thus avoiding the problems associated with rotational degrees of freedom. In particular, any given three-dimensional constitutive relations can be directly used within the framework of this formulation. Since the coarse mesh accuracy as compared to a conventional displacement-based formulation is very high, the scheme is cost effective as well. A general formulation is developed for the constrained motion of a given point on a line manifold, using a total Lagrangian method. The multipoint constraint equations are implemented using Lagrange multipliers. Various kinds of joints such as cylindrical, prismatic, and screw joints are implemented within this general framework. Hinge joints such as spherical, universal, and revolute joints are obtained simply by using shared nodes between the bodies. In addition to joints, the formulation and implementation details for a DC motor actuator and for prescribed relative rotation are also presented. Several example problems illustrate the efficacy of the developed formulation.