Asia-Pacific Journal of Operational Research

A simple and implementable two-loop smoothing method for semi-infinite minimax problem is given with the discretization parameter and the smoothing parameter being updated adaptively. We prove the global convergence of the algorithm when the steepest descent method or a BFGS type quasi-Newton method is applied to the smooth subproblems. The strategy for updating the smoothing parameter can not only guarantee the convergence of the algorithm but also considerably reduce the ill-conditioning caused by increasing the value of the smoothing parameter. Numerical tests show that the algorithm is robust and effective.

We consider a class of ℓ₀-minimization problems, which is to search for the partial sparsest solution to an underdetermined linear system with additional constraints. We introduce several concepts, including l_p-induced quasi-norm (0 < p < 1), maximal scaled spark and scaled mutual coherence, to develop several new uniqueness conditions for the partial sparsest solution to this class of ℓ₀-minimization problems. A further improvement of some of these uniqueness criteria has been also achieved through the so-called concepts such as maximal scaled (sub)coherence rank.

This paper concerns the asymmetric atomic selfish routing game for load balancing in ring networks. In the selfish routing, each player selects a path in the ring network to route one unit traffic between its source and destination nodes, aiming at a minimum maximum link load along its own path. The selfish path selections by individuals ignore the system objective of minimizing the maximum load over all network links. This selfish ring load (SRL) game arises in a wide variety of applications in decentralized network routing, where network performance is often measured by the price of anarchy (PoA), the worst-case ratio between the maximum link loads in an equilibrium routing and an optimal routing. It has been known that the PoA of SRL with respect to classical Nash Equilibrium (NE) cannot be upper bounded by any constant, showing large loss of efficiency at some NE outcome.

In an effort to improve the network performance in the SRL game, we generalize the model to so-called SRL with collusion (SRLC) which allows coordination within any coalition of up to k selfish players on the condition that every player of the coalition benefits from the coordination. We prove that, for m-player game on n-node ring, the PoA of SRLC is n - 1 when k ≤ 2, drops to 2 when k = 3 and is at least 1 + 2/m for k ≥ 4. Our study shows that on one hand, the performance of ring networks, in terms of maximum load, benefits significantly from coordination of self-interested players within small-sized coalitions; on the other hand, the equilibrium routing in SRL might not reach global optimum even if any number of players can coordinate.

In this paper, we present a bilinear second-order cone programming safe approximation for the distributionally robust chance constrained program (DRCCP), assuming that the support of the uncertain parameters, and the first and second marginal moments of the probability with respect to the interval constraint imposed on the sum of the uncertain parameters are given. If we further know the covariance matrix, we can obtain a bilinear semi-definite programming safe approximation. Preliminary numerical tests indicate that the proposed models are competitive.

The reflection shapes of configurations in ℜ^m with k landmarks consist of all the geometric information that is invariant under compositions of similarity and reflection transformations. By considering the corresponding Schoenberg embedding, we embed the reflection shape space into the Euclidean space of all (k - 1) by (k - 1) real symmetric matrices. In this paper, we provide a computable formula of the extrinsic mean of the reflection shapes in arbitrary dimensions. Moreover, the asymptotic analysis of the extrinsic mean of the reflection shapes is studied. By using the differentiability of spectral operators, we obtain a central limit theorem of the sample extrinsic mean of the reflection shapes. As a direct application, the two-example hypothesis test of the reflection shapes is also derived.

In this paper, we propose a class of new penalty-free method, which does not use any penalty function or a filter, to solve nonlinear semidefinite programming (NSDP). So the choice of the penalty parameter and the storage of filter set are avoided. The new method adopts trust region framework to compute a trial step. The trial step is then either accepted or rejected based on the some acceptable criteria which depends on reductions attained in the nonlinear objective function and in the measure of constraint infeasibility. Under the suitable assumptions, we prove that the algorithm is well defined and globally convergent. Finally, the preliminary numerical results are reported.

A quadratic optimization problem with one nonconvex quadratic constraint is studied using the canonical dual approach. Under the dual Slater's condition, we show that the canonical dual has a smooth concave objective function over a convex feasible domain, and this dual has a finite supremum unless the original quadratic optimization problem is infeasible. This supremum, when it exists, always equals to the minimum value of the primal problem. Moreover, a global minimizer of the primal problem can be provided by a dual-to-primal conversion plus a "boundarification" technique. Application to solving a quadratic programming problem over a ball is included and an error bound estimation is provided.

This paper studies a recovery task of finding a low multilinear-rank tensor that fulfills some linear constraints in the general settings, which has many applications in computer vision and graphics. This problem is named as the low multilinear-rank tensor recovery problem. The variable splitting technique and convex relaxation technique are used to transform this problem into a tractable constrained optimization problem. Considering the favorable structure of the problem, we develop a splitting augmented Lagrangian method (SALM) to solve the resulting problem. The proposed algorithm is easily implemented and its convergence can be proved under some conditions. Some preliminary numerical results on randomly generated and real completion problems show that the proposed algorithm is very effective and robust for tackling the low multilinear-rank tensor completion problem.

We study the Stackleberg variant of the repeated Sequential Prisoner's Dilemma (SPD). The game goes in two stages, and the two players, the leader and the follower, are asymmetric in both stages. In the first stage of the game, the leader chooses a strategy (for the repeated SPD of the second stage), which is immediately known to the follower. In the second stage, they play repeated SPD: In each round the follower moves after observing the leader's action.

Assuming complete rationality, we find some extraordinary properties of this model. (i) The (subgame perfect) equilibrium payoff profile is unique, which lies on the corner of the region predicted by classical folk theorems: It is best for the leader and at the same time worst for the follower, (ii) the leader has simple optimal strategies that are one-step memory and stationary. These features are in great contrast with classical results, where either uniqueness cannot be guaranteed and equilibrium strategies are often quite complicated, or bounded rationality is required. Although full cooperation, i.e., the outcome is always (cooperate, cooperate), is not attainable in our model, at least a half of the optimal social welfare can be guaranteed. We also do a non-equilibrium analysis which makes the usual equilibrium analysis more convincing.

The sum-max 2-most reliable sources (Sum-Max 2-MRS) problem in a given unreliable network is referred to as finding a pair of nodes in the network from which the expected number of reachable nodes is maximized. This problem is #P-hard on general graphs and admits a cubic time algorithm on trees with unreliable edges. In this paper, we revisit the problem on trees and design an edge-turbulence algorithm with a quadratic time and quadratic spaces. Finally, we further develop an edge-turbulence based parallel algorithm with a lower time complexity.

Very recently Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] initiate a new systematic way of studying online problems by introducing the competitive ratio approximation scheme (simplified as competitive schemes in this paper), which is a class of algorithms {A_ϵ|ϵ > 0} with a competitive ratio at most ρ*(1 + ϵ), where ρ* is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] provide competitive schemes for several online over time scheduling problems like Qm|r_j, (pmtn)|∑w_jc_j, while the running times are polynomial if the number of machines is a constant. In this paper, we consider the classical online scheduling problems, where jobs arrive in a list. We present competitive schemes for Rm‖C_max and , where the running times are polynomial if the number of machines is a constant. Specifically, we are able to derive a competitive scheme for P‖C_max which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] Indeed, by utilizing the standard rounding technique for the off-line scheduling problems, we reformulate the online scheduling problem into a game on an infinite graph, through which we arrive at the following key point: Assuming that the best competitive ratio is ρ*, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ* - O(ϵ). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.