-
作者：Ouyang, Wenqing; Milzarek, Andre
作者单位：Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; The Chinese University of Hong Kong, Shenzhen
摘要：We propose a novel trust region method for solving a class of nonsmooth, nonconvex composite-type optimization problems. The approach embeds inexact semismooth Newton steps for finding zeros of a normal map-based stationarity measure for the problem in a trust region framework. Based on a new merit function and acceptance mechanism, global convergence and transition to fast local q-superlinear convergence are established under standard conditions. In addition, we verify that the proposed trust...
-
作者：Chmiela, Antonia; Munoz, Gonzalo; Serrano, Felipe
作者单位：Zuse Institute Berlin; Universidad de Chile
摘要：Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve intersection cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting...
-
作者：Lin, Tianyi; Jordan, Michael I.
作者单位：Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley
摘要：This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding x ⋆is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x<^>\star \in {\mathcal {X}}$$\end{documen...
-
作者：Hanguir, Oussama; Ma, Will; Han, Jiangze; Ryan, Christopher Thomas
作者单位：Columbia University; Columbia University; University of British Columbia
摘要：We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different weapons or tactics as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call loadouts) of Linear Programs max{c(inverted perpendicular)x|Ax <= b,x >= 0} with ...
-
作者：Matuschke, Jannik
作者单位：KU Leuven
摘要：Given a set system (E,P) with rho is an element of[0,1](E) and pi is an element of[0,1](P), our goal is to find a probability distribution for a random set S subset of E such that Pr[e is an element of S ]= rho e for all e is an element of E and Pr [P boolean AND S not equal empty set] >= pi P for all P is an element of P. We extend the results of Dahan, Amin, and Jaillet [6] who studied this problem motivated by a security game in a directed acyclic graph (DAG). We focus on the setting where ...
-
作者：Garatti, Simone; Campi, Marco C.
作者单位：Polytechnic University of Milan; University of Brescia
摘要：Scenario optimization is an approach to data-driven decision-making that has been introduced some fifteen years ago and has ever since then grown fast. Its most remarkable feature is that it blends the heuristic nature of data-driven methods with a rigorous theory that allows one to gain factual, reliable, insight in the solution. The usability of the scenario theory, however, has been restrained thus far by the obstacle that most results are standing on the assumption of convexity. With this ...
-
作者：Rudi, Alessandro; Marteau-Ferey, Ulysse; Bach, Francis
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite s...
-
作者：Dvurechensky, Pavel; Staudigl, Mathias
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; University of Mannheim
摘要：A key problem in mathematical imaging, signal processing and computational statistics is the minimization of non-convex objective functions that may be non-differentiable at the relative boundary of the feasible set. This paper proposes a new family of first- and second-order interior-point methods for non-convex optimization problems with linear and conic constraints, combining logarithmically homogeneous barriers with quadratic and cubic regularization respectively. Our approach is based on ...
-
作者：Buchheim, Christoph
作者单位：Dortmund University of Technology
摘要：Extended formulations are an important tool in polyhedral combinatorics. Many combinatorial optimization problems require an exponential number of inequalities when modeled as a linear program in the natural space of variables. However, by adding artificial variables, one can often find a small linear formulation, i.e., one containing a polynomial number of variables and constraints, such that the projection to the original space of variables yields a perfect linear formulation. Motivated by b...
-
作者：Rebjock, Quentin; Boumal, Nicolas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Trust-region methods (TR) can converge quadratically to minima where the Hessian is positive definite. However, if the minima are not isolated, then the Hessian there cannot be positive definite. The weaker Polyak-& Lstrok;ojasiewicz (P & Lstrok;) condition is compatible with non-isolated minima, and it is enough for many algorithms to preserve good local behavior. Yet, TR with an exact subproblem solver lacks even basic features such as a capture theorem under P & Lstrok;. In practice, a popu...
