Table of Content

30 December 2023, Volume 11 Issue 4

Previous Issue    Next Issue

Convergence of Bregman Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization

Peng-Jie Liu, Jin-Bao Jian, Bo He, Xian-Zhen Jiang

2023, 11(4):  707-733.  doi:10.1007/s40305-022-00411-x

Asbtract ( 53 )   PDF  

References | Related Articles | Metrics

This work is about a splitting method for solving a nonconvex nonseparable optimization problem with linear constraints, where the objective function consists of two separable functions and a coupled term. First, based on the ideas from Bregman distance and Peaceman-Rachford splitting method, the Bregman Peaceman-Rachford splitting method with different relaxation factors for the multiplier is proposed. Second, the global and strong convergence of the proposed algorithm are proved under general conditions including the region of the two relaxation factors as well as the crucial Kurdyka-Łojasiewicz property. Third, when the associated Kurdyka-Łojasiewicz property function has a special structure, the sublinear and linear convergence rates of the proposed algorithm are guaranteed. Furthermore, some preliminary numerical results are shown to indicate the effectiveness of the proposed algorithm.

The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor

Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang

2023, 11(4):  735-758.  doi:10.1007/s40305-022-00425-5

Asbtract ( 29 )   PDF  

References | Related Articles | Metrics

We present an orthogonal matrix outer product decomposition for the fourth-order conjugate partial-symmetric (CPS) tensor and show that the greedy successive rank-one approximation (SROA) algorithm can recover this decomposition exactly. Based on this matrix decomposition, the CP rank of CPS tensor can be bounded by the matrix rank, which can be applied to low-rank tensor completion. Additionally, we give the rank-one equivalence property for the CPS tensor based on the SVD of matrix, which can be applied to the rank-one approximation for CPS tensors.

A Hybrid Conjugate Gradient Algorithm for Nonconvex Functions and Its Applications in Image Restoration Problems

Gong-Lin Yuan, Ying-Jie Zhou, Meng-Xiang Zhang

2023, 11(4):  759-781.  doi:10.1007/s40305-022-00424-6

Asbtract ( 46 )   PDF  

References | Related Articles | Metrics

It is prominent that conjugate gradient method is a high-efficient solution way for large-scale optimization problems. However, most of the conjugate gradient methods do not have sufficient descent property. In this paper, without any line search, the presented method can generate sufficient descent directions and trust region property. While use some suitable conditions, the global convergence of the method is established with Armijo line search. Moreover, we study the proposed method for solving nonsmooth problems and establish its global convergence. The experiments show that the presented method can be applied to solve smooth and nonsmooth unconstrained problems, image restoration problems and Muskingum model successfully.

Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du

2023, 11(4):  783-807.  doi:10.1007/s40305-023-00470-8

Asbtract ( 34 )   PDF  

References | Related Articles | Metrics

This work is devoted to studying an accelerated stochastic Peaceman-Rachford splitting method (AS-PRSM) for solving a family of structural empirical risk minimization problems. The objective function to be optimized is the sum of a possibly nonsmooth convex function and a finite sum of smooth convex component functions. The smooth subproblem in AS-PRSM is solved by a stochastic gradient method using variance reduction technique and accelerated techniques, while the possibly nonsmooth subproblem is solved by introducing an indefinite proximal term to transform its solution into a proximity operator. By a proper choice for the involved parameters, we show that AS-PRSM converges in a sublinear convergence rate measured by the function value residual and constraint violation in the sense of expectation and ergodic. Preliminary experiments on testing the popular graph-guided fused lasso problem in machine learning and the 3D CT reconstruction problem in medical image processing show that the proposed AS-PRSM is very efficient.

Optimality Conditions for Generalized Convex Nonsmooth Uncertain Multi-objective Fractional Programming

Xiao Pan, Guo-Lin Yu, Tian-Tian Gong

2023, 11(4):  809-826.  doi:10.1007/s40305-022-00423-7

Asbtract ( 43 )   PDF  

References | Related Articles | Metrics

This paper aims at studying optimality conditions of robust weak efficient solutions for a nonsmooth uncertain multi-objective fractional programming problem (NUMFP). The concepts of two types of generalized convex function pairs, called type-I functions and pseudo-quasi-type-I functions, are introduced in this paper for (NUMFP). Under the assumption that (NUMFP) satisfies the robust constraint qualification with respect to Clarke subdifferential, necessary optimality conditions of the robust weak efficient solution are given. Sufficient optimality conditions are obtained under pseudo-quasi-type-I generalized convexity assumption. Furthermore, we introduce the concept of robust weak saddle points to (NUMFP), and prove two theorems about robust weak saddle points. The main results in the present paper are verified by concrete examples.

Characterizing Shadow Price via Lagrange Multiplier for Nonsmooth Problem

Yan Gao

2023, 11(4):  827-838.  doi:10.1007/s40305-022-00416-6

Asbtract ( 46 )   PDF  

References | Related Articles | Metrics

In this paper, the relation between the shadow price and the Lagrange multiplier for nonsmooth optimization problem is explored. It is obtained that the Lagrange multipliers are upper bounds of the shadow price for a convex optimization problem and a class of Lipschtzian optimization problems. This result can be used in pricing mechanisms for nonsmooth situation. Several nonsmooth functions involved in this class of Lipschtzian optimizations are listed. Finally, an application to electricity pricing is discussed.

Residual Closeness of Graphs with Given Parameters

Mei-Qun Cheng, Bo Zhou

