Search

In this work we investigate the min-max-min robust optimization problem and the k-adaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It is known that the min-max-min robust problem can be solved efficiently if k is at least the dimension of the problem, while it is theoretically and computationally hard if k is small. However, nothing is known about the intermediate case, i.e., k lies between one and the dimension of the problem. We approach this open question and present an approximation algorithm which achieves good problem-specific approximation guarantees for the cases where k is close to or a fraction of the dimension. The derived bounds can be used to show that the min-max-min robust problem is solvable in oracle-polynomial time under certain conditions even if k is smaller than the dimension. We extend the previous results to the robust k-adaptability problem. As a consequence we can provide bounds on the number of necessary second-stage policies to approximate the exact two-stage robust problem. We derive an approximation algorithm for the k-adaptability problem which has similar guarantees as for the min-max-min problem. Finally, we test both algorithms on knapsack and shortest path problems. The experiments show that both algorithms calculate solutions with relatively small optimality gap in seconds. [ABSTRACT FROM AUTHOR]

We consider min-max-min optimization with smooth and strongly convex objectives. Our motivation for studying this class of problems stems from its connection to the κ-center problem and the growing literature on min-max-min robust optimization. In particular, the considered class of problems nontrivially generalizes the Euclidean κ-center problem in the sense that distances in this more general setting do not necessarily satisfy metric properties. We present a 9κ-approximation algorithm (whereκ is the maximum condition number of the functions involved) that generalizes a simple greedy 2-approximation algorithm for the classical κ-center problem. We show that for any choice ofκ, there is an instance with a condition number ofκ per which our algorithm yields a (4κ+ 4κ + 1)-approximation guarantee, implying that our analysis is tight whenκ=1. Finally, we compare the computational performance of our approximation algorithm with an exact mixed integer linear programming approach. [ABSTRACT FROM AUTHOR]

The matrix spectral norm and nuclear norm appear in enormous applications. The generalization of these norms to higher-order tensors is becoming increasingly important, but unfortunately they are NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. In this paper, we bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. Our methods not only improve the approximation bound for the nuclear norm but also are data independent and easily implementable compared to existing approximation methods for the tensor spectral norm. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. We believe the ideas of constructions and the applications to approximate tensor norms can be useful to tackle optimization problems over other sets, such as the binary hypercube. [ABSTRACT FROM AUTHOR]

We study geometric duality for convex vector optimization problems. For a primal problem with a q-dimensional objective space, we formulate a dual problem with a (q+1)-dimensional objective space. Consequently, different from an existing approach, the geometric dual problem does not depend on a fixed direction parameter, and the resulting dual image is a convex cone. We prove a one-to-one correspondence between certain faces of the primal and dual images. In addition, we show that a polyhedral approximation for one image gives rise to a polyhedral approximation for the other. Based on this, we propose a geometric dual algorithm which solves the primal and dual problems simultaneously and is free of direction-biasedness. We also modify an existing direction-free primal algorithm in such a way that it solves the dual problem as well. We test the performance of the algorithms for randomly generated problem instances by using the so-called primal error and hypervolume indicator as performance measures. [ABSTRACT FROM AUTHOR]

We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]

We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. We propose a new convergent approach to solve these semi-infinite programs. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the considered semi-infinite programming problem. We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an inner-outer approximation algorithm, and its value converges to the value of the original semi-infinite problem. This new algorithmic approach is compared with the classical cutting plane algorithm. We also propose a new rate of convergence of the cutting plane algorithm, directly related to the iteration index, derived when the objective function is strongly convex, and under a strict feasibility assumption. We successfully test the two methods on two applications: the constrained quadratic regression and a zero-sum game with cubic payoff. Our results are compared to those obtained using the approach proposed in [A. Mitsos, Optimization, 60 (2011), pp. 1291-1308], as well as using the classical relaxation approach based on the KKT conditions of the lower-level problem. [ABSTRACT FROM AUTHOR]

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]

The stochastic auxiliary problem principle (APP) algorithm is a general stochastic approximation (SA) scheme that turns the resolution of an original convex optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for an SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the reflexive separable Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fejér monotonicity to our framework. [ABSTRACT FROM AUTHOR]

