Table of Content

30 December 2025, Volume 13 Issue 4

Previous Issue   

Analyze Accelerated Mirror Descent via High-Resolution ODEs

Ya-Xiang Yuan, Yi Zhang

2025, 13(4):  873-899.  doi:10.1007/s40305-024-00542-3

Asbtract ( 189 )   PDF  

References | Related Articles | Metrics

Mirror descent, which can be seen as generalization of gradient descent for solving constrained optimization problem, has found a variety applications in many fields. As growing demand of solving high-dimensional constrained optimization problem, accelerated form of mirror descent has been proposed, along with its corresponding low-resolution ordinary differential equations (ODEs) framework has been studied. However, The low-resolution ODEs are unable to distinguish between Polyak’s heavy-ball method and Nesterov’s accelerated gradient method. This problem also arises with the low-resolution ODEs for accelerated mirror descent. To address this issue, we derive the high-resolution ODEs for accelerated mirror descent and propose a general Lyapunov function framework to analyze its convergence rates in both continuous time and discrete time. Furthermore, we demonstrate that the accelerated mirror descent can minimize the squared gradient norm at an inverse cubic rate by using the high-resolution ODEs framework. In the end, we extend the high-resolution ODEs framework for the accelerated mirror descent method to analyze the accelerated higher-order mirror descent and obtain finer convergence results.

Convexification for a Class of Global Optimization Problems with C^1,1 Functions

Qian Yan, Xin-Min Yang, Zhi-You Wu

2025, 13(4):  900-918.  doi:10.1007/s40305-023-00521-0

Asbtract ( 196 )   PDF  

References | Related Articles | Metrics

A general convexification method via domain transformation scheme is presented for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems with C^1,1 functions can be converted into equivalent convex optimization problems by using the proposed convexification method. Finally, an example is shown to illustrate how a monotone non-convex optimization problem can be transformed into an equivalent convex minimization problem.

Exact Vertex Migration Model of Graph Partitioning Based on Mixed 0-1 Linear Programming and Iteration Algorithm

Zheng-Xi Yang, Zhi-Peng Jiang, Wen-Guo Yang, Sui-Xiang Gao

2025, 13(4):  919-945.  doi:10.1007/s40305-023-00534-9

Asbtract ( 167 )   PDF  

References | Related Articles | Metrics

Graph partitioning problem is a classical NP-hard problem. The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning. The goal of graph partitioning is getting a partition with the least number of cut edges, while also satisfying the capacity limit of the partition. In this paper, an optimization model for vertex migration is proposed, considering the influence between neighboring vertices, so that the objective function value of the model is exactly equal to the amount of cut edge variation. The model is converted into a mixed 0–1 linear programming by introducing variables. Then, a heuristic iterative algorithm is designed, in which the mixed 0–1 linear programming model is transformed into a series of small-scale models that contain less integer variables. In the experiment, the method in this paper is simulated and compared with balanced label propagation methods and their related methods. The improvement effect of these methods based on three different initialization methods is analyzed. Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.

Some Properties of the Solution of the Extended Vertical Tensor Complementarity Problem

Li-Ming Li, Shi-Liang Wu, Cui-Xia Li

2025, 13(4):  946-965.  doi:10.1007/s40305-023-00531-y

Asbtract ( 41 )   PDF  

References | Related Articles | Metrics

In this paper, we introduce the extended vertical tensor complementarity problem and investigate the existence and uniqueness of its solution. We introduce several sets of special tensors and demonstrate their properties. We leverage the structure of tensors to obtain some properties of the solution of the extended vertical tensor complementarity problem. Furthermore, we use degree theory and the equivalent form of the minimum function to establish sufficient conditions for the existence and uniqueness of the solution of the extended vertical tensor complementarity problem, respectively.

On the Metric Resolvent: Nonexpansiveness, Convergence Rates and Applications

Feng Xue

2025, 13(4):  966-988.  doi:10.1007/s40305-023-00518-9

Asbtract ( 61 )   PDF  

References | Related Articles | Metrics

In this paper, we study the nonexpansive properties of metric resolvent and present the convergence analysis for the associated fixed-point iterations of both Banach-Picard and Krasnosel’ski$\breve{1}$–Mann types. A by-product of our expositions also extends the proximity operator and Moreau’s decomposition identity to arbitrary metric. It is further shown that many classes of the first-order operator splitting algorithms, including the alternating direction methods of multipliers, primal–dual hybrid gradient and Bregman iterations, can be expressed by the fixed-point iterations of a simple metric resolvent, and thus, the convergence can be easily obtained within this unified framework.

