Loading...

Table of Content

    30 June 2025, Volume 13 Issue 2
    Derivative-Free Optimization with Transformed Objective Functions and the Algorithm Based on the Least Frobenius Norm Updating Quadratic Model
    Peng-Cheng Xie, Ya-Xiang Yuan
    2025, 13(2):  327-363.  doi:10.1007/s40305-023-00532-x
    Asbtract ( 7 )  
    References | Related Articles | Metrics
    Derivative-free optimization (DFO) problems are optimization problems where the derivative information is unavailable. The least Frobenius norm updating quadratic interpolation model function is one of the essential under-determined model functions for model-based derivative-free trust-region methods. This article proposes derivative-free optimization with transformed objective functions (DFOTO) and gives a model-based trust-region method with the least Frobenius norm model. The model updating formula is based on Powell’s formula and can be easily implemented. The method shares the same framework with those for problems without transformations, and its query scheme is given. We propose the definitions related to optimality-preserving transformations to understand the interpolation model in our method when minimizing transformed objective functions. We prove the existence of model optimality-preserving transformations beyond translation transformations. The necessary and sufficient condition for such transformations is given. An interesting discovery is that, as a fundamental transformation, the affine transformation with a (non-trivial) positive multiplication coefficient is not model optimality-preserving. We also analyze the corresponding least Frobenius norm updating model and its interpolation error when the objective function is affinely transformed. The convergence property of a provable algorithmic framework containing the least Frobenius norm updating quadratic model for minimizing transformed objective functions is given. Numerical results show that our method can successfully solve most test problems with objective optimality-preserving transformations, even though some of such transformations will change the optimality of the model function. To our best knowledge, this is the first work providing the model-based derivative-free algorithm and analysis for transformed problems with the function evaluation oracle. This article also proposes the “moving-target” optimization problem as an open problem.
    Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization
    Hao-Yang Liu, Xian-Tao Xiao, Li-Wei Zhang
    2025, 13(2):  364-392.  doi:10.1007/s40305-023-00496-y
    Asbtract ( 11 )  
    References | Related Articles | Metrics
    In this paper, we consider online convex optimization (OCO) with time-varying loss and constraint functions. Specifically, the decision-maker chooses sequential decisions based only on past information; meantime, the loss and constraint functions are revealed over time. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO (without feedback delay). Under standard assumptions, we establish sublinear regret and sublinear constraint violation of MALM. Furthermore, we extend MALM to deal with time-varying functional constrained OCO with delayed feedback, in which the feedback information of loss and constraint functions is revealed to decision-maker with delays. Without additional assumptions, we also establish sublinear regret and sublinear constraint violation for the delayed version of MALM. Finally, numerical results for several examples of constrained OCO including online network resource allocation, online logistic regression and online quadratically constrained quadratical program are presented to demonstrate the efficiency of the proposed algorithms.
    A Switching Time Optimization Strategy for Optimal Control Problems
    Yin Chen, Chang-Jun Yu, Xi Zhu
    2025, 13(2):  393-414.  doi:10.1007/s40305-023-00499-9
    Asbtract ( 4 )  
    References | Related Articles | Metrics
    The time-scaling transformation is a widely used approach within the computational framework of control parameterization for optimizing the switching times of control variables. However, the conventional time-scaling transformation has the limitation that the switching times and the number of switches for each control component must be the same. In this paper, we present a novel technique to solve constrained optimal control problems that allows for adaptively optimizing the switching times for each control component. Numerical results demonstrate that this proposed method provides better flexibility in control strategy and yields improved performance.
    ε-Quasi-Weakly Solution for Semi-infinite Vector Optimization Problems with Data Uncertainty
    Thanh-Hung Pham, Thanh-Sang Nguyen
    2025, 13(2):  415-439.  doi:10.1007/s40305-023-00489-x
    Asbtract ( 7 )  
    References | Related Articles | Metrics
    This paper is concerned with an ε-quasi-weakly solution for a semi-infinite vector optimization problem with data uncertainty in constraints by using the Clarke subdifferential. Both necessary and sufficient optimality conditions for a semi-infinite vector optimization problem with data uncertainty in constraints are established. We also investigate a Mond–Weir-type dual problem with respect to the primal problem. An application to a fractional semi-infinite vector optimization problem with data uncertainty in constraints is provided. Some examples are given to illustrate our results.
    Global Approximation of Local Optimality: Nonsubmodular Optimization
    Wei-Li Wu, Zhao Zhang, Ding-Zhu Du
    2025, 13(2):  440-451.  doi:10.1007/s40305-023-00475-3
    Asbtract ( 2 )  
    References | Related Articles | Metrics
    In the study of information technology, one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such problems raised in various areas of computer and information science. Usually, nonsubmodular optimization problems are NP-hard. Therefore, design and analysis of approximation algorithms are important tasks in the study of nonsubmodular optimizations. However, the traditional methods do not work well. Therefore, a new method, the global approximation of local optimality, is proposed recently. In this paper, we give an extensive study for this new methodology.
    A Note on "Flowshop Scheduling with Learning Effectand Job Rejection"
    Jin Yu, Pei-Hai Liu, Xi-Wen Lu
    2025, 13(2):  452-462.  doi:10.1007/s40305-023-00487-z
    Asbtract ( 8 )  
    References | Related Articles | Metrics
    In this note, we point out that the dynamic programming algorithms for the proportionate flowshop scheduling problems presented by Mor et al. (J Sched 23:61–641, 2020) are incorrect by counterexamples. Moreover, we propose new dynamic programming algorithms to solve the corresponding problems.
    On Ratio-k-Cuts of Graphs
    Bo Bai, Xiang Chen, Jian-Feng Hou, Gong Zhang
    2025, 13(2):  463-483.  doi:10.1007/s40305-023-00465-5
    Asbtract ( 6 )  
    References | Related Articles | Metrics
    Let G be a graph and \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} be a k-partition of G. For \begin{document}$ 1\leqslant i \lt j\leqslant k $\end{document}, the ratio of \begin{document}$ (V_i, V_j) $\end{document}, denoted by \begin{document}$ R(V_i, V_j) $\end{document}, is \begin{document}$ e(V_i, V_j)/(|V_i||V_j|) $\end{document}, where \begin{document}$ e(V_i,V_j) $\end{document} is the number of crossing edges. The minimum k-ratio of G, denoted by \begin{document}$ R_k(G) $\end{document}, is the minimum \begin{document}$ \sum _{1\leqslant i \lt j\leqslant k}R(V_i,V_j) $\end{document} over all k-partitions \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} of G. Let \begin{document}$ R(G)=R_2(G) $\end{document}. The ratio cut problem, posed by Wei and Cheng, and independently by Leighton and Rao, is an extension of the min-cut problem and has important applications in CAD. It is easy to see that \begin{document}$ R_k(G) $\end{document} is closely related to the density d(G) of a graph G. In this paper, we mainly give some results on \begin{document}$ R_k(G) $\end{document} with respect to d(G). First, we show that \begin{document}$ R_k(G)\leqslant {k \atopwithdelims ()2}(1+o(1))d(G) $\end{document} for graphs G and \begin{document}$ R_k(G)\leqslant (k-1)(1+o(1))d(G) $\end{document} for sparse graphs G. Then, we give some upper and lower bounds on R(G). In particular, we show \begin{document}$ R(G)\leqslant 4/(n-3) $\end{document} for every planar graph G with \begin{document}$ n\geqslant 4 $\end{document} vertices. At last, we consider the random graph G(n, p) and show that R(G(n, p)) can be determined asymptotically almost surely if \begin{document}$ p\geqslant C\log n/n $\end{document} for some constant \begin{document}$ C \gt 0 $\end{document}.
    Double-Factored Decision Theory for Markov Decision Processes with Multiple Scenarios of the Parameters
    Cheng-Jun Hou
    2025, 13(2):  484-514.  doi:10.1007/s40305-023-00457-5
    Asbtract ( 9 )  
    References | Related Articles | Metrics
    The double-factored decision theory for Markov decision processes with multiple scenarios of the parameters is proposed in this article. We introduce scenario belief to describe the probability distribution of scenarios in the system, and scenario expectation to formulate the expected total discounted reward of a policy. We establish a new framework named as double-factored Markov decision process (DFMDP), in which the physical state and scenario belief are shown to be the double factors serving as the sufficient statistics for the history of the decision process. Four classes of policies for the finite horizon DFMDPs are studied and it is shown that there exists a double-factored Markovian deterministic policy which is optimal among all policies. We also formulate the infinite horizon DFMDPs and present its optimality equation in this paper. An exact solution method named as double-factored backward induction for the finite horizon DFMDPs is proposed. It is utilized to find the optimal policies for the numeric examples and then compared with policies derived from other methods from the related literatures.
    Characterizing the Extremal k-Girth Graphs on Feedback Vertex Set
    Zhong-Zheng Tang, Zhuo Diao
    2025, 13(2):  515-534.  doi:10.1007/s40305-023-00483-3
    Asbtract ( 10 )  
    References | Related Articles | Metrics
    A feedback vertex set in a graph G is a vertex subset S such that \begin{document}$ G\setminus S $\end{document} is acyclic. The girth of a graph is the minimum cycle length in G. In this paper, some results are proven: (i) Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is \begin{document}$ K_{3} $\end{document} or \begin{document}$ K_{4} $\end{document}. (ii) Alon et al. (J Graph Theory 38:113–123, 2001) proved every connected triangle-free graph G has a feedback vertex set at most m/4. We prove the bound is tight if and only if G is 4-cycle, Square-Claw or Double-Squares. (iii) Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle. This result verifies the conjecture of Dross et al. (Discrete Appl Math 214:99–107, 2016) on outerplanar graph.
    Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints
    Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li
    2025, 13(2):  535-554.  doi:10.1007/s40305-023-00488-y
    Asbtract ( 10 )  
    References | Related Articles | Metrics
    In this paper, we address the k-Chinese postman problem under interdiction budget constraints (the k-CPIBC problem, for short), which is a further generalization of the k-Chinese postman problem and has many practical applications in real life. Specifically, given a weighted graph \begin{document}$ G=(V,E;w,c;v_{1}) $\end{document} equipped with a weight function \begin{document}$ w:E\rightarrow {\mathbb {R}}^{+} $\end{document} that satisfies the triangle inequality, an interdiction cost function \begin{document}$ c:E\rightarrow {\mathbb {Z}}^{+} $\end{document}, a fixed depot \begin{document}$ v_{1}\in V $\end{document}, an integer \begin{document}$ k\in {\mathbb {Z}}^{+} $\end{document} and a budget \begin{document}$ B\in {\mathbb {N}} $\end{document}, we are asked to find a subset \begin{document}$ S_{k}\subseteq E $\end{document} such that \begin{document}$ c(S_{k})=\sum _{e\in S_{k}}c(e)\leqslant B $\end{document} and that the subgraph \begin{document}$ G\backslash S_{k} $\end{document} is connected, the objective is to minimize the value \begin{document}$ \min _{\mathcal{C}_{E\backslash S_{k}}} \max \{w(C_{i})\,\vert \,C_{i}\in \mathcal{C}_{E\backslash S_{k}}\} $\end{document} among such all aforementioned subsets \begin{document}$ S_{k} $\end{document}, where \begin{document}$ \mathcal{C}_{E\backslash S_{k}} $\end{document} is a set of k-tours (of \begin{document}$ G\backslash S_{k} $\end{document}) starting and ending at the depot \begin{document}$ v_{1} $\end{document}, jointly traversing each edge in \begin{document}$ G\backslash S_{k} $\end{document} at least once, and \begin{document}$ w(C_{i})=\sum _{e\in C_{i}}w(e) $\end{document} for each tour \begin{document}$ C_{i}\in \mathcal{C}_{E\backslash S_{k}} $\end{document}. We obtain the following main results: (1) Given an \begin{document}$ \alpha $\end{document}-approximation algorithm to solve the minimization knapsack problem, we design an \begin{document}$ (\alpha +\beta ) $\end{document}-approximation algorithm to solve the k-CPIBC problem, where \begin{document}$ \beta $\end{document} \begin{document}$ = $\end{document} \begin{document}$ \frac{7}{2}-\frac{1}{k}-\lfloor \frac{1}{k}\rfloor $\end{document}. (2) We present a \begin{document}$ \beta $\end{document}-approximation algorithm to solve the special version of the k-CPIBC problem, where c(e) \begin{document}$ \equiv $\end{document} 1 for each edge e in G and \begin{document}$ \beta $\end{document} is defined in (1).
    Two-Disjoint-Cycle-Cover Pancyclicity of Augmented Cubes
    Shu-Jie Zhou, Min Xu
    2025, 13(2):  555-573.  doi:10.1007/s40305-023-00474-4
    Asbtract ( 12 )  
    References | Related Articles | Metrics
    A graph G is two-disjoint-cycle-cover \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic, if for any integer \begin{document}$ \ell $\end{document} satisfying \begin{document}$ r_{1} \leqslant \ell \leqslant r_{2} $\end{document}, there exist two vertex-disjoint cycles \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} in G such that the lengths of \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} are \begin{document}$ \ell $\end{document} and \begin{document}$ |V(G)|-\ell $\end{document}, respectively, where |V(G)| denotes the number of vertices in G. More specifically, a graph G is two-disjoint-cycle-cover vertex \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic (resp. edge \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic) if for any two distinct vertices \begin{document}$ u_{1}, u_{2} \in V(G) $\end{document} (resp. two vertex-disjoint edges \begin{document}$ e_{1}, e_{2} \in E(G) $\end{document}), there exist two vertex-disjoint cycles \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} in G such that for every integer \begin{document}$ \ell $\end{document} satisfying \begin{document}$ r_{1} \leqslant \ell \leqslant r_{2} $\end{document}, \begin{document}$ C_{1} $\end{document} contains \begin{document}$ u_{1} $\end{document} (resp. \begin{document}$ e_{1} $\end{document}) with length \begin{document}$ \ell $\end{document} and \begin{document}$ C_{2} $\end{document} contains \begin{document}$ u_{2} $\end{document} (resp. \begin{document}$ e_{2} $\end{document}) with length \begin{document}$ |V(G)|-\ell $\end{document}. In this paper, we consider the problem of two-disjoint-cycle-cover pancyclicity of the n-dimensional augmented cube \begin{document}$ AQ_n $\end{document} and obtain the following results: \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover \begin{document}$ [3,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}. Moreover, \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover vertex \begin{document}$ [3,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}, and \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover edge \begin{document}$ [4,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}.
    Using the minimum and maximum degrees to bound the diameter of orientations of bridgeless graphs
    Wan-Ping Zhang, Ji-Xiang Meng, Baoyindureng Wu
    2025, 13(2):  574-589.  doi:10.1007/s40305-023-00476-2
    Asbtract ( 7 )  
    References | Related Articles | Metrics
    The oriented diameter of an undirected graph G, denoted by \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document}, is defined as the minimum diameter of any strong orientation of G. In this paper, we prove that the oriented diameter of a bridgeless \begin{document}$ C_{4} $\end{document}-free graph is at most \begin{document}$ \frac{37n}{\delta ^2-2\lfloor \delta /2\rfloor +1}+19 $\end{document}. We also consider some upper bounds of \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document} in terms of girth g, minimum degree \begin{document}$ \delta $\end{document} and maximum degree \begin{document}$ \Delta $\end{document} and give some upper bounds of \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document} in bridgeless \begin{document}$ (C_{4},C_{5}) $\end{document}-free graphs.
    The Single-Machine Preemptive or Resumable Scheduling with Maintenance Intervals
    Ru-Yan He, Jin-Jiang Yuan, Yuan Zhang
    2025, 13(2):  590-602.  doi:10.1007/s40305-023-00495-z
    Asbtract ( 9 )  
    References | Related Articles | Metrics
    We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern, respectively, to minimize the total weighted late work and the weighted number of tardy jobs, respectively, where each job has a release date and a due date. According to the different combinations of the two scheduling patterns and the two scheduling criteria, six scheduling problems (including two Pareto-scheduling problems) are studied in this paper. We show that by modifying the release dates and the due dates, the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time. As a consequence, complexity results of our problems can be directly obtained from the known results in the literature. In particular, for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time 0, an \begin{document}$ O(m{n^2}{P}) $\end{document}-time algorithm was presented in the literature, where m is the number of maintenance intervals, n is the number of jobs, and P is the total processing time of the jobs; and our research shows that the same problem is solvable in \begin{document}$ O(n^{2}{P}+m\log m ) $\end{document} time, improving this known result.
    A Best Possible Online Algorithm For Parallel-Batch Scheduling with Kind Release Times and Job Compatibilities
    Li-Yun Miao, Ji Tian, Ru-Yan Fu
    2025, 13(2):  603-615.  doi:10.1007/s40305-023-00480-6
    Asbtract ( 5 )  
    References | Related Articles | Metrics
    We investigate the problem of the online scheduling with kind release times and job compatibilities on a single unbounded parallel-batch machine to minimize makespan. The kind release times (KRT) means that under the online setting no jobs can be released when the machine is busy. What associated with each job \begin{document}$ J_{j} $\end{document} are its normal processing time \begin{document}$ p_j $\end{document} and release time \begin{document}$ r_j $\end{document}. Two jobs \begin{document}$ J_i $\end{document} and \begin{document}$ J_j $\end{document} are called compatible if \begin{document}$ \max \{p_i, p_j\} \leqslant (1+a) \min \{p_i, p_j\} $\end{document}, where a is a given positive constant. Compatible jobs could be processed in the same batch. We derive a best possible online algorithm with a competitive ratio of \begin{document}$ 1+\sqrt{\lambda ^{2}-\lambda +1}-\lambda $\end{document}, where \begin{document}$ \lambda =\frac{a}{1+a} $\end{document}.
    A Penalty Function Approach for Solving the Linear Trilevel Programming Problem
    Yan Peng, Yi-Bing Lv
    2025, 13(2):  616-629.  doi:10.1007/s40305-023-00464-6
    Asbtract ( 6 )  
    References | Related Articles | Metrics
    In this paper, we mainly focus on the solving approach for the linear trilevel programming (LTP) problem. Firstly, based on the lower-level problem’s Karush-Kuhn-Tucker (K-K-T) optimality conditions, we transform the LTP problem into a bilevel programming (BP) problem with complementary constraints. Secondly, taking the complementary constraints as penalties and appending them to the upper-level objective, a penalized BP problem is obtained. Thirdly, for the penalized BP problem, we use K-K-T optimality conditions again and append the corresponding complementary conditions to the upper level as penalties. Then, an overall penalized problem for the LTP problem is formed; we analyze the characteristics of the optimal solutions of the overall penalized problem and propose a penalty function algorithm. The numerical results show that the penalty function approach is feasible and effective.
    A Strong Convergence Result for Solving Split Variational Inequality Problem
    Jun Yang
    2025, 13(2):  630-649.  doi:10.1007/s40305-023-00482-4
    Asbtract ( 9 )  
    References | Related Articles | Metrics
    The purpose of this work is to investigate a new projection and contraction algorithm for solving split variational inequality problem. The strong convergence of the algorithm is established without the knowledge of the Lipschitz constants and the bounded linear operator norm. Finally, we consider some preliminary numerical experiments to show the advantages of proposed algorithm.
    Tight Toughness, Isolated Toughness and Binding Number Bounds for the {K2, Cn}-Factors
    Xia-Xia Guan, Tian-Long Ma, Chao Shi
    2025, 13(2):  650-659.  doi:10.1007/s40305-023-00485-1
    Asbtract ( 9 )  
    References | Related Articles | Metrics
    The \begin{document}$ \{K_2,C_n\} $\end{document}-factor of a graph is a spanning subgraph whose each component is either \begin{document}$ K_2 $\end{document} or \begin{document}$ C_n $\end{document}. In this paper, a sufficient condition with regard to tight toughness, isolated toughness and binding number bounds to guarantee the existence of the \begin{document}$ \{K_2,C_{2i+1}| i\geqslant 2 \} $\end{document}-factor for any graph is obtained, which answers a problem due to Gao and Wang (J Oper Res Soc China, 2021. https://doi.org/10.1007/s40305-021-00357-6).
    The mixed-strategy α-core of games with infinitely many pure strategies
    Neng-Fa Wang, Zhe Yang
    2025, 13(2):  660-670.  doi:10.1007/s40305-023-00497-x
    Asbtract ( 6 )  
    References | Related Articles | Metrics
    Inspired by Scarf (J Econ Theory 3:169–181, 1971) and Kajii (J Econ Theory 56:194–205, 1992), we introduce the notion of mixed-strategy α-core for games with infinitely many pure strategies. We first show the nonemptiness of the mixed-strategy α-core for normal-form games with infinitely many pure strategies and obtain the generic continuity property of the mixed-strategy α-core correspondence. Furthermore, we prove the existence of the mixed-strategy α-core for games with nonordered preferences and infinitely many pure strategies and show the generic continuity property of the mixed-strategy α-core correspondence.
    Atomic Dynamic Routing Games with Multiple Destinations
    Chang-Jun Wang
    2025, 13(2):  671-683.  doi:10.1007/s40305-023-00500-5
    Asbtract ( 5 )  
    References | Related Articles | Metrics
    In this paper, we study atomic dynamic routing games with multiple destinations. We first show that if the first-in–first-out (FIFO) principle is always fulfilled locally to regulate the congestion, then most probably we cannot guarantee the existence of any reasonable approximate Nash equilibrium. By partly discarding the FIFO principle and introducing destination priorities in the regulation rules, we propose a new atomic routing model. In each such game, we prove that a pure strategy Nash equilibrium always exists and can be computed in polynomial time. In addition, the multicommodity routing game can be iteratively decomposed into a series of well-behaved single-destination routing games, which will provide a good characterization of all NEs of the original game.