-
作者：Xu, Huifu; Meng, Fanwen
作者单位：University of Southampton; National University of Singapore
摘要：In this paper we discuss the sample average approximation (SAA) method for a class of stochastic programs with nonsmooth equality constraints. We derive a uniform Strong Law of Large Numbers for random compact set-valued mappings and use it to investigate the convergence of Karush-Kuhn-Tucker points of SAA programs as the sample size increases. We also study the exponential convergence of global minimizers of the SAA problems to their counterparts of the true problem. The convergence analysis ...
-
作者：Huang, Yongwei; Zhang, Shuzhong
作者单位：Chinese University of Hong Kong
摘要：This paper studies the possibilities of the linear matrix inequality characterization of the matrix cones formed by nonnegative complex Hermitian quadratic functions over specific domains in the complex space. In its real-case analog, such studies were conducted in Sturm and Zhang [Sturm, J. F., S. Zhang. 2003. On cones of nonnegative quadratic functions. Math. Oper Res. 28 246-267]. In this paper it is shown that stronger results can be obtained for the complex Hermitian case. In particular, ...
-
作者：Kanet, J. J.
作者单位：University System of Ohio; University of Dayton
摘要：In an earlier paper by Emmons [Emmons, H. 1969. One-machine sequencing to minimize certain functions of job tardiness. Oper Res. 17 701-715], the problem of sequencing jobs on a single machine in order to minimize total tardiness was analyzed. Emmons provided three theorems for specifying precedence relations for pairs of jobs. His theorems apply when the tardiness penalty for each job grows at the same rate. Rinnooy Kan et al. [Rinnooy Kan, A. H. G., B. J. Lageweg, J. K. Lenstra. 1975. Minimi...
-
作者：Conforti, Michele; Di Summa, Marco; Zambelli, Giacomo
作者单位：University of Padua
摘要：We study properties of systems of linear constraints that are minimally infeasible with respect to some subset S of constraints. (i.e., systems that are infeasible but that become feasible on removal of any constraint in S). We then apply these results and a theorem of Conforti, Cornuejols, Kapoor, and Vuskovic to a class of 0, 1 matrices, for which the linear relaxation of the set-partitioning polytope LSP(A) = (x vertical bar Ax = 1, x >= 0) is integral. In this way, we obtain combinatorial ...
-
作者：Maitra, Ashok P.; Sudderth, William D.
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：For an n-person stochastic game with Borel state space S and compact metric action sets A(1), A(2),...., A(n), sufficient conditions are given for the existence of subgame-perfect equilibria. One result is that such equilibria exist if the law of motion q(center dot vertical bar s, a) is, for fixed s, continuous in a = (a(1), a,....,a(n)) for the total variation norm and the payoff functions f(1), f(2),....,f(n) are bounded, Borel measurable functions of the sequence of states (s(1), s(2),...)...
-
作者：Kim, Sujin; Henderson, Shane G.
作者单位：Purdue University System; Purdue University; Cornell University
摘要：Adaptive Monte Carlo methods are simulation efficiency improvement techniques designed to adaptively tune simulation estimators. Most of the work on adaptive Monte Carlo methods has been devoted to adaptively tuning importance sampling schemes. We instead focus on adaptive methods based on control variate schemes. We introduce two adaptive control variate methods, and develop their asymptotic properties. The first method uses stochastic approximation to adaptively tune control variate estimato...
-
作者：Pang, J. S.
作者单位：Rensselaer Polytechnic Institute
摘要：This paper introduces a concept termed partial B-regularity for a feasible solution to a bivariate constraint system and shows that this condition leads to the equivalence between the B-stationarity of a pair of lifted and unlifted programs. In particular, for an optimization problem with a univariate pseudoconvex objective function constrained by such a nonconvex bivariate system, partial B-regularity provides a sufficient condition for a B-stationary point to be globally optimal. Application...
-
作者：Shepherd, F. B.; Vella, A.
作者单位：AT&T; McGill University
摘要：We examine formulations for the well-known b-matching problem in the presence of integer demands on the edges. A subset M of edges is feasible if for each node v the total demand of edges in M incident to v is at most b(v). We examine the system of star inequalities for this problem. This system yields an exact linear description for b-matchings in bipartite graphs. For the demand version, we show that the integrality gap for this system is at least 2.5 and at most 2.764. For general graphs, t...
-
作者：Debicki, K.; Dieker, A. B.; Rolski, T.
作者单位：University of Wroclaw; Centrum Wiskunde & Informatica (CWI); University of Twente
摘要：We study stochastic tree fluid networks driven by a multidimensional Levy process. We are interested in (the joint distribution of) the steady-state content in each of the buffers, the busy periods, and the idle periods. To investigate these fluid networks, we relate the above three quantities to fluctuations of the input Levy process by solving a multidimensional Skorokhod reflection problem. This leads to the analysis of the distribution of the componentwise maximums, the corresponding epoch...
-
作者：Kiwiel, Krzysztof C.; Larsson, Torbjoern; Lindberg, P. O.
作者单位：Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences; Linkoping University
摘要：We exhibit useful properties of ballstep subgradient methods for convex optimization using level controls for estimating the optimal value. Augmented with simple averaging schemes, they asymptotically find objective and constraint subgradients involved in optimality conditions. When applied to Lagrangian relaxation of convex programs, they find both primal and dual solutions, and have practicable stopping criteria. Up until now, similar results have only been known for proximal bundle methods,...
