Operations Research Transactions

On the linear convergence of the general alternating proximal gradient method for convex minimization

WAN Rui, XU Zi

2014, 18(3): 1-12.

Asbtract ( 1639 )

PDF (668KB) ( 1026 )

References | Related Articles | Metrics

In this paper, we propose a general alternating proximal gradient method for linear constrained convex optimization problems with the objective containing two separable functions. Our method is based on the framework of alternating direction method of multipliers. The global and linear convergence of the proposed method is established under certain conditions. Numerical experiments show that the algorithm has good numerical performance.

Tricyclic graphs with exactly two Q-main eigenvalues

CHEN Lin, HUANG Qiongxiang

2014, 18(3): 13-32.

Asbtract ( 916 )

PDF (1637KB) ( 773 )

References | Related Articles | Metrics

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all tricyclic graphs with exactly two Q-main eigenvalues are determined.

An inexact parallel splitting method for separable convex optimization problem

YANG Yun, PENG Zheng

2014, 18(3): 33-46.

Asbtract ( 1197 )

PDF (526KB) ( 605 )

References | Related Articles | Metrics

In this paper, an inexact parallel splitting method is proposed for a class of separable convex optimization problem. The proposed method makes full use of the separability of the problem under consideration, and all sub-problems are solved inexactly. Under some suitable conditions, the convergence of the proposed method is proved. Some primary numerical results indicate the validity of the proposed method.

Determining optimal routes for transit vehicles in no-notice emergency evacuation

HE Shengxue

2014, 18(3): 47-59.

Asbtract ( 1266 )

PDF (526KB) ( 673 )

References | Related Articles | Metrics

To determine the optimal routes for transit vehicles during no-notice emergency evacuation, a mixed integer nonlinear programming model is proposed. During the formulation of the model, the capacitated multi-shelters are considered and transit vehicles with different carrying capacities are also analyzed. By adding some virtual links and nodes to form a time-space network, the minimum total evacuation time and the minimum fatal casualties in the objective function can be realized at the same time. An effective method to produce feasible solution of the model is presented through analyzing the implementation process of actual transit evacuation. Through combining the classical Genetic Algorithm and a time-rolling flow uploading pattern, a practical solution method for the model is given. At last, the effectiveness and efficiency of the model and its solution method are verified by numerical experiment.

Newton methods for inverse problems of quadratic programming

CHENG Cong, ZHANG Liwei

2014, 18(3): 60-70.

Asbtract ( 1170 )

PDF (535KB) ( 821 )

References | Related Articles | Metrics

This paper is devoted to the study of the inverse quadratic programming. The problem can be formulated as a cone constrained optimization problem with a complementary constrain. Based on the theory of duality, we reformulate this problem as a linear complementarity constrained nonsmooth optimization problem with fewer variables than the original one. We introduce a perturbation approach to solve the reformulated problem and demonstrate the global convergence. An inexact Newton method is constructed to solve the perturbation problem and its global convergence and local quadratic rate can be obtained. In the end, our numerical experiment results show the feasibility of this method.

The bounded simplex method to solve the 0-1 linear integer programming problem

ZHANG Huizhen, WEI Xin, MA Liang

2014, 18(3): 71-78.

Asbtract ( 1298 )

PDF (611KB) ( 913 )

References | Related Articles | Metrics

In this paper, a bounded simplex method to solve the 0-1 linear integer programming problem is proposed. Not only is the reasonability of this method proved from the point of mathematical theory, which establishes its theoretic foundation, but also is its feasibility validated from the point of numerical experiments by solving the un-capacitated facility location problem. Furthermore, the further improvement approach and techniques are discussed to overcome the shortcoming of this simplex method.

Solving Chan-Vese model for image segmentation via BB algorithm

PENG Yaxin, CHEN Sasa, SHEN Chaomin, YING Shihui

2014, 18(3): 79-87.

Asbtract ( 1160 )

PDF (1452KB) ( 744 )

References | Related Articles | Metrics

This paper proposed a new approach for image segmentation-----BB algorithm. The advantage of this algorithm was using the current and last points' information to determine the step-size at each step. Firstly, the paper transformed the CV model into optimization problem through a variational level set method. Secondly, BB algorithm was introduced to solve the optimization problem. Then, the paper analyzed the convergence of BB algorithm, which provided a theoretical basis for the application of the algorithm in the CV model. At last, the proposed algorithm was compared with the conventional steepest descent method and conjugate descent method on several real data. The results validated that the proposed BB algorithm was faster with comparable accuracy.

