Search

Cooperative games form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing some of the most important solution concepts proposed in the literature. For this reason, a relevant question is whether one can give a polynomial-time characterization of submodular instances, for prominent cooperative games that are in general non-convex. In this paper, we focus on a fundamental and widely studied cooperative game, namely the spanning tree game. An efficient recognition of submodular instances of this game was not known so far, and explicitly mentioned as an open question in the literature. We here settle this open problem by giving a polynomial-time characterization of submodular spanning tree games.

In a recent paper M.C. Cheng proposed new criteria for the simplex algorithm which guarantee that (i) a nonbasic variable of a basic feasible solution will remain nonbasic in an optimal basic solution, (ii) a basic variable of a basic solution will remain basic in an optimal basic solution. This comment gives (i) a slight generalization of the first result and (ii) a counterexample to the second proposition.

We propose a complete-search algorithm for solving a class of non-convex, possibly infinite-dimensional, optimization problems to global optimality. We assume that the optimization variables are in a bounded subset of a Hilbert space, and we determine worst-case run-time bounds for the algorithm under certain regularity conditions of the cost functional and the constraint set. Because these run-time bounds are independent of the number of optimization variables and, in particular, are valid for optimization problems with infinitely many optimization variables, we prove that the algorithm converges to an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}ε-suboptimal global solution within finite run-time for any given termination tolerance \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon > 0$$\end{document}ε>0. Finally, we illustrate these results for a problem of calculus of variations.

