Mathematical Programming

最新文章

• Sum-of-squares hierarchies for binary polynomial optimization AI翻译
  作者：Slot, Lucas; Laurent, Monique
  作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
  摘要：We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r epsilon N a lower bound f((r)) on the minimum f(min) of f, given by the largest scalar lambda for which the polynomial f - lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worstcase error f(min) - f((r)) in terms of the least roots of the Kr...
• On implicit function theorem for locally Lipschitz equations AI翻译
  作者：Arutyunov, Aram, V; Zhukovskiy, Sergey E.
  作者单位：V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
  摘要：Equations defined by locally Lipschitz continuous mappings with a parameter are considered. Implicit function theorems for this equation are obtained. The regularity condition is formulated in the terms of the Clarke Jacobian. Implicit functions estimates are derived. It is shown that the considered regularity assumptions are weaker than most of the known ones. The obtained implicit function theorems are applied to derive conditions for upper semicontinuity of the optimal value function for pa...
• A trust region method for noisy unconstrained optimization AI翻译
  作者：Sun, Shigeng; Nocedal, Jorge
  作者单位：Northwestern University; Northwestern University
  摘要：Classical trust region methods were designed to solve problems in which function and gradient information are exact. This paper considers the case when there are errors (or noise) in the above computations and proposes a simple modification of the trust region method to cope with these errors. The new algorithm only requires information about the size/standard deviation of the errors in the function evaluations and incurs no additional computational expense. It is shown that, when applied to a...
• Softmax policy gradient methods can take exponential time to converge AI翻译
  作者：Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin
  作者单位：University of Pennsylvania; Carnegie Mellon University
  摘要：The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For gamma-discounted infinite horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear depe...
• The augmented lagrangian method can approximately solve convex optimization with least constraint violation AI翻译
  作者：Dai, Yu-Hong; Zhang, Liwei
  作者单位：Chinese Academy of Sciences; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Dalian University of Technology
  摘要：There are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A natural way for dealing with these problems is to extend the nonlinear optimization problem as the one optimizing the objective function over the set of points with the least constraint violation. This leads to the study of the shifted problem. This paper focuses on the constrained...
• Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity AI翻译
  作者：Garber, Dan
  作者单位：Technion Israel Institute of Technology
  摘要：We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underlying assumption in many cases is that the optimal solution is rank-one. In this paper we consider a simple and natural sufficient condition on the objective so that the optimal solution to these relaxations is indeed unique and rank-one. Mainly, we show that under this conditio...
• A globally convergent proximal Newton-type method in nonsmooth convex optimization AI翻译
  作者：Mordukhovich, Boris S.; Yuan, Xiaoming; Zeng, Shangzhi; Zhang, Jin
  作者单位：Wayne State University; University of Hong Kong; University of Victoria; Southern University of Science & Technology
  摘要：The paper proposes and justifies a new algorithm of the proximal Newton type to solve a broad class of nonsmooth composite convex optimization problems without strong convexity assumptions. Based on advanced notions and techniques of variational analysis, we establish implementable results on the global convergence of the proposed algorithm as well as its local convergence with superlinear and quadratic rates. For certain structured problems, the obtained local convergence conditions do not re...
• A duality based 2-approximation algorithm for maximum agreement forest AI翻译
  作者：Olver, Neil; Schalekamp, Frans; van der Ster, Suzanne; Stougie, Leen; van Zuylen, Anke
  作者单位：University of London; London School Economics & Political Science; Cornell University; Cornell University; Vrije Universiteit Amsterdam
  摘要：We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear progr...
• Proximity bounds for random integer programs AI翻译
  作者：Celaya, Marcel; Henk, Martin
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin
  摘要：We study proximity bounds within a natural model of random integer programs of the type max c(inverted perpendicular) x : Ax = b, x is an element of Z(>= 0), where A is an element of Z(mxn) is of rank m, b is an element of Z(m) and c is an element of Z(n). In particular, we seek bounds for proximity in terms of the parameter Delta( A), which is the square root of the determinant of the Gram matrix AA(inverted perpendicular) of A. We prove that, up to constants depending on n and m, the proximi...
• Perturbed Fenchel duality and first-order methods AI翻译
  作者：Gutman, David H.; Pena, Javier F.
  作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
  摘要：We show that the iterates generated by a generic first-order meta-algorithm satisfy a canonical perturbed Fenchel duality inequality. The latter in turn readily yields a unified derivation of the best known convergence rates for various popular first-order algorithms including the conditional gradient method as well as the main kinds of Bregman proximal methods: subgradient, gradient, fast gradient, and universal gradient methods.