Fundamental in matrix algebra and its applications, a generalized inverse of a real matrix A is a matrix H that satisfies the Moore--Penrose (M--P) property AH A = A. If H also satisfies the additional useful M--P property, H AH = H, it is called a reflexive generalized inverse. Reflexivity is equivalent to minimum rank, so we are particularly interested in reflexive generalized inverses. We consider aspects of symmetry related to the calculation of a sparse reflexive generalized inverse of A. As is common, and following Fampa and Lee [Oper. Res. Lett., 46 (2018), pp. 605-610] for calculating sparse generalized inverses, we use (vector) 1-norm minimization for inducing sparsity and for keeping the magnitude of entries under control. When A is symmetric, we may naturally desire a symmetric H, while generally such a restriction on H may not lead to a 1-norm minimizing reflexive generalized inverse. We investigate a block construction method to produce a symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to block construct an approximate 1-norm minimizing symmetric reflexive generalized inverse. Another aspect of symmetry that we consider relates to another M--P property: H is ah-symmetric if AH is symmetric. The ah-symmetry property is the key one for solving least-squares problems using H. Here we do not assume that A is symmetric, and we do not impose symmetry on H. We investigate a column block construction method to produce an ah-symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to column block construct an approximate 1-norm minimizing ah-symmetric reflexive generalized inverse. [ABSTRACT FROM AUTHOR]

Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of the MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose integrating the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones. [ABSTRACT FROM AUTHOR]

In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363–381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS. [ABSTRACT FROM AUTHOR]

Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n ² log n) steps, where n denotes the total number of nodes. However, for k \geq 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1 102k², even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn² ). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points. [ABSTRACT FROM AUTHOR]

The MaxCut approximation algorithm by Goemans and Williamson is one of the most celebrated results in semidefinite optimization, and the corresponding MaxCut semidefinite optimization problem (SDP) has many favourable properties. The feasible regions of this class of SDPs are known as elliptopes, and they have been studied extensively. One of their nicest geo-metric/duality properties is the fact that their vertices correspond exactly to the cuts of a graph, as proved by Laurent and Poljak in 1995. Recall that a boundary pointx of a convex set C is called a vertex of C if the normal cone of C at x is full-dimensional. Semidefinite programs over elliptopes were also exploited by Goemans and Williamson and by Nesterov to develop approximation algorithms for the Maximum-2-Satisfiability problem and for nonconvex quadratic optimization problems, respectively. We study how often strict complementarity holds or fails for SDPs over elliptopes when a vertex is optimal, i.e., when the SDP relaxation is tight. While strict complementarity is known to hold when the objective function is in the interior of the normal cone at any vertex, we prove that it fails generically (in a context of Hausdorff measure and Hausdorff dimension) at the boundary of such normal cones. In this regard, SDPs over elliptopes display the nastiest behavior possible for a convex optimization problem. We also study strict complementarity with respect to two classes of objective functions. We show that, when the objective functions are sampled uniformly from a class of negative semidefinite rank-one matrices in the boundary of the normal cone at any vertex, the probability that strict complementarity holds lies in (0,1). To complete our study with a spectral-graph-theory-based viewpoint of the data for the MaxCut SDP, we extend a construction due to Laurent and Poljak of weighted Laplacian matrices for which strict complementarity fails. Their construction works for complete graphs, and we extend it to cosums of graphs under some mild conditions. [ABSTRACT FROM AUTHOR]

We propose a fully polynomial-time approximation scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs, and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single nondiscrete resource over a finite time horizon. We show that under a value oracle model for the cost functions this result for one-dimensional state space is the “best possible,” because a similar dynamic programming model with two-dimensional state space does not admit a polynomial-time approximation scheme. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing, under suitable conditions, how to deal with multidimensional action spaces and with vectors of continuous random variables with bounded support. These results bring us one step closer to overcoming the curse of dimensionality of dynamic programming. [ABSTRACT FROM AUTHOR]

We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time the enforcement of an invariant, which corresponds to the approximate duality gap decreasing at a certain rate, exactly recovers a wide range of first-order continuous-time methods. We characterize the discretization errors incurred by different discretization methods, and show how iteration-complexity-optimal methods for various classes of problems cancel out the discretization error. The techniques are illustrated on various classes of problems--including convex minimization for Lipschitz-continuous objectives, smooth convex minimization, composite minimization, smooth and strongly convex minimization, solving variational inequalities with monotone operators, and convex-concave saddle-point optimization--and naturally extend to other settings. [ABSTRACT FROM AUTHOR]

