-
作者：Fang, Yuchen; Lavaei, Javad; Na, Sen
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we consider nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method and establish its high-probability iteration complexity bounds for identifying first- and second-order & varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage...
-
作者：Kukharenko, Kirill; Sanita, Laura
作者单位：Otto von Guericke University; Bocconi University
摘要：The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solutio...
-
作者：Zhou, Jinling; Liu, Xin; Nie, Jiawang; Tang, Xindong
作者单位：Xiangtan University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of California System; University of California San Diego; Hong Kong Baptist University
摘要：This paper studies how to compute global minimizers of the cubic-quartic regularization (CQR) problem where f0 is a constant, g is an n-dimensional vector, H is an n-by-n symmetric matrix, and & Vert;s & Vert; denotes the Euclidean norm of s. The parameter sigma is nonnegative while beta can have any sign. The CQR problem arises as a critical subproblem for getting efficient regularization methods for solving unconstrained nonlinear optimization. Its properties are recently well studied by Car...
-
作者：Xiao, Nachuan; Hu, Xiaoyin; Toh, Kim-Chuan
作者单位：The Chinese University of Hong Kong, Shenzhen; Shenzhen University; National University of Singapore; National University of Singapore
摘要：In this paper, we focus on providing convergence guarantees for stochastic subgradient methods in minimizing nonsmooth nonconvex functions. We first investigate the global stability of a general framework for stochastic subgradient methods, where the corresponding differential inclusion admits a coercive Lyapunov function. We prove that, for any sequence of sufficiently small stepsizes and approximation parameters, coupled with sufficiently controlled noises, the iterates are uniformly bounded...
-
作者：Dey, Santanu S.; Khajavirad, Aida
作者单位：Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; Lehigh University
摘要：We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation-Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under which the convex hull of the feasible region of the lifted quadratic program is SOC-representable. While th...
-
作者：Comaneci, Andrei; Plastria, Frank
作者单位：Technical University of Berlin; Vrije Universiteit Brussel
摘要：We compute the robustness of Fermat-Weber points with respect to any finite gauge. We show a breakdown point of 1/(1+sigma)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1+\sigma )$$\end{document} where sigma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackag...
-
作者：Gallego, Guillermo; Segev, Danny
作者单位：The Chinese University of Hong Kong, Shenzhen; Tel Aviv University; Tel Aviv University
摘要：In the adaptive ProbeTopK problem, given a collection of mutually independent random variables X1,..., Xn, our goal is to design an adaptive probing policy to sample these variables in a sequence of T stages, with the objective ofmaximizing the expected sum of the K highest rewards sampled. In spite of its stylized formulation, this setting captures numerous technical hurdles inherent to stochastic optimization, related to both information structure and efficient computation. For these reasons...
-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Evens, Brecht; Pas, Pieter; Latafat, Puya; Patrinos, Panagiotis
作者单位：KU Leuven; IMT School for Advanced Studies Lucca
摘要：The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in th...
-
作者：Gao, Bin; Peng, Renfeng; Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：In the realm of tensor optimization, the low-rank Tucker decomposition is crucial for reducing the number of parameters and for saving storage. We explore the geometry of Tucker tensor varieties-the set of tensors with bounded Tucker rank-which is notably more intricate than the well-explored matrix varieties. We give an explicit parametrization of the tangent cone of Tucker tensor varieties and leverage its geometry to develop provable gradient-related line-search methods for optimization on ...
