Table of Content

30 June 2024, Volume 12 Issue 2

Previous Issue    Next Issue

The Rate of Convergence of Augmented Lagrangian Method for Minimax Optimization Problems with Equality Constraints

Yu-Hong Dai, Li-Wei Zhang

2024, 12(2):  265-297.  doi:10.1007/s40305-022-00439-z

Asbtract ( 140 )   PDF  

References | Related Articles | Metrics

The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints. We prove that, under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem, for a given multiplier vector μ, the rate of convergence of the augmented Lagrangian method is linear with respect to ||μ - μ^*|| and the ratio constant is proportional to 1/c when the ratio ||μ - μ^*/c is small enough, where c is the penalty parameter that exceeds a threshold c_* > 0 and μ^* is the multiplier corresponding to a local minimizer. Moreover, we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters {c_k} is bounded and the convergence rate is superlinear if {c_k} is increasing to infinity. Finally, we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.

A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting: Convergence and Rate Analyses

Peng-Jie Liu, Jin-Bao Jian, Hu Shao, Xiao-Quan Wang, Jia-Wei Xu, Xiao-Yu Wu

2024, 12(2):  298-340.  doi:10.1007/s40305-023-00535-8

Asbtract ( 120 )   PDF  

References | Related Articles | Metrics

This work explores a family of two-block nonconvex optimization problems subject to linear constraints. We first introduce a simple but universal Bregman-style improved alternating direction method of multipliers (ADMM) based on the iteration framework of ADMM and the Bregman distance. Then, we utilize the smooth performance of one of the components to develop a linearized version of it. Compared to the traditional ADMM, both proposed methods integrate a convex combination strategy into the multiplier update step. For each proposed method, we demonstrate the convergence of the entire iteration sequence to a unique critical point of the augmented Lagrangian function utilizing the powerful Kurdyka–Łojasiewicz property, and we also derive convergence rates for both the sequence of merit function values and the iteration sequence. Finally, some numerical results show that the proposedmethods are effective and encouraging for the Lasso model.

Improved Approximation Schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date

Wei-Dong Li

2024, 12(2):  341-350.  doi:10.1007/s40305-022-00402-y

Asbtract ( 95 )   PDF  

References | Related Articles | Metrics

We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs that are executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, for any desired accuracy ε, we propose an efficient polynomial time approximation scheme with running time O (f (1/ε) n), where n is the number of jobs and f (1/ε) is exponential in 1/ε, and a fully polynomial time approximation scheme with running time O (1/ε^2m+1 + n) when the number of machines is fixed.

Local search yields a PTAS for fixed-dimensional k-means problem with penalties

Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang

2024, 12(2):  351-362.  doi:10.1007/s40305-022-00394-9

Asbtract ( 88 )   PDF  

References | Related Articles | Metrics

We study a problem called the k-means problem with penalties (k-MPWP), which is a natural generalization of the typical k-means problem. In this problem, we have a set D of client points in ℝ^d, a set F of possible centers in ℝ^d, and a penalty cost p_j > 0 for each point j ∈ D. We are also given an integer k which is the size of the center point set. We want to find a center point set S ⊆ F with size k, choose a penalized subset of clients P ⊆ D, and assign every client in D\P to its open center. Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P. By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting, we present a polynomial-time approximation scheme (PTAS) for the k-MPWP.

The Role of Consumer Privacy Concerns in Shaping Platform Strategy for Online Markets

Jin-Kun Yang, Yong-Rui Duan, Jia-Zhen Huo

2024, 12(2):  363-386.  doi:10.1007/s40305-022-00396-7

Asbtract ( 95 )   PDF  

References | Related Articles | Metrics

We investigate the effects of consumer privacy concerns on the pricing and personal data collection strategy of an online platform. The online platform derives revenues from disclosing consumer information to firms. Firms compete for the information in order to enable them to price discriminate and thus derive revenues from consumer purchases. A novel aspect of our research is that we allow the online platform to sell only a subset of consumer data. We develop analytical models where consumers can/cannot protect their privacy. Our analysis yields three main conclusions. First, in the monopoly case, we find that when the consumer privacy disclosure aversion cost is relatively low, it is optimal for the platform to sell all consumer information to the firm. Second, in the duopoly case, we illustrate that when the consumer privacy disclosure aversion cost is relatively low, the platform will sell all consumer information to only one firm; when the cost is moderate, the platform will choose to sell the information of only some consumers and to only one firm; when the cost is relatively high, the platform will select only some of the consumers and sell their information to both firms. Third, it will be better for the platform to provide the information protection service for free when the privacy cost is low.

An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties

Wen-Zhao Liu, Min Li

2024, 12(2):  387-409.  doi:10.1007/s40305-022-00399-4

