Journal of the Operations Research Society of China

Ya-XiangYuan

2013, 1(1): 1.

Asbtract ( 258 )

PDF (122KB) ( 135 )

Related Articles | Metrics

Approximation Algorithms for Discrete Polynomial Optimization

Si-Mai He · Zhe-Ning Li · Shu-Zhong Zhang

2013, 1(1): 3.

Asbtract ( 434 )

PDF (1021KB) ( 479 )

Related Articles | Metrics

In this paper, we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete (typically binary) variables. Such models have natural applications in graph theory, neural networks, error-correcting codes, among many others. In particular, we focus on three types of optimization models: (1) maximizing a homogeneous polynomial function in binary variables; (2) maximizing a homogeneous polynomial function in binary variables, mixed with variables under spherical constraints; (3) maximizing an inhomogeneous polynomial function in binary variables. We propose polynomial-time randomized approximation algorithms for such polynomial optimization models, and establish the approximation ratios (or relative approximation ratios whenever appropriate) for the proposed algorithms. Some examples of applications for these models and algorithms are discussed as well.

A Cone Constrained Convex Program: Structure and Algorithms

Li-qun Qi ·Yi Xu ·Ya-Xiang Yuan ·Xin-Zhen Zhang

2013, 1(1): 37.

Asbtract ( 256 )

PDF (560KB) ( 115 )

Related Articles | Metrics

In this paper, we consider the positive semi-definite space tensor cone constrained convex program, its structure and algorithms. We study defining functions, defining sequences and polyhedral outer approximations for this positive semidefinite space tensor cone, give an error bound for the polyhedral outer approximation approach, and thus establish convergence of three polyhedral outer approximation algorithms for solving this problem. We then study some other approaches for solving this structured convex program. These include the conic linear programming approach, the nonsmooth convex program approach and the bi-level program approach. Some numerical examples are presented.

Recent Advances in Mathematical Programming with Semi-continuous Variables and Cardinality Constraint

Xiao-Ling Sun · Xiao-Jin Zheng · Duan Li

2013, 1(1): 55.

Asbtract ( 472 )

PDF (742KB) ( 302 )

Related Articles | Metrics

Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications, including production planning, portfolio selection, compressed sensing and subset selection in regression. This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard. In the past few years, based on new reformulations, approximation and relaxation techniques, promising exact and approximate methods have been developed. We survey in this paper these recent developments for this challenging class of mathematical programming problems.

Theory of Compressive Sensing via 1_1nimization: a Non-RIP Analysis and Extensions

Yin Zhang

2013, 1(1): 79.

Asbtract ( 296 )

PDF

Related Articles | Metrics

Compressive sensing (CS) is an emerging methodology in computational signal processing that has recently attracted intensive research activities. At present, the basic CS theory includes recoverability and stability: the former quantifies the central fact that a sparse signal of length n can be exactly recovered from far fewer than n measurements via 1-minimization or other recovery techniques, while the latter specifies the stability of a recovery technique in the presence of measurement errors and inexact sparsity. So far, most analyses in CS rely heavily on the Restricted Isometry Property (RIP) for matrices. In this paper, we present an alternative, non-RIP analysis for CS via 1-minimization. Our purpose is three-fold: (a) to introduce an elementary and RIP-free treatment of the basic CS theory; (b) to extend the current recoverability and stability results so that prior knowledge can be utilized to enhance recovery via 1-minimization; and (c) to substantiate a property called uniform recoverability of 1-minimization; that is, for almost all random measurement matrices recoverability is asymptotically identical. With the aid of two classic results, the non-RIP approach enables us to quickly derive from scratch all basic results for the extended theory.

Exact Computable Representation of Some Second-Order Cone Constrained Quadratic Programming Problems

Qing-Wei Jin · Ye Tian · Zhi-Bin Deng · Shu-Cherng Fang ·Wen-Xun Xing

2013, 1(1): 107.

Asbtract ( 212 )

PDF

Related Articles | Metrics

Solving the quadratically constrained quadratic programming (QCQP) problem is in general NP-hard. Only a few subclasses of the QCQP problem are known to be polynomial-time solvable. Recently, the QCQP problem with a nonconvex quadratic objective function over one ball and two parallel linear constraints is proven to have an exact computable representation, which reformulates the original problem as a linear semidefinite program with additional linear and second-order cone constraints. In this paper, we provide exact computable representations for some more subclasses of the QCQP problem, in particular, the subclass with one second rder cone constraint and two special linear constraints.

Robust PCA for Ground Moving Target Indication in Wide-Area Surveillance Radar System

Qing-Na Li · He Yan · Le-Qin Wu · Robert Wang

2013, 1(1): 135.

Asbtract ( 217 )

PDF

Related Articles | Metrics

Robust PCA has found important applications in many areas, such as video surveillance, face recognition, latent semantic indexing and so on. In this paper, we study its application in ground moving target indication (GMTI) in wide-area surveillance radar system. MTI is the key task in wide-area surveillance radar system. Due to its great importance in future reconnaissance systems, it attracts great interest from scientists. In (Yan et al. in IEEE Geosci. Remote Sens. Lett., 10:617–621, 2013), the authors first introduced robust PCA to model the GMTI problem, and demonstrate promising simulation results to verify the advantages over other models. However, the robust PCA model can not fully describe the problem. As pointed out in (Yan et al. in IEEE Geosci. Remote Sens. Lett., 10:617–621, 2013), due to the special structure of the sparse matrix (which includes the moving target information), there will be difficulties for the exact extraction of moving targets. This motivates our work in this paper where we will detail the GMTI problem, explore the mathematical properties and discuss how to set up better models to solve the problem. We propose two models, the structured RPCA model and the row-modulus RPCA model, both of which will better fit the problem and take more use of the special structure of the sparse matrix. Simulation results confirm the improvement of the proposed models over the one in (Yan et al. in IEEE Geosci. Remote Sens. Lett., 10:617–621, 2013).

A Counter-Example to a Conjecture of Ben-Tal, Nemirovski and Roos

Ya-Xiang Yuan

2013, 1(1): 155.

Asbtract ( 223 )

PDF

Related Articles | Metrics

In this short note, we present a counter-example to a conjecture made by Ben-Tal et al. in SIAM J. Optim. 13: 535–560, 2002.

An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives

Dong-Lei Du · Da-Chuan Xu

2013, 1(1): 159.

Asbtract ( 177 )

PDF

Related Articles | Metrics

In this note, we provide an almost tight lower bound for the scheduling problem to meet two min-sum objectives considered by Angel et al. in Oper. Res. Lett. 35(1): 69–73, 2007.

Table of Content