-
作者：Ling, Shuyang
作者单位：New York University; NYU Shanghai
摘要：Group synchronization aims to recover the group elements from their noisy pairwise measurements. It has found many applications in community detection, clock synchronization, and joint alignment problem. This paper focuses on the orthogonal group synchronization which is often used in cryo-EM and computer vision. However, it is generally NP-hard to retrieve the group elements by finding the least squares estimator. In this work, we first study the semidefinite programming (SDP) relaxation of t...
-
作者：Bot, Radu Ioan; Csetnek, Erno Robert; Dang-Khoa Nguyen
作者单位：University of Vienna
摘要：This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Bot and Nguyen (J. Differential Equations 303:369-406, 2021), and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we c...
-
作者：Barbato, Michele; Grappe, Roland; Lacroix, Mathieu; Lancini, Emiliano
作者单位：University of Milan; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Given a graph G = (V, E) and an integer k >= 1, the graph H = (V, F), where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k - 1 elements of F. The convex hull of incidence vectors of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we als...
-
作者：Rockafellar, R. Tyrrell
作者单位：University of Washington; University of Washington Seattle
摘要：Second-order sufficient conditions for local optimality have long been central to designing solution algorithms and justifying claims about their convergence. Here a far-reaching extension of such conditions, called variational sufficiency, is explored in territory beyond just classical nonlinear programming. Variational sufficiency is already known to support multiplier methods that are able, even without convexity, to achieve problem decomposition, but further insight has been needed into ho...
-
作者：Eltved, Anders; Burer, Samuel
作者单位：Technical University of Denmark; University of Iowa
摘要：We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball r <= parallel to x parallel to <= R intersected with a full-dimensional second order cone (SOC) constraint of the form parallel to x - c parallel to <= b(T) x - a. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) relaxations and are separable in polynomial time. We connect our cuts to the literature on the optimal power flow (OPF) problem by demo...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Jiang, Hongyi
作者单位：Johns Hopkins University; University of Padua
摘要：We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash (International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145-160, 2002) to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable ...
-
作者：Combettes, Cyrille W.; Pokutta, Sebastian
作者单位：University System of Georgia; Georgia Institute of Technology; Technical University of Berlin; Zuse Institute Berlin
摘要：The approximate Caratheodory theorem states that given a compact convex set C subset of R-n and p is an element of[2,+infinity[, each point x*is an element of C can be approximated to epsilon-accuracy in the l(p)-norm as the convex combination of O(pD(p)(2)/epsilon(2)) vertices of C, where D-p is the diameter of C in the l(p)-norm. A solution satisfying these properties can be built using probabilistic arguments or by applying mirror descent to the dual problem. We revisit the approximate Cara...
-
作者：Tsuchiya, Takashi; Lourenco, Bruno F.; Muramatsu, Masakazu; Okuno, Takayuki
作者单位：National Graduate Institute for Policy Studies; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Electro-Communications - Japan; Seikei University
摘要：We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as t...
-
作者：Hu, Hao; Sotirov, Renata; Wolkowicz, Henry
作者单位：Clemson University; Tilburg University; University of Waterloo
摘要：We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN, relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN rel...
-
作者：Dzahini, Kwassi Joseph; Kokkolaras, Michael; Le Digabel, Sebastien
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; McGill University
摘要：This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose distribution is unknown. As in MADS, constraint violations are aggregated into a single constraint v...
