-
作者：Castro, Jordi; Nasini, Stefano; Saldanha-da-Gama, Francisco
作者单位：Universitat Politecnica de Catalunya; Centre National de la Recherche Scientifique (CNRS); IESEG School of Management; Universidade de Lisboa
摘要：We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling ...
-
作者：Cartis, C.; Gould, N. I. M.; Toint, Ph. L.
作者单位：University of Oxford; UK Research & Innovation (UKRI); Science & Technology Facilities Council (STFC); STFC Rutherford Appleton Laboratory; University of Namur; University of Namur
摘要：In a recent paper (Cartis et al. in Math Prog A 144(2):93-106, 2014), the evaluation complexity of an algorithm to find an approximate first-order critical point for the general smooth constrained optimization problem was examined. Unfortunately, the proof of Lemma 3.5 in that paper uses a result from an earlier paper in an incorrect way, and indeed the result of the lemma is false. The purpose of this corrigendum is to provide a modification of the previous analysis that allows us to restore ...
-
作者：Szeszler, David
作者单位：Budapest University of Technology & Economics
摘要：Two players, the Defender and the Attacker play the following game. A matroid , a weight function and a cost function are given. The Defender chooses a base B of the matroid M and the Attacker chooses an element of the ground set. In all cases, the Attacker pays the Defender the cost of attack c(s). Besides that, if then the Defender pays the Attacker the amount d(s); if, on the other hand, then there is no further payoff. Special cases of this two-player, zero-sum game were considered and sol...
-
作者：Pena, Javier; Soheili, Negar
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：We propose a simple projection and rescaling algorithm to solve the feasibility problem find x is an element of L boolean AND Omega, where L and Omega are respectively a linear subspace and the interior of a symmetric cone in a finite-dimensional vector space V. This projection and rescaling algorithm is inspired by previous work on rescaled versions of the perceptron algorithm and by Chubanov's projection-based method for linear feasibility problems. As in these predecessors, each main iterat...
-
作者：Suda, Sho; Tanaka, Hajime; Tokushige, Norihide
作者单位：Aichi University Education; Tohoku University; University of the Ryukyus
摘要：We present a semidefinite programming approach to bound the measures of cross-independent pairs in a bipartite graph. This can be viewed as a far-reaching extension of Hoffman's ratio bound on the independence number of a graph. As an application, we solve a problem on the maximum measures of cross-intersecting families of subsets with two different product measures, which is a generalized measure version of the ErdAs-Ko-Rado theorem for cross-intersecting families with different uniformities.
-
作者：Buchheim, Christoph; Kurtz, Jannis
作者单位：Dortmund University of Technology
摘要：The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min-max-min problem. In this paper, we consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case...
-
作者：Hong, Mingyi; Luo, Zhi-Quan
作者单位：University of Minnesota System; University of Minnesota Twin Cities; The Chinese University of Hong Kong, Shenzhen; Iowa State University
摘要：We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analy...
-
作者：Beck, Amir; Shtern, Shimrit
作者单位：Technion Israel Institute of Technology
摘要：We consider the problem of minimizing the sum of a linear function and a composition of a strongly convex function with a linear transformation over a compact polyhedral set. Jaggi and Lacoste-Julien (An affine invariant linear convergence analysis for Frank-Wolfe algorithms. NIPS 2013 Workshop on Greedy Algorithms, Frank-Wolfe and Friends, 2014) show that the conditional gradient method with away steps - employed on the aforementioned problem without the additional linear term - has a linear ...
-
作者：Guigues, Vincent
摘要：We consider risk-averse convex stochastic programs expressed in terms of extended polyhedral risk measures. We derive computable confidence intervals on the optimal value of such stochastic programs using the Robust Stochastic Approximation and the Stochastic Mirror Descent (SMD) algorithms. When the objective functions are uniformly convex, we also propose a multistep extension of the Stochastic Mirror Descent algorithm and obtain confidence intervals on both the optimal values and optimal so...
-
作者：Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generali...