Asbtract ( 72 )   PDF  

References | Related Articles | Metrics

As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean distance. Different from k-means problem and most of its variants, fuzzy k-means problem belongs to the soft clustering problem, where each given data point has relationship to every center point. Compared to fuzzy k-means problem, fuzzy k-means problem with penalties allows that some data points need not be clustered instead of being paid penalties. In this paper, we propose an O(αk ln k)- approximation algorithm based on seeding algorithm for fuzzy k-means problem with penalties, where α involves the ratio of the maximal penalty value to the minimal one. Furthermore, we implement numerical experiments to show the effectiveness of our algorithm.

A Nonmonotone Projected Gradient Method for Multiobjective Problems on Convex Sets

Gabrie Aníbal Carrizo, Nadia Soledad Fazzio, María Laura Schuverdt

2024, 12(2):  410-427.  doi:10.1007/s40305-022-00410-y

Asbtract ( 121 )   PDF  

References | Related Articles | Metrics

In this work we consider an extension of the classical scalar-valued projected gradient method for multiobjective problems on convex sets. As in Fazzio et al. (Optim Lett 13:1365–1379, 2019) a parameter which controls the step length is considered and an updating rule based on the spectral gradient method from the scalar case is proposed. In the present paper, we consider an extension of the traditional nonmonotone approach of Grippo et al. (SIAM J Numer Anal 23:707–716, 1986) based on the maximum of some previous function values as suggested in Mita et al. (J Glob Optim 75:539–559, 2019) for unconstrained multiobjective optimization problems. We prove the accumulation points of sequences generated by the proposed algorithm, if they exist, are stationary points of the original problem. Numerical experiments are reported.

Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions

Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang

2024, 12(2):  428-445.  doi:10.1007/s40305-022-00407-7

Asbtract ( 112 )   PDF  

References | Related Articles | Metrics

Submodular optimization is widely used in large datasets. In order to speed up the problems solving, it is essential to design low-adaptive algorithms to achieve acceleration in parallel. In general, the function values are given by a value oracle, but in practice, the oracle queries may consume a lot of time. Hence, how to strike a balance between optimizing them is important. In this paper, we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio γ under a cardinality constraint, and propose two algorithms to deal with it. We apply the adaptive sequencing technique to devise the first algorithm, whose approximation ratio is arbitrarily close to 1 - e^-γ in O(log n · log(log k/γ)) adaptive rounds, and requires O(n² ·log(log k/γ)) queries. Then by adding preprocessing and parameter estimation steps to the first algorithm, we get the second one. The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity. With the same approximation and adaptive complexity, the query complexity is improved to O(n ·log(log k/γ)). To the best of our knowledge, this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.

On Fractional (g, f, n’, m)-Critical Covered Graphs

Wei Gao, Wei-Fan Wang

2024, 12(2):  446-460.  doi:10.1007/s40305-022-00409-5

Asbtract ( 106 )   PDF  

References | Related Articles | Metrics

The main contribution in this article is threefold: (1) we show the necessary and sufficient condition for graphs to be fractional (g, f)-covered which can be expressed in different forms, and extended to fractional (g, f, m)-covered graphs; (2) the concept of fractional (g, f, n’, m)-critical covered graph is put forward and its necessary and sufficient condition is given; (3) we present the degree condition for a graph to be fractional (g, f, n’, m)-critical covered, and show that degree bound is sharp when m is small. Moreover, the related result in fractional (a, b, n’, m)-critical covered setting is also verified.

An Accelerated Proximal Gradient Algorithm for Hankel Tensor Completion

Chuan-Long Wang, Xiong-Wei Guo, Xi-Hong Yan

2024, 12(2):  461-477.  doi:10.1007/s40305-022-00422-8

Asbtract ( 111 )   PDF  

References | Related Articles | Metrics

In this paper, an accelerated proximal gradient algorithm is proposed for Hankel tensor completion problems. In our method, the iterative completion tensors generated by the new algorithm keep Hankel structure based on projection on the Hankel tensor set. Moreover, due to the special properties of Hankel structure, using the fast singular value thresholding operator of the mode-s unfolding of a Hankel tensor can decrease the computational cost. Meanwhile, the convergence of the new algorithm is discussed under some reasonable conditions. Finally, the numerical experiments show the effectiveness of the proposed algorithm.

The Non-inclusion Diagnosability of Hypercubes Under the PMC Model

Mei-Jie Ma, Min Xu, Tong-Tong Ding, Xiang-Jun Li, Qiang Zhu

2024, 12(2):  478-484.  doi:10.1007/s40305-022-00421-9

Asbtract ( 121 )   PDF  

References | Related Articles | Metrics

