-
作者：Pena, Javier; Soheili, Negar
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone . At each iteration, the algorithm only involves a query to a separation oracle for and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a point in after iterations, where is the width of the cone . We propose a version of the perceptron algorithm that includes a periodic rescaling of the ambient space. In contrast to the classical version, our rescaled version finds...
-
作者：Domes, Ferenc; Neumaier, Arnold
作者单位：University of Vienna
摘要：In rigorous constrained global optimization, upper bounds on the objective function help to reduce the search space. Obtaining a rigorous upper bound on the objective requires finding a narrow box around an approximately feasible solution, which then must be verified to contain a feasible point. Approximations are easily found by local optimization, but the verification often fails. In this paper we show that even when the verification of an approximate feasible point fails, the information ex...
-
作者：Freund, Robert M.; Grigas, Paul
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We present new results for the Frank-Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps an...
-
作者：Miao, Weimin; Pan, Shaohua; Sun, Defeng
作者单位：National University of Singapore; South China University of Technology; National University of Singapore; National University of Singapore
摘要：For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the low-rank correlation matrix completion in various fields such as the financial market and the low-rank density matrix completion from the quantum state tomography. To seek a solution of high recovery quality beyond the reach of the nuclear norm, in this paper, we propose a rank...
-
作者：Cheung, Maurice; Elmachtoub, Adam N.; Levi, Retsef; Shmoys, David B.
作者单位：Cornell University; Columbia University; Massachusetts Institute of Technology (MIT); Cornell University; Cornell University
摘要：The joint replenishment problem is a fundamental model in supply chain management theory that has applications in inventory management, logistics, and maintenance scheduling. In this problem, there are multiple item types, each having a given time-dependent sequence of demands that need to be satisfied. In order to satisfy demand, orders of the item types must be placed in advance of the due dates for each demand. Every time an order of item types is placed, there is an associated joint setup ...
-
作者：Adly, Samir; Hantoute, Abderrahim; Thera, Michel
作者单位：Universite de Limoges; Universidad de Chile; Federation University Australia
摘要：The general theory of Lyapunov stability of first-order differential inclusions in Hilbert spaces has been studied by the authors in the previous paper (Adly et al. in Nonlinear Anal 75(3): 985-1008, 2012). This new contribution focuses on the case when the interior of the domain of the maximally monotone operator governing the given differential inclusion is nonempty; this includes in a natural way the finite-dimensional case. The current setting leads to simplified, more explicit criteria an...
-
作者：Ghadimi, Saeed; Lan, Guanghui
作者单位：State University System of Florida; University of Florida
摘要：In this paper, we generalize the well-known Nesterov's accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order information, similarly to the gradient descent method. We then consider an important clas...
-
作者：Nayak, Ashwin; Sikora, Jamie; Tuncel, Levent
作者单位：University of Waterloo; University of Waterloo; National University of Singapore
摘要：Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips with near optimal bias away from uniform, even when one party deviates arbitrarily from the protocol. The probability of any outcome in these protocols is provably at most for any given . However, no explicit description of these protocols is known; in ...
-
作者：Drori, Yoel; Teboulle, Marc
作者单位：Tel Aviv University
摘要：We propose a new variant of Kelley's cutting-plane method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space. We derive the method through a constructive approach and prove that it attains the optimal rate of convergence for this class of problems.
-
作者：Kilinc-Karzan, Fatma; Steffy, Daniel E.
作者单位：Carnegie Mellon University; Oakland University
摘要：This paper studies -sublinear inequalities, a class of inequalities with strong relations to -minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of -sublinear inequalities. That is, we show that when is the nonnegative orthant or the second-order cone, -sublinear inequalities together with the original conic constraint are always sufficient for the closed convex hull description of the associated disjunctive conic set. When is the nonnegative ort...