In stochastic programming, statistics, or econometrics, the aim is in general the optimization of a criterion function that depends on a decision variable ϑ and reads as an expectation with respect to a probability P. When this function cannot be computed in closed form, it is customary to approximate it through an empirical mean function based on a random sample. On the other hand, several other methods have been proposed, such as quasi-Monte Carlo integration and numerical integration rules. In this paper, we propose a general approach for approximating such a function, in the sense of epigraphical convergence, using a sequence of functions of simpler type which can be expressed as expectations with respect to probability measures Pn's that, in some sense, approximate P. The main difference with the existing results lies in the fact that our main theorem does not impose conditions directly on the approximating probabilities but only on some integrals with respect to them. In addition, the Pn's can be transition probabilities, i.e., are allowed to depend on a further parameter, ξ, whose value results from deterministic or stochastic operations, depending on the underlying model. This framework allows us to deal with a large variety of approximation procedures such as Monte Carlo, quasi--Monte Carlo, numerical integration, quantization, several variations on Monte Carlo sampling, and some density approximation algorithms. As by-products, we discuss convergence results for stochastic programming and statistical inference based on dependent data, for programming with estimated parameters, and for robust optimization; we also provide a general result about the consistency of the bootstrap for M-estimators. [ABSTRACT FROM AUTHOR]

In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing schemes, our proposed SDP formulation gives rise to solutions that can be leveraged to identify the clusters. We devise a new approximation algorithm for K-means clustering that utilizes the improved formulation and empirically illustrate its superiority over the state-of-the-art solution schemes. [ABSTRACT FROM AUTHOR]

We study a semide finite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [SIAM J. Optim., 19 (2008), pp. 1559{1573] and show that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with n. To obtain this result, we search for feasible solutions within a highly structured class of matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, these solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other TSP relaxations. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik [Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012, pp. 171{199.] for the k-cycle cover problem also has an unbounded integrality gap. [ABSTRACT FROM AUTHOR]

We propose an optimization model using a novel robust preference relationship| reference-based almost stochastic dominance (RSD). The concept of RSD addresses the two problems in utility-based decision making: (i) ambiguity and inaccuracy in characterizing the decision maker's individual risk attitude, and (ii) overconservativeness of stochastic dominance representing general properties of risk aversion. The RSD rule reveals the maximum dominance level quantifying the robustness of the decision maker's preference between alternative choices. We first develop an approximation model using Bernstein polynomials, show the asymptotic convergence of its optimal value and set of optimal solutions to their true counterparts as the degree of Bernstein polynomials increases, and analyze the convergence rate of its feasible region. We next develop a cut-generation algorithm to solve the approximation model. Finally, we further adapt this cut-generation algorithm to seek a valid option most robustly preferable to a random benchmark. The effectiveness and computational complexity of the model have been illustrated using a portfolio optimization problem. [ABSTRACT FROM AUTHOR]

We revisit a classical problem in transportation, known as the (bilevel) continuous network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing costs of the induced Wardrop equilibrium and the investment costs for installing the edge's capacities. While this problem is considered to be challenging in the literature, its complexity status was still unknown. We close this gap, showing that CNDP is strongly NP-hard and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions [P. Marcotte, Math. Prog., 34 (1986), pp. 142{162]. We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. Then, we prove that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, for example, this best-of-two approach achieves an approximation factor of 49=41 ≈ 1:195, which improves on the factor of 5=4 that has been shown before by Marcotte. [ABSTRACT FROM AUTHOR]

The ball-constrained weighted maximin dispersion problem (Pball) is to find a point in an n-dimensional Euclidean ball such that the minimum of the weighted Euclidean distance from given m points is maximized. We propose a new second-order cone programming relaxation for (Pball). Under the condition m ≤ n, (Pball) is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that (Pball) is NP-hard. Then, we propose a new randomized approximation algorithm for solving (Pball), which provides a new approximation bound of.... [ABSTRACT FROM AUTHOR]

We develop a convex approximation for two-stage mixed-integer recourse models, and we derive an error bound for this approximation that depends on the total variations of the probability density functions of the random variables in the model. We show that the error bound converges to zero if all these total variations converge to zero. Our convex approximation is a generalization of the one in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear] restricted to totally unimodular integer recourse models. For this special case it has the best worst-case error bound possible. The error bound in this paper is the first in the general setting of mixed-integer recourse models. As main building blocks in its derivation we generalize the asymptotic periodicity results of Gomory [Linear Algebra Appl., 2 (1969), pp. 451-558] for pure integer programs to the mixed-integer case, and we use the total variation error bounds on the expectation of periodic functions derived in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear]. [ABSTRACT FROM AUTHOR]

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of $K$-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674--685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set. [ABSTRACT FROM AUTHOR]

