Table of Content

30 June 2019, Volume 7 Issue 2

Previous Issue    Next Issue

Set Function Optimization

Wei-Li Wu, Zhao Zhang, Ding-Zhu Du

2019, 7(2):  183-193.  doi:10.1007/s40305-018-0233-3

Asbtract ( 355 )   PDF  

References | Related Articles | Metrics

This article is an introduction to recent development of optimization theory on set functions, the nonsubmodular optimization, which contains two interesting results, DS (difference of submodular) functions decomposition and sandwich theorem, together with iterated sandwich method and data-dependent approximation. Some potential research problems will be mentioned.

Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems

Yin Zhang

2019, 7(2):  195-204.  doi:10.1007/s40305-019-00249-w

Asbtract ( 412 )   PDF  

References | Related Articles | Metrics

A unified convergence theory is derived for a class of stationary iterative methods for solving linear equality constrained quadratic programs or saddle point problems. This class is constructed from essentially all possible splittings of the submatrix residing in the (1,1)-block of the augmented saddle point matrix that would produce non-expansive iterations. The classic augmented Lagrangian method and alternating direction method of multipliers are two special members of this class.

Randomized Primal–Dual Proximal Block Coordinate Updates

Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang

2019, 7(2):  205-250.  doi:10.1007/s40305-018-0232-4

Asbtract ( 761 )   PDF  

References | Related Articles | Metrics

In this paper, we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its O(1/t) convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primal-dual method for bilinear saddle-point problems (PD-S), the proximal Jacobian alternating direction method of multipliers (Prox-JADMM) and a randomized variant of the ADMM for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility violation. It is well known that the original ADMM may fail to converge when the number of blocks exceeds two. Our result shows that if an appropriate randomization procedure is invoked to select the updating blocks, then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM, without assuming any strong convexity. The new approach is also extended to solve problems where only a stochastic approximation of the subgradient of the objective is available, and we establish an O(1/√t) convergence rate of the extended approach for solving stochastic programming.

A New Complementarity Function and Applications in Stochastic Second-Order Cone Complementarity Problems

Guo Sun, Jin Zhang, Li-Ying Yu, Gui-Hua Lin

2019, 7(2):  251-283.  doi:10.1007/s40305-018-0225-3

Asbtract ( 383 )   PDF  

References | Related Articles | Metrics

This paper considers the so-called expected residual minimization (ERM) formulation for stochastic second-order cone complementarity problems, which is based on a new complementarity function called termwise residual complementarity function associated with second-order cone. We show that the ERM model has bounded level sets under the stochastic weak R₀-property. We further derive some error bound results under either the strong monotonicity or some kind of constraint qualifications. Then, we apply the Monte Carlo approximation techniques to solve the ERM model and establish a comprehensive convergence analysis. Furthermore, we report some numerical results on a stochastic second-order cone model for optimal power flow in radial networks.

Optimality Conditions for Rank-Constrained Matrix Optimization

Xin-Rong Li, Wen Song, Nai-Hua Xiu

2019, 7(2):  285-301.  doi:10.1007/s40305-019-00245-0

Asbtract ( 424 )   PDF  

References | Related Articles | Metrics

In this paper, we comprehensively study optimality conditions for rank-constrained matrix optimization (RCMO). By calculating the Clarke tangent and normal cones to a rank-constrained set, along with the given Fréchet, Mordukhovich normal cones, we investigate four kinds of stationary points of the RCMO and analyze the relations between each stationary point and local/global minimizer of the RCMO. Furthermore, the second-order optimality condition of the RCMO is achieved with the help of the Clarke tangent cone.

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu

2019, 7(2):  303-319.  doi:10.1007/s40305-018-0192-8

Asbtract ( 9151 )   PDF  

References | Related Articles | Metrics

We study an online (over time) scheduling problem on two uniform unbounded parallel-batchmachines with processing speed 1 and v(0 < v ≤1),respectively, to minimize the makespan. We first show that no online algorithm can have a competitive ratio less than 1 + α_L, where α_L=(√5-1)/2 ≈ 0.618 if 0 < v 1/2, and α_L=α₂(v) is the positive root of α³+3α²+(3-1/v)α-1/v=0 if 1/2 < v 1. This lower bound is still valid when all jobs have the same processing times. Then, we provide an online algorithm with a competitive ratio at most min{(√5+1)/2, √2/v}. When the jobs have the same processing times, we present the best possible online algorithm with a competitive ratio 1 + α_L.

A New Approach on Mixed-Type Nondifferentiable Higher-Order Symmetric Duality

Khushboo Verma, Pankaj Mathur, Tilak Raj Gulati

2019, 7(2):  321-335.  doi:10.1007/s40305-018-0213-7

Asbtract ( 298 )   PDF  

References | Related Articles | Metrics

