Loading...

Table of Content

    30 September 2017, Volume 5 Issue 3
    Continuous Optimization
    An LQP-Based Two-Step Method for Structured Variational Inequalities
    Hong-Jin He · Kai Wang · Xing-Ju Cai ·De-Ren Han
    2017, 5(3):  301-317.  doi:10.1007/s40305-016-0147-x
    Asbtract ( 9755 )   PDF  
    Related Articles | Metrics

    The logarithmic quadratic proximal (LQP) regularization is a popular and powerful proximal regularization technique for solving monotone variational inequalities with nonnegative constraints. In this paper,we propose an implementable two-step method for solving structured variational inequality problems by combining LQP regularization and projection method. The proposed algorithm consists of two parts.The first step generates a pair of predictors via inexactly solving a system of nonlinear equations. Then, the second step updates the iterate via a simple correction step. We establish the global convergence of the new method under mild assumptions. To improve the numerical performance of our new method, we further present a self-adaptive version and implement it to solve a traffic equilibrium problem. The numerical results further demonstrate the efficiency of the proposed method.

    Stochastic Optimization
    An Improved Algorithm for Fixed-Hub Single Allocation Problems
    Dong-Dong Ge · Zi-Zhuo Wang · Lai Wei ·Jia-Wei Zhang
    2017, 5(3):  319-332.  doi:10.1007/s40305-016-0143-1
    Asbtract ( 4901 )   PDF  
    Related Articles | Metrics

    This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is assigned to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a new linear programming (LP) relaxation for this problem by incorporating a set of validity constraints into the classical formulations by Ernst and Krishnamoorthy (Locat Sci 4:139–154, Ann Op Res 86:141–159). A geometric rounding algorithm is then used to obtain an integral solution from the fractional solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little costs.

    Continuous Optimization
    Polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions
    Chang-He Liu · Yuan-Yuan Huang ·You-Lin Shang
    2017, 5(3):  333-346.  doi:10.1007/s40305-017-0172-4
    Asbtract ( 608 )   PDF  
    Related Articles | Metrics

    This paper presents a class of primal-dual path-following interior-point algorithms for symmetric cone programming (SCP) based on wide neighborhoods and new directions with a parameter θ. When the parameter θ = 1, the direction is exactly the classical Newton direction. When the parameter θ is independent of the rank of the associated Euclidean Jordan algebra, the algorithm terminates in at most O(κr log ε-1)  iterations, which coincides with the best known iteration bound for the classical wide neighborhood algorithms. When the parameterθ =√n/βτ and Nesterov–Todd search direction is used, the algorithm has O (√r log ε−1 )iteration complexity, the best iteration complexity obtained so far by any interior-point method for solving SCP. To our knowledge, this is the first time that a class of interior-point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed over symmetric cone.

     

    Discrete Optimization
    Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs
    Roghayeh Etemad · Behrooz Alizadeh
    2017, 5(3):  347-361.  doi:10.1007/s40305-016-0144-0
    Asbtract ( 643 )   PDF  
    Related Articles | Metrics

    This paper deals with a general variant of the reverse undesirable (obnoxious) center location problem on cycle graphs. Given a ‘selective’ subset of the vertices of the underlying cycle graph as location of the existing customers, the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths. We develop a combinatorial O(n log n) algorithm for the problem with continuous modifications. For the uniform-cost model, we solve this problem in linear time by an improved algorithm. Furthermore, exact solution methods are proposed for the problem with integer modifications.

    Management Science
    The Park-and-Ride Behavior in a Cumulative Prospect Theory-Based Model
    Li-Jun Tian · Cheng-Rui Lyu ·Yong-Xiang Zhao
    2017, 5(3):  363-376.  doi:10.1007/s40305-017-0153-7
    Asbtract ( 3040 )   PDF  
    Related Articles | Metrics

    As an effective travel demand management means, park-and-ride (P&R) mode is an important part of urban traffic. In a traffic corridor with P&R service, suppose that the travel time on highway is uncertain, a cumulative prospect theory (CPT)-based travel decision-making model is established with two travel modes of driving all the way and (P&R). With this setting, the effect of various factors such as the transit fare rate, the parking fee and the total travel demand on the CPT-based and expected utility theory (EUT)-based equilibrium results are compared. In addition, the sensitivity analysis focus on CPT-related parameters are also performed. The numerical results in our case show that the equilibrium flow on P&R mode is always underestimated in an EUT-based model, especially for a low total travel demand. Also, it is found that reducing the transit fare rate or parking fee for P&R station and raising the parking fee for CBD has the same effect on promoting more commuters transfer to P&R mode, whatever CPT-based or EUT-based model is employed.Furthermore, commuter’s reference dependence characteristic is also observed in a CPT-based model, and it is especially noticeable when the road uncertainty is large.

    Continuous Optimization
    Compromising Solution of Geometric Programming Problem with Bounded Parameters
    Mrinal Jana · Geetanjali Panda
    2017, 5(3):  377-390.  doi:10.1007/s40305-016-0145-z
    Asbtract ( 707 )   PDF  
    Related Articles | Metrics

    This paper addresses a geometric programming problem, where the objective function and constraints are interval-valued functions. The concept of acceptable feasible region is introduced, and a methodology is developed to transform this model to a general optimization problem, which is free from interval uncertainty. Relationship between the solution of the original problem and the transformed problem is established. The methodology is illustrated through numerical examples. Solutions by the proposed method and previous methods are analyzed.

    A Modified Proximal Gradient Method for a Family of Nonsmooth Convex Optimization Problems
    Ying-Yi Li · Hai-Bin Zhang· Fei Li
    2017, 5(3):  391.  doi:10.1007/s40305-017-0155-5
    Asbtract ( 9892 )   PDF  
    Related Articles | Metrics

    In this paper, we propose a modified proximal gradient method for solving a class of nonsmooth convex optimization problems, which arise in many contemporarystatistical and signal processing applications. The proposed method adopts a new scheme to construct the descent direction based on the proximal gradient method. It is proven that the modified proximal gradient method is Q-linearly convergent without the assumption of the strong convexity of the objective function. Some numerical experiments have been conducted to evaluate the proposed method eventually.

    On the Convergence Rate of a Proximal Point Algorithm for Vector Function on Hadamard Manifolds
    Feng-Mei Tang · Ping-Liang Huang
    2017, 5(3):  405-417.  doi:10.1007/s40305-016-0146-y
    Asbtract ( 711 )   PDF  
    Related Articles | Metrics

    The proximal point algorithm has many interesting applications, such as signal recovery, signal processing and others. In recent years, the proximal point method has been extended to Riemannian manifolds. The main advantages of these extensions are that nonconvex problems in classic sense may become geodesic convex by introducing an appropriate Riemannian metric, constrained optimization problems may be seen as unconstrained ones. In this paper, we propose an inexact proximal point algorithm for geodesic convex vector function on Hadamard manifolds. Under the assumption that the objective function is coercive, the sequence generated by this algorithm converges to a Pareto critical point.When the objective function is coercive and strictly geodesic convex, the sequence generated by this algorithm converges to a Pareto optimal point. Furthermore, under the weaker growth condition, we prove that the inexact proximal point algorithm has linear/superlinear convergence rate.

    Conic Scalarizations for Approximate Efficient Solutions in Nonconvex Vector Optimization Problems
    Hui Guo · Wan-li Zhang
    2017, 5(3):  419-430.  doi:10.1007/s40305-016-0139-x
    Asbtract ( 753 )   PDF  
    Related Articles | Metrics

    Nonlinear scalarization is a very important method to deal with the vector optimization problems. In this paper, some conic nonlinear scalarization characterizations
    of E-optimal points, weakly E-optimal points, and E-Benson properly efficient points proposed via improvement sets are established by a new scalarization function,
    respectively. These results improved and generalized some previously known results.As a special case, the scalarization of Benson properly efficient points is also given. Some examples are given to illustrate the main results.