检索结果-内蒙古大学图书馆

Comparing the p-independence number of regular graphs to the q-independence number of their line graphs

学校读者我要写书评

暂无评论

Discrete applied mathematics 2025年 373卷 316-326页

作者： Caro, Yair Davila, Randy Pepper, Ryan Department of Mathematics University of Haifa–Oranim Tivon36006 Israel Department of Computational Applied Mathematics & Operations Research Rice University HoustonTX77005 United States Department of Mathematics and Statistics University of Houston–Downtown HoustonTX77002 United States

Let G be a simple graph and let L(G) denote the line graph of G. A p-independent set in G is a set of vertices S⊆V(G) such that the subgraph induced by S has maximum degree at most p. The p-independence number of G, denoted by αp(G), is the cardinality of a maximum p-independent set in G. In this paper, and motivated by the recent result that independence number is at most matching number for regular graphs Caro et al., (2022), we investigate which values of the non-negative integers p, q, and r have the property that αp(G)≤αq(L(G)) for all r-regular graphs. Triples (p,q,r) having this property are called valid α-triples. Among the results we prove are: • (p,q,r) is valid α-triple for p≥0, q≥3, and r≥2. • (p,q,r) is valid α-triple for p≤q © 2025 Elsevier B.V.

关键词： Number theory

Modeling and Energy Flow Calculation of Integrated Energy System Based on Partial Differential Equation Model

学校读者我要写书评

暂无评论

Strategic Planning for Energy and the Environment 2024年第4期43卷 979-1006页

作者： Xu, Xiaofeng Department of Computational Applied Mathematics and Operations Research Rice University Houston77005 United States

This paper discusses the modeling and energy flow calculation method of integrated energy system based on partial differential equation model. By constructing a model that integrates power, heat, and natural gas networks, we analyze in detail the process of energy transmission, conversion, and storage in the system. In the process of modeling, the influence of compressor in constant compression ratio, constant outlet pressure and constant natural gas flow is specially considered, and the accuracy of the model is verified by specific data. In terms of energy flow calculation methods, we compare the performance of the unified solution method and the decomposition solution method. Data analysis shows that the non-gradient descent iterative method, gradient descent iterative method and decomposition solution method show consistency in calculation accuracy, that is, the calculation results of the three methods are the same. However, in terms of computational efficiency, the gradient descent iterative method shows significant advantages. Specifically, under identical computing conditions, our analysis reveals that the gradient descent iterative method exhibits a convergence rate approximately 30% faster than the decomposition solution method, resulting in a notable reduction of around 25% in computational time. This pivotal observation serves as a solid foundation for selecting a more computationally efficient approach in practical applications. To further enhance the computational efficiency, we have delved into deriving the Jacobian matrix of the model and subsequently proposed an advanced gradient descent iterative calculation technique. Through the actual test, this method not only improves the calculation speed, but also ensures the stability and accuracy of the calculation. The research in this paper not only provides a strong theoretical support for the optimal operation of the integrated energy system, but also provides a valuable reference for future research in

关键词： Jacobian matrices

On the convergence of projected alternating maximization for equitable and optimal transport

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research

The Journal of Machine Learning research 2024年第1期25卷 16456-16488页

作者： Minhui Huang Shiqian Ma Lifeng Lai Department of Electrical and Computer Engineering University of California Davis CA Department of Computational Applied Mathematics and Operations Research Rice University Houston TX

This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, (Scetbon et al., 2021) suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.

关键词： equitable and optimal transport fairness saddle point problem projected alternating maximization block coordinate descent acceleration rounding

An Energy Stable High-Order Cut Cell Discontinuous Galerkin Method with State Redistribution for Wave Propagation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Taylor, Christina G. Wilcox, Lucas Chan, Jesse Department of Computational Applied Mathematics and Operations Research Rice University United States Department of Applied Mathematics Naval Postgraduate School

Cut meshes are a type of mesh that is formed by allowing embedded boundaries to "cut" a simple underlying mesh resulting in a hybrid mesh of cut and standard elements. While cut meshes can allow complex boundaries to be represented well regardless of the mesh resolution, their arbitrarily shaped and sized cut elements can present issues such as the small cell problem, where small cut elements can result in a severely restricted CFL condition. State redistribution, a technique developed by Berger and Giuliani [1], can be used to address the small cell problem. In this work, we pair state redistribution with a high-order discontinuous Galerkin scheme that is L2 energy stable for arbitrary quadrature. We prove that state redistribution can be added to a provably L2 energy stable discontinuous Galerkin method on a cut mesh without damaging the scheme’s L2 stability. We numerically verify the high order accuracy and stability of our scheme on two-dimensional wave propagation problems. Copyright © 2024, The Authors. All rights reserved.