Many scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self-concordant barrier. We provide a new joint treatment of proximal and self-concordant barrier concepts and illustrate that such problems can be efficiently solved, without the need of lifting the problem dimensions, as in disciplined convex optimization approach. We propose an inexact path-following algorithmic framework and theoretically characterize the worst-case analytical complexity of this framework when the proximal subproblems are solved inexactly. To show the merits of our framework, we apply its instances to both synthetic and real-world applications, where it shows advantages over standard interior point methods. As a byproduct, we describe how our framework can obtain points on the Pareto frontier of regularized problems with self-concordant objectives in a tuning free fashion. [ABSTRACT FROM AUTHOR]

Multistate stochastic programs pose some of the more challenging optimization problems. Because such models can become rather intractable in general, it is important to design algorithms that can provide approximations which, in the long run, yield solutions that are arbitrarily close to an optimum. In this paper, we propose such a sequential sampling method which is applicable to multistage stochastic linear programs, and we refer to it as the multistage stochastic decomposition (MSD) algorithm. This algorithm represents a dynamic extension of a regularized version of stochastic decomposition (SD). While the method allows general correlation structures, specialized streamlined versions are also possible for special cases of stagewise independent and autoregressive processes commonly incorporated in stochastic programming. As with its two-stage counterpait, the MSD algorithm is shown to provide an asymptotically optimal solution, with probability one. As a by-product of this study, we also show that SD algorithms draw upon features of both approximate dynamic programming as well as stochastic programming. [ABSTRACT FROM AUTHOR]

