-
作者：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...
-
作者：Canovas, M. J.; Hantoute, A.; Parra, J.; Toledo, F. J.
作者单位：Universidad Miguel Hernandez de Elche; Universidad de Chile
摘要：This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations (i.e., perturbations of the objective function and the right-hand-side of the constraints), the paper provides ...
-
作者：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.
-
作者：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...
