-
作者：Pena, Javier; Roshchina, Vera
作者单位：Carnegie Mellon University; Federation University Australia; University of Evora
摘要：Consider a homogeneous multifold convex conic system Ax = 0, x is an element of K-1 x ... x K-r and its alternative system A(T) y is an element of K-1* x ... x K-r*, where K-1, ... , K-r are regular closed convex cones. We show that there is a canonical partition of the index set {1, ... , r} determined by certain complementarity sets associated to the most interior solutions to the two systems. Our results are inspired by and extend the Goldman-Tucker Theorem for linear programming.
-
作者：Guigues, Vincent; Sagastizabal, Claudia
作者单位：Getulio Vargas Foundation; Universidade Federal do Rio de Janeiro
摘要：We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. For each time step, a risk-averse problem with constraints that are deterministic for the current t...
-
作者：Hoheisel, Tim; Kanzow, Christian; Schwartz, Alexandra
作者单位：University of Wurzburg
摘要：Mathematical programs with equilibrium constraints (MPECs) are difficult optimization problems whose feasible sets do not satisfy most of the standard constraint qualifications. Hence MPECs cause difficulties both from a theoretical and a numerical point of view. As a consequence, a number of MPEC-tailored solution methods have been suggested during the last decade which are known to converge under suitable assumptions. Among these MPEC-tailored solution schemes, the relaxation methods are cer...
-
作者：Rodriguez-Chia, A. M.; Valero-Franco, C.
作者单位：Universidad de Cadiz
摘要：This paper presents a procedure to solve the classical location median problem where the distances are measured with l(p)-norms with p > 2. In order to do that we consider an approximated problem. The global convergence of the sequence generated by this iterative scheme is proved. Therefore, this paper closes the still open question of giving a modification of the Weiszfeld algorithm that converges to an optimal solution of the median problem with l(p) norms and p is an element of (2, infinity...
-
作者：Eggermont, Christian E. J.; Schrijver, Alexander; Woeginger, Gerhard J.
作者单位：Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI); University of Amsterdam
摘要：We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock state...
-
作者：Izmailov, Alexey F.; Kurennoy, Alexey S.; Solodov, Mikhail V.
作者单位：Lomonosov Moscow State University
摘要：We prove a new local upper Lipschitz stability result and the associated local error bound for solutions of parametric Karush-Kuhn-Tucker systems corresponding to variational problems with Lipschitzian base mappings and constraints possessing Lipschitzian derivatives, and without any constraint qualifications. This property is equivalent to the appropriately extended to this nonsmooth setting notion of noncriticality of the Lagrange multiplier associated to the primal solution, which is weaker...
-
作者：Rothvoss, Thomas
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We prove that there are 0/1 polytopes P subset of R-n that do not admit a compact LP formulation. More precisely we show that for every n there is a set X subset of {0, 1}(n) such that conv(X) must have extension complexity at least 2(n/2.(1-o(1))). In otherwords, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not subset of P-/poly, our ...
-
作者：Stockbridge, Rebecca; Bayraksan, Guzin
作者单位：University of Arizona; University of Arizona
摘要：Monte Carlo sampling-based estimators of optimality gaps for stochastic programs are known to be biased. When bias is a prominent factor, estimates of optimality gaps tend to be large on average even for high-quality solutions. This diminishes our ability to recognize high-quality solutions. In this paper, we present a method for reducing the bias of the optimality gap estimators for two-stage stochastic linear programs with recourse via a probability metrics approach, motivated by stability r...
-
作者：Wen, Zaiwen; Yin, Wotao
作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; Rice University
摘要：Minimization with orthogonality constraints (e.g., X-inverted perpendicular X = I) and/or spherical constraints (e. g., parallel to x parallel to(2) = 1) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these diff...
-
作者：Ioffe, Alexander D.
作者单位：Technion Israel Institute of Technology
摘要：The paper studies regularity properties of set-valued mappings between metric spaces. In the context of metric regularity, nonlinear models correspond to nonlinear dependencies of estimates of error bounds in terms of residuals. Among the questions addressed in the paper are equivalence of the corresponding concepts of openness and pseudo-Holder behavior, general and local regularity criteria with special emphasis on regularity of order , for local settings, and variational methods to extimate...
