Journal of the Operations Research Society of China

Block-Wise ADMM with a Relaxation Factor for Multiple-Block Convex Programming

Bing-Sheng He,Ming-Hua Xu,Xiao-Ming Yuan

2018, 6(4): 485-506. doi:https://doi.org/10.1007/s40305-017-0186-y

Asbtract ( 196 )

PDF

Related Articles | Metrics

It has been shown that the alternating direction method of multipliers (ADMM) is not necessarily convergent when it is directly extended to a multiple-block linearly constrained convex minimization model with an objective function that is in the sum of more than two functions without coupled variables. Recently, we proposed the block-wise ADMM, which was obtained by regrouping the variables and functions of such a model as two blocks and then applying the original ADMM in block-wise. This note is a further study on this topic with the purpose of showing that a well-known relaxation factor proposed by Fortin and Glowinski for iteratively updating the Lagrangian multiplier of the original ADMM can also be used in the block-wise ADMM. We thus propose the block-wise ADMM with Fortin and Glowinski’s relaxation factor for the multiple-block convex minimization model. Like the block-wise ADMM, we also suggest further decomposing the resulting subproblems and regularizing them by proximal terms to ensure the convergence. For the block-wise ADMM with Fortin and Glowinski’s relaxation factor, its convergence and worst-case convergence rate measured by the iteration complexity in the ergodic sense are derived.

Deterministic Bicriteria Model for Stochastic Variational Inequalities

Xin-Min Yang, Yong Zhao, Gui-Hua Lin

2018, 6(4): 507-528. doi:https://doi.org/10.1007/s40305-017-0190-2

Asbtract ( 157 )

PDF

Related Articles | Metrics

We propose a deterministic bicriteria model for stochastic variational inequalities based on some existing deterministic models. We reformulate the bicriteria model into a single objective problem involving a conditional value-at-risk (CVaR) term and introduce two approximation methods for solving the single objective problem, which are based on the primal and dual formulations of CVaR, respectively. In particular, for the primal problem, we introduce a smooth approximation of CVaR and establish some properties for this approximation problem. Then, we use sample average approximation methods to deal with the single objective problem and investigate the limiting behaviors of optimal solutions and stationary points. For the dual problem, we regularize the inner maximization problem and demonstrate the convergence of the approximation.

A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems

Mohammad Pirhaji,Hossein Mansouri,Maryam Zangiabadi

2018, 6(4): 529-544. doi:https://doi.org/10.1007/s40305-017-0178-y

Asbtract ( 101 )

PDF

Related Articles | Metrics

In this paper, a wide-neighborhood predictor-corrector feasible interior-point algorithm for linear complementarity problems is proposed. The algorithm is based on using the classical affine scaling direction as a part in a corrector step, not in a predictor step. The convergence analysis of the algorithm is shown, and it is proved that the algorithm has the polynomial complexity

O (\sqrt{n} \log ε^{- 1})

which coincides with the best known iteration bound for this class of mathematical problems. The numerical results indicate the efficiency of the algorithm.

Equivalence of Some Different Maintenance Activities in Single-Machine Scheduling

Juan Zou, Jin-Jiang Yuan

2018, 6(4): 545-556. doi:https://doi.org/10.1007/s40305-017-0182-2

Asbtract ( 122 )

PDF

Related Articles | Metrics

We study single-machine scheduling problems with a single maintenance activity (MA) of length $p_{0}$ under three types of assumptions: (A) the MA is required in a fixed time interval $[T - p_{0}, T]$ with $T ⩾ p_{0}$ and the job processing is of preemptive and resumable; (B) the MA is required in a relaxed time interval [0, T] with $T ⩾ p_{0}$ and the job processing is of nonpreemptive; (C) the MA is required in a relaxed time interval $[T_{0}, T]$ with $0 ⩽ T_{0} ⩽ T - p_{0}$ and the job processing is of nonpreemptive. We show in this paper that, up to the time complexity for solving scheduling problems, assumptions (A) and (B) are equivalent, and moreover, if $T - (T_{0} + p_{0})$ is greater than or equal to the maximum processing time of all jobs, the assumption (C) is also equivalent to (A) and (B). As an application, we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions, respectively, and present corresponding time-complexity results.

A Kind of Unified Strict Efficiency via Improvement Sets in Vector Optimization

Hui Guo, Yan-Qin Bai

2018, 6(4): 557-570. doi:https://doi.org/10.1007/s40305-017-0185-z

Asbtract ( 150 )

PDF

Related Articles | Metrics

In this paper, we propose a kind of unified strict efficiency named E-strict efficiency via improvement sets for vector optimization. This kind of efficiency is shown to be an extension of the classical strict efficiency and $ε$ -strict efficiency and has many desirable properties. We also discuss some relationships with other properly efficiency based on improvement sets and establish the corresponding scalarization theorems by a base-functional and a nonlinear functional. Moreover, some examples are given to illustrate the main conclusions.

A Preconditioned Conjugate Gradient Method with Active Set Strategy for 1-Regularized Least Squares

Wan-You Cheng, Dong-Hui Li

2018, 6(4): 571-586. doi:https://doi.org/10.1007/s40305-018-0202-x

Asbtract ( 132 )

PDF

Related Articles | Metrics

In the paper, we consider the $ℓ_{1}$ -regularized least square problem which has been intensively involved in the fields of signal processing, compressive sensing, linear inverse problems and statistical inference. The considered problem has been proved recently to be equivalent to a nonnegatively constrained quadratic programming (QP). In this paper, we use a recently developed active conjugate gradient method to solve the resulting QP problem. To improve the algorithm’s performance, we design a subspace exact steplength as well as a precondition technique. The performance comparisons illustrate that the proposed algorithm is competitive and even performs little better than several state-of-the-art algorithms.

A Stochastic Adaptive Radial Basis Function Algorithm for Costly Black-Box Optimization

Zhe Zhou, Fu-Sheng Bai

2018, 6(4): 587-610. doi:https://doi.org/10.1007/s40305-018-0204-8

Asbtract ( 150 )

PDF

Related Articles | Metrics

In this paper, we present a stochastic adaptive algorithm using radial basis function models for global optimization of costly black-box functions. The exploration radii in local searches are generated adaptively. Each iteration point is selected from some randomly generated trial points according to certain criteria. A restarting strategy is adopted to build the restarting version of the algorithm. The performance of the presented algorithm and its restarting version are tested on 13 standard numerical examples. The numerical results suggest that the algorithm and its restarting version are very effective.

Interval-Valued Programming Problem with Infinite Constraints

Promila Kumar, Bharti Sharma, Jyoti Dagar

2018, 6(4): 611-626. doi:https://doi.org/10.1007/s40305-018-0206-6

Asbtract ( 159 )

PDF

Related Articles | Metrics

In this paper, we explore a class of interval-valued programming problem where constraints are interval-valued and infinite. Necessary optimality conditions are derived. Notion of generalized $(Φ, ρ) -$ invexity is utilized to establish sufficient optimality conditions. Further, two duals, namely Wolfe and Mond–Weir, are proposed for which duality results are proved.

Table of Content