-
作者：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...
-
作者：Leyffer, Sven; Manns, Paul
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; Dortmund University of Technology
摘要：McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state cons...