关键词： Wave propagation

Riemannian Bilevel Optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Jiaxiang Ma, Shiqian Department of Electrical and Computer Engineering University of Minnesota Twin Cities United States Department of Computational Applied Math and Operations Research Rice University United States

In this work, we consider the bilevel optimization problem on Riemannian manifolds. We inspect the calculation of the hypergradient of such problems on general manifolds and thus enable the utilization of gradient-based algorithms to solve such problems. The calculation of the hypergradient requires utilizing the notion of Riemannian cross-derivative and we inspect the properties and the numerical calculations of Riemannian cross-derivatives. Algorithms in both deterministic and stochastic settings, named respectively RieBO and RieSBO, are proposed that include the existing Euclidean bilevel optimization algorithms as special cases. Numerical experiments on robust optimization on Riemannian manifolds are presented to show the applicability and efficiency of the proposed *** Codes 90C26 Copyright © 2024, The Authors. All rights reserved.

关键词： Numerical methods

MEAN FIELD GAMES WITH COMMON NOISE VIA MALLIAVIN CALCULUS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Tangpi, Ludovic Wang, Shichun Princeton University Department of Operations Research and Financial Engineering and Program in Computational and Applied Mathematics United States

We present a simpler proof of the existence of equilibria for a class of mean field games with common noise, where players interact through the conditional law given the current value of the common noise rather than its entire path. By extending a compactness criterion for Malliavin-differentiable random variables to processes, we establish existence of strong equilibria, where the conditional law and optimal control are adapted to the common noise filtration and defined on the original probability space. Notably, our approach only requires measurability of the drift and cost functionals with respect to the state *** Codes 91A16, 60H07 Copyright © 2024, The Authors. All rights reserved.

关键词： Cost functions

Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Lyu, Bochuan Hicks, Illya V. Rice University Department of Computational Applied Mathematics and Operations Research United States

The biclique cover number (bc) of a graph G denotes the minimum number of complete bipartite (biclique) subgraphs to cover all the edges of the graph. In this paper, we show that bc(G) ≥ ⌈log2(mc(Gc))⌉ ≥ ⌈log2(χ(G))⌉ for an arbitrary graph G, where χ(G) is the chromatic number of G and mc(Gc) is the number of maximal cliques of the complementary graph Gc, i.e., the number of maximal independent sets of G. We also show that ⌈log2(mc(Gc))⌉ could be a strictly tighter lower bound of the biclique cover number than other existing lower bounds. We can also provide a bound of bc(G) with respect to the biclique partition number (bp) of G: bc(G) ≥ ⌈log2(bp(G) + 1)⌉ or bp(G) ≤ 2bc(G) − 1 if G is co-chordal. Furthermore, we show that bc(G) ≤ χ′r(TKc), where G is a co-chordal graph such that each vertex is in at most two maximal independent sets and χ′r(TKc) is the optimal edge-ranking number of a clique tree of GcMSC Codes 05C70 Copyright © 2023, The Authors. All rights reserved.

关键词： Trees (mathematics)

Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Yang, Yifan Ban, Hao Huang, Minhui Ma, Shiqian Ji, Kaiyi Department of Computer Science and Engineering University at Buffalo United States AI Research for Monetization Meta United States Department of Computational Applied Math and Operations Research Rice University United States

Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require (Equation presented) and (Equation presented) iterations to find an ϵ-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees. Copyright © 2024, The Authors. All rights reserved.

关键词： Optimization algorithms

Riemannian Proximal Sampler for High-accuracy Sampling on Manifolds

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Guan, Yunrui Balasubramanian, Krishnakumar Ma, Shiqian Department of Computational Applied Mathematics and Operations Research Rice University United States Department of Statistics University of California Davis United States

We introduce the Riemannian Proximal Sampler, a method for sampling from densities defined on Riemannian manifolds. The performance of this sampler critically depends on two key oracles: the Manifold Brownian Increments (MBI) oracle and the Riemannian Heat-kernel (RHK) oracle. We establish high-accuracy sampling guarantees for the Riemannian Proximal Sampler, showing that generating samples with Ε-accuracy requires O(log(1/Ε)) iterations in Kullback-Leibler divergence assuming access to exact oracles and O(log2(1/Ε)) iterations in the total variation metric assuming access to sufficiently accurate inexact oracles. Furthermore, we present practical implementations of these oracles by leveraging heat-kernel truncation and Varadhan’s asymptotics. In the latter case, we interpret the Riemannian Proximal Sampler as a discretization of the entropy-regularized Riemannian Proximal Point Method on the associated Wasserstein space. We provide preliminary numerical results that illustrate the effectiveness of the proposed methodology. © 2025, CC BY.

关键词： Numerical methods