A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

Yang-He Liu, Ying-Zhe Xu, Cheng Lu, Zhi-Bin Deng

2025, 13(4):  989-1017.  doi:10.1007/s40305-023-00506-z

Asbtract ( 70 )   PDF  

References | Related Articles | Metrics

Complex quadratically constrained quadratic programs (QCQPs) with underlying acyclic graph structures have special interests in some important practical applications. In this paper, we propose a new second-order cone relaxation for complex QCQPs, and prove some sufficient conditions under which the proposed relaxation is tight. Then, based on the proposed second-order cone relaxation, a branch-and-bound algorithm is developed. The main feature of the proposed branch-and-bound algorithm is that some complex variables are selected with their bounds on modules or phase angles partitioned in the branching procedure. Numerical results indicate that the proposed branch-and-bound algorithm runs faster than Baron on randomly generated test instances, and is also effective in solving some publicly available test instances of optimal power flow problems.

Optimal Investment Strategies for DC Pension Plan with Administrative Fees and Return of Premiums Clauses Under the Heston Model

Jian Pan, Xiang-Ying Zhou

2025, 13(4):  1018-1047.  doi:10.1007/s40305-023-00505-0

Asbtract ( 104 )   PDF  

References | Related Articles | Metrics

In this paper, we study an optimal investment problem for a defined contribution (DC) pension plan with two administrative fees during the accumulation phase. In our model, the pension fund member contributes a predetermined amount of money as a premium and then the pension fund administrator invests the premium in a financial market to increase the value of the accumulation, where the financial market consists of a risk-free asset and a risky asset satisfied the Heston model. Besides, to protect the rights of pension fund members who die before retirement, we introduce a return of premiums clauses and use the Abraham De Moivre model to characterize the force of mortality. With the help of actuarial theory and Taylor expansion theorem, we formalize the problem as a continuous-time portfolio optimization problem. By applying the stochastic control method and variable change techniques, we derive closed-form expressions of optimal investment strategies and corresponding value functions under the power utility function and exponential utility function. Based on the closed-form expressions, we determine the equivalent administrative charges by equating the maximum terminal certainty equivalent that can be achieved under the two types of administrative charges and find out some relationships between the two charges under the same utility function. Finally, we provide numerical experiments to analyze the effects of some parameters on the optimal investment strategy, the value function and the relationship between the two equivalent administrative charges.

On the Existence of Solutions for Weak Nonlinear Bilevel Optimization Problems

Houda Keraoui, Fatima-Ezzahra Saissi, Abdelmalek Aboussoror

2025, 13(4):  1048-1065.  doi:10.1007/s40305-023-00515-y

Asbtract ( 65 )   PDF  

References | Related Articles | Metrics

In this paper,we are concernedwith aweak(pessimistic) nonlinear bilevel optimization problem. In a sequential setting, for such a problem, we provide sufficient conditions ensuring the existence of solutions via a regularization and the notion of variational convergence. Unlike the approaches adopted by Aboussoror and Loridan (J Math Anal Appl 254: 348-357, 2001) and Aboussoror (Adv Math Res 1: 83-92, 2002), our approach does not require convexity assumptions and gives an extension from the finite dimensional case to a general topological one. Moreover, it gives an improvement of the result given by Loridan and Morgan (in: Buhler et al. (ed) Operations Research Proceedings of the international Conference on Operations Research 90 in Vienna, Springer Verlag, Berlin 1992).

Properties Related with Conditional Expectation for a Non-homogeneous Poisson Process

Yu Wu, Bo Zeng

2025, 13(4):  1066-1082.  doi:10.1007/s40305-023-00527-8

Asbtract ( 92 )   PDF  

References | Related Articles | Metrics

In this paper, we study a non-homogeneous Poisson Process that generalizes the well-known Jelinski-Moranda (J-M) model, originally proposed as a predictive model for software failures. The process under investigation consists of a fixed number of identical independent Poisson arrival processes, each operating from a common starting point until its first arrival occurs. While numerous studies in the field of software reliability are built upon the J-M model, there is a dearth of existing literature that examines the properties of this generalized version beyond software reliability. Considering this process is very common in real-world scenarios situated within stochastic environments, our study focuses solely on its theoretical exploration of general mathematical properties. First we formally define it in two ways, and clarify its relationships with established models such as continuous-time Markov Chain, Markov process and Markov Arrival Process by constructing it as a special case. Then, within the framework of Poisson process, we delve into an analysis of specific properties related to conditional expectations, with our primary contribution being in the computation of expected conditional arrival times.

HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems

Jian-Feng Liu, Zi-Hao Wang, Wei Zhang, Chao-Rui Zhang, Jian-Feng Hou, Bo Bai, Gong Zhang

2025, 13(4):  1083-1107.  doi:10.1007/s40305-023-00507-y

Asbtract ( 257 )   PDF  

References | Related Articles | Metrics

Recently, learned heuristics have been widely applied to solve combinatorial optimization problems (e.g., traveling salesman problem (TSP)). However, the scalability of these learning-based methods hinders the applications in practical scenarios. Specifically, models pre-trained on the small-scale data generalize poorly to large-scale problems. Moreover, learning the heuristics directly for large-scale problems costs tremendous time and space. To extend the scalability of learned heuristics on TSP, we propose a Hierarchical neural framework for solving large-scale traveling salesman problems (HiTSPs) based on a divide-and-conquer strategy. In particular, the HiTSP framework first divides the large-scale problem into small-scale subproblems by node clustering. Each subproblem is conquered by a modified pointer network learned from reinforcement learning. The tour of the original TSP is constructed by linking solutions of subproblems and optimized by a novel segmented local search algorithm. Notably, the segmented local search algorithm leverages the node clustering information to prune many unnecessary operations and significantly reduces the complexity in theory. Extensive experiments show that HiTSP outperforms state-of-the-art learning-based methods and Google OR-Tools in large-scale cases. Moreover, compared to the best heuristic algorithms, HiTSP has a significant advantage in efficiency for large-scale TSP problems.

Computation over t-Product Based Tensor Stiefel Manifold: A Preliminary Study

Xian-Peng Mao, Ying Wang, Yu-Ning Yang

2025, 13(4):  1108-1156.  doi:10.1007/s40305-023-00522-z

Asbtract ( 112 )   PDF  

References | Related Articles | Metrics

Let $*$ denote the t -product between two third-order tensors proposed by Kilmer and Martin (Linear Algebra Appl 435(3): 641-658, 2011). The purpose of this work is to study fundamental computation over the set $\operatorname{St}(n, p, l):=\left\{\mathcal{X} \in \mathbb{R}^{n \times p \times l} \mid \mathcal{X}^{\top} * \mathcal{X}=\right. \mathcal{I}\}$, where $\mathcal{X}$ is a third-order tensor of size $n \times p \times l(n \geqslant p)$ and $\mathcal{I}$ is the identity tensor. It is first verified that St ( $n, p, l$) endowed with the Euclidean metric forms a Riemannian manifold, which is termed as the (third-order) tensor Stiefel manifold in this work. We then derive the tangent space, Riemannian gradient, and Riemannian Hessian on St ($n, p, l$). In addition, formulas of various retractions based on t-QR, t-polar decomposition, t-Cayley transform, and t-exponential, as well as vector transports, are presented. It is expected that analogous to their matrix counterparts, the derived formulas may serve as building blocks for analyzing optimization problems over the tensor Stiefel manifold and designing Riemannian algorithms.

Scheduling Games with Potential Penalties on the Move of Jobs

Zhu-Yi-Nan Wang, Chen Zhang, Zhi-Yi Tan

2025, 13(4):  1157-1180.  doi:10.1007/s40305-023-00501-4

Asbtract ( 158 )   PDF  

References | Related Articles | Metrics

This paper studies scheduling games with potential penalties on the move of jobs. There are a set of machines and a set of jobs. Each job could choose one machine and be processed by the chosen one. Jobs that try to change their original choice will incur additional costs, which is proportional to its processing time with proportional parameter $\delta \geqslant 0$. A schedule is a $\delta$-NE if no job has the incentive to change its choice unilaterally. The $\delta$-NE is a generation of Nash equilibrium, and its inefficiency can be measured by the $\delta$-PoA, which is also a generalization of the Price of Anarchy. For the game with the social cost of minimizing the makespan, the exact $\delta$-PoA for any number of machines and any $\delta \geqslant 0$ is obtained. For the game with the social cost of maximizing the minimum machine load, an upper bound on the $\delta$-PoA is presented, and tight bounds are given for $2 \leqslant m \leqslant 11$ and any $\delta \geqslant 0$, where $m$ is the number of machines.

Stability Analysis of a Car-Following Model with Effect of Driver’s Memory Delay in Connected Vehicle Environment

Wen-Ju Du, Yin-Zhen Li, Jian-Gang Zhang

2025, 13(4):  1181-1204.  doi:10.1007/s40305-023-00508-x

