We describe an interior point algorithm for convex quadratic problem with a strict complementarity constraints. We show that under some assumptions the approach requires a total of number of iterations, where L is the input size of the problem. The algorithm generates a sequence of problems, each of which is approximately solved by Newton's method.
We propose a feasible primal-dual path-following interior-point algorithm for semidefinite least squares problems (SDLS). At each iteration, the algorithm uses only full Nesterov-Todd steps with the advantage that no line search is required. Under new appropriate choices of the parameter which defines the size of the neighborhood of the central-path and of the parameter which determines the rate of decrease of the barrier parameter, we show that the proposed algorithm is well defined and converges...
This is a tutorial survey of recent results in the area of multiprocessor scheduling. Computational complexity theory provides the framework in which these results are presented. They involve on one hand the development of new polynomial optimization algorithms, and on the other hand the application of the concept of NP-hardness as well as the analysis of approximation algorithms.
The paper presents an iterative algorithm for computing the maximum cycle mean (or eigenvalue) of triangular Toeplitz matrix in max-plus algebra. The problem is solved by an iterative algorithm which is applied to special cycles. These cycles of triangular Toeplitz matrices are characterized by sub-partitions of .
This paper deals with a single server queue with compulsory server vacations. There are single Poisson arrivals with mean arrival date λ and the service is performed in batches of fixed size M (≥1) or min (n, M) and the service times of successive batches follow a general distribution with the density function D(x). The Laplace transforms of the probability generating functions of different states of the system have been obtained, the corresponding steady state results have been derived and in a...
This paper describes an unreliable server batch arrival retrial queue with two types of repair and second optional service. The server provides preliminary first essential service (FES) to the primary arriving customers or customers from retrial group. On successful completion of FES, the customer may opt for second optional service (SOS) with probability α. The server is subject to active break downs. The customer under FES (or SOS) during the failure decides, with probability q, to join the orbit(impatientcustomer)...
We propose a modification of MPGP algorithm for solving minimizing problem of strictly convex quadratic function subject to separable spherical constraints. This active set based algorithm explores the faces by the conjugate gradients and changes the active sets and active variables by the gradient projection with the Barzilai-Borwein steplength. We show how to use the algorithm for the solution of separable and equality constraints. The power of our modification is demonstrated on the solution...
This work concerns controlled Markov chains with finite state space and compact action sets. The decision maker is risk-averse with constant risk-sensitivity, and the performance of a control policy is measured by the long-run average cost criterion. Under standard continuity-compactness conditions, it is shown that the (possibly non-constant) optimal value function is characterized by a system of optimality equations which allows to obtain an optimal stationary policy. Also, it is shown that the...
We propose new alternative theorems for convex infinite systems which constitute the generalization of the corresponding to Gale, Farkas, Gordan and Motzkin. By means of these powerful results we establish new approaches to the Theory of Infinite Linear Inequality Systems, Perfect Duality, Semi-infinite Games and Optimality Theory for non-differentiable convex Semi-Infinite Programming Problem.
We address a queueing control problem considering service times and conversion times following normal distributions. We formulate the multi-server queueing control problem by constructing a semi-Markov decision process (SMDP) model. The mechanism of state transitions is developed through mathematical derivation of the transition probabilities and transition times. We also study the property of the queueing control system and show that optimizing the objective function of the addressed queueing control...