-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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 ...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
