Authors:Abdelmalek Aboussoror; Samir Adly Pages: 309 - 327 Abstract: In this paper we are interested in a strong bilevel programming problem (S). For such a problem, we establish necessary and sufficient global optimality conditions. Our investigation is based on the use of a regularization of problem (S) and some well-known global optimization tools. These optimality conditions are new in the literature and are expressed in terms of \(\max \) – \(\min \) conditions with linked constraints. PubDate: 2018-01-19 DOI: 10.1007/s10898-018-0606-5 Issue No:Vol. 70, No. 2 (2018)

Authors:Fengmin Xu; Meihua Wang; Yu-Hong Dai; Dachuan Xu Pages: 5 - 25 Abstract: Enhanced indexation aims to construct a portfolio to track and outperform the performance of a stock market index by employing both passive and active fund management strategies. This paper presents a novel sparse enhanced indexation model with chance and cardinality constraints. Its goal is to maximize the excess return that can be attained with a high probability, while the model allows a fund manger to limit the number of stocks in the portfolio and specify the maximum tolerable relative market risk. In particular, we model the asset returns as random variables and estimate their probability distributions by the Capital Asset Pricing Model or Fama-French 3-factor model, and measure the relative market risk with the coherent semideviation risk function. We deal with the chance constraint via distributionally robust approach and present a second-order cone programming and a semidefinite programming safe approximation for the model under different sets of potential distribution functions. A hybrid genetic algorithm is applied to solve the NP-hard problem. Numerical tests are conducted on the real data sets from major international stock markets, including USA, UK, Germany and China. The results demonstrate that the proposed model and the method can efficiently solve the enhanced indexation problem and our approach can generally achieve sparse tracking portfolios with good out-of-sample excess returns and high robustness. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0513-1 Issue No:Vol. 70, No. 1 (2018)

Authors:Yiju Wang; Hengxia Gao; Wei Xing Pages: 27 - 53 Abstract: This paper considers an inventory mechanism with a non-deterministic short-term price discount. In the mechanism, the supplier has a tendency to offer retailers a short-term price discount for a future occasion. Subsequently, when the discount occurs, the discount stock would start to reduce gradually. Therefore the discount might terminate ahead of schedule once the discount stock is depleted, which means that the discount possibility will gradually decrease from 1 ever after the start of the discount. For this system, to maximize the retailer’s profit, we establish an optimal replenishment and stocking strategies model. Based on the retailer’s cost-benefit analysis, we present a solution method for the model and provide an optimal ordering policy to the retailer. The given numerical experiments illustrate the validity of the model. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0522-0 Issue No:Vol. 70, No. 1 (2018)

Authors:Zai-Yun Peng; Jian-Wen Peng; Xian-Jun Long; Jen-Chih Yao Pages: 55 - 69 Abstract: This paper is concerned with the stability of semi-infinite vector optimization problems (SVO). Under weak assumptions, we establish sufficient conditions of the Berge-lower semicontinuity and lower Painlev \(\acute{e}\) –Kuratowski convergence of weak efficient solutions for (SVO) under functional perturbations of both objective functions and constraint sets. Some examples are given to illustrate that our results are new and interesting. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0553-6 Issue No:Vol. 70, No. 1 (2018)

Authors:Le Han; Shujun Bi Pages: 71 - 97 Abstract: In this paper we consider the rank and zero norm regularized least squares loss minimization problem with a spectral norm ball constraint. For this class of NP-hard optimization problems, we propose a two-stage convex relaxation approach by majorizing some suitable locally Lipschitz continuous surrogates. Furthermore, the Frobenius norm error bound for the optimal solution of each stage is characterized and the theoretical guarantee is established for the two-stage convex relaxation approach by showing that the error bound of the first stage convex relaxation (i.e., the nuclear norm and \(\ell _1\) -norm regularized minimization problem), can be reduced much by the second stage convex relaxation under a suitable restricted eigenvalue condition. Also, we verify the efficiency of the proposed approach by applying it to some random test problems and some real problems. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0573-2 Issue No:Vol. 70, No. 1 (2018)

Authors:Xiaojiao Tong; Hailin Sun; Xiao Luo; Quanguo Zheng Pages: 131 - 158 Abstract: Distributionally robust optimization (DRO) has become a popular research topic since it can solve stochastic programs with ambiguous distribution information. In this paper, as the background of economic dispatch (ED) in renewable integration systems, we present a new DRO-based ED optimization framework (DRED). The new DRED is addressed with a coupled format of distribution uncertainty for objective and chance constraints, which is different from most existing DRO frameworks. Some approximation strategies are adopted to handle the complicated DRED: the data-driven approach, the approximation of chance constraints by conditional value-at-risk, and the discrete scheme. The approximate reformulations are solvable nonconvex nonlinear programming problems. The approximation error analysis and convergence analysis are also established. Numerical results using an IEEE-30 buses system are presented to demonstrate the approach proposed in this paper. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0572-3 Issue No:Vol. 70, No. 1 (2018)

