-
作者：Skajaa, Anders; Ye, Yinyu
作者单位：Technical University of Denmark; Stanford University; Nanjing University
摘要：A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal-dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is need...
-
作者：Saunderson, James; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We give explicit polynomial-sized (in n and k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree k in n variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in k, m, and n) of the hyperbolicity con...
-
作者：Cominetti, Roberto
作者单位：Universidad de Chile
摘要：We provide a brief introduction to the basic models used to describe traffic on congested networks, both in urban transport and telecommunications. We discuss traffic equilibrium models, covering atomic and non-atomic routing games, with emphasis on situations where the travel times are subject to random fluctuations. We use convex optimization to present the models in a unified framework that stresses the common underlying structures. As a prototypical example of traffic equilibrium with elas...
-
作者：Bock, Adrian; Chandrasekaran, Karthekeyan; Koenemann, Jochen; Peis, Britta; Sanita, Laura
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Illinois System; University of Illinois Urbana-Champaign; University of Waterloo; RWTH Aachen University
摘要：An undirected graph is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges a stabilizer if its removal from yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph , can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111-130, 197...
-
作者：Conforti, Michele; Del Pia, Alberto; Di Summa, Marco; Faenza, Yuri
作者单位：University of Padua; University of Wisconsin System; University of Wisconsin Madison; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：The reverse split rank of an integral polyhedron is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is . Already in there exist polyhedra with infinite reverse split rank. We give a geometric characterization of the integral polyhedra in with infinite reverse split rank.
-
作者：Fernandes, Cristina G.; Meira, Luis A. A.; Miyazawa, Flavio K.; Pedrosa, Lehilton L. C.
作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas; Universidade Estadual de Campinas
摘要：A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the metric facility location problem (MFLP) and to a g...
-
作者：Arulselvan, Ashwin
作者单位：Technical University of Berlin
摘要：Padberg (Math Program 137:593-599, 2013) introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.
-
作者：Hanasusanto, Grani A.; Kuhn, Daniel; Wallace, Stein W.; Zymler, Steve
作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Norwegian School of Economics (NHH)
摘要：We present a risk-averse multi-dimensional newsvendor model for a class of products whose demands are strongly correlated and subject to fashion trends that are not fully understood at the time when orders are placed. The demand distribution is known to be multimodal in the sense that there are spatially separated clusters of probability mass but otherwise lacks a complete description. We assume that the newsvendor hedges against distributional ambiguity by minimizing the worst-case risk of th...
-
作者：Gustavsson, Emil; Patriksson, Michael; Stromberg, Ann-Brith
作者单位：Chalmers University of Technology; University of Gothenburg
摘要：When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which...
-
作者：Tapia, Richard
作者单位：Rice University
摘要：In this paper we present several representation theorems and averaging theorems for members of the difference class of secant updates introduced by Brodlie et al. (J Inst Math Appl 11:73-82, 1973). Major contributions are that the integral form of the mean-value theorem leads to a proof that the BFGS update is pointwise the infinite average of all the updates on the one-dimension manifold in the Dennis class that connects the DFP secant update to the Greenstadt update, and that it can be expre...
