Table of Content

15 September 2017, Volume 21 Issue 3

Previous Issue    Next Issue

Convergence analysis of an intrinsic steepest descent method on semi-supervised metric learning

LI Xin, BAI Yanqin

2017, 21(3):  1-13.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.001

Asbtract ( 1265 )   PDF (1389KB) ( 504 )  

Related Articles | Metrics

In this paper, we derive the convergence problem of an intrinsic steepest descent algorithm for semi-supervised metric learning problem on symmetric positive definite matrices groups.We first rewrite semi-supervised metric learning problem into an unconstrained optimization problem on symmetric positive definite matrices groups. Then we present an intrinsic steepest descent algorithm with an adaptive iteration step-size. Moreover, we prove that the algorithm converges linearly by using a Taylor's expansion of smooth function at any point in Lie groups. Finally, we show a few numerical experiments on classification problem to demonstrate the effectiveness of the proposed algorithm.

Single machine scheduling with dynamic delivery cost and fixed delivery dates

WANG Lei, ZHANG Yuzhong, XING Wei, REN Jianfeng

2017, 21(3):  14-22.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.002

Asbtract ( 1334 )   PDF (530KB) ( 361 )  

Related Articles | Metrics

This paper considers a coordination scheduling of production and delivery on a single machine. A customer places some jobs to a manufacturer at the planning horizon. Processed jobs are delivered in batches to their customer. Each batch can dispatch to its customer at some fixed delivery dates, and different delivery dates corresponding to different delivery cost. The objective is to find a coordinated production-and-delivery schedule to minimize the weighted sum of the scheduling cost and delivery cost. We consider four main objective functions in scheduling theory, construct the models in single machine environment, analyze the problem complexity and give optimal algorithms to solve the problems under the constraint that the delivery cost are non-increasing with respect to time.

The crossing number of the join product of C_6+3K_2 with P_n and C_n

SU Zhenhua

2017, 21(3):  23-34. 

Asbtract ( 862 )   PDF (656KB) ( 314 )  

Related Articles | Metrics

Let P_n be the path on n vertices, C_n be the cycle with n edges, C_6+3K_2 be the graph which is obtained from the cycle C_6 by adding three adjacent edges. In the paper, for special graph C_6+3K_2, we give the crossing numbers of its join product with the path P_n as well as the cycle C_n are Z(6,n)+3\lfloor \frac{n}{2} \rfloor+2 and Z(6,n)+3\lfloor \frac{n}{2} \rfloor+4. Our proof depends on Kleitman's results for the complete bipartite graph cr(K_{6,n})=Z(6,n).

Continuous solution method for 0-1 programming based on the sinusoidal smooth polish function

SUI Yunkang, LI Zhenzhen, LI Hong, CHEN Guoqing

2017, 21(3):  35-44.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.004

Asbtract ( 1440 )   PDF (902KB) ( 226 )  

Related Articles | Metrics

Traditional solutions of 0-1 programming problems belong mostly to direct discrete solving methods. A strict conversion for the problem and approximate continuous solution are proposed in this paper which have three steps: (1) 0-1 discrete variables were expressed as continuous variables on the interval [0, 1] by means of a step function; (2) Objective function is approximated to take more near smooth polish function to approach tradeoff step function, and every constraint function is approximated to take linear polish function to approach tradeoff step function, then 0-1 programming problem is transformed to continuous optimization model from discrete problem; (3) The model is solved by using the method with high smoothness solution. This method breaks certain solving method applies only to certain types of 0-1 programming, so it can solve more general problems. During the solving process, a sinusoidal polish function is taken to obtain very good computational results.

A new kind of second-order composed tangent derivatives and its applications

ZHOU Lixia, XU Yihong, L\"{U} Qiang

2017, 21(3):  45-54.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.005

Asbtract ( 1148 )   PDF (496KB) ( 223 )  

Related Articles | Metrics

A new kind of tangent cones is introduced, whose relationship to the contingent cone is discussed. With the introduced cones, a new kind of second-order tangent derivatives, termed  second-order composed tangent derivatives, is developed, and its relationship to other second-order composed tangent derivatives is discussed. Then, with the help of second-order composed tangent derivatives, optimality necessary conditions are established respectively for a Henig efficient solution and a globally proper efficient solution of set-valued optimization.

Genus distributions of double-path in series graphs

ZHANG Xianglin, HUANG Yuanqiu, GUO Ting

2017, 21(3):  55-64.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.006

Asbtract ( 1129 )   PDF (1111KB) ( 249 )  

Related Articles | Metrics

Calculating the genus distributions of double-path graphs is a concerned topic in topological graph theory. In this paper, by using transfer matrix method and a vectorized production matrix, the calculation formulas for the genus distributions of two types of graphs formed by double-path connect in series are derived.

Analysis and optimal control policy N* for Geo^{lambda_1, lambda_2}/Geo/1(MWV) queueing system with negative customers and N-policy

PAN Quyu, TANG Yinghui, LAN Shaojun

2017, 21(3):  65-76.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.007

Asbtract ( 1163 )   PDF (1191KB) ( 279 )  

Related Articles | Metrics

This paper deals with a discrete-time Geo/Geo/1 working vacations queue with negative customers and N-policy control in which the positive customers arrive at the system in different input rates during the working vacation period and the normal busy period.  Employing the quasi birth-death process and the matrix-geometric solution method, we derive the steady-state queue length distribution and the expected queue length, as well as the steady-state probabilities that the system is in working vacation state and busy state. Meanwhile, the busy period and the application for the steady state queue length distribution in system capacity optimum design are discussed. Finally, through numerical calculation, it is determined the optimal control policy N* such that the long-run expected cost rate is minimum under a given cost structure.

