Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Piece adding technique for convex maximization problems

In this article we provide an algorithm, where to escape from a local maximum y of convex function f over D, we (locally) solve piecewise convex maximization max{min{f (x) − f (y), p _y (x)} | x ∈ D} with an additional convex function p _y (·). The last problem can be seen as a strictly convex improvement of the standard cutting plane technique for convex maximization. We report some computational results, that show the algorithm efficiency.     

An approximation algorithm for the general max-min resource sharing problem

We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio The algorithm is faster and simpler than the previous known approximation algorithms for the problem [12, 13] Research of the author was supported in part by EU Thematic Network APPOL, Approximation and Online Algorithms, IST-2001-30012, by EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135 and by DFG Project, Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und überdeckungsprobleme, JA 612/10-1. Part of this work was done while visiting the Department of Computer Science at ETH Zürich. An extended abstract of this paper appeared in SWAT 2004, Scandinavian Workshop on Algorithm Theory, LNCS 3111, 311–322.     

An M/M/1 Driven Fluid Queue – Continued Fraction Approach

This paper presents complete solutions of the stationary distributions of buffer occupancy and buffer content of a fluid queue driven by an M/M/1 queue. We assume a general boundary condition when compared to the model discussed in Virtamo and Norros [Queueing Systems 16 (1994) 373–386] and Adan and Resing [Queueing Systems 22 (1996) 171–174]. We achieve the required solutions by transforming the underlying system of differential equations using Laplace transforms to a system of difference equations leading to a continued fraction. This continued fraction helps us to find complete solutions. We also obtain the buffer content distribution for this fluid model using the method of Sericola and Tuffin [Queueing Systems 31 (1999) 253–264].     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

Conditions for convergence of trust region algorithms for nonsmooth optimization

This paper discusses some properties of trust region algorithms for nonsmooth optimization. The problem is expressed as the minimization of a functionh(f(x), whereh(·) is convex andf is a continuously differentiable mapping from ℝ″ to ℝ‴. Bounds for the second order derivative approximation matrices are discussed. It is shown that Powel’s [7, 8] results hold for nonsmooth optimization.     

The Economic Lot Scheduling Problem without Capacity Constraints

This study presents a comprehensive analysis on the Economic Lot Scheduling Problem (ELSP) without capacity constraints. We explore the optimality structure of the ELSP without capacity constraints and discover that the curve for the optimal objective values is piecewise convex with repsect to B, i.e., the values of basic period. The theoretical properties of the junction points on the piecewise convex curve not only provides us the information on “which product i” to modify, but also on “where on the B-axis” to change the set of optimal multpliers in the search process. By making use of the junction points, we propose an effective search algorithm to secure a global optimal solution for the ELSP without capacity constraints. Also, we use random experiments to verify that the proposed algorithm is efficient. The results in this paper lay important foundation for deriving an efficient heuristic to solve the conventional ELSP with capacity constraints.     

On uniqueness and existence of entropy solutions for a nonlinear parabolic problem with absorption

The aim of this paper is to study, for L ¹-data, the absorption problem of parabolic type : with Dirichlet boundary conditions and initial conditions. Here a satisfies the classical Leray-Lions hypotheses and β(x, ·) is the subdifferential ∂j(x, ·), where j is a convex function such that j(·, 0) = 0. Existence and uniqueness of an entropy solution is established.      

Convex separable minimization with box constraints

A minimization problem with convex separable objective function subject to a convex separable inequality constraint of the form “less than or equal to” and bounds on the variables (box constraints) is considered. Necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. An iterative algorithm of polynomial complexity for solving problems of the considered form is suggested and its convergence is proved. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The long-step method of analytic centers for fractional problems

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t ₀ |t ₀ B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial “centering” phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds. The research was partly supported by the Israeli-American Binational Science Foundation (BSF).     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

The representations of two types of functionals on L∞(Ω, ?) and L∞(Ω, ?, ?)

This article gives the representations of two types of real functionals on L ^∞(Ω, Ƒ) or L ^∞(Ω, Ƒ, ℙ) in terms of Choquet integrals. These functionals are comonotonically subadditive and comonotonically convex, respectively.     

Generalized Semi-Infinite Programming: Optimality Conditions Involving Reverse Convex Problems

This article deals with a generalized semi-infinite programming problem (S). Under appropriate assumptions, for such a problem we give necessary and sufficient optimality conditions via reverse convex problems. In particular, a necessary and sufficient optimality condition reduces the problem (S) to a min-max problem constrained with compact convex linked constraints.     

A characterization of the<Emphasis Type="Italic">MM</Emphasis>*-position of a convex body in terms of covariance matrices

We characterize the position of a convex bodyK such that it minimizesM(TK)M*(TK) (theMM*-position) in terms of properties of the measures ‖ · ‖ _K d σ(·) and ‖ · ‖ _K °d σ(·), answering a question posed by A. Giannopoulos and V. Milman. The techniques used allow us to study other extremal problems in the context of dual Brunn-Minkowski theory. Partially supported by MCYT Grant (Spain) BFM2001-1793 and FEDER funds from UE. Partially supported by MCYT Grant (Spain) BFM2001-1793 and FEDER funds from UE.     

Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments —aimed at the improved efficiency of the algorithm — are presented. This research was supported in part by National Science Foundation Grant No. DCR-8401098-A0l.     

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.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.