-
作者：Hojny, Christopher; Pfetsch, Marc E.
作者单位：Technical University of Darmstadt
摘要：This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with ternary coefficients, based on knapsack polytopes arising from a single lexicographic order enforcing inequality. We show that ...
-
作者：Chen, Caihua; Li, Min; Liu, Xin; Ye, Yinyu
作者单位：Nanjing University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Stanford University
摘要：In this paper, we establish the convergence of the proximal alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) method for nonseparable minimization models with quadratic coupling terms. The novel convergence results presented in this paper answer several open questions that have been the subject of considerable discussion. We firstly extend the 2-block proximal ADMM to linearly constrained convex optimization with a coupled quadratic objective function, an ar...
-
作者：Cui, Ying; Sun, Defeng; Toh, Kim-Chuan
作者单位：University of Southern California; Hong Kong Polytechnic University; National University of Singapore
摘要：Due to the possible lack of primal-dual-type error bounds, it was not clear whether the Karush-Kuhn-Tucker (KKT) residuals of the sequence generated by the augmented Lagrangian method (ALM) for solving convex composite conic programming (CCCP) problems converge superlinearly. In this paper, we resolve this issue by establishing the R-superlinear convergence of the KKT residuals generated by the ALM under only a mild quadratic growth condition on the dual of CCCP, with easy-to-implement stoppin...
-
作者：Guo, Shaoyan; Xu, Huifu
作者单位：Dalian University of Technology; University of Southampton
摘要：Utility-based shortfall risk measures (SR) have received increasing attention over the past few years for their potential to quantify the risk of large tail losses more effectively than conditional value at risk. In this paper, we consider a distributionally robust version of the shortfall risk measure (DRSR) where the true probability distribution is unknown and the worst distribution from an ambiguity set of distributions is used to calculate the SR. We start by showing that the DRSR is a co...
-
作者：Bellavia, Stefania; Gondzio, Jacek; Porcelli, Margherita
作者单位：University of Florence; University of Edinburgh; Research & Academic Computer Network (NASK)
摘要：A dual logarithmic barrier method for solving large, sparse semidefinite programs is proposed in this paper. The method avoids any explicit use of the primal variable X and therefore is well-suited to problems with a sparse dual matrix S. It relies on inexact Newton steps in dual space which are computed by the conjugate gradient method applied to the Schur complement of the reduced KKT system. The method may take advantage of low-rank representations of matrices Ai to perform implicit matrix-...
-
作者：Chen, Xiaojun; Sun, Hailin; Xu, Huifu
作者单位：Hong Kong Polytechnic University; Nanjing University of Science & Technology; University of Southampton
摘要：In this paper, we propose a discretization scheme for the two-stage stochastic linear complementarity problem (LCP) where the underlying random data are continuously distributed. Under some moderate conditions, we derive qualitative and quantitative convergence for the solutions obtained from solving the discretized two-stage stochastic LCP (SLCP). We explain how the discretized two-stage SLCP may be solved by the well-known progressive hedging method (PHM). Moreover, we extend the discussion ...
-
作者：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...
