-
作者：Ahmed, Shabbir; Luedtke, James; Song, Yongjia; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Virginia Commonwealth University
摘要：We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a sin...
-
作者：Blanco, Victor; Puerto, Justo; Ponce, Diego
作者单位：University of Granada; University of Sevilla; University of Sevilla
摘要：In this paper we address the problem of locating a new facility on a d-dimensional space when the distance measure (- or polyhedral-norms) is different at each one of the sides of a given hyperplane . We relate this problem with the physical phenomenon of refraction, and extend it to any finite dimensional space and different distances at each one of the sides of any hyperplane. An application to this problem is the location of a facility within or outside an urban area where different distanc...
-
作者：Ringkamp, Maik; Ober-Blobaum, Sina; Leyendecker, Sigrid
作者单位：University of Erlangen Nuremberg; University of Oxford
摘要：Nonlinear control systems with instantly changing dynamical behavior can be modeled by introducing an additional control function that is integer valued in contrast to a control function that is allowed to have continuous values. The discretization of a mixed integer optimal control problem (MIOCP) leads to a non differentiable optimization problem and the non differentiability is caused by the integer values. The paper is about a time transformation method that is used to transform a MIOCP wi...
-
作者：Bomze, Immanuel M.; Cheng, Jianqiang; Dickinson, Peter J. C.; Lisser, Abdel
作者单位：University of Vienna; University of Arizona; University of Twente; Universite Paris Saclay
摘要：Triggered by Burer's seminal characterization from 2009, many copositive reformulations of mixed-binary QPs have been discussed by now. Most of them can be used as proper relaxations, if the intractable co(mpletely)positive cones are replaced by tractable approximations. While the widely used approximation hierarchies have the disadvantage to use positive-semidefinite (psd) matrices of orders which rapidly increase with the level of approximation, alternatives focus on the problem of keeping p...
-
作者：Pang, Jong-Shi; Sen, Suvrajeet; Shanbhag, Uday V.
作者单位：University of Southern California; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and r...
-
作者：Nakatsukasa, Yuji; Soma, Tasuku; Uschmajew, Andre
作者单位：University of Oxford; University of Tokyo; University of Bonn; University of Bonn
摘要：For a given matrix subspace, how can we find a basis that consists of low-rank matrices? This is a generalization of the sparse vector problem. It turns out that when the subspace is spanned by rank-1 matrices, the matrices can be obtained by the tensor CP decomposition. For the higher rank case, the situation is not as straightforward. In this work we present an algorithm based on a greedy process applicable to higher rank problems. Our algorithm first estimates the minimum rank by applying s...
-
作者：Puerto, J.; Rodriguez-Chia, A. M.; Tamir, A.
作者单位：University of Sevilla; Universidad de Cadiz; Tel Aviv University
摘要：In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this prob...
-
作者：Anthony, Martin; Boros, Endre; Crama, Yves; Gruber, Aritanan
作者单位：University of London; London School Economics & Political Science; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; University of Liege; Universidade de Sao Paulo
摘要：Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recent...
-
作者：Chen, Liang; Sun, Defeng; Toh, Kim-Chuan
作者单位：Hunan University; National University of Singapore; National University of Singapore
摘要：In this paper, we propose an inexact multi-block ADMM-type first-order method for solving a class of high-dimensional convex composite conic optimization problems to moderate accuracy. The design of this method combines an inexact 2-block majorized semi-proximal ADMM and the recent advances in the inexact symmetric Gauss-Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block-variable. One ...
-
作者：Qi, Yunwei; Sen, Suvrajeet
作者单位：University System of Ohio; Ohio State University; University of Southern California
摘要：This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first-stage approximation is solved by a branch-and-bound algorithm with its nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second-stage mixe...