2023, 11(4):  839-856.  doi:10.1007/s40305-022-00405-9

Asbtract ( 19 )   PDF  

References | Related Articles | Metrics

Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices. We identify those graphs with maximum residual closeness among connected graphs with fixed connectivity, edge connectivity and bipartiteness, respectively.

Optimal Control Policy of M/G/1 Queueing System with Delayed Randomized Multiple Vacations Under the Modified Min(N, D)-Policy Control

Le Luo, Ying-Hui Tang, Miao-Miao Yu, Wen-Qing Wu

2023, 11(4):  857-874.  doi:10.1007/s40305-022-00413-9

Asbtract ( 23 )   PDF  

References | Related Articles | Metrics

Based on the number of customers and the server’s workload, this paper proposes a modified Min(N, D)-policy and discusses an M/G/1 queueing model with delayed randomized multiple vacations under such a policy. Applying the well-known stochastic decomposition property of the steady-state queue size, the probability generating function of the steady-state queue length distribution is obtained. Moreover, the explicit expressions of the expected queue length and the additional queue length distribution are derived by some algebraic manipulations. Finally, employing the renewal reward theorem, the explicit expression of the long-run expected cost per unit time is given. Furthermore, we analyze the optimal policy for economizing the expected cost and compare the optimal Min(N, D)-policy with the optimal N-policy and the optimal D-policy by using numerical examples.

Approximation of the Shannon Capacity Via Matrix Cone Programming

Shi-Tong Wu, Zhen-Nan Zhou, Zhong-Yi Huang, Bo Bai

2023, 11(4):  875-889.  doi:10.1007/s40305-022-00408-6

Asbtract ( 25 )   PDF  

References | Related Articles | Metrics

This paper proposes a novel formulation using the matrix cone programming to compute an upper bound of the Shannon capacity of graphs, which is theoretically superior to the Lovász number. To achieve this, a sequence of matrix cones is constructed by adding certain co-positive matrices to the positive semi-definite matrix cones during the matrix cone programming. We require the sequence of matrix cones to have the weak product property so that the improved result of the matrix cone programming remains an upper bound of the Shannon capacity. Our result shows that the existence of a sequence of suitable matrix cones with the weak product property is equivalent to the existence of a co-positive matrix with testable conditions. Finally, we give some concrete examples with special structures to verify the existence of the matrix cone sequence.

The Non-Inclusive Diagnosability of Regular Graphs

Yu-Long Wei, Tong-Tong Ding, Min Xu

2023, 11(4):  891-910.  doi:10.1007/s40305-022-00415-7

Asbtract ( 20 )   PDF  

References | Related Articles | Metrics

Fault diagnosis is an important area of study with regard to the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, non-inclusive diagnosability (denoted by t_N(G)), was proposed by Ding et al. In this paper, we establish the non-inclusive diagnosability of a class of regular graphs under the PMC model and the MM^* model. As applications, the non-inclusive diagnosabilities of hypercubes, hierarchical hypercubes, folded hypercubes, star graphs, bubble-sort graphs, pancake graphs and dual cubes are determined under the PMC model and the MM^* model.

Approximation Algorithms on k-Correlation Clustering

Zhong-Zheng Tang, Zhuo Diao

2023, 11(4):  911-924.  doi:10.1007/s40305-022-00418-4

Asbtract ( 25 )   PDF  

References | Related Articles | Metrics

In this paper, we consider the k-correlation clustering problem. Given an edge-weighted graph G(V, E) where the edges are labeled either “+” (similar) or “-” (different) with nonnegative weights, we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of “+” edges within clusters and “-” edges between clusters. This problem is NP-hard. We design an approximation algorithm with the approximation ratio max $\left\{a, \frac{(2-k) a+k-1}{k}\right\}$, where a is the weighted proportion of “+” edges in all edges. As a varies from 0 to 1, the approximation ratio varies from $\frac{k-1}{k}$ to 1 and the minimum value is 1/2.

An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted $\ell_1$ Norm Ball

Yong-Jin Liu, Jia-Jing Xu, Lan-Yu Lin

2023, 11(4):  925-940.  doi:10.1007/s40305-022-00414-8

Asbtract ( 24 )   PDF  

References | Related Articles | Metrics

This paper concerns with efficient projection onto the ordered weighted $\ell_1$ norm ball, which is equivalent to the problem of finding projector onto the intersection of the monotone nonnegative cone and an affine subspace. Based on Lagrangian relaxation and secant approximation method, we propose an easily implementable yet efficient algorithm to solve the projection problem which is proved to terminate after a finite number of iterations. Furthermore, we design efficient implementations for our algorithm and compare it with a semismooth Newton (SSN) algorithm and a root-finding (Root-F) algorithm. Numerical results on a diversity of test problems show that our algorithm is superior than SSN and Root-F.

A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers

Xin-Xin Li, Xiao-Ya Zhang

2023, 11(4):  941-955.  doi:10.1007/s40305-022-00417-5

Asbtract ( 29 )   PDF  

References | Related Articles | Metrics

In this paper, we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers. The stopping criterion is easy to verify, and the computational cost is much less than the classical stopping criterion in the highly influential paper by Boyd et al. (Found Trends Mach Learn 3(1):1-122, 2011).

Maximum Independent Sets and Supervised Learning

Roberto Montemanni, Derek H. Smith, Xiao-Chen Chou

2023, 11(4):  957-972.  doi:10.1007/s40305-022-00395-8

Asbtract ( 35 )   PDF  

References | Related Articles | Metrics

The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea..