Table of Content

30 December 2024, Volume 12 Issue 4

Previous Issue   

Low Rank Tensor Decompositions and Approximations

Jiawang Nie, Li Wang, Zequn Zheng

2024, 12(4):  847-873.  doi:10.1007/s40305-023-00455-7

Asbtract ( 355 )   PDF  

References | Related Articles | Metrics

There exist linear relations among tensor entries of low rank tensors. These linear relations can be expressed by multi-linear polynomials, which are called generating polynomials. We use generating polynomials to compute tensor rank decompositions and low rank tensor approximations. We prove that this gives a quasi-optimal low rank tensor approximation if the given tensor is sufficiently close to a low rank one.

Polar Decomposition-based Algorithms on the Product of Stiefel Manifolds with Applications in Tensor Approximation

Jian-Ze Li, Shu-Zhong Zhang

2024, 12(4):  874-920.  doi:10.1007/s40305-023-00462-8

Asbtract ( 358 )   PDF  

References | Related Articles | Metrics

In this paper, we propose a general algorithmic framework to solve a class of optimization problems on the product of complex Stiefel manifolds based on the matrix polar decomposition. We establish the weak convergence, global convergence and linear convergence properties, respectively, of this general algorithmic approach using the Łojasiewicz gradient inequality and the Morse-Bott property. This general algorithmic approach and its convergence results are applied to the simultaneous approximate tensor diagonalization problem and the simultaneous approximate tensor compression problem, which include as special cases the low rank orthogonal approximation, best rank-1 approximation and low multilinear rank approximation for higher order complex tensors. We also present a variant of this general algorithmic framework to solve a symmetric version of this class of optimization models, which essentially optimizes over a single Stiefel manifold. We establish its weak convergence, global convergence and linear convergence properties in a similar way. This symmetric variant and its convergence results are applied to the simultaneous approximate symmetric tensor diagonalization, which includes as special cases the low rank symmetric orthogonal approximation and best symmetric rank-1 approximation for higher order complex symmetric tensors. It turns out that well-known algorithms such as LROAT, S-LROAT, HOPM and S-HOPM are all special cases of this general algorithmic framework and its symmetric variant, and our convergence results subsume the results found in the literature designed for those special cases. All the algorithms and convergence results in this paper are straightforwardly applicable to the real case.

A New Class of Filled Functions with Two Parameters for Solving Unconstrained Global Optimization Problems

Qiao Chen, Xin-Min Yang, Qian Yan

2024, 12(4):  921-936.  doi:10.1007/s40305-024-00548-x

Asbtract ( 364 )   PDF  

References | Related Articles | Metrics

A new class of filled functions for escaping the current local minimizer of unconstrained global optimization is proposed. This kind of filled functions is continuously differentiable. And it has no exponential terms and logarithmic terms, which reduce the possibility of computation overflows. Theoretical properties of the proposed filled functions are studied, including discussing the specific conditions that the proposed functions must meet to qualify as a filled function. Then, a new solution algorithm is developed according to the theoretical analysis. Six benchmark problems are tested, and the performance of the new algorithm is compared with two filled function methods. The numerical results prove that the new algorithm is effective and reliable.

An Affine Scaling Algorithm for Biobjective Linear Programming

Marco Antonio Figueiredo Menezes, Nelson Maculan

2024, 12(4):  937-951.  doi:10.1007/s40305-023-00486-0

Asbtract ( 348 )   PDF  

References | Related Articles | Metrics

Given a biobjective linear programming problem, we develop an affine scaling algorithm withmin-max direction and demonstrate its convergence for an efficient solution. We implement the algorithm for some minor issues in the literature.

Turán Numbers of Expanded Intersecting Cliques in 3-graphs

Yu-Cong Tang, Tong Li, Gui-Ying Yan

2024, 12(4):  952-964.  doi:10.1007/s40305-022-00451-3

Asbtract ( 328 )   PDF  

References | Related Articles | Metrics

