-
作者：Hungerlaender, P.; Rendl, F.
作者单位：University of Klagenfurt
摘要：Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on whether u is before v and r is before s. The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to...
-
作者：Goberna, M. A.; Jeyakumar, V.; Li, G.; Lopez, M. A.
作者单位：Universitat d'Alacant; University of New South Wales Sydney
摘要：In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. ...
-
作者：Dong, Hongbo; Anstreicher, Kurt
作者单位：University of Iowa; University of Iowa
摘要：The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation t...
-
作者：Sagastizabal, Claudia
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient information for the convex function, and the function and derivatives for the smooth mapping. With this information,...
-
作者：Lan, Guanghui; Monteiro, Renato D. C.
作者单位：State University System of Florida; University of Florida; University System of Georgia; Georgia Institute of Technology
摘要：This paper considers a special but broad class of convex programming problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. It studies the computational complexity of quadratic penalty based methods for solving the above class of problems. An iteration of these methods, which is simply an iteration of Nesterov's optimal method (or one of its variants) for approximately solving a smooth penalizatio...
-
作者：Fernandez, Damian
作者单位：National University of Cordoba
摘要：The quasi-Newton strategy presented in this paper preserves one of the most important features of the stabilized Sequential Quadratic Programming method, the local convergence without constraint qualifications assumptions. It is known that the primal-dual sequence converges quadratically assuming only the second-order sufficient condition. In this work, we show that if the matrices are updated by performing a minimization of a Bregman distance (which includes the classic updates), the quasi-Ne...
-
作者：Borndoerfer, Ralf; Karbstein, Marika; Pfetsch, Marc E.
作者单位：Zuse Institute Berlin; Technical University of Darmstadt
摘要：The Steiner connectivity problem has the same significance for line planning in public transport as the Steiner tree problem for telecommunication network design. It consists in finding a minimum cost set of elementary paths to connect a subset of nodes in an undirected graph and is, therefore, a generalization of the Steiner tree problem. We propose an extended directed cut formulation for the problem which is, in comparison to the canonical undirected cut formulation, provably strong, implyi...
-
作者：Basu, Amitabh; Campelo, Manoel; Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo
作者单位：University of California System; University of California Davis; Universidade Federal do Ceara; University of Padua; Carnegie Mellon University; University of London; London School Economics & Political Science
摘要：This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is e...
-
作者：Harks, Tobias; Hoefer, Martin; Klimm, Max; Skopalik, Alexander
作者单位：Maastricht University; RWTH Aachen University; Technical University of Berlin; Dortmund University of Technology
摘要：Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria-a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., m...
-
作者：Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher i...
