-
作者：Hunkenschroder, Christoph; Reuland, Gina; Schymura, Matthias
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal o...
-
作者：Pohl, Mathias; Ristig, Alexander; Schachermayer, Walter; Tangpi, Ludovic
作者单位：University of Vienna; University of Vienna; Princeton University
摘要：Understanding the structure of financial markets deals with suitably determining the functional relation between financial variables. In this respect, important variables are the trading activity, defined here as the number of tradesN, the traded volumeV, the asset priceP, the squared volatility sigma 2 the bid-ask spreadSand the cost of tradingC. Different reasonings result in simple proportionality relations (scaling laws) between these variables. A basic proportionality is established betwe...
-
作者：Baiou, Mourad; Barahona, Francisco
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Clermont Auvergne (UCA); International Business Machines (IBM); IBM USA
摘要：The maximum number of edge-disjoint spanning trees in a network has been used as a measure of the strength of a network. It gives the number of disjoint ways that the network can be fully connected. This suggests a game theoretic analysis that shows the relative importance of the different links to form a strong network. We introduce the Network strength game as a cooperative game defined on a graph G=(V,E). The player set is the edge-set E and the value of a coalition S subset of Eis the maxi...
-
作者：Lodi, Andrea; Nagarajan, Viswanath
-
作者：Permenter, Frank; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone-namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also s...
-
作者：Andreani, Roberto; Haeser, Gabriel; Viana, Daiana S.
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidade Federal do Acre (UFAC)
摘要：Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker (AKKT), well known in nonlinear optimization. The second one, called...
-
作者：Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff
作者单位：Texas Tech University System; Texas Tech University; University of Bremen; University of Cologne; Columbia University
摘要：We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least 1+epsilon times its processing time, for some epsilon>0. We quantify the impact that different prov...
-
作者：Qian, Xun; Liao, Li-Zhi; Sun, Jie
作者单位：Hong Kong Baptist University; Curtin University; National University of Singapore
摘要：The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult to prove its convergence. It often requires additional restrictive conditions such as nondegeneracy, specific initial solutions, and/or small step length to guarantee its global convergence. This situation is made worse when it comes to applying the affine scaling idea to the s...
-
作者：Attouch, Hedy; Cabot, Alexandre
作者单位：Universite de Montpellier; Universite Bourgogne Europe; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：In a Hilbert spaceHgivenA:H -> 2Ha maximally monotone operator, we study the convergence properties of a general class of relaxed inertial proximal algorithms. This study aims to extend to the case of the general monotone inclusionAxCONTAINS AS MEMBER0the acceleration techniques initially introduced by Nesterov in the case of convex minimization. The relaxed form of the proximal algorithms plays a central role. It comes naturally with the regularization of the operatorAby its Yosida approximat...
-
作者：Fernandez, Damian; Solodov, Mikhail
作者单位：Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of Cordoba; National University of Cordoba
摘要：At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two...
