1-2期

最新文章

• Approximating the little Grothendieck problem over the orthogonal and unitary groups AI翻译
  作者：Bandeira, Afonso S.; Kennedy, Christopher; Singer, Amit
  作者单位：Massachusetts Institute of Technology (MIT); University of Texas System; University of Texas Austin; Princeton University; Princeton University
  摘要：The little Grothendieck problem consists of maximizing for a positive semidefinite matrix C, over binary variables . In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given a positive semidefinite matrix, the objective is to maximize restricting to take values in the group of orthogonal matrices , where denotes the (ij)-th block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve...
• Data-driven chance constrained stochastic program AI翻译
  作者：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...
• Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles AI翻译
  作者：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...
• Variable metric random pursuit AI翻译
  作者：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...
• A semismooth Newton-CG based dual PPA for matrix spectral norm approximation problems AI翻译
  作者：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...
• Average case polyhedral complexity of the maximum stable set problem AI翻译
  作者：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...
• Nearly convex sets: fine properties and domains or ranges of subdifferentials of convex functions AI翻译
  作者：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.
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy AI翻译
  作者：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...
• Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings AI翻译
  作者：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...
• Optimized first-order methods for smooth convex minimization AI翻译
  作者：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...