In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem (CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities. The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting plane algorithm for the CVRP. Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances.

This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization problem to find the best set of input values of a given trained neural network in order to produce a predefined desired output in presence of constraints on input values. This paper analyzes the characteristics of optimal solutions of neural network inverse problems with rectified activation units and proposes an outer-approximation algorithm by exploiting their characteristics. The proposed outer-approximation guided optimization comprises primal and dual phases. The primal phase incorporates neighbor curvatures with neighbor outer-approximations to expedite the process. The dual phase identifies and utilizes the structure of local convex regions to improve the convergence to a local optimal solution. At last, computation experiments demonstrate the superiority of the proposed algorithm compared to a projected gradient method.

Choice of a risk measure for quantifying risk of an investment portfolio depends on the decision maker’s risk preference. In this paper, we consider the case when such a preference can be described by a law invariant coherent risk measure but the choice of a specific risk measure is ambiguous. We propose a robust spectral risk approach to address such ambiguity. Differing from Wang and Xu (SIAM J Optim 30(4):3198–3229, 2020), the new robust model allows one to elicit the decision maker’s risk preference through pairwise comparisons and use the elicited preference information to construct an ambiguity set of risk spectra. The robust spectral risk measure (RSRM) is based on the worst case risk spectrum from the set. To calculate RSRM and solve the associated optimal decision making problem, we use a technique from Acerbi and Simonetti (Portfolio optimization with spectral measures of risk. Working paper, 2002) to develop a new computational approach which is independent of order statistics and reformulate the robust spectral risk optimization problem as a single deterministic convex programming problem when the risk spectra in the ambiguity set are step-like. Moreover, we propose an approximation scheme when the risk spectra are not step-like and derive a bound for the model approximation error and its propagation to the optimal decision making problems. Some preliminary numerical test results are reported about the performance of the robust model and the computational scheme.

International audience; Sampled-data control systems have steadily been gaining interest for their applications in automatic engineering where they are implemented as digital controllers and recently results have been obtained in optimal control theory for nonlinear sampled-data control systems and certain generalizations. In this paper we derive a Pontryagin maximum principle for general nonlinear finite-dimensional optimal sampled-data control problems with running inequality state constraints. In particular, we obtain a nonpositive averaged Hamiltonian gradient condition with the adjoint vector being a function of bounded variations. Our proof is based on the Ekeland variational principle. In general, optimal control problems with running inequality state constraints are difficult to solve using numerical methods due to the discontinuities (the jumps and the singular part) of the adjoint vector. However in our case we find that under certain general hypotheses the adjoint vector only experiences jumps at most at the sampling times and moreover the trajectory only contacts the running inequality state constraints at most at the sampling times. We call this behavior a bouncing trajectory phenomenon and it constitutes the second major focus of this paper. Finally taking advantage of the bouncing trajectory phenomenon we numerically solve three examples with different kinds of constraints and in several dimensions.

Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best existing VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, path enumeration, and rounded capacity cuts; all generalized through the new concepts of “packing set” and “elementarity set”. The concepts are also used to derive a branching rule based on accumulated resource consumption and to generalize the Ryan and Foster branching rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in $$\mathcal{O}(|V|(|V| \log |V| + |E|))$$ time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in $$\mathcal{O}(|V|^2)$$ time. In two companion papers we showed that the MWSS problem can be solved in $$\mathcal{O}(|E| \log |V|)$$ time in claw-free graphs with $$\alpha (G) \le 3$$ and in $$\mathcal{O}(|V| \sqrt{|E|})$$ time in {claw, net}-free graphs with $$\alpha (G) \ge 4$$ . These results prove that the MWSS problem in a claw-free graph can be solved in $$\mathcal{O}(|V|^2 \log |V|)$$ time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs.

In this paper we study nonconvex and nonsmooth multi-block optimization over Euclidean embedded (smooth) Riemannian submanifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. By utilizing the embedding structure, we develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings, where the duality is with respect to the embedded Euclidean spaces. First, we introduce the optimality conditions for the afore-mentioned optimization models. Then, the notion of $$\epsilon $$ -stationary solutions is introduced as a result. The main part of the paper is to show that the proposed algorithms possess an iteration complexity of $$O(1/\epsilon ^2)$$ to reach an $$\epsilon $$ -stationary solution. For prohibitively large-size tensor or machine learning models, we present a sampling-based stochastic algorithm with the same iteration complexity bound in expectation. In case the subproblems are not analytically solvable, a feasible curvilinear line-search variant of the algorithm based on retraction operators is proposed. Finally, we show specifically how the algorithms can be implemented to solve a variety of practical problems such as the NP-hard maximum bisection problem, the $$\ell _q$$ regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods.

This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although prior work has established convergence results for algorithms that integrate both descent and negative curvature steps, there has not yet been extensive numerical evidence showing that such methods offer consistent performance improvements. In this paper, we present new frameworks for combining descent and negative curvature directions: alternating two-step approaches and dynamic step approaches. The aspect that distinguishes our approaches from ones previously proposed is that they make algorithmic decisions based on (estimated) upper-bounding models of the objective function. A consequence of this aspect is that our frameworks can, in theory, employ fixed stepsizes, which makes the methods readily translatable from deterministic to stochastic settings. For deterministic problems, we show that instances of our dynamic framework yield gains in performance compared to related methods that only follow descent steps. We also show that gains can be made in a stochastic setting in cases when a standard stochastic-gradient-type method might make slow progress.

Stochastic variational inequalities (SVI) provide a unified framework for the study of a general class of nonlinear optimization and Nash-type equilibrium problems with uncertain model data. Often the true solution to an SVI cannot be found directly and must be approximated. This paper considers the use of a sample average approximation (SAA), and proposes a new method to compute confidence intervals for individual components of the true SVI solution based on the asymptotic distribution of SAA solutions. We estimate the asymptotic distribution based on one SAA solution instead of generating multiple SAA solutions, and can handle inequality constraints without requiring the strict complementarity condition in the standard nonlinear programming setting. The method in this paper uses the confidence regions to guide the selection of a single piece of a piecewise linear function that governs the asymptotic distribution of SAA solutions, and does not rely on convergence rates of the SAA solutions in probability. It also provides options to control the computation procedure and investigate effects of certain key estimates on the intervals.

In this paper, we establish the convergence of the proximal alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) method for nonseparable minimization models with quadratic coupling terms. The novel convergence results presented in this paper answer several open questions that have been the subject of considerable discussion. We firstly extend the 2-block proximal ADMM to linearly constrained convex optimization with a coupled quadratic objective function, an area where theoretical understanding is currently lacking, and prove that the sequence generated by the proximal ADMM converges in point-wise manner to a primal-dual solution pair. Moreover, we apply randomly permuted ADMM (RPADMM) to nonseparable multi-block convex optimization, and prove its expected convergence for a class of nonseparable quadratic programming problems. When the linear constraint vanishes, the 2-block proximal ADMM and RPADMM reduce to the 2-block cyclic proximal BCD method and randomly permuted BCD (RPBCD). Our study provides the first iterate convergence result for 2-block cyclic proximal BCD without assuming the boundedness of the iterates. We also theoretically establish the expected iterate convergence result concerning multi-block RPBCD for convex quadratic optimization. In addition, we demonstrate that RPBCD may have a worse convergence rate than cyclic proximal BCD for 2-block convex quadratic minimization problems. Although the results on RPADMM and RPBCD are restricted to quadratic minimization models, they provide some interesting insights: (1) random permutation makes ADMM and BCD more robust for multi-block convex minimization problems; (2) cyclic BCD may outperform RPBCD for “nice” problems, and RPBCD should be applied with caution when solving general convex optimization problems especially with a few blocks.

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent's overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent's risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents' objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents' objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players' optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players' smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.

