-
作者：Adam, Lukas; Henrion, Rene; Outrata, Jiri
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：Depending on whether a mathematical program with equilibrium constraints (MPEC) is considered in its original or its enhanced (via KKT conditions) form, the assumed qualification conditions as well as the derived necessary optimality conditions may differ significantly. In this paper, we study this issue when imposing one of the weakest possible qualification conditions, namely the calmness of the perturbation mapping associated with the respective generalized equations in both forms of the MP...
-
作者：Campi, M. C.; Garatti, S.
作者单位：University of Brescia; Polytechnic University of Milan
摘要：We consider convex optimization problems with uncertain, probabilistically described, constraints. In this context, scenario optimization is a well recognized methodology where a sample of the constraints is used to describe uncertainty. One says that the scenario solution generalizes well, or has a high robustness level, if it satisfies most of the other constraints besides those in the sample. Over the past 10 years, the main theoretical investigations on the scenario approach have related t...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：Concave mixed- integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed- integer points in a polyhedral region. In this work we describe an algorithm that finds an - approximate solution to a concave mixed- integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ , provided that the number of integer variables and the number of negative eigenvalues of the objective functi...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
摘要：We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when is decomposable into simpler Multilinea...
-
作者：Cartis, C.; Scheinberg, K.
作者单位：University of Oxford; Lehigh University
摘要：We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. We particularize an...
-
作者：Ioffe, Alexander D.
作者单位：Technion Israel Institute of Technology
摘要：The results on regularity behavior of solutions to variational inequalities over polyhedral sets proved in a series of papers by Robinson, Ralph and Dontchev-Rockafellar in the 90s has long become classics of variational analysis. But the available proofs are very complicated and practically do not use techniques of variational analysis. The only exception is the proof by Dontchev and Rockafellar of their critical face regularity criterion. In the paper we offer a different approach completely...
-
作者：Kim, Youngdae; Huber, Olivier; Ferris, Michael C.
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：Affine variational inequalities (AVI) are an important problem class that subsumes systems of linear equations, linear complementarity problems and optimality conditions for quadratic programs. This paper describes PathAVI, a structure-preserving pivotal approach, that can efficiently process (solve or determine infeasible) large-scale sparse instances of the problem with theoretical guarantees and at high accuracy. PathAVI implements a strategy known to process models with good theoretical pr...
-
作者：Esfahani, Peyman Mohajerin; Shafieezadeh-Abadeh, Soroosh; Hanasusanto, Grani A.; Kuhn, Daniel
作者单位：Delft University of Technology; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Texas System; University of Texas Austin
摘要：In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent's objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect information, that is, where the agent's true objective function is not contained in the search space of candidate objectives,...
-
作者：Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
作者单位：Max Planck Society; Maastricht University; University of Bonn; University of Wurzburg
摘要：We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is 2(Omega(root log n)), assuming NP not subset of DTIME(n(O(log n))). This constitutes a significant gap to the best known approximation upper bound of O(root n) due to Chekuri et al. (Theo...
-
作者：Gottschalk, Corinna; Koster, Arie M. C. A.; Liers, Frauke; Peis, Britta; Schmand, Daniel; Wierz, Andreas
作者单位：RWTH Aachen University; RWTH Aachen University; University of Erlangen Nuremberg
摘要：We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an edge. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most travel times may be prolonged simultaneously due to delay. We develop and study a ...