The stability of Nash equilibria for generalized games under graph topology of feasible strategy correspondence

CHEN Pinbo, WANG Nengfa, QIU Xiaoling, WANG Chun

2017, 21(3):  77-85.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.008

Asbtract ( 1110 )   PDF (570KB) ( 249 )  

Related Articles | Metrics

For the stability of generalized games' Nash equilibria, current researches are investigated by uniform metric topology of feasible strategy correspondence. However, this paper presents a weaker metric and uses Hausdorff distance of graph of feasible strategy correspondence to study the stability of Nash equilibria. Under weaker graph topology, we prove that the space of generalized games is complete, and Nash equilibrium correspondence is upper semi-continuous and compact-valued. These lead to generic stability of generalized games' Nash equilibria, i.e., in the sense of Baire category, most of generalized games are essential.

A global optimization method for solving the weak linear bilevel programming problems

ZHENG Yue, ZHUANG Daoyuan, WAN Zhongping

2017, 21(3):  86-94.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.009

Asbtract ( 1380 )   PDF (525KB) ( 326 )  

Related Articles | Metrics

Bilevel programming has been widely applied to economics, transportation, ecology, engineering and other fields. At present, the research of bilevel programming is mainly based on the strong bilevel programming and the weak bilevel programming. However, there are few studies on the solution methods to the weak bilevel programming. In this paper, we present a global optimization method for solving the weak linear bilevel programming problems (WLBPP). We first give the relations between the WLBPP and its relaxation problem with respect to their optimal solutions. Using the dual theory of linear programming and penalty function method, we then discuss the relations between the relaxation problem and its penalized problem. Furthermore, we develop a global optimization method, whose advantage is that it only requires solving several linear programming problems to obtain a globally optimal solution of the original problem, for solving the WLBPP. Finally, a simple example illustrates that the proposed method is feasible.

Nonsmooth Newton method for solving symmetrical tensor absolute value equations

LIANG Na, DU Shouqiang

2017, 21(3):  95-102.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.010

Asbtract ( 1214 )   PDF (541KB) ( 290 )  

Related Articles | Metrics

In this paper, we propose a kind of  symmetrical tensor absolute value equations. And a kind of nonsmooth Newton method is also proposed. Under mild assumption, the local convergence of the method is given. Finally, numerical results indicate the efficiency of the method.

Bounds of the general Randi\'{c} Estrada index of a graph

GAO Nan, LI Meili, SHE Yanhong

2017, 21(3):  103-110.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.011

Asbtract ( 1091 )   PDF (494KB) ( 269 )  

Related Articles | Metrics

Motivated by the Randi\'{c} Estrada index and the general Randi\'{c} energy of a graph, we define the concept of general Randi\'{c} Estrada index of a graph. By using the algebraic and elementary analysis method, we obtain lower and upper bounds for the general Randi\'{c} Estrada index of a simple connected graph of order n and an r-regular graph, which generalize the results of Bozkurt et. al. on the Randi\'{c} Estrada of a graph.

A new single parameter filled function method for nonlinear integer programming

WU Peipei, GAO Yuelin

2017, 21(3):  111-118.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.012

Asbtract ( 1187 )   PDF (518KB) ( 274 )  

Related Articles | Metrics

Nonlinear integer programming problem is a kind of complex optimization problem. The filled function algorithm is an effective method for solving integer programming problems. It involves an auxiliary function to move successively from one local minimum to another better one. At the same time, the method for using only the local minimization algorithm of mature and popular. However, most of the existing filled functions contain one or two interdependent parameters, which makes it difficult to select and adjust the parameters. And the filled function is a composite function of the objective function, and the objective function itself is more complex. Therefore, it is important to construct a filled function which is simple in form, with fewer parameters and good properties. To solve such problems, in this paper, firstly, we construct a new filled function with one parameter, analyze and prove its filling properties; then, the filled function combined with discrete steepest descent method and proposes a new filled function algorithm; finally, the implementation of the algorithms on six test problems show that the algorithm has good effect and is effective and feasible.

Adjacent vertex-distinguishing colorings of the semistrong product of graphs

TIAN Shuangliang, DONG Xinfang, LIU Ruilin

2017, 21(3):  119-125.  doi:10.15960/j.cnki.issn.1007-6093.2017.03.013

Asbtract ( 1171 )   PDF (554KB) ( 255 )  

Related Articles | Metrics

The semistrong product of simple graphs G and H is the simple graph G\bullet H with vertex set V(G)\times V(H), in which (u,v) is adjacent to (u',v') if and only if either u=u' and vv'\in E(H) or uu'\in E(G) and vv'\in E(H). An adjacent vertex distinguishing edge (total) coloring of a graph is a proper edge (total) coloring of the graph such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex distinguishing edge  coloring and adjacent vertex distinguishing total coloring of a  graph are collectively called the adjacent vertex distinguishing  coloring of the graph. The minimum number of colors required for an adjacent vertex distinguishing coloring of G is called the adjacent vertex distinguishing chromatic number of G, and denoted by \chi^{(\tau)}_{a}(G), where \tau=1,2, \chi^{(1)}_{a}(G) and \chi^{(2)}_{a}(G) denote the  adjacent vertex distinguishing edge chromatic number and adjacent vertex distinguishing total chromatic number, respectively. An upper bound for these parameters of  the semistrong product of two simple graphs G and H is given in this paper, and it is proved that the upper bound is attained precisely. Then the necessary and sufficient conditions is discussed which the two different semistrong product of two trees have the same the value of these parameters. Furthermore, the exact value of these parameters for the semistrong product of a class graphs and complete graphs are determined.