In this paper we introduce the notions of critical and noncritical multipliers for variational systems and extend to a general framework the corresponding notions by Izmailov and Solodov developed for classical Karush–Kuhn–Tucker (KKT) systems. It has been well recognized that critical multipliers are largely responsible for slow convergence of major primal–dual algorithms of optimization. The approach of this paper allows us to cover KKT systems arising in various classes of smooth and nonsmooth problems of constrained optimization including composite optimization, minimax problems, etc. Concentrating on a polyhedral subdifferential case and employing recent results of second-order subdifferential theory, we obtain complete characterizations of critical and noncritical multipliers via the problem data. It is shown that noncriticality is equivalent to a certain calmness property of a perturbed variational system and that critical multipliers can be ruled out by full stability of local minimizers in problems of composite optimization. For the latter class we establish the equivalence between noncriticality of multipliers and robust isolated calmness of the associated solution map and then derive explicit characterizations of these notions via appropriate second-order sufficient conditions. It is finally proved that the Lipschitz-like/Aubin property of solution maps yields their robust isolated calmness.

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.

Recently, Bandeira [arXiv:1509.00824] introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. In this paper, we devise such an algorithm for the problem of k-means clustering. First, we prove that Peng and Wei's semidefinite relaxation of k-means is tight with high probability under a distribution of planted clusters called the stochastic ball model. Our proof follows from a new dual certificate for integral solutions of this semidefinite program. Next, we show how to test the optimality of a proposed k-means solution using this dual certificate in quasilinear time. Finally, we analyze a version of spectral clustering from Peng and Wei that is designed to solve k-means in the case of two clusters. In particular, we show that this quasilinear-time method typically recovers planted clusters under the stochastic ball model., Major revision from previous version. This paper is a extension of and improvement to the authors' preprint [arXiv:1505.04778]

In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.

The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of "positive" ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks which improve on previously known bounds. Additionally the bounds we propose can be computed by semidefinite programming. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that is at least as good as other existing norm-based bounds. We mainly focus our attention on the two important cases of nonnegative rank and cp-rank where our bounds satisfying interesting properties: For the nonnegative rank we show that our lower bound can be interpreted as a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lov\'asz theta number of the rectangle graph of the matrix. We also prove that the lower bound inherits many of the structural properties satisfied by the nonnegative rank such as invariance under diagonal scaling, subadditivity, etc. We also apply our method to obtain lower bounds on the cp-rank for completely positive matrices. In this case we prove that our lower bound is always greater than or equal the plain rank lower bound, and we show that it has interesting connections with combinatorial lower bounds based on edge-clique cover number.

Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear inequalities for the disjunction and then using conic duality to derive a family of convex, possibly nonlinear, valid inequalities that correspond to these linear inequalities. We identify and study the cases where these valid inequalities can equivalently be expressed in conic quadratic form and where a single inequality from this family is sufficient to describe the convex hull. In particular, our results on two-term disjunctions on the second-order cone generalize related results on split cuts by Modaresi, Kilinc, and Vielma, and by Andersen and Jensen.

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.

