-
作者：Kiessling, David; Leyffer, Sven; Vanaret, Charlie
作者单位：KU Leuven; United States Department of Energy (DOE); Argonne National Laboratory; Zuse Institute Berlin
摘要：We consider nonlinearly constrained optimization problems and discuss a generic double-loop framework consisting of basic algorithmic ingredients that unifies a broad range of nonlinear optimization solvers. This framework has been implemented in the open-source solver Uno, a Swiss Army knife-like C++ optimization framework that unifies many nonlinearly constrained nonconvex optimization solvers. We illustrate the framework with a sequential quadratic programming (SQP) algorithm that maintains...
-
作者：Gupta, Akshita; Hunter, Susan R.
作者单位：Purdue University System; Purdue University
摘要：We consider a two-stage stochastic multi-objective linear program (TSSMOLP) that is a natural generalization of the well-studied two-stage stochastic linear program (TSSLP) allowing modelers to specify multiple objectives in each stage. The second-stage recourse decision is governed by an uncertain multi-objective linear program (MOLP) whose solution maps to an uncertain second-stage nondominated set. The TSSMOLP then comprises the objective, which is the Minkowski sum of a linear term plus th...
-
作者：Doikov, Nikita
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton ...
-
作者：Nutov, Zeev
作者单位：Open University Israel
摘要：A set family F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{F}$$\end{document} is uncrossable if A boolean AND B,A boolean OR B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \u...
-
作者：Nie, Jiawang; Qu, Zheng; Tang, Xindong; Zhang, Linghao
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University; Hong Kong Baptist University
摘要：This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particu...
-
作者：Chua, Chek Beng
作者单位：Nanyang Technological University
摘要：We study the Carath & eacute;odory number of homogeneous convex cones via their spectrahedral representations. A characterization of homogeneous convex cones whose ranks match their Carath & eacute;odory numbers is given. This characterization is then used to show that a homogeneous convex cone is selfdual if and only if its rank matches the Carath & eacute;odory numbers of both its closure and its dual cone. It is further used to show that the only sparse spectrahedral cones that are homogene...
-
作者：Doron-Arad, Ilan; Kulik, Ariel; Shachnai, Hadas
作者单位：Technion Israel Institute of Technology; Ben-Gurion University of the Negev
摘要：We study the budgeted versions of the well known matching, matroid independent set, and matroid intersection problems. While all problems admit polynomial-time approximation schemes (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondr & aacute;k and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit an efficient PTAS (EPTAS). In this paper, we answer this question affirmatively, by presenting an EPTAS for budgeted matching, budgeted matroid ...
-
作者：Ju, Caleb; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper proposes a novel termination criterion, termed the advantage gap function, for finite state and action Markov decision processes (MDP) and reinforcement learning (RL). By incorporating this advantage gap function into the design of step size rules and deriving a new linear rate of convergence that is independent of the stationary state distribution of the optimal policy, we demonstrate that policy gradient methods can solve MDPs in strongly-polynomial time. To the best of our knowle...
-
作者：Rubbens, Anne; Hendrickx, Julien M.
作者单位：Universite Catholique Louvain
摘要：We consider the problem of obtaining interpolation constraints for function classes, i.e., necessary and sufficient constraints that a set of points, function values and (sub)gradients must satisfy to ensure the existence of a global function of the class considered, consistent with this set. The derivation of such constraints is crucial, e.g., in the performance analysis of optimization methods, since obtaining a priori tight performance guarantees requires using a tight description of functi...
-
作者：Moura, Phablo F. S.; Yaman, Hande; Leus, Roel
作者单位：KU Leuven
摘要：Let k be a positive integer and let G be a graph with n vertices. A connected k-subpartition of G is a collection of k pairwise disjoint sets (a.k.a. classes) of vertices in G such that each set induces a connected subgraph. The connected k-subpartition polytope of G, denoted by P(G,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} ...