We consider the general polynomial optimization problem P : /* = min{f(x) : x ∈ K}, where K is a compact basic semialgebraic set. We first show that the standard Lagrangian relaxation yields a lower bound as close as desired to the global optimum /*, provided that it is applied to a problem P equivalent to P, in which sufficiently many redundant constraints (products of the initial ones) are added to the initial description of P. Next we show that the standard hierarchy of linear program (LP-)relaxations of P (in the spirit of the Sherali--Adams reformulation-linearization technique) can be interpreted as a brute force simplification of the above Lagrangian relaxation in which a nonnegative polynomial (with coefficients to be determined) is replaced with a constant polynomial equal to zero. Inspired by this interpretation, we provide a systematic improvement of the LP-hierarchy by doing a much less brutal simplification which results into a parametrized hierarchy of semidefinite programs (and not LPs any more). For each semidefinite program in the parametrized hierarchy, the semidefinite constraint has a fixed size O(nk), independent of the rank in the hierarchy. When applied to a nontrivial class of convex problems, the first relaxation of the parametrized hierarchy is exact, in contrast with the LP-hierarchy, where convergence cannot be finite. [ABSTRACT FROM AUTHOR]

We present a bundle method for convex nondifferentiable minimization where the model is a piecewise-quadratic convex approximation of the objective function. Unlike standard bundle approaches, the model only needs to support the objective function from below at a properly chosen (small) subset of points, as opposed to everywhere. We provide the convergence analysis for the algorithm, with a general form of master problem which combines features of trust region stabilization and proximity stabilization, taking care of all the important practical aspects such as proper handling of the proximity parameters and the bundle of information. Numerical results are also reported. [ABSTRACT FROM AUTHOR]

We study linear optimization problems over the cone of copositive matrices. These problems appear in nonconvex quadratic and binary optimization; for instance, the maximum clique problem and other combinatorial problems can be reformulated as such problems. We present new polyhedral inner and outer approximations of the copositive cone which we show to be exact in the limit. In contrast to previous approximation schemes, our approximation is not necessarily uniform for the whole cone but can be guided adaptively through the objective function, yielding a good approximation in those parts of the cone that are relevant for the optimization and only a coarse approximation in those parts that are not. Using these approximations, we derive an adaptive linear approximation algorithm for copositive programs. Numerical experiments show that our algorithm gives very good results for certain nonconvex quadratic problems. [ABSTRACT FROM AUTHOR]

Given A := {a¹, . . . , am} ⊂ ℝn, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of A. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in A that are guaranteed to lie in the interior of the minimum-radius ball enclosing A. Our computational results reveal that incorporating this procedure into two recent algorithms proposed by Yildirim lead to significant speed-ups in running times especially for randomly generated largescale problems. We also illustrate that the extra overhead due to the elimination procedure remains at an acceptable level for spherical or almost spherical input sets. [ABSTRACT FROM AUTHOR]

We consider the offline and online versions of a bin packing problem called bin packing with conflicts. Given a set of items V = {1, 2, . . . ,n} with sizes s1, s2, . . . , sn ∈ [0, 1] and a conflict graph G = (V,E), the goal is to find a partition of the items into independent sets of G, where the total size of items in each independent set is at most 1 so that the number of independent sets in the partition is minimized. This problem is clearly a generalization of both the classical (one-dimensional) bin packing problem where E = ø and of the graph coloring problem where si = 0 for all i = 1, 2, . . . , n. Since coloring problems on general graphs are hard to approximate, following previous work, we study the problem on specific graph classes. For the offline version, we design improved approximation algorithms for perfect graphs and other special classes of graphs: These are a 5÷2 = 2.5-approximation algorithm for perfect graphs; a 7÷3 ≈ 2.33333-approximation algorithm for a subclass of perfect graphs, which contains interval graphs and chordal graphs; and a 7÷4 = 1.75-approximation for algorithm bipartite graphs. For the online problem on interval graphs, we design a 4.7-competitive algorithm and show a lower bound of 155÷36 ≈ 4.30556 on the competitive ratio of any algorithm. To derive the last lower bound, we introduce the first lower bound on the asymptotic competitive ratio of any online bin packing algorithm with known optimal value, which is 47÷36 ≈ 1.30556. [ABSTRACT FROM AUTHOR]

Given A := {a¹, . . . ,am} ⊂ ℝn and ∈ > 0, we propose and analyze two algorithms for the problem of computing a (1+∈)-approximation to the radius of the minimum enclosing ball of A. The first algorithm is closely related to the Frank--Wolfe algorithm with a proper initialization applied to the dual formulation of the minimum enclosing ball problem. We establish that this algorithm converges in O(1/∈) iterations with an overall complexity bound of O(mn/∈) arithmetic operations. In addition, the algorithm returns a "core set" of size O(1/∈), which is independent of both m and n. The latter algorithm is obtained by incorporating "away" steps into the former one at each iteration and achieves the same asymptotic complexity bound as the first one. While the asymptotic bound on the size of the core set returned by the second algorithm also remains the same as the first one, the latter algorithm has the potential to compute even smaller core sets in practice, since, in contrast to the former one, it allows "dropping" points from the working core set at each iteration. Our analysis reveals that the leading terms in the asymptotic complexity analysis are reasonably small. In contrast to the first algorithm, we also establish that the second algorithm asymptotically exhibits linear convergence, which provides further insight into our computational results, indicating that the latter algorithm indeed terminates faster with smaller core sets in comparison with the first one. We also discuss how our algorithms can be extended to compute an approximation to the minimum enclosing ball of more general input sets without sacrificing the iteration complexity and the bound on the core set size. In particular, we establish the existence of a core set of size O(1/∈) for a much wider class of input sets. We adopt the real number model of computation in our analysis. [ABSTRACT FROM AUTHOR]

We show that any rational convex polytope is polynomial-time representable as a 3-way line-sum transportation polytope of "slim" (r, c, 3) format. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure. We provide a polynomial-time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bitransportation programs. Our construction resolves several standing problems on 3-way transportation polytopes. For example, it demonstrates that, unlike the case of 2-way contingency tables, the range of values an entry can attain in any slim 3-way contingency table with specified 2-margins can contain arbitrary gaps. Our smallest such example has format (6, 4, 3). Our construction provides a powerful automatic tool for studying concrete questions about transportation polytopes and contingency tables. For example, it automatically provides new proofs for some classical results, including a well-known "real-feasible but integer-infeasible" (6, 4, 3)-transportation polytope of M. Vlach, and bitransportation programs where any feasible bitransportation must have an arbitrarily large prescribed denominator. [ABSTRACT FROM AUTHOR]

Let S denote the convex hull of m full-dimensional ellipsoids in ℝn. Given ∈ > 0 and δ > 0, we study the problems of computing a (1 + ∈)-approximation to the minimum volume covering ellipsoid of S and a (1 + δ)n-rounding of S. We extend the first-order algorithm of Kumar and Yildirim [J. Optim. Theory Appl., 126 (2005), pp. 1-21] that computes an approximation to the minimum volume covering ellipsoid of a finite set of points inℝn, which, in turn, is a modification of Khachiyan's algorithm [L. G. Khachiyan, Math. Oper. Res., 21 (1996), pp. 307-320]. Our algorithm can also compute a (1 + δ)n-rounding of S. For fixed ∈ > 0 and δ > 0, we establish polynomial-time complexity results for the respective problems, each of which is linear in the number of ellipsoids m. In particular, our algorithm can approximate the minimum volume covering ellipsoid of S in asymptotically the same number of iterations as that required by the algorithm of Kumar and Yildirim to approximate the minimum volume covering ellipsoid of a set of m points. The main ingredient in our analysis is the extension of polynomial-time complexity of certain subroutines in the algorithm from a set of points to a set of ellipsoids. As a byproduct, our algorithm returns a finite "core" set X ⊆ S with the property that the minimum volume covering ellipsoid of X provides a good approximation to the minimum volume covering ellipsoid of S. Furthermore, the size of the core set depends only on the dimension n and the approximation parameter ∈, but not on the number of ellipsoids m. We also discuss the extent to which our algorithm can be used to compute an approximate minimum volume covering ellipsoid and an approximate n-rounding of the convex hull of other sets in ℝn. We adopt the real number model of computation in our analysis. [ABSTRACT FROM AUTHOR]

We propose an approximation algorithm based on the Lagrangian or price-directive decomposition method to compute an ∈ B approximate solution of the mixed fractional packing and covering problem: find x ∈ B such that f(x) ≤ (1+∈)a, g(x) ≥ (1-∈)b, where f(x), g(x) are vectors with M nonnegative convex and concave functions, a and b are M-dimensional nonnegative vectors, and B is a convex set that can be queried by an optimization oracle. We propose an algorithm that needs only O(M ∈ -2 O(M ∈ -1)) iterations or calls to the oracle. The main contribution is that the algorithm solves the general mixed fractional packing and covering problem (in contrast to pure fractional packing and covering problems and to the special mixed packing and covering problem with B = ℝ + N) and runs in time independent of the so-called width of the problem. [ABSTRACT FROM AUTHOR]

We propose a simple and natural linear randomized algorithm for the approximate 1-median selection problem in metric spaces. The 1-median of a finite subset S of a metric space is the element of S which minimizes the average distance from the remaining points in S. This problem is extremely important in most applications using clustering of metric spaces, but also in connection with several algorithms in bioinformatics. The only linear approximation algorithm for the 1-median problem, which provably works in any metric space without going through any Euclidean space, has been proposed by Indyk in [Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Atlanta, 1999, pp. 428--432]. However, Indyk's algorithm, which is based on sufficiently large sampling, turns out not to be a practical solution. The same holds true even for its heuristic variants which use samplings of smaller size. The algorithm we propose has a simple and efficient implementation, which performs better than Indyk's algorithm in practice. On the other hand, while the performance of Indyk's algorithm is guaranteed by an approximation factor, in the case of our algorithm we are only able to produce experimental evidence of its precision. Extensive experimentation has been performed on both synthetic and real input datasets. Synthetic datasets were generated with uniform and skewed distributions, using various metrics. Real datasets have been extrapolated from real world official databases available on the web. Successful results of the proposed algorithm are reported for several applications in bioinformatics and various classes of approximate search queries. [ABSTRACT FROM AUTHOR]