Table of Content

15 March 2019, Volume 23 Issue 1

Previous Issue    Next Issue

Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization

CHEN Xinbei, ZHU Mingkang, CHEN Jianli

2019, 23(1):  1-14.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.001

Asbtract ( 760 )   PDF (5439KB) ( 528 )  

References | Related Articles | Metrics

The gradient hard threshold pursuit algorithm is considered as one of the most effective algorithms for solving sparse optimization problems. Since greedy projection operator affects the performance of the algorithm, it is desirable to propose a better projection algorithm besides the greedy strategies. In this paper, we first formulate the projection problem as an integer programming subproblem. Then, by iteratively solving the subproblem, we obtain a better support set of the sparse optimization problem, thus the original problem is solved to improve the performance of the gradient hard threshold pursuit algorithm. Finally, the convergence of the improved algorithm is proved, and the effectiveness of the algorithm is verified by numerical experiments.

Cross entropy algorithm with multiple important sample level estimation for global optimization problems

ZHOU Xinyi, WANG Ke, WU Donghua, WANG Chen

2019, 23(1):  15-27.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.002

Asbtract ( 1071 )   PDF (668KB) ( 295 )  

References | Related Articles | Metrics

This paper studies a kind of bounded closed box-constrained global optimization problem. In this paper, we utilize the equivalence relation between the maximum root of the generalized variance function equation and the global minimum value, and the cross-entropy to design the integral level value estimation algorithm for the global optimization. To improve the algorithm, we divide the function values generated by the important sampling techniques into clusters in each iteration according to certain rules. Based on the cross-entropy method to update important samples in each cluster, a new algorithm for global searching with multiple important samples is proposed. One of the advantages of the algorithm is that the preferable function values are selected to achieve a random search for better function value information in each iteration. Meanwhile, multiple important samples make for excavating more and better global information. A series of numerical experiment results show that the algorithm is effective.

Filled function method for solving non-smooth box constrained global optimization problems

WANG Weixiang, SHANG Youlin, WANG Duo

2019, 23(1):  28-34.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.003

Asbtract ( 1082 )   PDF (553KB) ( 264 )  

References | Related Articles | Metrics

This paper introduces a new filled function method for solving non-smooth box constrained global optimization problems. The constructed filled function contains only one parameter, which could be adjusted readily during the process of the iterations. The theoretical properties of the filled function are analyzed, and a filled function algorithm is designed. Finally, the effectiveness of the proposed algorithm is verified by some numerical calculations.

The optimality conditions of approximate solutions for quasiconvex multiobjective optimization problem

CHEN Ruiting, XU Zhihui, GAO Ying

2019, 23(1):  35-44.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.004

Asbtract ( 861 )   PDF (626KB) ( 443 )  

References | Related Articles | Metrics

In this paper, we study the optimality conditions of approximate weak efficient solutions and approximate efficient solutions for quasiconvex multiobjective optimization problems. We introduce four concepts of approximate subdifferentials based on the existing subdifferentials of quasiconvex function, and give the relationship among them. And then, we apply these concepts to the quasiconvex multiobjective optimization problems, derive the sufficient conditions and necessary conditions for the approximate weak efficient solutions and the approximate efficient solution, and give some examples to illustrate the main results.

Second-order characterizations for local weakly nondominated points with variable ordering structure

XU Yihong, MEI Fang

2019, 23(1):  45-52.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.005

Asbtract ( 698 )   PDF (437KB) ( 1834 )  

References | Related Articles | Metrics

A kind of second-order tangent derivatives is introduced, with which a second-order necessary optimality condition is established for set-valued optimization with variable ordering structure in the sense of local weakly nondominated points. Under special circumstances, a first-order necessary optimality condition is obtained. The relationship to second-order contingent tangent derivatives for the sum of two set-valued maps is given under some constraint qualification indued by modified Dubovitskij-Miljutin tangent cones. Further more, a necessary optimality condition is obtained where the objective and constraining functions are considered separately with respect to second-order contingent tangent derivatives.

The best rank-one approximation of the symmetric tensor based on the block circulant matrix

XU Jiaojiao, YANG Zhixia, JIANG Yaolin

2019, 23(1):  53-60.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.006

Asbtract ( 1046 )   PDF (517KB) ( 217 )  

References | Related Articles | Metrics

In this paper we mainly study the best rank-one approximation problem of a symmetric tensor. This problem plays an important role in our investigation of the tensor. Firstly, we propose a new method to solve the best rank-one approximation problem of a symmetric tensor, which is based on the block circulant matrix of a third-order tensor. Secondly, sufficient and necessary conditions and an estimation of error upper bound are provided for the best rank-one approximation method. Finally, the numerical example is presented to illustrate the feasibility of our approach and the correctness of the error upper bound.

Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine

CHEN Qiuhong, ZHANG Xingong

2019, 23(1):  61-71.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.007

Asbtract ( 729 )   PDF (550KB) ( 243 )  

References | Related Articles | Metrics

This paper considers two agent scheduling problems with fixed time windows on a single machine. The jobs of the first agent might be preemptive. There exists agreeable condition with release time and due data. The objective function is to minimize the total tardiness. The focus is to find an optimal sequence that minimizes the objective of the first agent, while keeping all jobs of the second agent schedule within fixed time windows. By block principle, we present a pseudo-polynomial time dynamic programming algorithm when fixed time window equals the processing time. If the fixed time windows is larger than the processing time, we give the time complexity of the proposed problem.

Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m)

SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao

2019, 23(1):  72-80.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.008

Asbtract ( 1005 )   PDF (559KB) ( 1249 )  

References | Related Articles | Metrics

