-
作者：Zeng, Liaoyuan; Zhang, Yongle; Li, Guoyin; Pong, Ting Kei; Wang, Xiaozhou
作者单位：Zhejiang University of Technology; Sichuan Normal University; University of New South Wales Sydney; Hong Kong Polytechnic University
摘要：The Frank-Wolfe (FW) method, which implements efficient linear oracles that minimize linear approximations of the objective function over a fixed compact convex set, has recently received much attention in the optimization and machine learning literature. In this paper, we propose a new FW-type method for minimizing a smooth function over a compact set defined as the level set of a single difference-of-convex function, based on new generalized linear-optimization oracles (LO). We show that the...
-
作者：Qi, Yunwei; Sen, Suvrajeet
作者单位：University System of Ohio; Ohio State University; University of Southern California
-
作者：Korda, Milan; Laurent, Monique; Magron, Victor; Steenkamp, Andries
作者单位：Centre National de la Recherche Scientifique (CNRS); Czech Technical University Prague; Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：We explore a new type of sparsity for the generalized moment problem (GMP) that we call ideal-sparsity. In this setting, one optimizes over a measure restricted to be supported on the variety of an ideal generated by quadratic bilinear monomials. We show that this restriction enables an equivalent sparse reformulation of the GMP, where the single (high dimensional) measure variable is replaced by several (lower dimensional) measure variables supported on the maximal cliques of the graph corres...
-
作者：Bertsimas, Dimitris; ten Eikelder, Stefan C. M.; den Hertog, Dick; Trichakis, Nikolaos
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Tilburg University; University of Amsterdam
摘要：We formalize the concept of Pareto Adaptive Robust Optimality (PARO) for linear two-stage Adaptive Robust Optimization (ARO) problems, with fixed continuous recourse. A worst-case optimal solution pair of here-and-now decisions and wait-and-see decisions is PARO if it cannot be Pareto dominated by another solution, i.e., there does not exist another worst-case optimal pair that performs at least as good in all scenarios in the uncertainty set and strictly better in at least one scenario. We ar...
-
作者：Bolte, Jerome; Miclo, Laurent; Villeneuve, Stephane
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Using jointly geometric and stochastic reformulations of nonconvex problems and exploiting a Monge-Kantorovich (or Wasserstein) gradient system formulation with vanishing forces, we formally extend the simulated annealing method to a wide range of global optimization methods. Due to the built-in combination of a gradient-like strategy and particle interactions, we call them swarm gradient dynamics. As in the original paper by Holley-Kusuoka-Stroock, a functional inequality is the key to the ex...
-
作者：Brosch, Daniel; Polak, Sven C.
作者单位：University of Klagenfurt; Tilburg University
摘要：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,K-n, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624]. We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of th...
-
作者：Iwamasa, Yuni
作者单位：Kyoto University
摘要：In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = ( Aa ss xa ss t(da ss)), where A(a ss) is a 2x2 matrix over a field F, x(a ss) is an indeterminate, and d(a ss) is an integer for a = 1, 2,..., mu and ss = 1, 2,...,., and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching probl...
-
作者：Del Pia, Alberto; Linderoth, Jeff; Zhu, Haoran
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1, k)-configuration inequalities, and weight inequalities are all NP-complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can ...
-
作者：Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin
作者单位：Technical University of Berlin; University of Warwick; University of Virginia; Uppsala University; Technische Universitat Wien
摘要：In the late 19th century, Swedish mathematician Edvard Phragmen proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants-one minimizing the maximum load and one minimizing the variance of loads-and a sequential variant. We study Phragmen 's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential...
-
作者：Brill, Markus; Golz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai
作者单位：Technical University of Berlin; Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：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 ...