Asbtract ( 83 )   PDF  

References | Related Articles | Metrics

The paper investigated the stability of a car-following model with the effect of driver’s memory delay on the basis of synchronization theory of complex network with time delay in connected vehicle environment. By using the Lyapunov stability theory and designing the appropriate controller, the car-following model with the effect of driver’s memory delay is quickly stabilized and the stability condition of the model is obtained. Besides, based on the adaptive H_∞ synchronization theory for complex networks with time delay, the stability of car-followingmodel with the effect of driver’smemory delay is studied when the vehicles are subjected to random external disturbance. Finally, the numerical simulation is carried out by using MATLAB simulation technology; the results show that the car-following model with the effect of driver’s memory delay is rapidly stabilizing and congestion phenomenon is effectively alleviated under the controller designed.

On Forcibly k-Connected Uniform Hypergraphic Sequences

Xue-Mei Liu, Ji-Xiang Meng, Ying-Zhi Tian

2025, 13(4):  1205-1215.  doi:10.1007/s40305-023-00509-w

Asbtract ( 83 )   PDF  

References | Related Articles | Metrics

For two nondecreasing sequences $d=\left(d_1, d_2, \cdots, d_n\right)$ and $d^{\prime}=\left(d_1^{\prime}, d_2^{\prime}, \cdots, d_n^{\prime}\right)$ of nonnegative integers, we say that $d^{\prime}$ majorizes $d$, denoted by $d^{\prime} \geqslant d$, if $d_i^{\prime} \geqslant d_i$ for $1 \leqslant i \leqslant n$. An $r$-uniform hypergraphic sequence $d=\left(d_1, d_2, \cdots, d_n\right)$ is forcibly $k$-connected if every $r$-uniform hypergraph with degree sequence $d$ is $k$-connected. In this paper, we give a sufficient condition for an $r$-uniform hypergraphic sequence to be forcibly $k$-connected and observe that if an $r$-uniform hypergraphic sequence $d$ satisfies the condition (which implies $d$ is forcibly $k$-connected); then, any $r$-uniform hypergraphic sequence $d^{\prime} \geqslant d$ also satisfies the condition. As a corollary, we obtain the condition of Bondy for forcibly $k$-connected graphic sequences.

Revisit the Coloring Problem of Gallai Graphs

Qiu-Lan Zhao, Jin-Jiang Yuan

2025, 13(4):  1216-1225.  doi:10.1007/s40305-023-00510-3

Asbtract ( 81 )   PDF  

References | Related Articles | Metrics

Given a graph $G=(V, E)$, the Gallai graph of $G$, denoted by $\Gamma(G)$, is the graph with vertex set $E$ in which two edges $e$ and $f$ of $G$ are adjacent in $\Gamma(G)$ iff $e$ and $f$ are adjacent in $G$ but do not span a triangle in $G$. The Gallai chromatic number of $G$, denoted by $\chi^{\Gamma}(G)$, is defined to be the chromatic number of $\Gamma(G)$. It is known that the problem for determining $\chi^{\Gamma}(G)$ is NP-complete for a general graph $G$. In this paper, we study the Gallai chromatic number of graphs and relate our research with some parameters about edge coloring of graphs, such as PC number, SPC number, as well as chromatic index. For the $(k, r)$-star, we determine its PC number, SPC number, Gallai chromatic number, and chromatic index, and show that these parameters differ considerably in a sense. Then we show that the problem for determining $\chi^{\Gamma}(G)$ is still NP-complete even when $G$ is a 3-regular graph, a near-complete graph or a chordal graph of diameter 5 . Our result also implies that the problem for determining the SPC number of a graph $G$ is NP-complete when $G$ is a chordal graph of diameter 5.

Global Optimization for the Portfolio Selection Model with High-Order Moments

Liu Yang, Yi Yang, Su-Han Zhong

2025, 13(4):  1226-1247.  doi:10.1007/s40305-023-00519-8

Asbtract ( 70 )   PDF  

References | Related Articles | Metrics

In this paper, we study the global optimality of polynomial portfolio optimization (PPO). The PPO is a kind of portfolio selection model with high-order moments and flexible risk preference parameters. We introduce a perturbation sample average approximation method, which can give a robust approximation of the PPO in form of linear conic optimization. The approximated problem can be solved globally with Moment-SOS relaxations. We summarize a semidefinite algorithm, which can be used to find reliable approximations of the optimal value and optimizer set of the PPO. Numerical examples are given to show the efficiency of the algorithm.