-
作者：Drusvyatskiy, Dmitriy; Ioffe, Alexander D.; Lewis, Adrian S.
作者单位：University of Washington; University of Washington Seattle; University of Waterloo; Technion Israel Institute of Technology; Cornell University
摘要：Using a geometric argument, we show that under a reasonable continuity condition, the Clarke subdifferential of a semi-algebraic (or more generally stratifiable) directionally Lipschitzian function admits a simple form: The normal cone to the domain and limits of gradients generate the entire Clarke subdifferential. The characterization formula we obtain unifies various apparently disparate results that have appeared in the literature. Our techniques also yield a simplified proof that closed s...
-
作者：Muthuraman, Kumar; Seshadri, Sridhar; Wu, Qi
作者单位：University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; Indian School of Business (ISB); University System of Ohio; Case Western Reserve University
摘要：This article analyzes a continuous time back-ordered inventory system with stochastic demand and stochastic delivery lags for placed orders. This problem in general has an infinite dimensional state space and is hence intractable. We first obtain the set of minimal conditions for reducing such a system's state space to one dimension and show how this reduction is done. Next, by modeling demand as a diffusion process, we reformulate the inventory control problem as an impulse control problem. W...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koeppe, Matthias
作者单位：Johns Hopkins University; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Davis
摘要：We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality...
-
作者：Bensoussan, Alain; Cadenillas, Abel; Koo, Hyeng Keun
作者单位：University of Texas System; University of Texas Dallas; City University of Hong Kong; University of Alberta; Ajou University
摘要：We propose and solve a general entrepreneurial/managerial decision-making problem. Instead of employing concave objective functions, we use a broad class of nonconcave objective functions. We approach the problem by a martingale method. We show that the optimization problem with a nonconcave objective function has the same solution as the optimization problem when the objective function is replaced by its concave hull, and thus the problems are equivalent to each other. The value function is s...
-
作者：Marechal, Pierre; Ye, Jane J.; Zhou, Julie
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; University of Victoria
摘要：In this paper, we consider the problem of optimal design of experiments. A two-step inference strategy is proposed. The first step consists in minimizing the condition number of the so-called information matrix. This step can be turned into a semidefinite programming problem. The second step is more classical, and it entails the minimization of a convex integral functional under linear constraints. This step is formulated in some infinite-dimensional space and is solved by means of a dual appr...
-
作者：Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
作者单位：Carnegie Mellon University; Princeton University; International Business Machines (IBM); IBM USA; Carnegie Mellon University
摘要：In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the tota...
-
作者：Braun, Gabor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
作者单位：University System of Georgia; Georgia Institute of Technology; Universite Libre de Bruxelles; Cornell University
摘要：We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n(1/2-is an element of))-approximations for CLIQUE require LPs of size 2(n Omega(is an element of)). This lower bound applies to LPs using a certain ...
-
作者：Chen, Xin; Peng, Jiming
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Houston System; University of Houston
摘要：The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In a recent paper [Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1-2): 273-293], Chen, et al. showed that with a high probability close to 1, StQPs with random data have sparse optimal solutions when the associated...
-
作者：Kanzow, Christian; Schwartz, Alexandra
作者单位：University of Wurzburg; Technical University of Darmstadt
摘要：Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, form a difficult class of optimization problems. The feasible set has a very special structure and violates most of the standard constraint qualifications. Therefore, one typically applies specialized algorithms in order to solve MPECs. One prominent class of specialized algorithms is the relaxation (or regularization) methods. The first relaxation method for MPECs is due to Scholtes [35] [Scholtes S (200...
-
作者：Huynh Van Ngai; Thera, Michel
作者单位：Universite de Limoges; Federation University Australia
摘要：In this paper, we study relative metric regularity of set-valued mappings with emphasis on directional metric regularity. We establish characterizations of relative metric regularity without assuming the completeness of the image spaces, by using the relative lower semicontinuous envelopes of the distance functions to set-valued mappings. We then apply these characterizations to establish a coderivative type criterion for directional metric regularity as well as for the robustness of metric re...
