-
作者：Jeyakumar, V
作者单位：University of New South Wales Sydney
摘要：The strong conical hull intersection property ( CHIP) is a geometric property of a collection of finitely many closed convex intersecting sets. This basic property, which was introduced by Deutsch et al. in 1997, is one of the central ingredients in the study of constrained interpolation and best approximation. In this paper we establish that the strong CHIP of intersecting sets of constraints is the key characterizing property for optimality and strong duality of convex programming problems. ...
-
作者：Salazar-González, JJ
作者单位：Universidad de la Laguna
摘要：Rounding methods are common techniques in many statistical offices to protect sensitive information when publishing data in tabular form. Classical versions of these methods do not consider protection levels while searching patterns with minimum information loss, and therefore typically the so-called auditing phase is required to check the protection of the proposed patterns. This paper presents a mathematical model for the whole problem of finding a protected pattern with minimum loss of info...
-
作者：Nesterov, Yurii; Polyak, B. T.
作者单位：Universite Catholique Louvain; V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
摘要：In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.
-
作者：Dyer, M; Stougie, L
作者单位：University of Leeds; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-sta...
-
作者：Bonomo, F; Durán, G; Lin, MC; Szwarcfiter, JL
作者单位：University of Buenos Aires; Universidad de Chile; Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
摘要：Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomia...
-
作者：Ahmed, S
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criteri...
-
作者：Perakis, G; Sood, A
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We study a multi-period oligopolistic market for a single perishable product with fixed inventory. Our goal is to address the competitive aspect of the problem together with demand uncertainty using ideas from robust optimization and variational inequalities. The demand function for each seller has some associated uncertainty and we assume that the sellers would like to adopt a policy that is robust to adverse uncertain circumstances. We believe this is the first paper that uses robust optimiz...
-
作者：Cameron, K; Hell, P
作者单位：Wilfrid Laurier University; Simon Fraser University
摘要：Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocompa...
-
作者：Bertsimas, Dimitris; Natarajan, Karthik; Teo, Chung-Piaw
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); National University of Singapore; National University of Singapore
摘要：An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the netw...
-
作者：Jibetean, D; de Klerk, E
作者单位：Eindhoven University of Technology; Tilburg University
摘要：We consider the problem of global minimization of rational functions on R-n (unconstrained case), and on an open, connected, semi-algebraic subset of R-n, or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [6]. This extends the analogous results by Nesterov [13] for global minimization of univa...
