-
作者：Houska, Boris; Chachuat, Benoit
作者单位：ShanghaiTech University; Imperial College London
摘要：We propose a complete-search algorithm for solving a class of non-convex, possibly infinite-dimensional, optimization problems to global optimality. We assume that the optimization variables are in a bounded subset of a Hilbert space, and we determine worst-case run-time bounds for the algorithm under certain regularity conditions of the cost functional and the constraint set. Because these run-time bounds are independent of the number of optimization variables and, in particular, are valid fo...
-
作者：Doss, Charles R.
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：We propose a likelihood ratio statistic for forming hypothesis tests and confidence intervals for a nonparametrically estimated univariate regression function, based on the shape restriction of concavity (alternatively, convexity). Dealing with the likelihood ratio statistic requires studying an estimator satisfying a null hypothesis, that is, studying a concave least-squares estimator satisfying a further equality constraint. We study this null hypothesis least-squares estimator (NLSE) here, ...
-
作者：Jofre, Alejandro; Thompson, Philip
作者单位：Universidad de Chile; Universidad de Chile
摘要：We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound sigma(2) on its variance (OUBV). Differently, we assume an oracle with multiplicative noise. This rarely addressed setup is more aggressive but realistic, where the variance may not be uniformly bounded. Our met...
-
作者：Chen, Yuxin; Chi, Yuejie; Fan, Jianqing; Ma, Cong
作者单位：Princeton University; Carnegie Mellon University; Princeton University
摘要：This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x?Rn from m quadratic equations/samples yi=(ai?x?)2,1im. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descentwhen randomly initializedyields a...
-
作者：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...