Optimal consumption-portfolio and bequest with insurance and retirement under Knighting uncertainty

LIU Hongjian, FEI Weiyin, ZHU Yongwang$, ZHENG Anman

2014, 18(3): 88-98.

Asbtract ( 959 )

PDF (822KB) ( 777 )

References | Related Articles | Metrics

This paper studies an optimal consumption and portfolio problem with an investor's heritage and insurance under Knighting uncertainty and three different borrowing constraints. The optimal consumption-investment and bequest of an investor have been solved explicitly by using of the backward stochastic differential equations (BSDE) theory. Finally, numerical results show that both ambiguity and ambiguity attitude affect the optimal consumption and portfolio choices.

An optimal algorithm for the two-order multiple problem

WAN Long

2014, 18(3): 99-103.

Asbtract ( 857 )

PDF (773KB) ( 539 )

References | Related Articles | Metrics

In this paper, we present a new and interesting combination optimization problem called two-order multiple problem. The problem is stated as follows. There are $n\geq 2$ integers $a_1$, $a_2$, $\cdots$, $a_n$, let $\pi$ be a permutation of $\{1,2,\cdots,n\}$ which also shows a solution to the problem. We must try to find the optimal permutation $\pi$ so that the value of $\sum^n_{i=1}a_{\pi_{i}}a_{\pi_{i+1}}$ is minimal, where $\pi_{n+1}=\pi_1$. We provide a polynomial-time algorithm with the complexity of $O(n\log{n})$ for it.

The Alcuin number of a hypergraph and its connections to the transversal number

SHAN Erfang, KONG Lu

2014, 18(3): 104-110.

Asbtract ( 970 )

PDF (537KB) ( 913 )

References | Related Articles | Metrics

More than 1000 years ago, Alcuin proposed a classical puzzle involving a wolf, a goat and a bunch of cabbages. Recently, Prisner and Csorba et al. considered this transportation planning problem that generalizes Alcuin's river crossing problem to arbitrary conflict graphs $G$. In this paper we generalize this problem to arbitrary hypergraphs $H=(V,\mathcal{E})$. Now the man has to transport a set $V$ of items/vertices across the river. Some items of $V$ formed a hyperedge in $\mathcal{E}$ iff they are conflicting and thus cannot be left together without human supervision. The Alcuin number of a conflict hypergraph is the smallest capacity of a boat for which the hypergraph possesses a feasible schedule. In this paper we give the Alcuin numbers of complete bipartite $r$-uniform hypergraphs and their adjoint hypergraphs, $r$-uniform hypergraphs. We also prove that it's NP-hard to decide whether a given $r$-uniform hypergraph is a small boat hypergraph.

A note on regularity condition in multiobjective optimization

ZHAO Kequan, YANG Xinmin

2014, 18(3): 111-115.

Asbtract ( 943 )

PDF (413KB) ( 605 )

References | Related Articles | Metrics

In this paper, an example is given on regularity condition for a class of nonsmooth multiobjective optimization problems with inequality constraints. This example implies that the regularity condition proposed by Burachik and Rizvi for differentiable multiobjective optimization by the linearizing cone could not be generalized to the nonsmooth case in terms of Clarke derivative.

The properly colored paths and cycles for the triangle-free graphs

DING Lushun, WANG Guanghui, YAN Jin

2014, 18(3): 116-120.

Asbtract ( 1130 )

PDF (460KB) ( 593 )

References | Related Articles | Metrics

Let $G$ be an edge colored graph, $v$ be a vertex in $G$. $d^c(v)$ denotes the color degree of a vertex $v$, i.e. the number of edges with distinct colors incident to $v$. At the same time, $\delta^c(G)$ denotes the minimum color degree of $G$, i.e. $\delta^c(G)={\rm min}\{d^c(v):v\in G\}$. Let $G$ be an edge colored triangle-free graph such that $\delta^c(G)\geq 2$. We prove that $G$ contains a properly colored path of length $4d-2$ or a properly colored cycle of length at least $2d-2$.

Table of Content