1-2期

最新文章

• Multiplicative updates for symmetric-cone factorizations AI翻译
  作者：Soh, Yong Sheng; Varvitsiotis, Antonios
  作者单位：National University of Singapore; Agency for Science Technology & Research (A*STAR); Agency for Science Technology & Research (A*STAR); A*STAR - Institute of High Performance Computing (IHPC); Singapore University of Technology & Design
  摘要：Given a matrix X is an element of R-mxn (+) with non-negative entries, the cone factorization problem concerns computing {a(1),..., a(m)}subset of Kappa belonging to a convex cone K subset of R-k, and {b(1),..., b(n)}subset of K-* belonging to its dual so that X-i j = < a(i), b(j) > for all i is an element of [m], j is an element of [n]. Cone factorizations are fundamental to mathematical optimization as they allow us to express convex bodies as feasible regions of linear conic programs. In th...
• On the minimum s - t cut problem with budget constraints AI翻译
  作者：Aissi, Hassene; Mahjoub, A. Ridha
  作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Universite Paris-Dauphine; Kuwait University
  摘要：We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = (V, A) with two distinguished nodes s and t, k non-negative cost functions c(1),..., c(k) : A -> Z(+), and k - 1 budget bounds b(1),..., bk(-1). The goal is to find a s - t cut C satisfying the budget constraints c(h)(C) <= b(h), for h = 1,..., k-1, and whose cost c(k) (C) is minimum. In this paper we discuss the linear relaxation of the problem and introduce a strict partial orderi...
• Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization AI翻译
  作者：Bin, Michelangelo; Notarnicola, Ivano; Parisini, Thomas
  作者单位：University of Bologna; Imperial College London; University of Cyprus; University of Trieste
  摘要：We consider the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm, also known as the first-order Lagrangian method, for constrained optimization problems involving a smooth strongly convex cost and smooth convex constraints. We prove that, for every given compact set of initial conditions, there always exists a sufficiently small stepsize guaranteeing exponential stability of the optimal primal-dual solution of the problem with a domain of attraction including the initialization set. Ins...
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k AI翻译
  作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We consider the problem of deterministically enumerating all minimum k-cut-sets in a given hypergraph for fixed constant k. The input here is a hypergraph G = (V, E) with non-negative hyperedge costs. A subset F subset of E of hyperedges is a k-cut-set if the number of connected components in G - F is at least k and it is a minimum k-cut-set if it has the least cost among all k-cut-sets. For fixed k, we call the problem of finding a minimum k-cut-set as Hypergraph- k- Cut and the problem of en...
• Graph isomorphism: physical resources, optimization models, and algebraic characterizations AI翻译
  作者：Mancinska, Laura; Roberson, David E.; Varvitsiotis, Antonios
  作者单位：University of Copenhagen; Technical University of Denmark; Singapore University of Technology & Design
  摘要：In the (G, H)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either G or H. The goal of the players is to convince the verifier that the graphs G and H are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser B 136:89-328, 2019) we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In t...
• Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization AI翻译
  作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Phat, Vo Thanh; Tran, Dat Ba
  作者单位：Wayne State University
  摘要：This paper proposes and justifies two globally convergent Newton-type methods to solve unconstrained and constrained problems of nonsmooth optimization by using tools of variational analysis and generalized differentiation. Both methods are coderivative-based and employ generalized Hessians (coderivatives of subgradient mappings) associated with objective functions, which are either of class C1,1, or are represented in the form of convex composite optimization, where one of the terms may be ex...
• Graph coloring and semidefinite rank AI翻译
  作者：Mirka, Renee; Smedira, Devin; Williamson, David P.
  作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
  摘要：This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger et al. (J ACM 45(2):246-265, 1998) give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optima...
• Deciding whether a lattice has an orthonormal basis is in co-NP AI翻译
  作者：Hunkenschroeder, Christoph
  作者单位：Technical University of Berlin
  摘要：We show that the problem of deciding whether a given Euclidean lattice L has an orthonormal basis is in NP and co-NP. Since this is equivalent to saying that L is isomorphic to the standard integer lattice, this problem is a special form of the lattice isomorphism problem, which is known to be in the complexity class SZK. We achieve this by deploying a result on characteristic vectors by Elkies that gained attention in the context of 4-manifolds and Seiberg-Witten equations, but seems rather u...
• No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians AI翻译
  作者：Tian, Lai; So, Anthony Man-Cho
  作者单位：Chinese University of Hong Kong
  摘要：We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the ...
• Residuals-based distributionally robust optimization with covariate information AI翻译
  作者：Kannan, Rohit; Bayraksan, Guezin; Luedtke, James R.
  作者单位：Virginia Polytechnic Institute & State University; University System of Ohio; Ohio State University; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained using Wasserstein, sample robust optimization, and phi-divergence-based ambiguity sets within ...