-
作者：Huang, LR; Ng, KF
作者单位：Chinese University of Hong Kong
摘要：Let f be a regular, locally Lipschitz real-valued function defined on an open convex subset of a normed space. We show that at any unit direction u, the upper second-order derivative D(+)(2)f(.;u, 0) (in the sense of Dem'yanov and Pevnyi 1974; Ben-Tal and Zowe 1982) has the same lower bounds as the lower second-order derivatives D(-)(2)f(.; u, 0). Consequently, one can characterize the convexity of f in terms of these derivatives. We also obtain the corresponding results in terms of Chaney's s...
-
作者：Muller, A
摘要：The present work deals with the comparison of (discrete time) Markov decision processes (MDPs), which differ only in their transition probabilities. We show that the optimal value function of an MDP is monotone with respect to appropriately defined stochastic order relations. We also find conditions for continuity with respect to suitable probability metrics. The results are applied to some well-known examples, including inventory control and optimal stopping.
-
作者：Nagamochi, H; Zeng, DZ; Kabutoya, N; Ibaraki, T
作者单位：Kagawa University
摘要：This paper studies the complexity of computing solution concepts for a cooperative game, called the minimum base game (MEG) (E, c), where its characteristic function c:2(E) --> N is defined as c(S) = (the weight w(B) of a minimum weighted base B subset of or equal to S), for a given matroid M=(E, J) and a weight function w: E --> N. The minimum base game contains, as a special case, the minimum spanning tree game (MSTG) in an edge-weighted graph in which players are located on the edges. By in...
-
作者：Yushkevich, AA
摘要：The background for this paper is a dynamic programming model with a Borel state space and compact action sets. A new simple proof of the compactness of a space of measures corresponding to randomized stationary policies is given, in a topology induced by Caratheodory functions on the state-action space. For this purpose an extension theorem for Caratheodory functions is proved, which is a new version of the Tietze's extension theorem for continuous functions.
-
作者：Goldfarb, D; Jin, ZY; Orlin, JB
作者单位：Massachusetts Institute of Technology (MIT)
摘要：This paper presents two new combinatorial algorithms for the generalized circulation problem. After an initial step in which all flow-generating cycles are canceled and excesses are created, both algorithms bring these excesses to the sink via highest-gain augmenting paths. Scaling is applied to the fixed amount of flow that the algorithms attempt to send to the sink, and both node and are excesses are used. The algorithms have worst-case complexities of O(m(2)(m + n log n) log B), where n is ...
-
作者：Zhou, XY
摘要：Near-optimization is as sensible and important as optimization for both theory and applications. This paper concerns dynamic near-optimization, or near-optimal controls, for systems governed by deterministic ordinary differential equations, and uses dynamic programming to study the near-optimality. Since nonsmoothness is inherent in this subject, the viscosity solution approach is employed to investigate the problem. The dynamic programming equation is derived in terms of epsilon-superdifferen...
-
作者：Lewis, AS
摘要：A spectral function of a Hermitian matrix X is a function which depends only on the eigenvalues of X, lambda(1)(X) greater than or equal to lambda(2)(X) greater than or equal to ... greater than or equal to lambda(n)(X), and hence may be written f(lambda(2)(X), lambda(2)(X),..., lambda(n)(X)) for some symmetric function f. Such functions appear in a wide variety of matrix optimization problems. We give a simple proof that this spectral function is differentiable at X if and only if the functio...
-
作者：Khachiyan, LG
摘要：Let A be a set of m points in R(n). We show that the problem of (1 + epsilon)n-rounding of A,, i.e., the problem of computing an ellipsoid E subset of or equal to R(n) such that [(1 + epsilon)n](-1)E subset of or equal to conv. hull(A) subset of or equal to E, can be solved in O(mn(2)(epsilon(-1) + In n + In In m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about A can be solved in O(m(3.5) In(m epsilo...
-
作者：Monteiro, RDC; Pang, JS
作者单位：Johns Hopkins University
摘要：Using a unified theory of local homeomorphic maps, we establish some basic properties of a fundamental mapping associated with the family of path-following interior-point methods for solving a mixed nonlinear complementarity problem.
-
作者：More, JJ
摘要：Global methods for nonlinear complementarity problems formulate the problem as a system of nonsmooth nonlinear equations, or use continuation to trace a path defined by a smooth system of nonlinear equations. We formulate the nonlinear complementarity problem as a bound-constrained nonlinear least squares problem. Algorithms based on this formulation are applicable to general nonlinear complementarity problems, can be started from any nonnegative starting point, and each iteration only require...