This paper studies the use of mathematical programming for the repair and restoration of a transmission system after a significant disruption (e.g., a natural disaster). Such blackouts may last several days and have significant impact on human and economic welfare. The transmission system repair and restoration problem (TSRRP) consists in dispatching crews to repair damaged electrical components in order to minimize the size of the blackout. The TSRRP can be modeled as a large-scale mixed nonlinear, nonconvex program, including both routing components and the nonlinear steady-state power flow equations. To tackle its daunting computational complexity, this paper proposes a 2-stage approach, decoupling the restoration and repair aspects. The first step is a restoration ordering problem, a mixed nonlinear, nonconvex program which is approximated by a mixed integer program. The approximation does not use the traditional DC power flow approximation which is plagued by convergence issues and inoperable dispatches; rather, it uses the recent LPAC approximation that captures reactive power and voltage magnitudes. The second stage is a pickup and repair routing problem which is solved using a constraint-programming model, large neighborhood search, and a randomized adaptive decomposition. Experimental results on benchmarks based on the US electrical infrastructures and state-of-the-art damage scenarios indicate that the 2-stage approach provides significant improvements over the "best practice" in the field.

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.

This paper is devoted to the design of an efficient and convergent {semi-proximal} alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP., 39 pages, 1 figure, 4 tables

This special issue is dedicated to the geometry and complexity of lifts or extended formulations of convex sets which has been an active area of research in recent years. This developing field lies at the intersection of several areas such as convex geometry, polyhedral theory, real algebraic geometry, combinatorics, optimization, and computer science, among others. The idea of finding efficient representations of convex sets (especially polytopes) by expressing them as projections of simple convex sets in higher dimensions is not new and is well-known in areas such as integer programming and real algebraic geometry. The current view of the topic is inspired by the 1991 paper of Mihalis Yannakakis who showed that the matching polytope does not admit a small “symmetric” polyhedral lift, in striking contrast to the classical result of Jack Edmonds that linear optimization over the matching polytope is possible in polynomial time. Yannakakis also showed that there is a precise connection between the nonnegative rank of the slack matrix of a polytope and the size of the smallest polyhedral lift that is possible for this polytope. Both of these results have been extended in multiple directions in recent papers. The restrictions imposed by symmetry on the size of lifts has been explored in multiple papers by now. Also, the connection between lifts and nonnegative ranks have been extended to general convex sets and closed cones. In particular, positive semidefinite lifts of polytopes have received a fair bit of attention lately, while the older notion of

In this paper we continue the studies of the persistent effect of attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers. It appears very important to understand the nature of this striking phenomenon, in particular, because it is precisely the reason of slow convergence of such methods when applied to problems with degenerate constraints. All previously known results concerned with this effect were a posteriori by nature: they were showing that in case of convergence, the dual limit is in a sense unlikely to be noncritical. This paper suggests the first a priori result in this direction, showing that critical multipliers actually serve as attractors: for a fully quadratic optimization problem with equality constraints, under certain reasonable assumptions we establish actual local convergence of the Newton---Lagrange method to a critical multiplier starting from a "dense" set around a given critical multiplier. This is an important step forward in understanding the attraction phenomenon.

