Search

In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1–17, 1964), it is well known that such a scheme is very efficient for C 2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional regularity such as quasi-strong convexity, or strong convexity, were recently obtained in Aujol et al. (Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization, 2020). Convergence results with much weaker assumptions are given in the present paper: namely, linear convergence rates when assuming a growth condition (which amounts to a Łojasiewicz property in the convex case). This analysis is firstly performed in continuous time for the ODE, and then transposed for discrete optimization schemes. In particular, a variant of the Heavy Ball algorithm is proposed, which converges geometrically whatever the parameters choice, and which has the best state of the art convergence rate for first order methods to minimize composite non smooth convex functions satisfying a Łojasiewicz property. [ABSTRACT FROM AUTHOR]

Birkhoff's representation theorem (Birkhoff, Duke Math J 3(3):443–454, 1937) defines a bijection between elements of a distributive lattice and the family of upper sets of an associated poset. Although not used explicitly, this result is at the backbone of the combinatorial algorithm by Irving et al. (J ACM 34(3):532-543, 1987) for maximizing a linear function over the set of stable matchings in Gale and Shapley's stable marriage model (Gale and Shapley, Am Math Monthly 69(1):9–15 1962). In this paper, we introduce a property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of the lattice elements. We apply this concept to the stable matching model with path-independent quota-filling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all those for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond classical extensions of the Deferred Acceptance algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph K m , n , extending a method from de Klerk et al. (SIAM J Discrete Math 20:189–202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613–624, 2007). We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that cr (K 10 , n) ≥ 4.87057 n 2 - 10 n , cr (K 11 , n) ≥ 5.99939 n 2 - 12.5 n , cr (K 12 , n) ≥ 7.25579 n 2 - 15 n , cr (K 13 , n) ≥ 8.65675 n 2 - 18 n for all n. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A α β x α β) , where A α β is a 2 × 2 matrix over a field F and x α β is an indeterminate for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν . This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial O ((μ ν) 2 min { μ , ν }) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ × 2 ν . Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field F . [ABSTRACT FROM AUTHOR]

In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes (Nemirovski in Math Oper Res 35(1):52–78, 2010). [ABSTRACT FROM AUTHOR]

We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: "how closely can we approximate the set of unit-trace n × n PSD matrices, denoted by D, using at most N number of k × k PSD constraints?" In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace n × n symmetric matrices that are PSD when restricted to a fixed set of k-dimensional subspaces in R n . We prove that if this set is a good approximation of D, then the number of subspaces must be at least exponentially large in n for any k = o (n) . Second, we show that any set S that approximates D within a constant approximation ratio must have superpolynomial S + k -extension complexity. To be more precise, if S is a constant factor approximation of D, then S must have S + k -extension complexity at least exp (C · min { n , n / k }) where C is some absolute constant. In addition, we show that any set S such that D ⊆ S and the Gaussian width of S is at most a constant times larger than the Gaussian width of D must have S + k -extension complexity at least exp (C · min { n 1 / 3 , n / k }) . These results imply that the cone of n × n PSD matrices cannot be approximated by a polynomial number of k × k PSD constraints for any k = o (n / log 2 n) . These results generalize the recent work of Fawzi (Math Oper Res 46(4):1479–1489, 2021) on the hardness of polyhedral approximations of S + n , which corresponds to the special case with k = 1 . [ABSTRACT FROM AUTHOR]

Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to address this issue, Burer and Monteiro (Math Program 95(2):329–357, 2003) proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subsequent non-convex problem instead. In this paper, we present coordinate ascent based methods to solve this non-convex problem with provable convergence guarantees. More specifically, we prove that the block-coordinate maximization algorithm applied to the non-convex Burer–Monteiro method globally converges to a first-order stationary point with a sublinear rate without any assumptions on the problem. We further show that this algorithm converges linearly around a local maximum provided that the objective function exhibits quadratic decay. We establish that this condition generically holds when the rank of the factorization is sufficiently large. Furthermore, incorporating Lanczos method to the block-coordinate maximization, we propose an algorithm that is guaranteed to return a solution that provides 1 - O 1 / r approximation to the original SDP without any assumptions, where r is the rank of the factorization. This approximation ratio is known to be optimal (up to constants) under the unique games conjecture, and we can explicitly quantify the number of iterations to obtain such a solution. [ABSTRACT FROM AUTHOR]

We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted to the intersection of the positive semidefinite cone and a polyhedral cone representing the algebraic properties of binary and box constraints as well as the sparsity structure of the objective polynomial. Our DNN relaxation serves as a variant of the Lasserre moment-SOS hierarchy of relaxations for binary and box constrained POPs when the size of the cones is gradually increased to compute tighter lower bounds for their optimal values. A significant part of the paper is devoted to deriving and analyzing a class of polyhedral cones to strengthen the DNN relaxation, and the design of efficient computation of the metric projections onto these cones in the accelerated BP algorithm. Numerical results on various POPs are available in Ito et al. (ACM Trans Math Softw 45, Article 34, 2019). [ABSTRACT FROM AUTHOR]

