-
作者：Zou, Jikai; Ahmed, Shabbir; Sun, Xu Andy
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders' decomposition and its stochastic variant, stochastic dual dynamic programming (S...
-
作者：Bassett, Robert; Deride, Julio
作者单位：University of California System; University of California Davis
摘要：Maximum a posteriori and Bayes estimators are two common methods of point estimation in Bayesian statistics. It is commonly accepted that maximum a posteriori estimators are a limiting case of Bayes estimators with 0-1 loss. In this paper, we provide a counterexample which shows that in general this claim is false. We then correct the claim that by providing a level-set condition for posterior densities such that the result holds. Since both estimators are defined in terms of optimization prob...
-
作者：Nouiehed, Maher; Pang, Jong-Shi; Razaviyayn, Meisam
作者单位：University of Southern California
摘要：With the increasing interest in applying the methodology of difference-of-convex (dc) optimization to diverse problems in engineering and statistics, this paper establishes the dc property of many functions in various areas of applications not previously known to be of this class. Motivated by a quadratic programming based recourse function in two-stage stochastic programming, we show that the (optimal) value function of a copositive (thus not necessarily convex) quadratic program is dc on the...
-
作者：Conforti, Michele; Wolsey, Laurence A.
作者单位：University of Padua; Universite Catholique Louvain
摘要：Given polyhedron P and and a point x* the separation problem for polyhedra asks to certify that x* is an element of P and if not, to determine an inequality that is satisfied by P and violated by x*. This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In this paper we address the problem of finding efficiently an inequality that is violated by x and either defin...
-
作者：Kim, Do Sang; Tien-Son Pham; Nguyen Van Tuyen
作者单位：Pukyong National University; Hanoi Pedagogical University 2 (HPU2)
摘要：We are interested in the existence of Pareto solutions to the vector optimization problem where f:Rn -> Rm is a polynomial map. By using the tangency variety of f we first construct a semi-algebraic set of dimension at most m-1 containing the set of Pareto values of the problem. Then we establish connections between the Palais-Smale conditions, M-tameness, and properness for the map f. Based on these results, we provide some sufficient conditions for the existence of Pareto solutions of the pr...
-
作者：Quoc Tran-Dinh; Sun, Tianxiao; Lu, Shu
作者单位：University of North Carolina; University of North Carolina Chapel Hill
摘要：We study a class of monotone inclusions called self-concordant inclusion which covers three fundamental convex optimization formulations as special cases. We develop a new generalized Newton-type framework to solve this inclusion. Our framework subsumes three schemes: full-step, damped-step, and path-following methods as specific instances, while allows one to use inexact computation to form generalized Newton directions. We prove the local quadratic convergence of both full-step and damped-st...
-
作者：Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey
作者单位：Princeton University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; Northwestern University; Carnegie Mellon University
摘要：Existing nonconvex statistical optimization theory and methods crucially rely on the correct specification of the underlying true statistical models. To address this issue, we take a first step towards taming model misspecification by studying the high-dimensional sparse phase retrieval problem with misspecified link functions. In particular, we propose a simple variant of the thresholded Wirtinger flow algorithm that, given a proper initialization, linearly converges to an estimator with opti...
-
作者：Adams, Warren; Gupte, Akshay; Xu, Yibo
作者单位：Clemson University
摘要：Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of . This implies additive error bounds for relaxing a polynomial optimization problem by convexifying each monomial separately. Our main error bounds dep...
-
作者：Roosta-Khorasani, Farbod; Mahoney, Michael W.
作者单位：University of Queensland; University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：For large-scale finite-sum minimization problems, we study non-asymptotic and high-probability global as well as local convergence properties of variants of Newton's method where the Hessian and/or gradients are randomly sub-sampled. For Hessian sub-sampling, using random matrix concentration inequalities, one can sub-sample in a way that second-order information, i.e., curvature, is suitably preserved. For gradient sub-sampling, approximate matrix multiplication results from randomized numeri...
-
作者：Necoara, I.; Nesterov, Yu.; Glineur, F.
作者单位：National University of Science & Technology POLITEHNICA Bucharest; Universite Catholique Louvain
摘要：The standard assumption for proving linear convergence of first order methods for smooth convex optimization is the strong convexity of the objective function, an assumption which does not hold for many practical applications. In this paper, we derive linear convergence rates of several first order methods for solving smooth non-strongly convex constrained optimization problems, i.e. involving an objective function with a Lipschitz continuous gradient that satisfies some relaxed strong convexi...