Let $\ell$ > r ≥ 3. Given a 2-graph F, the expansion F^(r) of F is an r-graph obtained from F by adding r - 2 new vertices into each edge. When F is a clique of order $\ell$, the Turán number ex(n, F^(r)) was first asymptotically determined by Mubayi (J Comb Theory Ser B 96:122-134, 2006) and exactly computed by Pikhurko (J Comb Theory Ser B 103:220-225, 2013). Let F_k,$\ell$ be the 2-graph on ($\ell$-1)k + 1 vertices consisting of k cliques of order $\ell$ intersecting at exactly one vertex. We determine the exact Turán number ex(n, F_k,$\ell$⁽³⁾) for all $\ell$ > 3, k ≥ 1 and sufficiently large n, as well as the corresponding extremal graphs.

The Multi-visits Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery Service

Si Zhang, Lu Li

2024, 12(4):  965-995.  doi:10.1007/s40305-023-00471-7

Asbtract ( 332 )   PDF  

References | Related Articles | Metrics

The development of convergent technology makes the drone expected to become a commercial delivery method for terminal logistics distribution. Although the industry has begun to experiment with the coordinated transportation of drones and vehicles, some limited assumptions have been made to reduce the complexity of synchronization. This paper studies the mathematical formulations and efficient solution methodologies for the multi-visits drone-vehicle routing problem with simultaneous pickup and delivery service (MDVRPSPD), whose objective is to minimize the distance traveled by drones and vehicles and the total number of drones used. To solve the MDVRPSPD problem, a three-stage solution method is designed. Firstly, the scalable K-means++ algorithm is used to determine the vehicle’s parking location, and we optimize the vehicle’s driving route by traveling salesman problem (TSP) modeling; then, the classic tabu search algorithm is extended to arrange the schedule of drones which consider multi-visits and simultaneous pickup and delivery service. Meanwhile, a set of extensive computational experiments are conducted to demonstrate the efficiency of developed heuristics and the superiority of drone-vehicle delivery system on delivery issues.

Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length

Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng

2024, 12(4):  996-1021.  doi:10.1007/s40305-022-00443-3

Asbtract ( 334 )   PDF  

References | Related Articles | Metrics

In this paper, we address the problem of constructing a Steiner tree in the Euclidean plane $\mathbb{R}^2$ using stock pieces of materials with fixed length, which is modelled as follows. Given a set X = {r₁,r₂, …,r_n} of n terminals in $\mathbb{R}^2$ and some stock pieces of materials with fixed length L, we are asked to construct a Steiner tree T interconnecting all terminals in X, and each edge in T must be constructed by a part of that stock piece of material. The objective is to minimize the cost of constructing such a Steiner tree T, where the cost includes three components, (1) The cost of Steiner points needed in T; (2) The construction cost of constructing all edges in T and (3) The cost of stock pieces of such materials used to construct all edges in T. We can obtain two main results. (1) Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem, we present a simple 4-approximation algorithm in time O(nlogn) to solve this new problem; (2) Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the binpacking problem, we design a 3-approximation algorithm in time O(n³) to resolve this new problem.

A General Framework for Nonconvex Sparse Mean-CVaR Portfolio Optimization Via ADMM

Ke-Xin Sun, Zhong-Ming Wu, Neng Wan

2024, 12(4):  1022-1047.  doi:10.1007/s40305-024-00551-2

Asbtract ( 338 )   PDF  

References | Related Articles | Metrics

This paper presents a general framework for addressing sparse portfolio optimization problems using the mean-CVaR (Conditional Value-at-Risk) model and regularization techniques. The framework incorporates a non-negative constraint to prevent the portfolio from being too heavily weighted in certain assets. We propose a specific ADMM (alternating directional multiplier method) for solving themodel and provide a subsequential convergence analysis for theoretical integrity. To demonstrate the effectiveness of our framework, we consider the $\ell$₁ and SCAD (smoothly clipped absolute deviation) penalties as notable instances within our unified framework. Additionally, we introduce a novel synthesis of the CVaR-based model with $\ell$₁/$\ell$₂ regularization. We explore the subproblems of ADMM associated with CVaR and the presented regularization functions, employing the gradient descent method to solve the subproblem related to CVaR and the proximal operator to evaluate the subproblems with respect to penalty functions. Finally, we evaluate the proposed framework through a series of parametric and out-of-sample experiments, which shows that the proposed framework can achieve favorable out-of-sample performance. We also compare the performance of the proposed nonconvex penalties with that of convex ones, highlighting the advantages of nonconvex penalties such as improved sparsity and better risk control.