We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so called multi-stage stochastic IPs. A 2-stage stochastic IP is an integer program of the form max { c T x ∣ A x = b , l ≤ x ≤ u , x ∈ Z s + n t } where the constraint matrix A ∈ Z r n × s + n t consists roughly of n repetitions of a matrix A ∈ Z r × s on the vertical line and n repetitions of a matrix B ∈ Z r × t on the diagonal. In this paper we improve upon an algorithmic result by Hemmecke and Schultz from 2003 [Hemmecke and Schultz, Math. Prog. 2003] to solve 2-stage stochastic IPs. The algorithm is based on the Graver augmentation framework where our main contribution is to give an explicit doubly exponential bound on the size of the augmenting steps. The previous bound for the size of the augmenting steps relied on non-constructive finiteness arguments from commutative algebra and therefore only an implicit bound was known that depends on parameters r, s, t and Δ , where Δ is the largest entry of the constraint matrix. Our new improved bound however is obtained by a novel theorem which argues about intersections of paths in a vector space. As a result of our new bound we obtain an algorithm to solve 2-stage stochastic IPs in time f (r , s , Δ) · poly (n , t) , where f is a doubly exponential function. To complement our result, we also prove a doubly exponential lower bound for the size of the augmenting steps. [ABSTRACT FROM AUTHOR]

In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., y a ≈ x a for all arcs a. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17–41, 1999) proved that there exists an unsplittable flow y such that y a ≤ x a + d max for all arcs a, where d max denotes the maximum demand value. Our first contribution is a considerably simpler one-page proof for this classical result, based upon an entirely new approach. Secondly, using a subtle variant of this approach, we obtain a new result: There is an unsplittable flow y such that y a ≥ x a - d max for all arcs a. Finally, building upon an iterative rounding technique previously introduced by Kolliopoulos and Stein (SIAM J Comput 31:919–946, 2002) and Skutella (Math Program 91:493–514, 2002), we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case when demands are integer multiples of each other. For arbitrary demand values, we prove the weaker simultaneous bounds x a / 2 - d max ≤ y a ≤ 2 x a + d max for all arcs a. [ABSTRACT FROM AUTHOR]

Rank regularized minimization problem is an ideal model for the low-rank matrix completion/recovery problem. The matrix factorization approach can transform the high-dimensional rank regularized problem to a low-dimensional factorized column-sparse regularized problem. The latter can greatly facilitate fast computations in applicable algorithms, but needs to overcome the simultaneous non-convexity of the loss and regularization functions. In this paper, we consider the factorized column-sparse regularized model. Firstly, we optimize this model with bound constraints, and establish a certain equivalence between the optimized factorization problem and rank regularized problem. Further, we strengthen the optimality condition for stationary points of the factorization problem and define the notion of strong stationary point. Moreover, we establish the equivalence between the factorization problem and its nonconvex relaxation in the sense of global minimizers and strong stationary points. To solve the factorization problem, we design two types of algorithms and give an adaptive method to reduce their computation. The first algorithm is from the relaxation point of view and its iterates own some properties from global minimizers of the factorization problem after finite iterations. We give some analysis on the convergence of its iterates to a strong stationary point. The second algorithm is designed for directly solving the factorization problem. We improve the PALM algorithm introduced by Bolte et al. (Math Program Ser A 146:459–494, 2014) for the factorization problem and give its improved convergence results. Finally, we conduct numerical experiments to show the promising performance of the proposed model and algorithms for low-rank matrix completion. [ABSTRACT FROM AUTHOR]

In the classic apportionment problem, the goal is to decide how many seats of a parliament should be allocated to each party as a result of an election. The divisor methods solve this problem by defining a notion of proportionality guided by some rounding rule. Motivated by recent challenges in the context of electoral apportionment, we consider the question of how to allocate the seats of a parliament under parity constraints between candidate types (e.g., an equal number of men and women elected) while at the same time satisfying party proportionality. We study two different approaches to solve this question. We first provide a theoretical analysis of a recently devised mechanism based on a greedy approach. We then propose and analyze a mechanism that follows the idea of biproportionality introduced by Balinski and Demange. In contrast with the classic biproportional method by Balinski and Demange, this mechanism is ruled by two levels of proportionality: Proportionality is satisfied at the level of parties by means of a divisor method, and then biproportionality is used to decide the number of candidates allocated to each type and party. A typical benchmark used in the context of two-dimensional apportionment is the fair share (a.k.a matrix scaling), which corresponds to an ideal fractional biproportional solution. We provide lower bounds on the distance between these two types of solutions, and we explore their consequences in the context of two-dimensional apportionment. [ABSTRACT FROM AUTHOR]

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters can support multiple parties by casting approval ballots. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates instead of parties. Using techniques from both apportionment and multiwinner elections, we identify rules that generalize the D'Hondt apportionment method and that satisfy strong axioms which are generalizations of properties commonly studied in the apportionment literature. In fact, the rules we discuss provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity (also known as house monotonicity). [ABSTRACT FROM AUTHOR]

