-
作者：Netzer, Tim; Sanyal, Raman
作者单位：Leipzig University; Free University of Berlin
摘要：Hyperbolicity cones are convex algebraic cones arising from hyperbolic polynomials. A well-understood subclass of hyperbolicity cones is that of spectrahedral cones and it is conjectured that every hyperbolicity cone is spectrahedral. In this paper we prove a weaker version of this conjecture by showing that every smooth hyperbolicity cone is the linear projection of a spectrahedral cone, that is, a spectrahedral shadow.
-
作者：Cornuejols, Gerard; Wolsey, Laurence; Yildiz, Sercan
作者单位：Carnegie Mellon University; Universite Catholique Louvain
摘要：The concept of cut-generating function has its origin in the work of Gomory and Johnson from the 1970s. It has received renewed attention in the past few years. Recently Conforti, Cornu,jols, Daniilidis, Lemar,chal, and Malick proposed a general framework for studying cut-generating functions. However, they gave an example showing that not all cuts can be produced by cut-generating functions in this framework. They conjectured a natural condition under which cut-generating functions might be s...
-
作者：Izmailov, A. F.; Uskov, E. I.
作者单位：Lomonosov Moscow State University
摘要：In this paper we continue the studies of the persistent effect of attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers. It appears very important to understand the nature of this striking phenomenon, in particular, because it is precisely the reason of slow convergence of such methods when applied to problems with degenerate constraints. All previously known results concerned with this effect were a posteriori by nature: they were showing that in case of...
-
作者：Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.
作者单位：Lancaster University
摘要：The reformulation-linearization technique, due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. Computational experiments, conduct...
-
作者：Bertsimas, Dimitris; Gupta, Vishal; Paschalidis, Ioannis Ch.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Boston University
摘要：Equilibrium modeling is common in a variety of fields such as game theory and transportation science. The inputs for these models, however, are often difficult to estimate, while their outputs, i.e., the equilibria they are meant to describe, are often directly observable. By combining ideas from inverse optimization with the theory of variational inequalities, we develop an efficient, data-driven technique for estimating the parameters of these models from observed equilibria. We use this tec...
-
作者：Lan, Guanghui
作者单位：State University System of Florida; University of Florida
摘要：The main goal of this paper is to develop uniformly optimal first-order methods for convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. By incorporating a multi-step acceleration scheme into the well-known bundle-level method, we develop an accelerated bundle-level method, and show that it can achieve the optimal complexity for solv...
-
作者：Song, Wen; Xu, Xiaomei; Yao, Jen-Chih
作者单位：Harbin Normal University; Kaohsiung Medical University; King Abdulaziz University
摘要：In this note, we give a counterexample to show that the characterization formula for the condition numbers of a convex set of given in Coulibaly and Crouzeix (Math Program 116:79-113, 2009) is incorrect.
-
作者：Kozmik, Vaclav; Morton, David P.
作者单位：Charles University Prague; University of Texas System; University of Texas Austin
摘要：We consider a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new approach based on importance sampling, which yields improved upper bound estimators. Modest additional computational effort is requ...
-
作者：Maehara, Takanori; Murota, Kazuo
作者单位：Japan Science & Technology Agency (JST); Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; University of Tokyo
摘要：A theoretical framework of difference of discrete convex functions (discrete DC functions) and optimization problems for discrete DC functions is established. Standard results in continuous DC theory are exported to the discrete DC theory with the use of discrete convex analysis. A discrete DC algorithm, which is a discrete analogue of the continuous DC algorithm (Concave-Convex procedure in machine learning) is proposed. The algorithm contains the submodular-supermodular procedure as a specia...
-
作者：Bonami, Pierre; Margot, Francois
作者单位：Aix-Marseille Universite; Carnegie Mellon University
摘要：For a mixed integer linear program where all integer variables are bounded, we study a reformulation introduced by Roy that maps general integer variables to a collection of binary variables. We study theoretical properties and empirical strength of rank-2 simple split cuts of the reformulation. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensio...
