-
作者：Cornaz, Denis; Meurdesoif, Philippe
作者单位：Universite PSL; Universite Paris-Dauphine; Universite de Bordeaux
摘要：If is a triangle-free graph, then two Gallai identities can be written as , where and denote the stability number and the clique-partition number, and is the line graph of . We show that, surprisingly, both equalities can be preserved for any graph by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of . As a consequence, one obtains an operator which associates to any graph parameter such that for all graph , a graph...
-
作者：Combettes, Patrick L.; Hiriart-Urruty, Jean-Baptiste; Thera, Michel
作者单位：Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite de Limoges; Centre National de la Recherche Scientifique (CNRS)
-
作者：Emich, Konstantin; Henrion, Rene; Roemisch, Werner
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Humboldt University of Berlin
摘要：In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-...
-
作者：Pennanen, Teemu
作者单位：University of London; King's College London
摘要：We study the problem of optimal investment by embedding it in the general conjugate duality framework of convex analysis. This allows for various extensions to classical models of liquid markets. In particular, we obtain a dual representation for the optimum value function in the presence of portfolio constraints and nonlinear trading costs that are encountered e.g. in modern limit order markets. The optimization problem is parameterized by a sequence of financial claims. Such a parameterizati...
-
作者：Amaral, Paula; Bomze, Immanuel M.; Judice, Joaquim
作者单位：Universidade Nova de Lisboa; University of Vienna; Universidade de Coimbra; Institute of Telecommunications - Coimbra; Universidade de Coimbra
摘要：We provide Completely Positive and Copositive Optimization formulations for the Constrained Fractional Quadratic Problem (CFQP) and Standard Fractional Quadratic Problem (StFQP). Based on these formulations, Semidefinite Programming relaxations are derived for finding good lower bounds to these fractional programs, which can be used in a global optimization branch-and-bound approach. Applications of the CFQP and StFQP, related with the correction of infeasible linear systems and eigenvalue com...
-
作者：Facchinei, Francisco; Kanzow, Christian; Sagratella, Simone
作者单位：Sapienza University Rome; University of Wurzburg
摘要：We propose to solve a general quasi-variational inequality by using its Karush-Kuhn-Tucker conditions. To this end we use a globally convergent algorithm based on a potential reduction approach. We establish global convergence results for many interesting instances of quasi-variational inequalities, vastly broadening the class of problems that can be solved with theoretical guarantees. Our numerical testings are very promising and show the practical viability of the approach.
-
作者：Toriello, Alejandro
作者单位：University of Southern California
摘要：We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with different basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between cities. We then introduce an exact reformulation that generates a family of successively tighter lower bounds, all solvable ...
-
作者：Sponsel, Julia; Duer, Mirjam
作者单位：Universitat Trier
摘要：We consider the problem of projecting a matrix onto the cones of copositive and completely positive matrices. As this can not be done directly, we use polyhedral approximations of the cones. With the help of these projections we obtain a technique to compute factorizations of completely positive matrices. We also describe a method to determine a cutting plane which cuts off an arbitrary matrix from the completely positive (or copositive) cone.
-
作者：Hintermueller, Michael; Mordukhovich, Boris S.; Surowiec, Thomas M.
作者单位：Humboldt University of Berlin; Wayne State University
摘要：The derivation of multiplier-based optimality conditions for elliptic mathematical programs with equilibrium constraints (MPEC) is essential for the characterization of solutions and development of numerical methods. Though much can be said for broad classes of elliptic MPECs in both polyhedric and non-polyhedric settings, the calculation becomes significantly more complicated when additional constraints are imposed on the control. In this paper we develop three derivation methods for constrai...
-
作者：Mehrotra, Sanjay; Zhang, He
作者单位：Northwestern University
摘要：We present three different robust frameworks using probabilistic ambiguity descriptions of the data in least squares problems. These probability ambiguity descriptions are given by: (1) confidence region over the first two moments; (2) bounds on the probability measure with moments constraints; (3) the Kantorovich probability distance from a given measure. For the first case, we give an equivalent formulation and show that the optimization problem can be solved using a semidefinite optimizatio...