Expected Residual Minimization Method for Stochastic Tensor Variational Inequalities

Tong-Tong Shang, Guo-Ji Tang

2024, 12(4):  1048-1071.  doi:10.1007/s40305-022-00450-4

Asbtract ( 335 )   PDF  

References | Related Articles | Metrics

The goal of this paper is to introduce and investigate a model called the stochastic tensor variational inequality (denoted by STVI), which is a natural extension of the stochastic linear complementarity problem and the stochastic affine variational inequality. Firstly, the STVI is transformed into an expected residual minimization (ERM) problem involved the regularized gap function. Then, the properties of the ERM problem are investigated. Finally, a discrete approximation of ERM problem is obtained by quasi-Monte Carlo method. The convergence of optimal solutions and stationary points of the approximation problem are analyzed as well.

Disjoint Cycles and Degree Sum Condition in a Graph

Chun-Jiao Song, Yun Wang, Jin Yan

2024, 12(4):  1072-1087.  doi:10.1007/s40305-023-00473-5

Asbtract ( 407 )   PDF  

References | Related Articles | Metrics

For an integer t, where t ≥ 2, let σ_t(G) denote the minimum degree sum of an independent set with t vertices in a graph G. We prove that for two integers k, t with k ≥ 3, t ≥ 4, every graph G with |V(G)| ≥ kt + 1.5k + t and σ_t(G) ≥ 2kt -t +1 contains k disjoint cycles. This result improves the theorem of Ma and Yan by optimizing the lower bound of |V(G)|. In addition, we also improve the theorem of Gould et al. for t = 4 and k ≥ 2.

Single-Machine Scheduling with Step-Deteriorating Jobs and Rejection

Fan-Yu Kong, Cui-Xia Miao, Yu-Jia Huo, Jia-Xin Song, Yu-Zhong Zhang

2024, 12(4):  1088-1102.  doi:10.1007/s40305-023-00481-5

Asbtract ( 386 )   PDF  

References | Related Articles | Metrics

In this paper, we consider the single-machine scheduling with step-deteriorating jobs and rejection. Each job is either rejected by paying a rejection penalty, or accepted and processed on the single machine, and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date. The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. For the case of common deteriorating penalty, we first show that the problem is NP-hard in the ordinary sense. Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm. Furthermore, we propose a fully polynomial time approximation scheme. For the case of common normal processing time, we present two pseudo-polynomial time algorithms, a 2-approximation algorithm and a fully polynomial time approximation scheme.

Directional Derivative and Subgradient of Cone-Convex Set-Valued Mappings with Applications in Set Optimization Problems

Yu Han

2024, 12(4):  1103-1125.  doi:10.1007/s40305-023-00454-8

Asbtract ( 366 )   PDF  

References | Related Articles | Metrics

In this paper, we introduce a new directional derivative and subgradient of set-valued mappings by using a nonlinear scalarizing function. We obtain some properties of directional derivative and subgradient for cone-convex set-valued mappings. As applications, we present necessary and sufficient optimality conditions for set optimization problems and show that the local weak l-minimal solutions of set optimization problems are the global weak l-minimal solutions of set optimization problems under the assumption that the objective mapping is cone-convex.

Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

Man Xiao, Yu-Fei Du, Wei-Dong Li, Jin-Hua Yang

2024, 12(4):  1126-1138.  doi:10.1007/s40305-023-00477-1

Asbtract ( 379 )   PDF  

References | Related Articles | Metrics

In this paper, we consider the problem of semi-online machine covering on three machines with two hierarchies, whose objective is to maximize the minimum machine load. Since there is no online algorithm with bounded competitive ratio for the online machine covering problem, we consider the semi-online case where the processing times of all jobs lie in [1, α]. When there are one machine of hierarchy 1 and two machines of hierarchy 2, we design an optimal online algorithm with a competitive ratio of 1 + α. When there are two machines of hierarchy 1 and one machine of hierarchy 2, we give an optimal online algorithm with a competitive ratio of 1 + 2α.