-
作者：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...
-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：Technion Israel Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first o...
-
作者：Chang, Cheng-Shang; Liao, Wanjiun; Lien, Ching-Min
作者单位：National Tsing Hua University; National Taiwan University
摘要：One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this paper, we focus on the fundamental limits of the multichannel re...
-
作者：Saban, Daniela; Sethuraman, Jay
作者单位：Columbia University; Columbia University
摘要：The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, an ordering over the agents is selected uniformly at random; the first agent is then allocated his most-preferred object, the second agent is allocated his most-preferred object among the remaining ones, and so on. The outcome of the mechanism is a bi-stochastic matrix in which entry (i, a) represents the probability that agent i is given ...