Diagnosability of a multiprocessor system is an important measure of the reliability of interconnection networks. System-level diagnosis is a primary strategy to identify the faulty processors in a multiprocessor system. Based on a sound assumption proposed by Zhu et al. recently, we proposed a new diagnosability named non-inclusion diagnosability and showed that the non-inclusion diagnosability t_N(Q_n) of the hypercube under the PMC model is 2n - 2. That is, assume that if two vertex sets F₁ and F₂ are both consistent with a syndrome and F₁ ⊂ F₂, then F₂ is not the faulty set which we are looking for; the faulty set F is 1-step diagnosable if |F| ≤2n - 2 in Q_n under the PMC model.

2-Independent Domination in Trees

Gang Zhang, Baoyindureng Wu

2024, 12(2):  485-494.  doi:10.1007/s40305-022-00428-2

Asbtract ( 98 )   PDF  

References | Related Articles | Metrics

A subset D ⊆ V (G) in a graph G is a dominating set if every vertex in V (G) \ D is adjacent to at least one vertex of S. A subset S ⊆ V (G) in a graph G is a 2-independent set if ∆(G[S])<2. The 2-independence number α₂(G) is the order of a largest 2-independent set in G. Further, a subset D ⊆ V (G) in a graph G is a 2-independent dominating set if D is both dominating and 2-independent. The 2-independent domination number i²(G) is the order of a smallest 2-independent dominating set in G. In this paper, we characterize all trees T of order n with i²(T) = n/2. Moreover, we prove that for any tree T of order n≥2, i²(T)≤2/3α₂(T), and this bound is sharp.

An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou

2024, 12(2):  495-504.  doi:10.1007/s40305-022-00430-8

Asbtract ( 86 )   PDF  

References | Related Articles | Metrics

In this paper, we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties. In this problem, we are given m dedicated machines in parallel and n customer orders. Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine. An order is either rejected, in which case a rejection penalty has to be paid, or accepted and manufactured on the m dedicated machines. The objective is to find a solution tominimize the sum of themaximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular function. We design an LP rounding algorithm with approximation ratio of n + 1 for this problem.

The Q-index and Connectivity of Graphs

Peng-Li Zhang, Li-Hua Feng, Wei-Jun Liu, Xiao-Dong Zhang

2024, 12(2):  505-519.  doi:10.1007/s40305-022-00427-3

Asbtract ( 89 )   PDF  

References | Related Articles | Metrics

A connected graph G is said to be k -connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted. In this paper, for a connected graph G with sufficiently large order, we present a tight sufficient condition for G with fixed minimum degree to be k -connected based on the Q-index. Our result can be viewed as a spectral counterpart of the corresponding Dirac-type condition.

Existence of α-Cores for Games Without Compact Assumptions

Hai-Qun Zhang

2024, 12(2):  520-527.  doi:10.1007/s40305-022-00420-w

Asbtract ( 134 )   PDF  

References | Related Articles | Metrics

Following the representation of Kajii (J Econ Theory 56:194–205, 1992), we provide some existence theorems of α-cores for games without ordered preferences and compact assumptions. As applications, we obtain some existence results of the α-core for normal-form games without compact assumptions.

The Minimum Centroid Branch Spanning Tree Problem

Hao Lin, Cheng He

2024, 12(2):  528-539.  doi:10.1007/s40305-022-00419-3

Asbtract ( 128 )   PDF  

References | Related Articles | Metrics

For a spanning tree T of graph G, the centroid of T is a vertex v for which the largest component of T - v has as few vertices as possible. The number of vertices of this component is called the centroid branch weight of T. The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized. In application to design of communication networks, the loads of all branches leading from the switch center should be as balanced as possible. In this paper, we prove that the problem is strongly NP-hard even for bipartite graphs. Moreover, the problem is shown to be polynomially solvable for split graphs, and exact formulae for special graph families, say K_n1,_n2,…,_nk and P_m×P_n, are presented.

Restricted Arc-Connectivity of Harary Digraphs

Jun-Hao Zhang, Ji-Xiang Meng

2024, 12(2):  540-547.  doi:10.1007/s40305-022-00406-8

Asbtract ( 124 )   PDF  

References | Related Articles | Metrics

The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the h-restricted arc-connectivity of the Harary digraph D = G(n; 1, 2, …, k) is equal to n/2 for 2≤h≤n/2, k = 2 and n is even, and λ_h(D) = g(k - 1) for 2≤h≤g and 3≤k <n/2, where g is the girth of D. As consequences, the super restricted arc-connectedness of Harary digraph D is obtained immediately. In particular, for k = 2 and n is even or 3≤k < n/2 and n can be divided by k, it can be determined that distinct positive (respectively, negative) λ_h-superatoms of D are vertex disjoint for 2≤h≤g.