Apportionment methods are used in proportional representation systems for the apportionment of parliamentary seats among political parties proportionately to their vote counts, or for the allocation of parliamentary seats between geographical districts proportionately to their population figures. From an axiomatic viewpoint apportionment methods ought to satisfy six basic principles: anonymity, balancedness, concordance, decency, exactness, and fairness. It is well-known that the first two principles are implied by the last four. In this note it is shown that the last four principles are logically independent of each other. [ABSTRACT FROM AUTHOR]

We propose the maximin support method, a novel extension of the D'Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the voter support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D'Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and alternative D'Hondt extensions due to Phragmén. [ABSTRACT FROM AUTHOR]

Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover? When k = 1 , the problem is equivalent to the existence of a perfect matching for which Tutte's celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a 'good' characterization. We prove here, when k is greater than one, a 'good' characterization à la Kőnig: for k ≥ 2 , there existkmatchings covering every node if and only if for every stable setS, we have | S | ≤ k · | N (S) | . Moreover, somewhat surprisingly, we use only techniques from bipartite matching in the proof, through a simple, polynomial algorithm. A different approach to matching-k-covers has been previously suggested by Wang et al. (Math. Prog., 2014), relying on general matching and using matroid union for matching-matroids, or the Edmonds-Gallai structure theorem. Our approach provides a simpler polynomial algorithm together with an elegant certificate of non-existence when appropriate. Further results, generalizations and interconnections between several problems are then deduced as consequences of the new minimax theorem, with surprisingly simple proofs (again using only the level of difficulty of bipartite matchings). One of the equivalent formulations leads to a solution of weighted minimization for non-negative edge-weights, while the edge-cardinality maximization of matching-2-covers turns out to be already NP-hard. We have arrived at this problem as the line graph special case of a model arising for manufacturing integrated circuits with the technology called 'Directed Self Assembly'. [ABSTRACT FROM AUTHOR]

Several different arguments support the use of Webster's method when seats in a parliament are to be apportioned proportionally according to populations. This note—instigated by a new property—summarizes the reasons. [ABSTRACT FROM AUTHOR]

Proximal operations are among the most common primitives appearing in both practical and theoretical (or high-level) optimization methods. This basic operation typically consists in solving an intermediary (hopefully simpler) optimization problem. In this work, we survey notions of inaccuracies that can be used when solving those intermediary optimization problems. Then, we show that worst-case guarantees for algorithms relying on such inexact proximal operations can be systematically obtained through a generic procedure based on semidefinite programming. This methodology is primarily based on the approach introduced by Drori and Teboulle (Math Program 145(1–2):451–482, 2014) and on convex interpolation results, and allows producing non-improvable worst-case analyses. In other words, for a given algorithm, the methodology generates both worst-case certificates (i.e., proofs) and problem instances on which they are achieved. Relying on this methodology, we study numerical worst-case performances of a few basic methods relying on inexact proximal operations including accelerated variants, and design a variant with optimized worst-case behavior. We further illustrate how to extend the approach to support strongly convex objectives by studying a simple relatively inexact proximal minimization method. [ABSTRACT FROM AUTHOR]

For a binary integer program (IP) max c T x , A x ≤ b , x ∈ { 0 , 1 } n , where A ∈ R m × n and c ∈ R n have independent Gaussian entries and the right-hand side b ∈ R m satisfies that its negative coordinates have ℓ 2 norm at most n/10, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by poly (m) (log n) 2 / n with probability at least 1 - 2 / n 7 - 2 - poly (m) . Our results give a Gaussian analogue of the classical integrality gap result of Dyer and Frieze (Math OR, 1989) in the case of random packing IPs. In constrast to the packing case, our integrality gap depends only polynomially on m instead of exponentially. Building upon recent breakthrough work of Dey, Dubey and Molinaro (SODA, 2021), we show that the integrality gap implies that branch-and-bound requires n poly (m) time on random Gaussian IPs with good probability, which is polynomial when the number of constraints m is fixed. We derive this result via a novel meta-theorem, which relates the size of branch-and-bound trees and the integrality gap for random logconcave IPs. [ABSTRACT FROM AUTHOR]

We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying that first and higher order terms of the integrand's ANOVA decomposition (Math. Comp. 79 (2010), 953–966) have mixed weak first order partial derivatives. This leads to a good smooth approximation of the integrand and, hence, to good convergence rates of randomized QMC methods if the effective (superposition) dimension is low. [ABSTRACT FROM AUTHOR]