40 results
Search Results
2. Maximizing monotone submodular functions over the integer lattice.
- Author
-
Soma, Tasuku and Yoshida, Yuichi
- Subjects
MATHEMATICAL functions ,ALGORITHMS ,VECTORS (Calculus) ,ALGEBRA ,MATHEMATICAL analysis - Abstract
The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. Scenario reduction for stochastic programs with Conditional Value-at-Risk.
- Author
-
Arpón, Sebastián, Homem-de-Mello, Tito, and Pagnoncelli, Bernardo
- Subjects
MATHEMATICAL optimization ,MAXIMA & minima ,OPERATIONS research ,RANDOM variables ,MATHEMATICAL analysis - Abstract
In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem easier to solve. The majority of works for scenario reduction are designed for classical risk-neutral stochastic optimization problems; however, it is intuitive that in the risk-averse case one is more concerned with scenarios that correspond to high cost. By building upon the notion of effective scenarios recently introduced in the literature, we formalize that intuitive idea and propose a scenario reduction technique for stochastic optimization problems where the objective function is a Conditional Value-at-Risk. Numerical results presented with problems from the literature illustrate the performance of the method and indicate the cases where we expect it to perform well. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
4. Smooth hyperbolicity cones are spectrahedral shadows.
- Author
-
Netzer, Tim and Sanyal, Raman
- Subjects
POLYNOMIALS ,HYPERBOLIC spaces ,SET theory ,CONES ,LINEAR systems ,MATHEMATICAL analysis - Abstract
Hyperbolicity cones are convex algebraic cones arising from hyperbolic polynomials. A well-understood subclass of hyperbolicity cones is that of spectrahedral cones and it is conjectured that every hyperbolicity cone is spectrahedral. In this paper we prove a weaker version of this conjecture by showing that every smooth hyperbolicity cone is the linear projection of a spectrahedral cone, that is, a spectrahedral shadow. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
5. Nearly linear-time packing and covering LP solvers: Achieving width-independence and -convergence.
- Author
-
Allen-Zhu, Zeyuan and Orecchia, Lorenzo
- Subjects
BANACH spaces ,LINEAR statistical models ,FUNCTIONAL equations ,MATHEMATICAL analysis ,NUMERICAL analysis - Abstract
Packing and covering linear programs (PC-LP s) form an important class of linear programs (LPs) across computer science, operations research, and optimization. Luby and Nisan (in: STOC, ACM Press, New York, 1993) constructed an iterative algorithm for approximately solving PC-LP s in nearly linear time, where the time complexity scales nearly linearly in N, the number of nonzero entries of the matrix, and polynomially in ε , the (multiplicative) approximation error. Unfortunately, existing nearly linear-time algorithms (Plotkin et al. in Math Oper Res 20(2):257–301, 1995; Bartal et al., in: Proceedings 38th annual symposium on foundations of computer science, IEEE Computer Society, 1997; Young, in: 42nd annual IEEE symposium on foundations of computer science (FOCS'01), IEEE Computer Society, 2001; Koufogiannakis and Young in Algorithmica 70:494–506, 2013; Young in Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs, 2014. arXiv:1407.3015; Allen-Zhu and Orecchia, in: SODA, 2015) for solving PC-LP s require time at least proportional to ε - 2 . In this paper, we break this longstanding barrier by designing a packing solver that runs in time O ~ (N ε - 1) and covering LP solver that runs in time O ~ (N ε - 1.5) . Our packing solver can be extended to run in time O ~ (N ε - 1) for a class of well-behaved covering programs. In a follow-up work, Wang et al. (in: ICALP, 2016) showed that all covering LPs can be converted into well-behaved ones by a reduction that blows up the problem size only logarithmically. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
6. Polytopes associated with symmetry handling.
- Author
-
Hojny, Christopher and Pfetsch, Marc E.
- Subjects
POLYTOPES ,POLYHEDRAL functions ,INTEGER programming ,MATHEMATICAL analysis ,NUMERICAL analysis - Abstract
This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with ternary coefficients, based on knapsack polytopes arising from a single lexicographic order enforcing inequality. We show that for these polytopes, the optimization as well as the separation problem of minimal cover inequalities can be solved in almost linear time. We demonstrate the usefulness of this approach by computational experiments, showing that it is competitive with state-of-the-art methods and is considerably faster for specific problem classes. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
7. On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints.
- Author
-
Awasthi, Pranjal, Goyal, Vineet, and Lu, Brian Y.
- Subjects
APPROXIMATION algorithms ,MATHEMATICS theorems ,FINITE element method ,MATHEMATICAL analysis ,VARIATIONAL inequalities (Mathematics) - Abstract
In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage constraints from a given uncertainty set. We consider the case where the uncertainty set is column-wise and constraint-wise (any constraint describing the set involve entries of only a single column or a single row). This is a fairly general class of uncertainty sets to model constraint coefficient uncertainty. We show that the two-stage adjustable robust problem is Ω(logn)-hard to approximate. On the positive side, we show that a static solution is an O(logn·min(logΓ,log(m+n)))-approximation for the two-stage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and Γ is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant Γ, surprisingly the performance bound for static solutions and therefore, the adaptivity gap matches the hardness of approximation for the adjustable problems. Furthermore, in general the static solution provides nearly the best efficient approximation for the two-stage adjustable robust problem. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
8. Constant factor approximation for ATSP with two edge weights.
- Author
-
Svensson, Ola, Tarnawski, Jakub, and Végh, László A.
- Subjects
APPROXIMATION theory ,NUMERICAL analysis ,FUNCTIONAL analysis ,MATHEMATICAL analysis ,ALGORITHMS - Abstract
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
9. Polyhedral approximation in mixed-integer convex optimization.
- Author
-
Lubin, Miles, Yamangil, Emre, Bent, Russell, and Vielma, Juan Pablo
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,ALGEBRA ,MATHEMATICAL analysis ,MACHINE learning - Abstract
Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
10. On quantile cuts and their closure for chance constrained optimization problems.
- Author
-
Xie, Weijun and Ahmed, Shabbir
- Subjects
MATHEMATICAL programming ,MATHEMATICAL analysis ,MATHEMATICAL optimization ,MATHEMATICS ,POLYHEDRA - Abstract
A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MINLP formulation have been developed. In this paper we consider a family of cuts in the original space rather than those in the extended space of the MINLP reformulation. These cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MINLP reformulation onto the original problem space. We show that the closure of the infinite family of all quantile cuts has a finite description. An important corollary of this result is that for linear chance constrained problems the quantile closure is polyhedral. We further show that a recursive application of quantile closure operations recovers the convex hull of the nonconvex chance constrained set in the limit, and in the pure integer setting the convergence is finite. We show that separation of quantile cuts is in general NP-hard, develop a heuristic separation method, and demonstrate its effectiveness through a computational study. We also study an approximation of the quantile closure and propose a generalization by grouping scenarios. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
11. A parametric simplex algorithm for linear vector optimization problems.
- Author
-
Rudloff, Birgit, Ulus, Firdevs, and Vanderbei, Robert
- Subjects
PARAMETRIC downconversion ,ALGORITHMS ,MATHEMATICAL optimization ,VECTOR spaces ,MATHEMATICAL analysis - Abstract
In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287-1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson's algorithm in Hamel et al. (J Global Optim 59(4):811-836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans-Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with the Evans-Steuer algorithm. For highly degenerate problems Benson's algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans-Steuer algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
12. Conditioning of linear-quadratic two-stage stochastic optimization problems.
- Author
-
Emich, Konstantin, Henrion, René, and Römisch, Werner
- Subjects
MATHEMATICAL optimization ,LINEAR control systems ,LIPSCHITZ spaces ,CONTROL theory (Engineering) ,MATHEMATICAL analysis - Abstract
In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
13. Applications of convex analysis within mathematics.
- Author
-
Aragón Artacho, Francisco, Borwein, Jonathan, Martín-Márquez, Victoria, and Yao, Liangjin
- Subjects
CONVEX functions ,MONOTONE operators ,HILBERT space ,MATHEMATICAL analysis ,LINEAR control systems ,MATHEMATICAL optimization - Abstract
In this paper, we study convex analysis and its theoretical applications. We first apply important tools of convex analysis to Optimization and to Analysis. We then show various deep applications of convex analysis and especially infimal convolution in Monotone Operator Theory. Among other things, we recapture the Minty surjectivity theorem in Hilbert space, and present a new proof of the sum theorem in reflexive spaces. More technically, we also discuss autoconjugate representers for maximally monotone operators. Finally, we consider various other applications in mathematical analysis. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
14. Two pairs of families of polyhedral norms versus $$\ell _p$$ ℓ p -norms: proximity and applications in optimization
- Author
-
Jun-ya Gotoh and Stan Uryasev
- Subjects
021103 operations research ,Linear programming ,General Mathematics ,Mathematical analysis ,0211 other engineering and technologies ,020206 networking & telecommunications ,Single parameter ,02 engineering and technology ,Limiting ,Combinatorics ,0202 electrical engineering, electronic engineering, information engineering ,Convex combination ,Software ,Dual norm ,Mathematics ,Dual pair - Abstract
This paper studies four families of polyhedral norms parametrized by a single parameter. The first two families consist of the CVaR norm (which is equivalent to the D-norm, or the largest-$$k$$k norm) and its dual norm, while the second two families consist of the convex combination of the $$\ell _1$$l1- and $$\ell _\infty $$l?-norms, referred to as the deltoidal norm, and its dual norm. These families contain the $$\ell _1$$l1- and $$\ell _\infty $$l?-norms as special limiting cases. These norms can be represented using linear programming (LP) and the size of LP formulations is independent of the norm parameters. The purpose of this paper is to establish a relation of the considered LP-representable norms to the $$\ell _p$$lp-norm and to demonstrate their potential in optimization. On the basis of the ratio of the tight lower and upper bounds of the ratio of two norms, we show that in each dual pair, the primal and dual norms can equivalently well approximate the $$\ell _p$$lp- and $$\ell _q$$lq-norms, respectively, for $$p,q\in [1,\infty ]$$p,q?[1,?] satisfying $$1/p+1/q=1$$1/p+1/q=1. In addition, the deltoidal norm and its dual norm are shown to have better proximity to the $$\ell _p$$lp-norm than the CVaR norm and its dual. Numerical examples demonstrate that LP solutions with optimized parameters attain better approximation of the $$\ell _{2}$$l2-norm than the $$\ell _1$$l1- and $$\ell _\infty $$l?-norms do.
- Published
- 2015
15. A nonsmooth Robinson’s inverse function theorem in Banach spaces
- Author
-
Asen L. Dontchev and Radek Cibulka
- Subjects
Inverse function theorem ,0209 industrial biotechnology ,Pure mathematics ,Picard–Lindelöf theorem ,General Mathematics ,010102 general mathematics ,Mathematical analysis ,Eberlein–Šmulian theorem ,Banach space ,02 engineering and technology ,01 natural sciences ,Implicit function theorem ,020901 industrial engineering & automation ,Fréchet space ,Danskin's theorem ,0101 mathematics ,Bounded inverse theorem ,Software ,Mathematics - Abstract
In a recent paper, Izmailov (Math Program Ser A 147:581---590, 2014) derived an extension of Robinson's implicit function theorem for nonsmooth generalized equations in finite dimensions, which reduces to Clarke's inverse function theorem when the generalized equation is just an equation. Pales (J Math Anal Appl 209:202---220, 1997) gave earlier a generalization of Clarke's inverse function theorem to Banach spaces by employing Ioffe's strict pre-derivative. In this paper we generalize both theorems of Izmailov and Pales to nonsmooth generalized equations in Banach spaces.
- Published
- 2015
16. A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems.
- Author
-
Boland, Natashia, Christiansen, Jeffrey, Dandurand, Brian, Eberhard, Andrew, and Oliveira, Fabricio
- Subjects
LAGRANGIAN functions ,MATHEMATICAL optimization ,INTEGERS ,MATHEMATICAL analysis ,DIFFERENTIAL equations - Abstract
We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. We adapt the augmented Lagrangian method framework to address the presence of nonconvexity in the non-relaxed constraint set and to enable efficient parallelization. The development of our approach is most naturally compared with the development of proximal bundle methods and especially with their use of serious step conditions. However, deviations from these developments allow for an improvement in efficiency with which parallelization can be utilized. Pivotal in our modification to the augmented Lagrangian method is an integration of the simplicial decomposition method and the nonlinear block Gauss–Seidel method. An adaptation of a serious step condition associated with proximal bundle methods allows for the approximation tolerance to be automatically adjusted. Under mild conditions optimal dual convergence is proven, and we report computational results on test instances from the stochastic optimization literature. We demonstrate improvement in parallel speedup over a baseline parallel approach. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
17. Error bounds for monomial convexification in polynomial optimization.
- Author
-
Adams, Warren, Gupte, Akshay, and Xu, Yibo
- Subjects
POLYNOMIALS ,CONVEX functions ,MATHEMATICAL optimization ,APPROXIMATION theory ,MATHEMATICAL analysis - Abstract
Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of. This implies additive error bounds for relaxing a polynomial optimization problem by convexifying each monomial separately. Our main error bounds depend primarily on the degree of the monomial, making them easy to compute. Since monomial convexification studies depend on the bounds on the associated variables, in the second part, we conduct an error analysis for a multilinear monomial over two different types of box constraints. As part of this analysis, we also derive the convex hull of a multilinear monomial over. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
18. Rates of convergence for inexact Krasnosel'skii–Mann iterations in Banach spaces.
- Author
-
Bravo, Mario, Cominetti, Roberto, and Pavez-Signé, Matías
- Subjects
BANACH spaces ,EVOLUTION equations ,NUMERICAL analysis ,FISHBONE diagrams ,MATHEMATICAL analysis - Abstract
We study the convergence of an inexact version of the classical Krasnosel'skii–Mann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. The results are applied to three variants of the basic iteration: infeasible iterations with approximate projections, the Ishikawa iteration, and diagonal Krasnosels'kii–Mann schemes. The results are also extended to continuous time in order to study the asymptotics of nonautonomous evolution equations governed by nonexpansive operators. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
19. On partial smoothness, tilt stability and the VU-decomposition.
- Author
-
Eberhard, A. C., Luo, Y., and Liu, S.
- Subjects
DIFFERENTIAL equations ,SMOOTHNESS of functions ,MATHEMATICAL analysis ,MATHEMATICAL functions ,FUNCTIONAL equations - Abstract
Under the assumption of prox-regularity and the presence of a tilt stable local minimum we are able to show that a VU like decomposition gives rise to the existence of a smooth manifold on which the function in question coincides locally with a smooth function. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
20. Scaling, proximity, and optimization of integrally convex functions.
- Author
-
Moriguchi, Satoko, Murota, Kazuo, Tamura, Akihisa, and Tardella, Fabio
- Subjects
MATHEMATICS theorems ,CONVEX functions ,MATHEMATICAL functions ,FUNCTIONAL equations ,MATHEMATICAL analysis - Abstract
In discrete convex analysis, the scaling and proximity properties for the class of L ♮ -convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n ≤ 2 , while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
21. On representing the positive semidefinite cone using the second-order cone.
- Author
-
Fawzi, Hamza
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,NUMERICAL analysis ,DIFFERENTIAL equations ,MATHEMATICS theorems - Abstract
The second-order cone plays an important role in convex optimization and has strong expressive abilities despite its apparent simplicity. Second-order cone formulations can also be solved more efficiently than semidefinite programming problems in general. We consider the following question, posed by Lewis and Glineur, Parrilo, Saunderson: is it possible to express the general positive semidefinite cone using second-order cones? We provide a negative answer to this question and show that the 3 × 3 positive semidefinite cone does not admit any second-order cone representation. In fact we show that the slice consisting of 3 × 3 positive semidefinite Hankel matrices does not admit a second-order cone representation. Our proof relies on exhibiting a sequence of submatrices of the slack matrix of the 3 × 3 positive semidefinite cone whose "second-order cone rank" grows to infinity. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
22. Robust monotone submodular function maximization.
- Author
-
Orlin, James B., Schulz, Andreas S., and Udwani, Rajan
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,ALGEBRA ,MATHEMATICAL analysis ,APPROXIMATION theory - Abstract
We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42:427-486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to τ elements from the chosen set. For the fundamental case of τ=1, we give a deterministic (1-1/e)-1/Θ(m) approximation algorithm, where m is an input parameter and number of queries scale as O(nm+1). In the process, we develop a deterministic (1-1/e)-1/Θ(m) approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (in: FOCS 10, IEEE, pp 575-584, 2010), we show a randomized (1-1/e)-ϵ approximation for constant τ and ϵ≤1Ω~(τ), making O(n1/ϵ3) queries. Further, for τ≪k, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. Strong reductions for extended formulations.
- Author
-
Braun, Gábor, Pokutta, Sebastian, and Roy, Aurko
- Subjects
MATHEMATICAL analysis ,ALGORITHMS ,MATHEMATICS ,ALGEBRA ,MATHEMATICAL models - Abstract
We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun et al. (Inapproximability of combinatorial problems via small LPs and SDPs, 2015) in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the problem, the problem, and the problem and show how to extend ad-hoc reductions between Sherali-Adams relaxations to reductions between LPs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
24. A polyhedral approach to online bipartite matching.
- Author
-
Torrico, Alfredo, Ahmed, Shabbir, and Toriello, Alejandro
- Subjects
PROBABILITY theory ,ALGORITHMS ,ALGEBRA ,NUMERICAL analysis ,MATHEMATICAL analysis - Abstract
We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various relaxations of the polyhedral set of achievable matching probabilities, introduce valid inequalities, and discuss when they are facet-defining. We also show how several of these relaxations correspond to ranking policies and their time-dependent generalizations. We finally present a computational study of these relaxations and policies to determine their empirical performance. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
25. Valid inequalities for separable concave constraints with indicator variables.
- Author
-
Lim, Cong Han, Linderoth, Jeff, and Luedtke, James
- Subjects
LINEAR programming ,MATHEMATICAL analysis ,LINEAR substitutions ,MATHEMATICS ,LINEAR equations - Abstract
We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. Extreme functions with an arbitrary number of slopes.
- Author
-
Basu, Amitabh, Conforti, Michele, Di Summa, Marco, and Paat, Joseph
- Subjects
NUMERICAL analysis ,MATHEMATICAL functions ,MATHEMATICAL analysis ,DIFFERENTIAL equations ,ADDITION (Mathematics) - Abstract
For the one dimensional infinite group relaxation, we construct a sequence of extreme valid functions that are piecewise linear and such that for every natural number k≥2, there is a function in the sequence with k slopes. This settles an open question in this area regarding a universal bound on the number of slopes for extreme functions. The function which is the pointwise limit of this sequence is an extreme valid function that is continuous and has an infinite number of slopes. This provides a new and more refined counterexample to an old conjecture of Gomory and Johnson stating that all extreme functions are piecewise linear. These constructions are extended to obtain functions for the higher dimensional group problems via the sequential-merge operation of Dey and Richard. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
27. Approximating graph-constrained max-cut.
- Author
-
Shen, Xiangkun, Lee, Jon, and Nagarajan, Viswanath
- Subjects
GRAPH theory ,ALGORITHMS ,GEOMETRY ,ALGEBRA ,MATHEMATICAL analysis - Abstract
An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G=(V,E) and (ii) edge-weights c:V2→R+ on a complete undirected graph. The objective is to find a subset S⊆V of vertices satisfying some graph-based constraint in G that maximizes the weight ∑u∈S,v∉Scuv of edges in the cut (S,V\S). The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a 12-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali-Adams hierarchy. It can handle any graph constraint for which there is a dynamic program of a specific form. Using known decomposition results, these imply essentially the same approximation ratio for GCMC under constraints such as independent set, dominating set and connectivity on a planar graph G. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
28. Minimal cut-generating functions are nearly extreme.
- Author
-
Basu, Amitabh, Hildebrand, Robert, and Molinaro, Marco
- Subjects
MATHEMATICAL functions ,INTEGERS ,MATHEMATICAL analysis ,MATHEMATICS ,APPROXIMATION theory - Abstract
We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Yıldız and Cornuéjols (Math Oper Res 41:1381-1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are “dense” in the set of continuous (strongly) minimal functions. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
29. Exact algorithms for the chance-constrained vehicle routing problem.
- Author
-
Dinh, Thai, Fukasawa, Ricardo, and Luedtke, James
- Subjects
VEHICLE routing problem ,MATHEMATICAL optimization ,PROBABILITY theory ,MATHEMATICAL analysis ,COMBINATORIAL optimization - Abstract
We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly NP-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
30. New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure.
- Author
-
Freund, Robert M. and Lu, Haihao
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,MATHEMATICAL functions ,FUNCTIONAL equations ,NONLINEAR analysis - Abstract
Motivated by recent work of Renegar (A framework for applying subgradient methods to conic optimization problems,
arXiv:1503.02611v2 ,2015 ) we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f∗=minx∈Qf(x), where we presume knowledge of a strict lower bound fslb . [Indeed, fslb is naturally known when optimizing many loss functions in statistics and machine learning (least-squares, logistic loss, exponential loss, total variation loss, etc.) as well as in Renegar’s transformed version of the standard conic optimization problem arXiv:1503.02611v2 ,2015 ; in all these cases one has fslb=0.] We introduce a new functional measure called the growth constant G for f(·) , that measures how quickly the level sets of f(·) grow relative to the function value, and that plays a fundamental role in the complexity analysis. When f(·) is non-smooth, we present new computational guarantees for the Subgradient Descent Method and for smoothing methods, that can improve existing computational guarantees in several ways, most notably when the initial iterate x0 is far from the optimal solution set. When f(·) is smooth, we present a scheme for periodically restarting the Accelerated Gradient Method that can also improve existing computational guarantees when x0 is far from the optimal solution set, and in the presence of added structure we present a scheme using parametrically increased smoothing that further improves the associated computational guarantees. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
31. Strong formulations for quadratic optimization with M-matrices and indicator variables.
- Author
-
Atamtürk, Alper and Gómez, Andrés
- Subjects
MATHEMATICAL optimization ,QUADRATIC programming ,NONLINEAR programming ,MATHEMATICAL analysis ,MAXIMA & minima - Abstract
We study quadratic optimization with indicator variables and an M-matrix, i.e., a PSD matrix with non-positive off-diagonal entries, which arises directly in image segmentation and portfolio optimization with transaction costs, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular minimization problem. To strengthen the formulation, we decompose the quadratic function into a sum of simple quadratic functions with at most two indicator variables each, and provide the convex-hull descriptions of these sets. We also describe strong conic quadratic valid inequalities. Preliminary computational experiments indicate that the proposed inequalities can substantially improve the strength of the continuous relaxations with respect to the standard perspective reformulation. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
32. Binary decision rules for multistage adaptive mixed-integer optimization.
- Author
-
Bertsimas, Dimitris and Georghiou, Angelos
- Subjects
MIXED integer linear programming ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,INDUSTRIAL efficiency - Abstract
Decision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameterised binary decision rule structure and derive the exact reformulation of the decision rule problem. In the cases where the resulting optimization problem grows exponentially with respect to the problem data, we provide a systematic methodology that trades-off scalability and optimality, resulting to practical binary decision rules. We also apply the proposed binary decision rules to the class of problems with random-recourse and show that they share similar complexity as the fixed-recourse problems. Our numerical results demonstrate the effectiveness of the proposed binary decision rules and show that they are (i) highly scalable and (ii) provide high quality solutions. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
33. Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming.
- Author
-
Liu, Minghui and Pataki, Gábor
- Subjects
LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,INDUSTRIAL efficiency - Abstract
In conic linear programming—in contrast to linear programming—the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality gap. The corresponding Farkas’ lemma is also not exact (it does not always prove infeasibility). We describe exact duals, and certificates of infeasibility and weak infeasibility for conic LPs which are nearly as simple as the Lagrange dual, but do not rely on any constraint qualification. Some of our exact duals generalize the SDP duals of Ramana, and Klep and Schweighofer to the context of general conic LPs. Some of our infeasibility certificates generalize the row echelon form of a linear system of equations: they consist of a small, trivially infeasible subsystem obtained by elementary row operations. We prove analogous results for weakly infeasible systems. We obtain some fundamental geometric corollaries: an exact characterization of when the linear image of a closed convex cone is closed, and an exact characterization of nice cones. Our infeasibility certificates provide algorithms to generate
all infeasible conic LPs over several important classes of cones; andall weakly infeasible SDPs in a natural class. Using these algorithms we generate a public domain library of infeasible and weakly infeasible SDPs. The status of our instances can be verified by inspection in exact arithmetic, but they turn out to be challenging for commercial and research codes. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
34. Data-driven inverse optimization with imperfect information.
- Author
-
Mohajerin Esfahani, Peyman, Shafieezadeh-Abadeh, Soroosh, Hanasusanto, Grani A., and Kuhn, Daniel
- Subjects
INVERSE problems ,MATHEMATICAL optimization ,LIPSCHITZ spaces ,ARTIFICIAL intelligence ,MATHEMATICAL analysis - Abstract
In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent's objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect information, that is, where the agent's true objective function is not contained in the search space of candidate objectives, where the agent suffers from bounded rationality or implementation errors, or where the observed signal-response pairs are corrupted by measurement noise. We formalize this inverse optimization problem as a distributionally robust program minimizing the worst-case risk that the predicted decision (i.e., the decision implied by a particular candidate objective) differs from the agent's actual response to a random signal. We show that our framework offers rigorous out-of-sample guarantees for different loss functions used to measure prediction errors and that the emerging inverse optimization problems can be exactly reformulated as (or safely approximated by) tractable convex programs when a new suboptimality loss function is used. We show through extensive numerical tests that the proposed distributionally robust approach to inverse optimization attains often better out-of-sample performance than the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
35. Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures.
- Author
-
Guigues, Vincent
- Subjects
STOCHASTIC analysis ,MATHEMATICAL analysis ,STOCHASTIC processes ,COUNTERPARTY risk ,ALGORITHMS - Abstract
We consider risk-averse convex stochastic programs expressed in terms of extended polyhedral risk measures. We derive computable confidence intervals on the optimal value of such stochastic programs using the Robust Stochastic Approximation and the Stochastic Mirror Descent (SMD) algorithms. When the objective functions are uniformly convex, we also propose a multistep extension of the Stochastic Mirror Descent algorithm and obtain confidence intervals on both the optimal values and optimal solutions. Numerical simulations show that our confidence intervals are much less conservative and are quicker to compute than previously obtained confidence intervals for SMD and that the multistep Stochastic Mirror Descent algorithm can obtain a good approximate solution much quicker than its nonmultistep counterpart. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
36. Sufficiency of cut-generating functions.
- Author
-
Cornuéjols, Gérard, Wolsey, Laurence, and Yıldız, Sercan
- Subjects
GENERATING functions ,PROBLEM solving ,POLYHEDRA ,MIXED integer linear programming ,MATHEMATICAL analysis - Abstract
The concept of cut-generating function has its origin in the work of Gomory and Johnson from the 1970s. It has received renewed attention in the past few years. Recently Conforti, Cornuéjols, Daniilidis, Lemaréchal, and Malick proposed a general framework for studying cut-generating functions. However, they gave an example showing that not all cuts can be produced by cut-generating functions in this framework. They conjectured a natural condition under which cut-generating functions might be sufficient. This note settles this open problem. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
37. Linear passive systems and maximal monotone mappings
- Author
-
Johannes Schumacher, M.K. Camlibel, Econometrics and Operations Research, Research Group: Operations Research, Systems, Control and Applied Analysis, Actuarial Science & Mathematical Finance (ASE, FEB), Doğuş Üniversitesi, Mühendislik Fakültesi, Elektronik ve Haberleşme Mühendisliği Bölümü, TR142349, and Çamlıbel, Mehmet Kanat
- Subjects
0209 industrial biotechnology ,Pure mathematics ,Mathematics(all) ,COMPLEMENTARITY SYSTEMS ,Dynamical systems theory ,Differential equation ,General Mathematics ,02 engineering and technology ,01 natural sciences ,020901 industrial engineering & automation ,Differential inclusion ,VARIATIONAL-INEQUALITIES ,Differential Equations ,Uniqueness ,0101 mathematics ,Mathematics ,Numerical analysis ,010102 general mathematics ,Linear system ,Mathematical analysis ,Linear Systems ,Dynamical Systems ,DIFFERENTIAL-INCLUSIONS ,NETWORKS ,Monotone polygon ,UNIQUENESS ,Mapping ,Variational inequality ,DYNAMICAL-SYSTEMS ,RELAY SYSTEMS ,Software ,ABSOLUTE STABILITY - Abstract
Çamlıbel, Mehmet Kanat (Dogus Author) This paper deals with a class of dynamical systems obtained from interconnecting linear systems with static set-valued relations. We first show that such an interconnection can be described by a differential inclusions with a maximal monotone set-valued mappings when the underlying linear system is passive and the static relation is maximal monotone. Based on the classical results on such differential inclusions, we conclude that such interconnections are well-posed in the sense of existence and uniqueness of solutions. Finally, we investigate conditions which guarantee well-posedness but are weaker than passivity.
- Published
- 2016
38. Simple examples for the failure of Newton’s method with line search for strictly convex minimization
- Author
-
Florian Jarre and Philippe L. Toint
- Subjects
021103 operations research ,Line search ,General Mathematics ,Numerical analysis ,Mathematical analysis ,Newton’s method ,0211 other engineering and technologies ,Convex minimization ,010103 numerical & computational mathematics ,02 engineering and technology ,Wolfe conditions ,01 natural sciences ,symbols.namesake ,Convex optimization ,symbols ,Minification ,0101 mathematics ,Invariant (mathematics) ,Convex function ,Newton's method ,Software ,Mathematics - Abstract
In this paper two simple examples of a twice continuously differentiable strictly convex function (Formula presented.) are presented for which Newton’s method with line search converges to a point where the gradient of (Formula presented.) is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function (Formula presented.) is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of (Formula presented.). Then (Formula presented.) is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant.
- Published
- 2016
39. $$L^{\infty }$$ L ∞ estimates on trajectories confined to a closed subset, for control systems with bounded time variation
- Author
-
Richard B. Vinter and Piernicola Bettiol
- Subjects
0209 industrial biotechnology ,General Mathematics ,010102 general mathematics ,Mathematical analysis ,Hamilton–Jacobi–Bellman equation ,02 engineering and technology ,Absolute continuity ,Optimal control ,Lipschitz continuity ,01 natural sciences ,Constraint (information theory) ,020901 industrial engineering & automation ,Bellman equation ,Bounded function ,Bounded variation ,0101 mathematics ,Software ,Mathematics - Abstract
The term ‘distance estimate’ for state constrained control systems refers to an estimate on the distance of an arbitrary state trajectory from the subset of state trajectories that satisfy a given state constraint. Distance estimates have found widespread application in state constrained optimal control. They have been used to establish regularity properties of the value function, to establish the non-degeneracy of first order conditions of optimality, and to validate the characterization of the value function as a unique solution of the HJB equation. The most extensively applied estimates of this nature are so-called linear \(L^\infty \) distance estimates. The earliest estimates of this nature were derived under hypotheses that required the multifunctions, or controlled differential equations, describing the dynamic constraint, to be locally Lipschitz continuous w.r.t. the time variable. Recently, it has been shown that the Lipschitz continuity hypothesis can be weakened to a one-sided absolute continuity hypothesis. This paper provides new, less restrictive, hypotheses on the time-dependence of the dynamic constraint, under which linear \(L^{\infty }\) estimates are valid. Here, one-sided absolute continuity is replaced by the requirement of one-sided bounded variation. This refinement of hypotheses is significant because it makes possible the application of analytical techniques based on distance estimates to important, new classes of discontinuous systems including some hybrid control systems. A number of examples are investigated showing that, for control systems that do not have bounded variation w.r.t. time, the desired estimates are not in general valid, and thereby illustrating the important role of the bounded variation hypothesis in distance estimate analysis.
- Published
- 2016
40. Nonsmooth Lyapunov pairs for differential inclusions governed by operators with nonempty interior domain
- Author
-
Michel Théra, Samir Adly, Abderrahim Hantoute, Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Centre de modélisation mathématique (CMM), and Universitad de Chile-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Lyapunov function ,Pure mathematics ,Current (mathematics) ,General Mathematics ,0211 other engineering and technologies ,Monotonic function ,02 engineering and technology ,Invariant sets ,01 natural sciences ,Domain (mathematical analysis) ,symbols.namesake ,Differential inclusion ,0101 mathematics ,Variational analysis ,Mathematics ,Lyapunov stability ,021103 operations research ,Generalized subdifferentials ,010102 general mathematics ,Mathematical analysis ,Lower semicontinuous Lyapunov pairs and functions ,Hilbert space ,Evolution differential inclusions ,Maximally monotone operators ,symbols ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,Software - Abstract
International audience; The general theory of Lyapunov stability of first-order differential inclu- sions in Hilbert spaces has been studied by the authors in the previous paper (Adly et al. in Nonlinear Anal 75(3): 985–1008, 2012). This new contribution focuses on the case when the interior of the domain of the maximally monotone operator governing the given differential inclusion is nonempty; this includes in a natural way the finite- dimensional case. The current setting leads to simplified, more explicit criteria and permits some flexibility in the choice of the generalized subdifferentials. Some con- sequences of the viability of closed sets are given. Our analysis makes use of standard tools from convex and variational analysis.
- Published
- 2015
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.