Loading...

Table of Content

    15 September 2017, Volume 21 Issue 3
    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.