Let H(p,tK_1,m) denote an unicyclic graph with p+mt vertices obtained from C_p by attaching the center of star K_1,m to each one of t mutual adjacent vertices of the cycle C_p, respectively. In this paper, we show that the unicyclic graphs H(p,p K_1,5) and H((p,(p-1)K_1,4) are determined by their Laplacian spectra, and if p is an even number, then the unicyclic graphs H(p, 2K_1,4), H(p,(p-2)K_1,4) and H(p,(p-3)K_1,4) are also determined by their Laplacian spectra.

On the signless Laplacian spectral radius of tricyclic graphs

CHEN Yuanyuan, WANG Guoping

2019, 23(1):  81-89.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.009

Asbtract ( 1264 )   PDF (867KB) ( 298 )  

References | Related Articles | Metrics

Suppose that the vertex set of a graph G is V(G)={v₁,v₂,…,v_n}. Then we denote by d_vi(G) the degree of v_i in G. Let A(G) be the adjacent matrix of G and D(G) be the n×n diagonal matrix with its (i,i)-entry equal to d_vi(G). Then Q(G)=D(G)+A(G) is the signless Laplacian matrix of G. The signless Laplacian spectral radius of G is the largest eigenvalue of Q(G). In this paper we determine the extremal graph with maximum signless Laplacian spectral radius among all tricyclic graphs of order n.

The least eignvalue of the graphs whose complements are connected and have pendant vertices

YU Guidong, SUN Wei, LU Xingting

2019, 23(1):  90-96.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.010

Asbtract ( 689 )   PDF (1051KB) ( 233 )  

References | Related Articles | Metrics

The least eigenvalue of the graph is defined as the smallest eigenvalue of adjacency matrix of the graph, which is an important algebraic parameter on characterizing structural property of graphs. In this paper, we characterize the unique graph with the minimum least eigenvalue among all graphs of fixed order whose complements are connected and have pendent vertices, and present the lower bound of the least eigenvalue of such classes of graphs.

The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model

REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU

2019, 23(1):  97-103.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.011

Asbtract ( 832 )   PDF (628KB) ( 259 )  

References | Related Articles | Metrics

Diagnosability of a multiprocessor system is an important study topic. A new measure for fault diagnosis of the system is called g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topology structure of interconnection networks, the Cayley graph UG_n generated by unicyclic graphs has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of the Cayley graph UG_n generated by unicyclic graphs is 2n-1 under the PMC model for n ≥ 4; the 1-good-neighbor diagnosability of the Cayley graph UG_n generated by unicyclic graphs is 2n-1 under the MM^* model for n ≥ 5.

An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles

CHEN Hongyu, TAN Xiang

2019, 23(1):  104-110.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.012

Asbtract ( 910 )   PDF (541KB) ( 287 )  

References | Related Articles | Metrics

An edge-partition of a graph G is a decomposition of G into subgraphs G₁, G₂,…, G_m such that E(G)=E(G₁)∪ E(G₂)∪…∪ E(G_m) and E(G_i)∩ E(G_j)=∅ for i≠j. A linear k-forest is a graph in which each component is a path of length at most k. The linear k-arboricity la_k(G) of a graph G is the least integer m such that G can be edge-partitioned into m linear k-forests. For extremities, la₁(G) is the edge chromatic number χ'(G) of G; la_∞(G) representing the case when component paths have unlimited lengths is the ordinary linear arboricity la(G) of G. In this paper, we use the discharging method to study the linear 2-arboricity la₂(G) of planar graphs. Let G be a planar graph with neither 5-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge xy with d(x)+d(y) ≤ 8 or a 2-alternating cycle. By this result, we obtain the upper bound of the linear 2-arboricity of G is ?△/2?+4.

Online batch scheduling problem on uniform machines with agreeable processing times

PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei

2019, 23(1):  111-118.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.013

Asbtract ( 854 )   PDF (590KB) ( 308 )  

References | Related Articles | Metrics

We study the online batch scheduling problem on two uniform machines, where the batch capacity is unbounded. When the arrival times and the processing times of jobs are agreeable, two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q₂|r_i < r_j⇒ p_i ≤ p_j, B=∞, on-line|C_max and Q₂|r_i < r_j⇒ p_i ≥ p_j, B=∞, on-line|F_max. Without loss of generality, the speeds of the two machines are assumed to be 1 and s,s ≥ 1. We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+α and 1+1/α, respectively, where α is the positive root of α²+sα-1=0. Moreover, for the former scheduling model, we prove that the competitive ratio of the algorithm is not more than 1.618, when s=1.

The theory and application of nondeterministic selfish routing model

DIAO Zhuo

2019, 23(1):  119-126.  doi:10.15960/j.cnki.issn.1007-6093.2019.01.014

Asbtract ( 591 )   PDF (668KB) ( 272 )  

References | Related Articles | Metrics

In order to describe the traffic condition in daily life more precisely, based on the classical deterministic selfish routing model, we consider the nondeterministic selfish routing model by introducing uncertainty to each edge's cost function. For the nondeterministic selfish routing model, we take three cost measurement criterions:the risk-averse type (conservatism),the risk-neutral type (rationality) and the risk-seeking type (optimism) which correspond to three different ways of thinking in daily life. Under three different cost measurement criterions, we define the stable strategy (Nash equilibrium strategy). Firstly, we prove that for each instance, the Nash equilibrium strategy always exists and is unique in essence. Secondly, we compare the three different cost measurement criterions, and find a counterintuitive phenomenon:in some instances, the cost under the risk-averse type (conservatism) is smaller than the cost under the risk-seeking type (optimism), which means high risk, low revenue and low risk, high revenue. This is on the contrary to the normal principle of high-risk-high-revenue and low-risk-low-revenue in economics. Based on this phenomenon, we define a paradox called nondeterministic paradox, and prove this paradox is actually a generalization of Braess's Paradox. Finally, we characterize the network which is paradox-free, and prove a single commodity network is nondeterministic-paradox-free if and only if it is series-parallel network.