-
作者：Sen, Buse; Akkaya, Deniz; Pinar, Mustafa c.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Ihsan Dogramaci Bilkent University
摘要：We consider the problem of mean-variance portfolio selection regularized with an & ell;0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _0$$\end{document}-penalty term to control the sparsity of the portfolio. We analyze the structure of local and global minimizers and use our results in the design of a Branch...
-
作者：Alcantara, Jan Harold; Nguyen, Chieu Thanh; Okuno, Takayuki; Takeda, Akiko; Chen, Jein-Shan
作者单位：RIKEN; Vietnam National University of Agriculture (VNUA); Seikei University; University of Tokyo; National Taiwan Normal University
摘要：Strongly motivated from applications in various fields including machine learning, the methodology of sparse optimization has been developed intensively so far. Especially, the advancement of algorithms for solving problems with nonsmooth regularizers has been remarkable. However, those algorithms suppose that weight parameters of regularizers, called hyperparameters hereafter, are pre-fixed, but it is a crucial matter how the best hyperparameter should be selected. In this paper, we focus on ...
-
作者：Eberle, Franziska; Gupta, Anupam; Megow, Nicole; Moseley, Benjamin; Zhou, Rudy
作者单位：Technical University of Berlin; New York University; University of Bremen; Carnegie Mellon University
摘要：The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple possible configurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the makespan: the load of the most-loaded resource. In the stochastic setting, the amount by which a ...
-
作者：Wang, Guanghui; Hu, Zihao; Gentile, Claudio; Muthukumar, Vidya; Abernethy, Jacob
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated; Hong Kong University of Science & Technology
摘要：First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective that has multiple global optima. This phenomenon, known as implicit bias, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that in separable binary classification tasks gradient-descent-based methods exhibit an implicit bias for the & ell;2\documentclass[12pt]{minimal} \usepac...
-
作者：Balogh, Janos; Cohen, Ilan Reuven; Epstein, Leah; Levin, Asaf
作者单位：Szeged University; Bar Ilan University; University of Haifa; Technion Israel Institute of Technology
摘要：In this work, we consider online d-dimensional vector bin packing. For this problem, it is known that no algorithm can have a competitive ratio of o(d/log2d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(d/\log <^>2 d)$$\end{document} in the absolute sense, although upper bounds for it are typically presented in...
-
作者：Lovitz, Benjamin; Johnston, Nathaniel
作者单位：Northeastern University; Mount Allison University
摘要：We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS....
-
作者：Cornuejols, Gerard; Dubey, Yatharth
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this note, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis by streamlining the definition of branch-and-bound. We introduce skewed k-trees which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also give an example where lift-and-project does very well and branch-and-bound does not. Finally, we study the set of branc...
-
作者：He, Chang; Jiang, Yuntian; Zhang, Chuwen; Ge, Dongdong; Jiang, Bo; Ye, Yinyu
作者单位：Shanghai University of Finance & Economics; Shanghai Jiao Tong University; Stanford University
摘要：This paper proposes a homogeneous second-order descent framework (HSODF) for nonconvex and convex optimization based on the generalized homogeneous model (GHM). In comparison to the Newton steps, the GHM can be solved by extremal symmetric eigenvalue procedures and thus grant an advantage in ill-conditioned problems. Moreover, GHM extends the ordinary homogeneous model (Zhang et al. A homogenous second-order descent method for nonconvex optimization, 2022. arXiv:2211.08212 [math]) to allow ada...
-
作者：Feng, Fuxiaoyue; Ding, Chao; Li, Xudong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Fudan University
摘要：We introduce a quadratically convergent semismooth Newton method for nonlinear semidefinite programming that eliminates the need for the generalized Jacobian regularity, a common yet stringent requirement in existing approaches. Our strategy involves identifying a single nonsingular element within the Bouligand generalized Jacobian, thus avoiding the standard requirement for nonsingularity across the entire generalized Jacobian set, which is often too restrictive for practical applications. Th...
-
作者：Poremba, Joseph; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely dire...
