1-2期

最新文章

• Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint AI翻译
  作者：Adachi, Satoru; Nakatsukasa, Yuji
  作者单位：University of Tokyo; University of Oxford
  摘要：A nonconvex quadratically constrained quadratic programming (QCQP) with one constraint is usually solved via a dual SDP problem, or More's algorithm based on iteratively solving linear systems. In this work we introduce an algorithm for QCQP that requires finding just one eigenpair of a generalized eigenvalue problem, and involves no outer iterations other than the (usually black-box) iterations for computing the eigenpair. Numerical experiments illustrate the efficiency and accuracy of our al...
• Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces AI翻译
  作者：Bravo, Mario; Cominetti, Roberto; Pavez-Signe, Matias
  作者单位：Universidad de Santiago de Chile; Universidad Adolfo Ibanez; Universidad de Chile
  摘要：We study the convergence of an inexact version of the classical Krasnosel'skii-Mann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. The results are applied to three variants of the basic iteration: infeasible iterations with approximate projections, the Ishikawa iteration, and diagonal Krasnosel...
• On representing the positive semidefinite cone using the second-order cone AI翻译
  作者：Fawzi, Hamza
  作者单位：University of Cambridge
  摘要：The second-order cone plays an important role in convex optimization and has strong expressive abilities despite its apparent simplicity. Second-order cone formulations can also be solved more efficiently than semidefinite programming problems in general. We consider the following question, posed by Lewis and Glineur, Parrilo, Saunderson: is it possible to express the general positive semidefinite cone using second-order cones? We provide a negative answer to this question and show that the 3x...
• Distributed nonconvex constrained optimization over time-varying digraphs AI翻译
  作者：Scutari, Gesualdo; Sun, Ying
  作者单位：Purdue University System; Purdue University
  摘要：This paper considers nonconvex distributed constrained optimization over networks, modeled as directed (possibly time-varying) graphs. We introduce the first algorithmic framework for the minimization of the sum of a smooth nonconvex (nonseparable) functionthe agent's sum-utilityplus a difference-of-convex function (with nonsmooth convex part). This general formulation arises in many applications, from statistical machine learning to engineering. The proposed distributed method combines succes...
• Eventual convexity of probability constraints with elliptical distributions AI翻译
  作者：van Ackooij, Wim; Malick, Jerome
  作者单位：Electricite de France (EDF); Centre National de la Recherche Scientifique (CNRS)
  摘要：Probability constraints are often employed to intuitively define safety of given decisions in optimization problems. They simply express that a given system of inequalities depending on a decision vector and a random vector is satisfied with high enough probability. It is known that, even if this system is convex in the decision vector, the associated probability constraint is not convex in general. In this paper, we show that some degree of convexity is still preserved, for the large class of...
• An extension of Chubanov's algorithm to symmetric cones AI翻译
  作者：Lourenco, Bruno F.; Kitahara, Tomonari; Muramatsu, Masakazu; Tsuchiya, Takashi
  作者单位：Seikei University; Institute of Science Tokyo; Tokyo Institute of Technology; University of Electro-Communications - Japan; National Graduate Institute for Policy Studies
  摘要：In this work we present an extension of Chubanov's algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov's method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an earlier work by Kitahara and Tsuchiya on second order cone feasibility problems, progress is measured through the volumes of those intersections: when they become ...
• Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach AI翻译
  作者：Fang, Ethan X.; Liu, Han; Wang, Mengdi
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Princeton University
  摘要：We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the 0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this blessing of massive scale phenomenon. Motivated by this result, we propose an efficient algorithm to solve the dual problem (which is concave) and prove that the solution achieves optima...
• A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems AI翻译
  作者：Boland, Natashia; Christiansen, Jeffrey; Dandurand, Brian; Eberhard, Andrew; Oliveira, Fabricio
  作者单位：University System of Georgia; Georgia Institute of Technology; Royal Melbourne Institute of Technology (RMIT); Aalto University
  摘要：We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. We adapt the augmented Lagrangian method framework to address the presence of nonconve...
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications AI翻译
  作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
  作者单位：Princeton University; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore; National University of Singapore
  摘要：For a symmetric positive semidefinite linear system of equations Qx=b, where x=(x1,...,xs) is partitioned into s blocks, with s2, we show that each cycle of the classical block symmetric Gauss-Seidel (sGS) method exactly solves the associated quadratic programming (QP) problem but added with an extra proximal term of the form, where T is a symmetric positive semidefinite matrix related to the sGS decomposition of Q and xk is the previous iterate. By leveraging on such a connection to optimizat...
• Level-set methods for convex optimization AI翻译
  作者：Aravkin, Aleksandr Y.; Burke, James V.; Drusvyatskiy, Dmitry; Friedlander, Michael P.; Roy, Scott
  作者单位：University of Washington; University of Washington Seattle; University of Washington; University of Washington Seattle; University of British Columbia
  摘要：Convex optimization problems arising in applications often have favorable objective functions and complicated constraints, thereby precluding first-order methods from being immediately applicable. We describe an approach that exchanges the roles of the objective with one of the constraint functions, and instead approximately solves a sequence of parametric level-set problems. Two Newton-like zero-finding procedures for nonsmooth convex functions, based on inexact evaluations and sensitivity in...