-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions are determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving the polynomial optimization. We show that the hierarchy of new relaxatio...
-
作者：Awasthi, Pranjal; Goyal, Vineet; Lu, Brian Y.
作者单位：Rutgers University System; Rutgers University New Brunswick; Columbia University
摘要：In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage constraints from a giv...
-
作者：Haeser, Gabriel; Liu, Hongcheng; Ye, Yinyu
作者单位：Universidade de Sao Paulo; Stanford University; Stanford University
摘要：In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is available. For this type of problems, existing necessary conditions often rely on the notion of subdifferential or become non-trivially ...
-
作者：Lee, Euiwoong
作者单位：Carnegie Mellon University
摘要：Given a graph G=(V,E) and an integer k is an element of N, we study k-Vertex Separator (resp. k-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has less than k vertices. We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. Our main results are the following improved approximation algorithms.O(logk)-approximati...
-
作者：Bach, Francis
作者单位：Universite PSL; Ecole Normale Superieure (ENS)
摘要：Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it...
-
作者：Huang, Cheng; Huo, Xiaoming
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Distributed statistical inference has recently attracted enormous attention. Many existing work focuses on the averaging estimator, e.g., Zhang and Duchi (J Mach Learn Res 14:3321-3363, 2013) together with many others. We propose a one-step approach to enhance a simple-averaging based distributed estimator by utilizing a single Newton-Raphson updating. We derive the corresponding asymptotic properties of the newly proposed estimator. We find that the proposed one-step estimator enjoys the same...
-
作者：Yue, Man-Chung; Zhou, Zirui; So, Anthony Man-Cho
作者单位：Imperial College London; Hong Kong Baptist University; Chinese University of Hong Kong
摘要：We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem...
-
作者：Chen, Yifan; Sun, Yuejiao; Yin, Wotao
作者单位：Tsinghua University; University of California System; University of California Los Angeles
摘要：Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers or stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an inspect phase to existing algorithms that helps escape from non-global stationary points. It samples a set of points in a radius R around the current point. When a sample point yields a sufficient decrease in the objective, we resume an existing algorithm from that poin...
-
作者：Lu, Zhaosong; Zhou, Zirui; Sun, Zhe
作者单位：Simon Fraser University; Hong Kong Baptist University; Jiangxi Normal University
摘要：In this paper we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and nonsmooth functions while the second convex component is the supremum of possibly infinitely many convex smooth functions. We first propose an inexact enhanced DC algorithm for solving this problem in which the second convex component is the supremum of finitely many convex smooth functions, and show that every accumulation point of the...
-
作者：O'Neill, Michael; Wright, Stephen J.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process). We show by mean...
