-
作者：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...
-
作者：Scholtes, S
摘要：This article is mainly concerned with the homeomorphism problem for piecewise affine mappings (PA-maps), i.e., mappings which coincide with an affine mapping on each polyhedron of some finite polyhedral subdivision of R(n). In the first part, we prove that a PA-map can be defined without referring to a subdivision of R(n) as a continuous mapping which coincides at every point x is an element of R(n) with al least one function from a finite collection of affine functions. The second part studie...
-
作者：Guler, O
摘要：We show that the universal barrier function of a convex cone introduced by Nesterov and Nemirovskii is the logarithm of the characteristic function of the cone. This interpretation demonstrates the invariance of the universal barrier under the automorphism group of the underlying cone. This provides a simple method for calculating the universal barrier for homogeneous cones. We identify some known barriers as the universal barrier scaled by an appropriate constant. We also calculate some new u...
-
作者：Pang, JS; Ralph, D
作者单位：University of Melbourne
摘要：This paper is concerned with properties of the Euclidean projection map onto a convex set defined by finitely many smooth, convex inequalities and affine equalities. Under a constant rank constraint qualification, we show that the projection map is piecewise smooth (PC1) hence B(ouligand)-differentiable, or directionally differentiable; and a relatively simple formula is given for the B-derivative. These properties of the projection map are used to obtain inverse and implicit function theorems...
-
作者：Flesch, J; Thuijsman, F; Vrieze, OJ
摘要：We show the existence of stationary limiting average epsilon-equilibria (epsilon > 0) for two-person recursive repeated games with absorbing states. These are stochastic games where all states but one are absorbing, and in the nonabsorbing state ail payoffs are equal to zero. A state is called absorbing if the probability of a transition to any other state is zero for all available pairs of actions. For the purpose of our proof, we introduce properness for stationary strategy pairs. Our result...
-
作者：Bertsimas, D; Nino-Mora, J
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible region of achievable performance is a polyhedron called an extended polymatroid, that generalizes the classical polymatroids introduced by Edmonds. Optimization of a linear objective over an extended polymatroid is solved by an adaptive greedy algorithm, which leads to an optimal solution having an indexability property (indexable systems). Under a certain...