In this paper, we analyze and discuss the well-posedness of two new variants of the so-called sweeping process, introduced by Moreau in the early 70s (Moreau in Sem Anal Convexe Montpellier, 1971) with motivation in plasticity theory. The first new variant is concerned with the perturbation of the normal cone to the moving convex subset $$C(t)$$ C ( t ) , supposed to have a bounded variation, by a Lipschitz mapping. Under some assumptions on the data, we show that the perturbed differential measure inclusion has one and only one right continuous solution with bounded variation. The second variant, for which a large analysis is made, concerns a first order sweeping process with velocity in the moving set $$C(t)$$ C ( t ) . This class of problems subsumes as a particular case, the evolution variational inequalities [widely used in applied mathematics and unilateral mechanics (Duvaut and Lions in Inequalities in mechanics and physics. Springer, Berlin, 1976]. Assuming that the moving subset $$C(t)$$ C ( t ) has a continuous variation for every $$t\in [0,T]$$ t ? [ 0 , T ] with $$C(0)$$ C ( 0 ) bounded, we show that the problem has at least a Lipschitz continuous solution. The well-posedness of this class of sweeping process is obtained under the coercivity assumption of the involved operator. We also discuss some applications of the sweeping process to the study of vector hysteresis operators in the elastoplastic model (Kreja?i in Eur J Appl Math 2:281---292, 1991), to the planning procedure in mathematical economy (Henry in J Math Anal Appl 41:179---186, 1973 and Cornet in J. Math. Anal. Appl. 96:130---147, 1983), and to nonregular electrical circuits containing nonsmooth electronic devices like diodes (Acary et al. Nonsmooth modeling and simulation for switched circuits. Lecture notes in electrical engineering. Springer, New York 2011). The theoretical results are supported by some numerical simulations to prove the efficiency of the algorithm used in the existence proof. Our methodology is based only on tools from convex analysis. Like other papers in this collection, we show in this presentation how elegant modern convex analysis was influenced by Moreau's seminal work.

This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with $$m$$ m linear inequality constraints. When $$m=0,\,m = 1$$ m = 0 , m = 1 , or $$m = 2$$ m = 2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when $$m \ge 2$$ m ? 2 and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same convex relaxation may admit a gap with eTRS. This paper shows that the convex relaxation has no gap for arbitrary $$m$$ m as long as the linear constraints are non-intersecting.

This paper addresses a problem that is typical of multi-period capacity expansion equilibrium models: plants or sectors have different risk exposures that may warrant different costs of capital. The paper examines modifications of a capacity expansion model interpreted in equilibrium terms to account for asset-specific costs of capital

This paper addresses a new class of differential variational inequalities that have recently been introduced and investigated in finite dimensions as a new modeling paradigm of variational analysis to treat many applied problems in engineering, operations research, and physical sciences. This new subclass of general differential inclusions unifies ordinary differential equations with possibly discontinuous right-hand sides, differential algebraic systems with constraints, dynamic complementarity systems, and evolutionary variational systems. The purpose of this paper is two-fold. Firstly, we show that these differential variational inequalities, when considering slow solutions and the more general level of a Hilbert space, contain projected dynamical systems, another recent subclass of general differential inclusions. This relation follows from a precise geometric description of the directional derivative of the metric projection in Hilbert space, which is based on the notion of the quasi relative interior. Secondly we are concerned with stability of the solution set to this class of differential variational inequalities. Here we present a novel upper set convergence result with respect to perturbations in the data, including perturbations of the associated set-valued maps and the constraint set. Here we impose weak convergence assumptions on the perturbed set-valued maps, use the monotonicity method of Browder and Minty, and employ Mosco convergence as set convergence. Also as a consequence, we obtain a stability result for linear complementarity systems.

The paper studies regularity properties of set-valued mappings between metric spaces. In the context of metric regularity, nonlinear models correspond to nonlinear dependencies of estimates of error bounds in terms of residuals. Among the questions addressed in the paper are equivalence of the corresponding concepts of openness and “pseudo-Holder” behavior, general and local regularity criteria with special emphasis on “regularity of order $$k$$ ”, for local settings, and variational methods to extimate regularity moduli in case of length range spaces. The majority of the results presented in the paper are new.

We consider a version of the stochastic network interdiction problem modeled by Morton et al. (IIE Trans 39:3---14, 2007) in which an interdictor attempts to minimize a potential smuggler's chance of evasion via discrete deployment of sensors on arcs in a bipartite network. The smuggler reacts to sensor deployments by solving a maximum-reliability path problem on the resulting network. In this paper, we develop the (minimal) convex hull representation for the polytope linking the interdictor's decision variables with the smuggler's for the case in which the smuggler's origin and destination are known and interdictions are cardinality-constrained. In the process, we propose an exponential class of easily-separable inequalities that generalize all of those developed so far for the bipartite version of this problem. We show how these cuts may be employed in a cutting-plane fashion when solving the more difficult problem in which the smuggler's origin and destination are stochastic, and argue that some instances of the stochastic model have facets corresponding to the solution of NP-hard problems. Our computational results show that the cutting planes developed in this paper may strengthen the linear programming relaxation of the stochastic model by as much as 25 %.

This paper provides a rigorous asymptotic analysis and justification of upper and lower confidence bounds proposed by Dantzig and Infanger (A probabilistic lower bound for two-stage stochastic programs, Stanford University, CA, 1995) for an iterative sampling-based decomposition algorithm, introduced by Dantzig and Glynn (Ann. Oper. Res. 22:1–21, 1990) and Infanger (Ann. Oper. Res. 39:41–67, 1992), for solving two-stage stochastic programs. The paper provides confidence bounds in the presence of both independent sampling across iterations, and when common samples are used across different iterations. Confidence bounds for sample-average approximation then follow as a special case. Extensions of the theory to cover use of variance reduction and the dropping of cuts are also presented. An extensive empirical investigation of the performance of these bounds establishes that the bounds perform reasonably on realistic problems.

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory–Chvatal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality $$cx \le d$$ where $$c$$ and $$d$$ are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set $$P \cap \{x\in \mathbb R ^n \mid cx \ge d + 1\} \cap \mathbb Z ^n$$ is empty using cutting-planes from the black-box. Here $$P$$ is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures.

In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently been found to have many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to make the defined MCP tractable and meaningful, we must first understand the structure of these epigraphs. So far, only the epigraph of the Frobenius matrix norm, which can be regarded as a second order cone, has been well studied. Here, we take an initial step to study several important properties, including its closed form solution, calm Bouligand-differentiability and strong semismoothness, of the metric projection operator over the epigraph of the $$l_1,\,l_\infty $$, spectral or operator, and nuclear matrix norm, respectively. These properties make it possible to apply augmented Lagrangian methods, which have recently received a great deal of interests due to their high efficiency in solving large scale semidefinite programming, to this class of MCP problems. The work done in this paper is far from comprehensive. Rather it is intended as a starting point to call for more insightful research on MCP so that it can serve as a basic tool to solve more challenging convex matrix optimization problems in years to come.

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $\epsilon$-accurate solution with probability at least $1-\rho$ in at most $O(\tfrac{n}{\epsilon} \log \tfrac{1}{\rho})$ iterations, where $n$ is the number of blocks. For strongly convex functions the method converges linearly. This extends recent results of Nesterov [Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper #2010/2], which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\epsilon$ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving true iteration complexity bounds. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $\ell_1$-regularized least squares and support vector machine problems with a billion variables., Comment: 33 pages, 7 figures, 10 tables

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min---max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min---max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min---max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.

This paper presents a methodology for using varying sample sizes in batch-type optimization methods for large-scale machine learning problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the function and gradient. We propose a criterion for increasing the sample size based on variance estimates obtained during the computation of a batch gradient. We establish an $${O(1/\epsilon)}$$ complexity bound on the total cost of a gradient method. The second part of the paper describes a practical Newton method that uses a smaller sample to compute Hessian vector-products than to evaluate the function and the gradient, and that also employs a dynamic sampling technique. The focus of the paper shifts in the third part of the paper to L 1-regularized problems designed to produce sparse solutions. We propose a Newton-like method that consists of two phases: a (minimalistic) gradient projection phase that identifies zero variables, and subspace phase that applies a subsampled Hessian Newton iteration in the free variables. Numerical tests on speech recognition problems illustrate the performance of the algorithms.

In this paper we consider the infinite relaxation of the corner polyhedron with 2 rows. For the 1-row case, Gomory and Johnson proved in their seminal paper a sufficient condition for a minimal function to be extreme, the celebrated 2-Slope Theorem. Despite increased interest in understanding the multiple row setting, no generalization of this theorem was known for this case. We present an extension of the 2-Slope Theorem for the case of 2 rows by showing that minimal 3-slope functions satisfying an additional regularity condition are facets (and hence extreme). Moreover, we show that this regularity condition is necessary, unveiling a structure which is only present in the multi-row setting.

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate the proposed approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n−1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.

This paper studies the local analysis of equations on a product U × U of Banach spaces, whose variables lie in a subset having the special property that it is locally Lipschitz-homeomorphic to an open subset of U. A prominent example, to which we devote most of the paper, is a system of equations whose variables lie in the graph of a maximal monotone operator. This general formulation covers many specific problems of interest, and our objective is to understand the local behavior of solutions of such equations when they depend on parameters. We analyze this local behavior in stages, the first stage being to apply a tailored implicit-function theorem to an abstract formulation of the problem, thereby producing a set of results applicable to any particular problem instance. The second stage is to specialize the analysis to a Hilbert space H, with the subset mentioned above being the graph of a maximal monotone operator on H. This makes the results of the first stage applicable to many variational problems of practical importance. We then develop in detail the analytical steps to apply these results to finite-dimensional variational conditions with constraints of generalized nonlinear-programming type. The conditions thus identified generalize the strong second-order sufficient condition and linear-independence constraint qualification of nonlinear programming. A detailed example brings out some of the issues involved in practical implementation of this method. It also shows that aspects of representation (problem formulation) can strongly influence the feasibility of local analysis. This sensitivity to representation does not seem to be well known.

This paper presents a procedure to solve the classical location median problem where the distances are measured with lp-norms with p > 2. In order to do that we consider an approximated problem. The global convergence of the sequence generated by this iterative scheme is proved. Therefore, this paper closes the still open question of giving a modification of the Weiszfeld algorithm that converges to an optimal solution of the median problem with lp norms and \({p \in (2, \infty)}\). The paper ends with a computational analysis of the different provided iterative schemes.

This paper formally introduces a linear complementarity system (LCS) formulation for a continuous-time, multi-user class, dynamic user equilibrium (DUE) model for the determination of trip timing decisions in a simplified single bottleneck model. Existence of a Lipschitz solution trajectory to the model is established by a constructive time-stepping method whose convergence is rigorously analyzed. The solvability of the time-discretized subproblems by Lemke's algorithm is also proved. Combining linear complementarity with ordinary differential equations and being a new entry to the mathematical programming field, the LCS provides a computational tractable framework for the rigorous treatment of the DUE problem in continuous time, this paper makes a positive contribution in this promising research venue pertaining to the application of differential variational theory to dynamic traffic problems. � 2011 Springer and Mathematical Optimization Society.

This paper considers an important class of convex programming (CP) problems, namely, the stochastic composite optimization (SCO), whose objective function is given by the summation of general nonsmooth and smooth stochastic components. Since SCO covers non-smooth, smooth and stochastic CP as certain special cases, a valid lower bound on the rate of convergence for solving these problems is known from the classic complexity theory of convex programming. Note however that the optimization algorithms that can achieve this lower bound had never been developed. In this paper, we show that the simple mirror-descent stochastic approximation method exhibits the best-known rate of convergence for solving these problems. Our major contribution is to introduce the accelerated stochastic approximation (AC-SA) algorithm based on Nesterov’s optimal method for smooth CP (Nesterov in Doklady AN SSSR 269:543–547, 1983; Nesterov in Math Program 103:127–152, 2005), and show that the AC-SA algorithm can achieve the aforementioned lower bound on the rate of convergence for SCO. To the best of our knowledge, it is also the first universally optimal algorithm in the literature for solving non-smooth, smooth and stochastic CP problems. We illustrate the significant advantages of the AC-SA algorithm over existing methods in the context of solving a special but broad class of stochastic programming problems.

This special issue of Mathematical Programming Series B is titled Challenges and Opportunities for Optimization in Electricity Systems and contains six papers focused mainly on optimization in deregulated electricity markets. Since the 1990s markets for electricity generation and transmission have emerged around the world, and this volume focuses on mathematical programming models for understanding these markets. The special issue is dedicated to Professor Yves Smeers on the occasion of his retirement in 2010 from the University of Louvain, where he was Tractebel Professor of Energy Economics. For the last thirty years, Yves Smeers has been at the forefront of the development and understanding of models of competition, and their application to electricity systems, and his contributions to this field are widely recognized within the operations research and economics communities. He was made an INFORMS Fellow in 2012 for his pioneering work in this field. The papers in this volume all deal with aspects of electricity markets. Electricity auctions are designed with the goal of encouraging efficient markets. This means efficient dispatch of power at prices that give the correct economic signals for consumption

It is known that the Clarke generalized directional derivative is nonnegative along the limit directions generated by directional direct-search methods at a limit point of certain subsequences of unsuccessful iterates, if the function being minimized is Lipschitz continuous near the limit point. In this paper we generalize this result for discontinuous functions using Rockafellar generalized directional derivatives (upper subderivatives). We show that Rockafellar derivatives are also nonnegative along the limit directions of those subsequences of unsuccessful iterates when the function values converge to the function value at the limit point. This result is obtained assuming that the function is directionally Lipschitz with respect to the limit direction. It is also possible under appropriate conditions to establish more insightful results by showing that the sequence of points generated by these methods eventually approaches the limit point along the locally best branch or step function (when the number of steps is equal to two). The results of this paper are presented for constrained optimization and illustrated numerically.

[EN] In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. © 2010 Springer and Mathematical Optimization Society., The authors want to thank the three referees for their careful reading of the manuscript and for their many comments and suggestions that have contributed to improve the paper content and readability. In particular, several remarks regarding the discussion of C-G and mod-k inequalities were pointed out by one of the referees. A. Corberan, I. Plana and J.M. Sanchis wish to thank the Ministerio de Educacion y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support.

For 30 years after their invention half a century ago, cutting planes for integer programs have been an object of theoretical investigations that had no apparent practical use. When they finally proved their practical usefulness in the late eighties, that happened in the framework of branch and bound procedures, as an auxiliary tool meant to reduce the number of enumerated nodes. To this day, pure cutting plane methods alone have poor convergence properties and are typically not used in practice. Our reason for studying them is our belief that these negative properties can be understood and thus remedied only based on a thorough investigation of such procedures in their pure form. In this paper, the second in a sequence, we address some important issues arising when designing a computationally sound pure cutting plane method. We analyze the dual cutting plane procedure proposed by Gomory in 1958, which is the first (and most famous) convergent cutting plane method for integer linear programming. We focus on the enumerative nature of this method as evidenced by the relative computational success of its lexicographic version (as documented in our previous paper on the subject), and we propose new versions of Gomory’s cutting plane procedure with an improved performance. In particular, the new versions are based on enumerative schemes that treat the objective function implicitly, and redefine the lexicographic order on the fly to mimic a sound branching strategy. Preliminary computational results are reported.

In this paper, we consider various moment inequalities for sums of random matrices—which are well-studied in the functional analysis and probability theory literature—and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine’s inequality in functional analysis. Using this result, we show that an SDP-based algorithm of Nemirovski, which is developed for solving a class of quadratic optimization problems with orthogonality constraints, has a logarithmic approximation guarantee. This improves upon the polynomial approximation guarantee established earlier by Nemirovski. Furthermore, we obtain improved safe tractable approximations of a certain class of chance constrained linear matrix inequalities. Secondly, we consider a recent result of Delage and Ye on the so-called data-driven distributionally robust stochastic programming problem. One of the assumptions in the Delage–Ye result is that the underlying probability distribution has bounded support. However, using a suitable moment inequality, we show that the result in fact holds for a much larger class of probability distributions. Given the close connection between the behavior of sums of random matrices and the theoretical properties of various optimization problems, we expect that the moment inequalities discussed in this paper will find further applications in optimization.