Authors:Cheng Lu; Zhibin Deng; Wei-Qiang Zhang; Shu-Cherng Fang Pages: 171 - 187 Abstract: This paper proposes a branch-and-bound algorithm for solving the unit-modulus constrained complex quadratic programming problems (CQPP). We study the convex hull of a unit-modulus complex variable with argument constraints, derive new valid linear inequalities from the convex hull, construct an improved semidefinite relaxation of CQPP, and then design an efficient algorithm for solving CQPP globally. The proposed algorithm branches on the sets of argument constraints and derives new valid inequalities from the partitioned sets of arguments. Numerical results are included to support the effectiveness of the proposed algorithm for finding a global solution to CQPP. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0551-8 Issue No:Vol. 70, No. 1 (2018)

Authors:Chenchen Wu; Dachuan Xu; Dongmei Zhang; Peng Zhang Pages: 207 - 222 Abstract: In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based \((3+\epsilon )\) -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a \( (4+ 1/ (e-1) +\epsilon )\) -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately. PubDate: 2018-01-01 DOI: 10.1007/s10898-017-0566-1 Issue No:Vol. 70, No. 1 (2018)

Authors:Takahito Kuno Abstract: The simplicial algorithm is a popular branch-and-bound approach to the convex maximization problem with multiple local maxima. In this paper, we discuss some difficulties revealed when implementing this algorithm under the \(\omega \) -subdivision rule. To overcome those, we modify the bounding process and extend the \(\omega \) -subdivision rule. We also report numerical results for the simplicial algorithm according to the new subdivision rule. PubDate: 2018-02-07 DOI: 10.1007/s10898-018-0619-0

Authors:Felipe Fidalgo; Douglas S. Gonçalves; Carlile Lavor; Leo Liberti; Antonio Mucherino Abstract: Discretizable distance geometry problems consist in a subclass of distance geometry problems where the search space can be discretized and reduced to a tree. Such problems can be tackled by applying a branch-and-prune algorithm, which is able to perform an exhaustive enumeration of the solution set. In this work, we exploit the concept of symmetry in the search tree for isolating subtrees that are explored only one time for improving the algorithm performances. The proposed strategy is based on the idea of dividing an original instance of the problem into sub-instances that can thereafter be solved (almost) independently. We present some computational experiments on a set of artificially generated instances, with exact distances, to validate the theoretical results. PubDate: 2018-02-01 DOI: 10.1007/s10898-018-0610-9

Authors:Anwa Zhou; Xin Zhao; Jinyan Fan; Yanqin Bai Abstract: This paper studies the tensor maximal correlation problem, which aims at optimizing correlations between sets of variables in many statistical applications. We reformulate the problem as an equivalent polynomial optimization problem, by adding the first order optimality condition to the constraints, then construct a hierarchy of semidefinite relaxations for solving it. The global maximizers of the problem can be detected by solving a finite number of such semidefinite relaxations. Numerical experiments show the efficiency of the proposed method. PubDate: 2018-01-30 DOI: 10.1007/s10898-017-0592-z

Authors:Kamil A. Khan; Matthew Wilhelm; Matthew D. Stuber; Huiyi Cao; Harry A. J. Watson; Paul I. Barton Abstract: These errata correct various errors in the closed-form relaxations provided by Khan, Watson, and Barton in the article “Differentiable McCormick Relaxations” (J Glob Optim, 67:687–729, 2017). Without these corrections, the provided closed-form relaxations may fail to be convex or concave and may fail to be valid relaxations. PubDate: 2018-01-25 DOI: 10.1007/s10898-017-0601-2

Authors:Yinrun Lyu; Li Chen; Changyou Zhang; Dacheng Qu; Nasro Min-Allah; Yongji Wang Abstract: Being an extension of classical linear programming, disjunctive programming has the ability to express the problem constraints as combinations of linear equalities and inequalities linked with logic AND and OR operations. All the existing theories such as generalized disjunctive programming, optimization modulo theories, linear optimization over arithmetic constraint formula, and mixed logical linear programming pose one commonality of branching among different solving techniques. However, branching constructs a depth-first search which may traverse a whole bad subtree when the branching makes a mistake ordering a bad successor. In this paper, we propose the interleaved depth-first search with stochastic local optimal increasing (IDFS-SLOI) method for solving the linear optimization problem with disjunctive constraints. Our technique searches depth-first several subtrees in turn, accelerates the search by subtree splitting, and uses efficient backtracking and pruning among the subtrees. Additionally, the local optimal solution is improved iteratively by constructing and solving a stochastic linear programming problem. We evaluate our approach against existing counterparts on the rate-monotonic optimization problem (RM-OPT) and the linear optimization with fuzzy relation inequalities problem (LOFRI). Experimental results show that for the tested instances, the IDFS-SLOI method performs better from performance perspective, especially promising results have been obtained for the larger three groups where the execution time is reduced by 85.6 and 51.6% for RM-OPT and LOFRI, respectively. PubDate: 2018-01-24 DOI: 10.1007/s10898-017-0602-1

