-
作者：Deng, Yan; Shen, Siqian
作者单位：University of Michigan System; University of Michigan
摘要：This paper investigates a problem of scheduling appointments with random service durations on multiple servers with operating time limits. We minimize the cost of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server running overtime. With finite samples of random service time, we consider a mixed-integer linear programming extended formulation and propose a two-stage decomposition framework with cutting planes. The first stage considers a...
-
作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：This paper is devoted to the design of an efficient and convergent semi-proximal alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though...
-
作者：Modaresi, Sina; Kilinc, Mustafa R.; Vielma, Juan Pablo
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Carnegie Mellon University; Massachusetts Institute of Technology (MIT)
摘要：We study the generalization of split, k-branch split, and intersection cuts from mixed integer linear programming to the realm of mixed integer nonlinear programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-...
-
作者：Shalev-Shwartz, Shai; Zhang, Tong
作者单位：Hebrew University of Jerusalem; Rutgers University System; Rutgers University New Brunswick; Baidu
摘要：We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.
-
作者：Shefi, Ron; Teboulle, Marc
作者单位：Tel Aviv University
摘要：We consider the class of nondifferentiable convex problems which minimizes a nonsmooth convex objective over a single smooth constraint. Exploiting the smoothness of the feasible set and using duality, we introduce a simple first order algorithm proven to globally converge to an optimal solution with a efficiency estimate. The performance of the algorithm is demonstrated by solving large instances of the convex sparse recovery problem.
-
作者：Camlibel, M. K.; Schumacher, J. M.
作者单位：University of Groningen; Dogus University; Tilburg University
摘要：This paper deals with a class of dynamical systems obtained from interconnecting linear systems with static set-valued relations. We first show that such an interconnection can be described by a differential inclusions with a maximal monotone set-valued mappings when the underlying linear system is passive and the static relation is maximal monotone. Based on the classical results on such differential inclusions, we conclude that such interconnections are well-posed in the sense of existence a...
-
作者：Ahmed, Shabbir; Linderoth, Jeff
-
作者：Conforti, Michele; Pashkovich, Kanstantsin
作者单位：University of Padua; Universite Libre de Bruxelles
摘要：Margot (1994) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from smaller polytopes via some composition rule. He introduced the projected faces property of a polytope and showed that this property suffices to iteratively build extended formulations of composed polytopes. For the composed polytopes, we show that an extended formulation of the type defined by Margot is always possible only if the smaller polytopes have the projected faces proper...
-
作者：Jarre, Florian; Toint, Philippe L.
作者单位：Heinrich Heine University Dusseldorf; University of Namur
摘要：In this paper two simple examples of a twice continuously differentiable strictly convex function are presented for which Newton's method with line search converges to a point where the gradient of is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of . Then is perturbed such that these search d...
-
作者：Bandeira, Afonso S.; Kennedy, Christopher; Singer, Amit
作者单位：Massachusetts Institute of Technology (MIT); University of Texas System; University of Texas Austin; Princeton University; Princeton University
摘要：The little Grothendieck problem consists of maximizing for a positive semidefinite matrix C, over binary variables . In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given a positive semidefinite matrix, the objective is to maximize restricting to take values in the group of orthogonal matrices , where denotes the (ij)-th block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve...
