Table of Content

30 June 2018, Volume 6 Issue 2

Previous Issue    Next Issue

Discrete Optimization

Convex Analysis and Duality over Discrete Domains

Murat Adivar, Shu-Cherng Fang

2018, 6(2):  189-247.  doi:10.1007/s40305-017-0158-2

Asbtract ( 122 )   PDF  

Related Articles | Metrics

The aim of this paper is to establish a fundamental theory of convex analysis for the sets and functions over a discrete domain. By introducing conjugate/biconjugate functions and a discrete duality notion for the cones over discrete domains, we study duals of optimization problems whose decision parameters are integers. In particular, we construct duality theory for integer linear programming, provide a discrete version of Slater’s condition that implies the strong duality and discuss the relationship between
integrality and discrete convexity.

Continuous Optimization

Complexity Analysis and Algorithm Design of Pooling Problem

Yu-Hong Dai, Rui Diao, Kai Fu

2018, 6(2):  249-266.  doi:10.1007/s40305-018-0193-7

Asbtract ( 118 )   PDF  

Related Articles | Metrics

The pooling problem, also called the blending problem, is fundamental in production planning of petroleum. It can be formulated as an optimization problem similar with the minimum-cost flow problem. However, Alfaki and Haugland (J Glob Optim 56:897–916,2013) proved the strong NP-hardness of the pooling problem in general case. They also pointed out that it was an open problem to determine the computational complexity of the pooling problem with a fixed number of qualities. In this paper, we prove that the pooling problem is still strongly NP-hard even with only one quality. This means the quality is an essential difference between minimum-cost flow problem and the pooling problem. For solving large-scale pooling problems in real applications, we adopt the non-monotone strategy to improve the traditional successive linear programming method. Global convergence of the algorithm is established. The numerical experiments show that the non-monotone strategy is effective to push the algorithm to explore the global minimizer or provide a good local minimizer. Our results for real problems from factories show that the proposed algorithm is competitive to the one embedded in the famous commercial software Aspen PIMS.

Second-Order Optimality Conditions for Multiobjective Optimization Whose Order Induced by Second-Order Cone

Li-Wei Zhang, Ji-Hong Zhang, Yu-Le Zhang

2018, 6(2):  267-288.  doi:10.1007/s40305-018-0201-y

Asbtract ( 128 )   PDF  

Related Articles | Metrics

This paper is devoted to developing first-order necessary, second-order necessary, and second-order sufficient optimality conditions for a multiobjective optimization problem whose order is induced by a finite product of second-order cones (here named as Q-multiobjective optimization problem). For an abstract-constrained Q-multiobjective optimization problem, we derive two basic necessary optimality theorems for weak efficient solutions and a second-order sufficient optimality theorem for efficient solutions. For Q-multiobjective optimization problem with explicit constraints, we demonstrate first-order and second-order necessary optimality conditions under Robinson constraint qualification as well as second-order sufficient optimality conditions under upper second-order regularity for the explicit constraints. As applications, we obtain optimality conditions for polyhedral conic, second-order conic, and semi-definite conic Q-multiobjective optimization problems.

Optimality Conditions of Approximate Solutions for Nonsmooth Semi-infinite Programming Problems

Xian-Jun Long, Yi-Bin Xiao, Nan-Jing Huang

2018, 6(2):  289-299.  doi:10.1007/s40305-017-0167-1

Asbtract ( 119 )   PDF  

Related Articles | Metrics

In this paper, we study optimality conditions of approximate solutions for nonsmooth semi-infinite programming problems. Three new classes of functions, namely -pseudoconvex functions of type I and type II and ε-quasiconvex functions are introduced, respectively. By utilizing these new concepts, sufficient optimality conditions of approximate solutions for the nonsmooth semi-infinite programming problem are established. Some examples are also presented. The results obtained in this paper improve the corresponding results of Son et al. (J Optim Theory Appl 141:389–409, 2009).

A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization

Behrouz Kheirfam

2018, 6(2):  301-315.  doi:10.1007/s40305-017-0168-0

Asbtract ( 115 )   PDF  

Related Articles | Metrics

We present a modified and simplified version of an infeasible interior-point method for second-order cone optimization published in 2013 (Zangiabadi et al. in J Optim Theory Appl, 2013). In the earlier version, each iteration consisted of one so-called feasibility step and a few centering steps. Here, each iteration consists of only a feasibility step. Thus, the new algorithm improves the number of iterations and the improvement is due to a lemma which gives an upper bound for the proximity after the feasibility step. The complexity result coincides with the best-known iteration bound for infeasible interior-point methods.

Error Bounds for Generalized Mixed Vector Equilibrium Problems via a Minimax Strategy

Chun-Rong Chen, Xia Chen, Hong-Zhi Wei, Sheng-Jie Li

2018, 6(2):  317-331.  doi:10.1007/s40305-017-0169-z

Asbtract ( 95 )   PDF  

Related Articles | Metrics

In this paper, by using scalarization techniques and a minimax strategy, error bound results in terms of gap functions for a generalized mixed vector equilibrium problem are established, where the solutions for vector problems may be general sets under natural assumptions, but are not limited to singletons. The other essentially equivalent approach via a separation principle is analyzed. Special cases to the classical vector equilibrium problem and vector variational inequality are also discussed.

Discrete Optimization

The g-Good-Neighbor Conditional Diagnosability of Locally Twisted Cubes

Yu-Long Wei, Min Xu

2018, 6(2):  333-347.  doi:10.1007/s40305-017-0166-2

Asbtract ( 94 )   PDF  

Related Articles | Metrics

In the work of Peng et al. (Appl Math Comput 218(21):10406–10412, 2012), a new measure was proposed for fault diagnosis of systems: namely g-good-neighbor conditional diagnosability, which requires that any fault-free vertex has at least g fault-free neighbors in the system. In this paper, we establish the g-good-neighbor conditional diagnosability of locally twisted cubes under the PMC model and the MM^∗ model.