Authors:Immanuel M. Bomze; Vaithilingam Jeyakumar; Guoyin Li Abstract: We establish a geometric condition guaranteeing exact copositive relaxation for the nonconvex quadratic optimization problem under two quadratic and several linear constraints, and present sufficient conditions for global optimality in terms of generalized Karush–Kuhn–Tucker multipliers. The copositive relaxation is tighter than the usual Lagrangian relaxation. We illustrate this by providing a whole class of quadratic optimization problems that enjoys exactness of copositive relaxation while the usual Lagrangian duality gap is infinite. Finally, we also provide verifiable conditions under which both the usual Lagrangian relaxation and the copositive relaxation are exact for an extended CDT (two-ball trust-region) problem. Importantly, the sufficient conditions can be verified by solving linear optimization problems. PubDate: 2018-01-24 DOI: 10.1007/s10898-018-0607-4

Authors:Shengguan Xu; Hongquan Chen Abstract: A novel Nash-EGO algorithm is presented to extend the usage of efficient global optimization (EGO) into large-scale optimizations by coupling with Nash game strategy. In our Nash-EGO, the large-scale design variables are split into several subsets by adopting Nash variable territory splitting, and the EGO optimizer acts as a player of specific Nash game. All the EGO players are coupled with each other and assigned to optimize their own subsets synchronously in parallel to produce the corresponding approximate optimal subsets. Doing in this way, the performance of EGO players could be expected to keep at a high level due to the fact that EGO players now take care of only their own small-scale subsets instead of facing the large-scale problem directly. A set of typical cases with a small number of variables are firstly selected to validate the performance of each EGO player mentioned. Then, the Nash-EGO proposed is tested by representative functions with a scale up to 30 design variables. Finally, more challenge cases with 90 design variables are constructed and investigated to mimic the real large-scale optimizations. It can be learned from the tests that, with respect to conventional EGO the present algorithm can always find near optimal solutions, which are more close to the theoretical values, and are achieved, moreover, less CPU time-consuming, up to hundreds times faster. All cases with 30 or 90 design variables have similar efficient performances, which indicates the present algorithm has the potential to cope with real large-scale optimizations. PubDate: 2018-01-22 DOI: 10.1007/s10898-018-0608-3

Authors:Angelo Lucia; Peter A. DiMaggio; Diego Alonso-Martinez Abstract: A novel approach to metabolic network analysis using a Nash Equilibrium (NE) formulation is proposed in which enzymes are considered players in a multi-player game. Each player has its own payoff function with the objective of minimizing the Gibbs free energy associated with the biochemical reaction(s) it catalyzes subject to elemental mass balances while the network objective is to find the best solution to the sum of the player payoff functions. Consequently, any NE solution may not be best solution for all players. Key advantages of the NE approach include the ability to account for (1) aqueous electrolyte behavior, (2) the consumption/production of co-factors, and (3) charge balancing. However, the proposed Nash equilibrium formulation results in a set of nonlinear programming sub-problems that are more demanding to solve than conventional flux balance analysis (FBA) formulations which rely on linear programming. A direct substitution solution methodology for pathways with feedback is described. The Krebs cycle is used to demonstrate the efficacy of the NE approach while comparisons with both FBA and experimental data are used to show that it represents a paradigm shift in metabolic network analysis. PubDate: 2018-01-18 DOI: 10.1007/s10898-018-0605-6

Authors:M. V. Dolgopolik Abstract: In this article we present a general theory of augmented Lagrangian functions for cone constrained optimization problems that allows one to study almost all known augmented Lagrangians for these problems within a unified framework. We develop a new general method for proving the existence of global saddle points of augmented Lagrangian functions, called the localization principle. The localization principle unifies, generalizes and sharpens most of the known results on the existence of global saddle points, and, in essence, reduces the problem of the existence of global saddle points to a local analysis of optimality conditions. With the use of the localization principle we obtain first necessary and sufficient conditions for the existence of a global saddle point of an augmented Lagrangian for cone constrained minimax problems via both second and first order optimality conditions. In the second part of the paper, we present a general approach to the construction of globally exact augmented Lagrangian functions. The general approach developed in this paper allowed us not only to sharpen most of the existing results on globally exact augmented Lagrangians, but also to construct first globally exact augmented Lagrangian functions for equality constrained optimization problems, for nonlinear second order cone programs and for nonlinear semidefinite programs. These globally exact augmented Lagrangians can be utilized in order to design new superlinearly (or even quadratically) convergent optimization methods for cone constrained optimization problems. PubDate: 2018-01-05 DOI: 10.1007/s10898-017-0603-0

Authors:Davood Hajinezhad; Qingjiang Shi Abstract: In this paper, we study a class of nonconvex nonsmooth optimization problems with bilinear constraints, which have wide applications in machine learning and signal processing. We propose an algorithm based on the alternating direction method of multipliers, and rigorously analyze its convergence properties (to the set of stationary solutions). To test the performance of the proposed method, we specialize it to the nonnegative matrix factorization problem and certain sparse principal component analysis problem. Extensive experiments on real and synthetic data sets have demonstrated the effectiveness and broad applicability of the proposed methods. PubDate: 2017-12-29 DOI: 10.1007/s10898-017-0594-x