In this paper, a new mixed-type higher-order symmetric duality in scalar-objective programming is formulated. In the literature we have results either Wolfe or Mond-Weir-type dual or separately, while in this we have combined those results over one model. The weak, strong and converse duality theorems are proved for these programs under η-invexity/η-pseudoinvexity assumptions. Self-duality is also discussed. Our results generalize some existing dual formulations which were discussed by Agarwal et al. (Generalized second-order mixed symmetric duality in nondifferentiable mathematical programming. Abstr. Appl. Anal. 2011. https://doi.org/10.1155/2011/103597), Chen (Higher-order symmetric duality in nonlinear nondifferentiable programs), Gulati and Gupta (Wolfe type second order symmetric duality in nondifferentiable programming. J. Math. Anal. Appl. 310, 247-253, 2005, Higher order nondifferentiable symmetric duality with generalized F-convexity. J. Math. Anal. Appl. 329, 229-237, 2007), Gulati and Verma (Nondifferentiable higher order symmetric duality under invexity/generalized invexity. Filomat 28(8), 1661-1674, 2014), Hou and Yang (On second-order symmetric duality in nondifferentiable programming. J Math Anal Appl. 255, 488-491, 2001), Verma and Gulati (Higher order symmetric duality using generalized invexity. In:Proceeding of 3rd International Conference on Operations Research and Statistics (ORS). 2013. https://doi.org/10.5176/2251-1938_ORS13.16, Wolfe type higher order symmetric duality under invexity. J Appl Math Inform. 32, 153-159, 2014).

Internet Resources and Organizational Knowledge Creation: Role of Environmental Dynamism

Cai-Yun Zhuang, Guo-Hong Chen, Li-Li Wang

2019, 7(2):  337-354.  doi:10.1007/s40305-018-0220-8

Asbtract ( 279 )   PDF  

References | Related Articles | Metrics

The development of the Internet has provided firms with the ideal opportunity to make up for the knowledge gap for achieving internal knowledge generation (IKG) and external knowledge acquisition (EKA). It is worth exploring how Internet resources can be used to satisfy organizational knowledge needs efficiently to adapt to dynamic environments. Thus, according to the resource-based view, knowledge-based view, and contingency theory, we study the impact of different types of Internet resources on the two modes of knowledge creation (IKG and EKA), as well as the moderating effect of environmental dynamism (ED) on this relationship. The hypothesized relationships were tested using the hierarchical regression analysis method with survey data collected from 399 Chinese firms.We found that Internet relationship resource and Internet human resource can simultaneously facilitate IKG and EKA, while Internet infrastructure resource positively affects IKG but has no significant impact on EKA. Furthermore, ED positively moderates the relationship between Internet relationship resource and IKG and EKA, but negativelymoderates the relationship between Internet human resource and EKA.

Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances

Mobarakeh Karimi, Massoud Aman, Ardeshir Dolati

2019, 7(2):  355-364.  doi:10.1007/s40305-018-0231-5

Asbtract ( 341 )   PDF  

References | Related Articles | Metrics

Given a generalized minimum cost flow problem, the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem. In this paper, we consider both types of the weighted Hamming distances for measuring the adjustment. In the sum-type case, it is shown that the inverse problem is APX-hard. In the bottleneck-type case, we present a polynomial time algorithm.

An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes

Zhong-Ming Wu, Min Li

2019, 7(2):  365-383.  doi:10.1007/s40305-019-00247-y

Asbtract ( 457 )   PDF  

References | Related Articles | Metrics

Symmetric alternating direction method of multipliers (ADMM) is an efficient method for solving a class of separable convex optimization problems. Thismethod updates the Lagrange multiplier twice with appropriate step sizes at each iteration. However, such step sizes were conservatively shrunk to guarantee the convergence in recent studies. In this paper, we are devoted to seeking larger step sizes whenever possible. The logarithmic-quadratic proximal (LQP) terms are applied to regularize the symmetric ADMM subproblems, allowing the constrained subproblems to then be converted to easier unconstrained ones. Theoretically, we prove the global convergence of such LQP-based symmetric ADMM by specifying a larger step size domain. Moreover, the numerical results on a traffic equilibrium problem are reported to demonstrate the advantage of the method with larger step sizes.

Computing the Number of k-Component Spanning Forests of a Graph with Bounded Treewidth

Peng-Fei Wan, Xin-Zhuang Chen

2019, 7(2):  385-394.  doi:10.1007/s40305-019-00241-4

Asbtract ( 333 )   PDF  

References | Related Articles | Metrics

Let G be a graph on n vertices with bounded treewidth. We use f_k(G) to denote the number of spanning forests of G with k components. Given a tree decomposition of width at most p of G, we present an algorithm to compute f_k(G) for k=1, 2,…, n. The running time of our algorithm is O((B(p + 1))³ pn³), where B(p + 1) is the (p + 1)-th Bell number.