-
作者：Jiang, Ruiwei; Guan, Yongpei
作者单位：University of Arizona; State University System of Florida; University of Florida
摘要：In this paper, we study data-driven chance constrained stochastic programs, or more specifically, stochastic programs with distributionally robust chance constraints (DCCs) in a data-driven setting to provide robust solutions for the classical chance constrained stochastic program facing ambiguous probability distributions of random parameters. We consider a family of density-based confidence sets based on a general -divergence measure, and formulate DCC from the perspective of robust feasibil...
-
作者：Abdi, Ahmad; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：We study a substructure appearing in mixed-integer programming reformulations of chance-constrained programs with stochastic right-hand-sides over a finite discrete distribution, which we call the mixing set with a knapsack constraint. Recently, Luedtke et al. (Math. Program. 122(2):247-272, 2010) and KuA A1/4kyavuz (Math Program 132(1):31-56, 2012) studied valid inequalities for such sets. However, most of their results were focused on the equal probabilities case (when the knapsack constrain...
-
作者：Juditsky, Anatoli; Nemirovski, Arkadi
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：The standard algorithms for solving large-scale convex-concave saddle point problems, or, more generally, variational inequalities with monotone operators, are proximal type algorithms which at every iteration need to compute a prox-mapping, that is, to minimize over problem's domain X the sum of a linear form and the specific convex distance-generating function underlying the algorithms in question. (Relative) computational simplicity of prox-mappings, which is the standard requirement when i...
-
作者：Stich, S. U.; Mueller, C. L.; Gaertner, B.
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Universite Catholique Louvain; Simons Foundation
摘要：We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel vari...
-
作者：Chen, Caihua; Liu, Yong-Jin; Sun, Defeng; Toh, Kim-Chuan
作者单位：Nanjing University; Shenyang Aerospace University; National University of Singapore; National University of Singapore
摘要：We consider a class of matrix spectral norm approximation problems for finding an affine combination of given matrices having the minimal spectral norm subject to some prescribed linear equality and inequality constraints. These problems arise often in numerical algebra, engineering and other areas, such as finding Chebyshev polynomials of matrices and fastest mixing Markov chain models. Based on classical analysis of proximal point algorithms (PPAs) and recent developments on semismooth analy...
-
作者：Braun, Gabor; Fiorini, Samuel; Pokutta, Sebastian
作者单位：University System of Georgia; Georgia Institute of Technology; Universite Libre de Bruxelles
摘要：We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via linear programs (LPs), in two distinct models. In the uniform model, the constraints of the LP are not allowed to depend on the input graph, which should be encoded solely in the objective function. There we prove a lower bound with probability at least for every LP that is exact for a randomly selected set of instances; each graph on at most n vertices being selected independe...
-
作者：Moffat, Sarah M.; Moursi, Walaa M.; Wang, Xianfu
作者单位：University of British Columbia; University of British Columbia Okanagan; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：Nearly convex sets play important roles in convex analysis, optimization and theory of monotone operators. We give a systematic study of nearly convex sets, and construct examples of subdifferentials of lower semicontinuous convex functions whose domains or ranges are nonconvex.
-
作者：Cheriyan, Joseph; Gao, Zhihan; Georgiou, Konstantinos; Singla, Sahil
作者单位：University of Waterloo; Carnegie Mellon University
摘要：We study the Asymmetric Traveling Salesman Problem (ATSP), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result pertains to the standard linear programming (LP) relaxation of ATSP, due to Dantzig, Fulkerson, and Johnson. For any fixed integer and small , , there exists a digraph G on vertices such that the integrality ratio for level t of the SA system starting with the standard LP on G is . Thus, in terms of the input size, t...
-
作者：Iiduka, Hideaki
作者单位：Meiji University
摘要：This paper considers a networked system with a finite number of users and supposes that each user tries to minimize its own private objective function over its own private constraint set. It is assumed that each user's constraint set can be expressed as a fixed point set of a certain quasi-nonexpansive mapping. This enables us to consider the case in which the projection onto the constraint set cannot be computed efficiently. This paper proposes two methods for solving the problem of minimizin...
-
作者：Kim, Donghwan; Fessler, Jeffrey A.
作者单位：University of Michigan System; University of Michigan
摘要：We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi: 10.1007/s10107-013-0653-010.1007/s10107-013-0653-0 TargetType=) recently described a numerical method for computing the N-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods (Polyak in USSR Comput Math Math Phys 4(5):1-17, 1964. doi: 10.1016/0041-5553(64)90137-510.1016/0...
