1-2期

最新文章

• Characterizations of mixed binary convex quadratic representable sets AI翻译
  作者：Del Pia, Alberto; Poskin, Jeffrey
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this paper we study the sets that appear in the feasibility version of mixed binary convex quadratic optimization problems. We provide a complete characterization of the sets that can be obtained as the projection of such feasible regions. In order to obtain this result, we first provide a complete characterization of these sets in...
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems AI翻译
  作者：Razaviyayn, Meisam; Hong, Mingyi; Reyhanian, Navid; Luo, Zhi-Quan
  作者单位：University of Southern California; University of Minnesota System; University of Minnesota Twin Cities; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen
  摘要：Consider the classical problem of solving a general linear system of equations Ax=b. It is well known that the (successively over relaxed) Gauss-Seidel scheme and many of its variants may not converge when A is neither diagonally dominant nor symmetric positive definite. Can we have a linearly convergent G-S type algorithm that works for anyA? In this paper we answer this question affirmatively by proposing a doubly stochastic G-S algorithm that is provably linearly convergent (in the mean squ...
• Conditional gradient type methods for composite nonlinear and stochastic optimization AI翻译
  作者：Ghadimi, Saeed
  作者单位：Princeton University
  摘要：In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient method improves its rate of convergence, it does not cost per iteration as much as general proximal type algorithms. More specifically, we present a unified analysis for t...
• Identifying effective scenarios in distributionally robust stochastic programs with total variation distance AI翻译
  作者：Rahimian, Hamed; Bayraksan, Guzin; Homem-de-Mello, Tito
  作者单位：University System of Ohio; Ohio State University; Universidad Adolfo Ibanez
  摘要：Traditional stochastic programs assume that the probability distribution of uncertainty is known. However, in practice, the probability distribution oftentimes is not known or cannot be accurately approximated. One way to address such distributional ambiguity is to work with distributionally robust convex stochastic programs (DRSPs), which minimize the worst-case expected cost with respect to a set of probability distributions. In this paper we analyze the case where there is a finite number o...
• Computation of the maximum likelihood estimator in low-rank factor analysis AI翻译
  作者：Khamaru, Koulik; Mazumder, Rahul
  作者单位：University of California System; University of California Berkeley; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：Factor analysis is a classical multivariate dimensionality reduction technique popularly used in statistics, econometrics and data science. Estimation for factor analysis is often carried out via the maximum likelihood principle, which seeks to maximize the Gaussian likelihood under the assumption that the positive definite covariance matrix can be decomposed as the sum of a low-rank positive semidefinite matrix and a diagonal matrix with nonnegative entries. This leads to a challenging rank c...
• Convexification of generalized network flow problem AI翻译
  作者：Sojoudi, Somayeh; Fattahi, Salar; Lavaei, Javad
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley
  摘要：This paper is concerned with the minimum-cost flow problem over an arbitrary flow network. In this problem, each node is associated with some possibly unknown injection and each line has two unknown flows at its ends that are related to each other via a nonlinear function. Moreover, all injections and flows must satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicit...
• Optimization problems involving group sparsity terms AI翻译
  作者：Beck, Amir; Hallak, Nadav
  作者单位：Tel Aviv University; Technion Israel Institute of Technology
  摘要：This paper studies a general form problem in which a lower bounded continuously differentiable function is minimized over a block separable set incorporating a group sparsity expression as a constraint or a penalty (or both) in the group sparsity setting. This class of problems is generally hard to solve, yet highly applicable in numerous practical settings. Particularly, we study the proximal mapping that includes group-sparsity terms, and derive an efficient method to compute it. Necessary o...
• First-order methods almost always avoid strict saddle points AI翻译
  作者：Lee, Jason D.; Panageas, Ioannis; Piliouras, Georgios; Simchowitz, Max; Jordan, Michael I.; Recht, Benjamin
  作者单位：University of Southern California; Singapore University of Technology & Design; University of California System; University of California Berkeley
  摘要：We establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-orde...
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems AI翻译
  作者：Liu, Tianxiang; Pong, Ting Kei; Takeda, Akiko
  作者单位：Hong Kong Polytechnic University; University of Tokyo; RIKEN
  摘要：We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises naturally in various applications when different regularizers are introduced for inducing simultaneous structures in the solutions. Solving these problems, however, can be challe...
• Ambiguous risk constraints with moment and unimodality information AI翻译
  作者：Li, Bowen; Jiang, Ruiwei; Mathieu, Johanna L.
  作者单位：University of Michigan System; University of Michigan; University of Michigan System; University of Michigan
  摘要：Optimization problems face random constraint violations when uncertainty arises in constraint parameters. Effective ways of controlling such violations include risk constraints, e.g., chance constraints and conditional Value-at-Risk constraints. This paper studies these two types of risk constraints when the probability distribution of the uncertain parameters is ambiguous. In particular, we assume that the distributional information consists of the first two moments of the uncertainty and a g...