-
作者：Xiong, Zikai; Freund, Robert M.
作者单位：Northwestern University; Massachusetts Institute of Technology (MIT)
摘要：In recent years, there has been growing interest in solving linear optimization problems - or more simply LP - using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) - together with some heuristic techniques - has emerged as a powerful tool for solving huge-scale LPs. However, the theoretical understanding of the restarted PDHG and the validation of various heuristi...
-
作者：Aolaritei, Liviu; Shafiee, Soroosh; Dorfler, Florian
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Cornell University
摘要：Distributionally robust optimization (DRO) has become a powerful framework for estimation under uncertainty, offering strong out-of-sample performance and principled regularization. In this paper, we propose a DRO-based method for linear regression and address a central question: how to optimally choose the robustness radius, which controls the trade-off between robustness and accuracy. Focusing on high-dimensional settings where the dimension and the number of samples are both large and compa...
-
作者：Toint, Philippe L.
作者单位：University of Namur
摘要：The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in [7, 20] to require, under standard assumptions, at most O(& varepsilon;(3/(3-q))) evaluations of the objective function and its derivatives of degrees one and two to produce an & varepsilon;-approximate critical point of order q is an element of{1,2}. This bound was shown to be sharp in [5, 6] for q=1 and in [11] for arbitrary q is an element of{1,2}. This note revisits these results and shows that the ...
-
作者：Mulansky, Bernd; Potschka, Andreas
作者单位：TU Clausthal
摘要：We derive a mixed integer nonlinear programming formulation for the problem of finding a convex polygon with n vertices that is small (diameter at most one) and has maximum perimeter provided a stated conjecture is true. The formulation is based on a geometric construction using centrally symmetric polygons (zonogons). The resulting zonogons can be characterized by equivalence classes (under the action of the dihedral group) of 2n-vectors with entries either plus or minus one and a self-dualit...
-
作者：Gabl, Markus; Anstreicher, Kurt M.
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; University of Iowa
摘要：We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a variety of different nonconvex quadratic problems.
-
作者：Kazachkov, Aleksandr M.; Balas, Egon
作者单位：State University System of Florida; University of Florida; Carnegie Mellon University
摘要：Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a nu-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal s...
-
作者：Aktas, Fatih S.; Kroer, Christian
作者单位：Columbia University
摘要：We study the convergence properties of the greedy Frank-Wolfe (GFW) algorithm with a unit step size, for a concave minimization problem (or equivalently, convex maximization) over a compact set. We assume that the function satisfies smoothness and strong concavity. These assumptions, together with the Kurdyka-& Lstrok;ojasiewicz (KL) property, allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depend...
-
作者：Cristi, Andres; Salas, David
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universidad de O'Higgins
摘要：In 1960, B. Gr & uuml;nbaum proved that, for any convex body C subset of Rd and every halfspace H containing the centroid of C, the volume of H boolean AND C is at least a 1e -fraction of the volume of C. In 2014, Oertel conjectured that a similar result holds for mixed-integer convex sets. Concretely, he proposed that for any convex body C subset of Rn+d , there should exist a point x is an element of S=C boolean AND(Zn & times;Rd) such that every halfspace H containing x satisfies where Hd d...
-
作者：Bok, Jinho; Altschuler, Jason M.
作者单位：University of Pennsylvania
摘要：Recent advances in convex optimization have leveraged computer-assisted proofs to develop optimized first-order methods that improve over classical algorithms. However, each optimized method is specially tailored for a particular problem setting, and it is a well-documented challenge to extend optimized methods to other settings due to their highly bespoke design and analysis. We provide a framework that derives optimized methods for composite optimization directly from those for unconstrained...
-
作者：Gupta, Swati; Moondra, Jai; Singh, Mohit
作者单位：Massachusetts Institute of Technology (MIT); Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by fairness concerns, we study the 'portfolio problem': given an optimization problem with set D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {D}$$\end{document} of feasible solutions, a class C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepac...
