Search

Infinitesimal perturbation analysis (IPA) provides formulas for random gradients (derivatives) of performance measures with respect to parameters of interest, computed from sample paths of stochastic systems. In practice, IPA derivatives may be computed either from simulation runs or from empirical field data (when the formulas are nonparametric). Nonparametric IPA derivatives in fluid-flow queues have been recently derived for the loss volume and time average of buffer occupancy, with respect to buffer size, and arrival-rate or service-rate parameters. Additionally, these IPA derivatives have been shown to be unbiased in the sense that their expectation and differentiation operators commute, while their traditional discrete counterparts have long been known to be generally biased. Recent work has further shown how to map the computation of IPA derivatives from a fluid-flow queue to a compatible discrete counterpart without an appreciable loss of accuracy in performance measures. Thus, this work holds the promise of potential applications of IPA derivatives to gradient-based optimization of objective functions involving performance metrics parameterized by settable parameters in a queueing network context. This paper is an empirical study of IPA derivatives of individual queues within queueing systems which model telecommunications networks and some of their protocols. As a testbed, we used HNS (Hybrid Network Simulator) — a hybrid Java simulator of queueing networks with traffic streams subject to several telecommunications protocols. More specifically, the hybrid feature of HNS admits models with mixtures of discrete (packet) flows and continuous (fluid) flows, and collects detailed statistics and IPA derivatives for all flow types. The paper outlines the mapping of IPA derivatives from the fluid domain to the packet domain as implemented in HNS, and studies the accuracy of IPA derivatives in compatible fluid and packet queueing models, as well as the stabilization of their values in time. Our experimental results lend empirical support to the contention that IPA derivatives can be accurately computed from discrete versions by adopting a fluid-flow view. Furthermore, the long-run values of various IPA derivatives are empirically shown to stabilize quite fast. Finally, the results provide the basis and motivation for IPA applications to the optimization of telecommunications network design and to potential new open-loop protocols that take advantage of IPA information. [Copyright &y& Elsevier]

Abstract: A novel modified differential evolution algorithm (NMDE) is proposed to solve constrained optimization problems in this paper. The NMDE algorithm modifies scale factor and crossover rate using an adaptive strategy. For any solution, if it is at a standstill, its own scale factor and crossover rate will be adjusted in terms of the information of all successful solutions. We can obtain satisfactory feasible solutions for constrained optimization problems by combining the NMDE algorithm and a common penalty function method. Experimental results show that the proposed algorithm can yield better solutions than those reported in the literature for most problems, and it can be an efficient alternative to solving constrained optimization problems. [Copyright &y& Elsevier]

Abstract: Many real problems can be modeled to the problems with a hierarchical structure, and bilevel programming is a useful tool to solve the hierarchical optimization problems. So the bilevel programming is widely applied, and numerous methods have been proposed to solve this programming. In this paper, we propose an approximate programming algorithm to solve bilevel nonlinear programming problem. Finally, the example illustrates the feasibility of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: We consider a multiserver retrial queueing model with applications in service industries, in which customers arrive according to a Markovian arrival process (MAP). Any admitted customer either [(a)] gets service and leaves the system as a satisfied primary customer; or [(b)] gets service and becomes a secondary customer. The secondary customers leave the system either as satisfied or unsatisfied with their services. In this paper, we perform the steady state analysis of the model and also study the algorithmic aspects of this queueing model including an optimization problem. [Copyright &y& Elsevier]

Abstract: In this paper, a kind of nonlinear optimization problems with nonlinear inequality constraints are discussed, and a new SQP feasible descent algorithm for solving the problems is presented. At each iteration of the new algorithm, a convex quadratic program (QP) which always has feasible solution is solved and a master direction is obtained, then, an improved (feasible descent) direction is yielded by updating the master direction with an explicit formula, and in order to avoid the Maratos effect, a height-order correction direction is computed by another explicit formula of the master direction and the improved direction. The new algorithm is proved to be globally convergent and superlinearly convergent under mild conditions without the strict complementarity. Furthermore, the quadratic convergence rate of the algorithm is obtained when the twice derivatives of the objective function and constrained functions are adopted. Finally, some numerical tests are reported. [Copyright &y& Elsevier]

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem. [Copyright &y& Elsevier]

In this paper, we combine the new trust region subproblem proposed in [1] with the nonmonotone technique to propose a new algorithm for unconstrained optimization—the nonmonotone adaptive trust region method. The local and global convergence properties of the nonmonotone adaptive trust region method are proved. Its efficiency is tested by numerical results. [Copyright &y& Elsevier]