Search

Abstract. In the paper "On the nucleolus of the basic vehicle routing game", Mathematical Programming 72, 83-100 (1996), Gothe-Lundgren et al. develop a constraint generation method to compute the pre-nucleolus of a game. Their method assumes that constraints that are redundant in the representation of the core can be ignored in the computation of the prenucleolus. We provide an example that shows that for a game with an empty core such an assumption is, in general, not valid. Further, we show that a statement made by Gothe-Lundgren et al. about an intuitive interpretation of the pre-nucleolus is misleading. [ABSTRACT FROM AUTHOR]

Branch and cut is the dominant paradigm for solving a wide range of mathematical programming problems—linear or nonlinear—combining efficient search (via branch and bound) and relaxation-tightening procedures (via cutting planes, or cuts). While there is a wealth of computational experience behind existing cutting strategies, there is simultaneously a relative lack of theoretical explanations for these choices, and for the tradeoffs involved therein. Recent papers have explored abstract models for branching and for comparing cuts with branch and bound. However, to model practice, it is crucial to understand the impact of jointly considering branching and cutting decisions. In this paper, we provide a framework for analyzing how cuts affect the size of branch-and-cut trees, as well as their impact on solution time. Our abstract model captures some of the key characteristics of real-world phenomena in branch-and-cut experiments, regarding whether to generate cuts only at the root or throughout the tree, how many rounds of cuts to add before starting to branch, and why cuts seem to exhibit nonmonotonic effects on the solution process. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including gradient descent, random initialization, and nonconvex optimization.

Currently, for generic MINLP for which no structure is known in advance, the best exact[2] algorithm for solving MINLP is the spatial Branch-and-Bound (sBB) algorithm. This special issue of Mathematical Programming series B collects papers authored (or co-authored) by researchers who attended the second Oberwolfach workshop on MINLP, titled "Mixed-integer Nonlinear Optimization: a hatchery for modern mathematics", and co-organized by the guest editors of this special issue. On the one hand such I mixed-integer optimal control i (MIOC) problems are a generalization of MINLPs, because the problem formulations allow for trivial special cases with HT ht differential states that are formally equivalent to a MINLP. The sBB algorithm is a variant of the Branch-and-Bound (BB) algorithm, which was introduced in [[32]] and extended to (separable) Nonlinear Programming (NLP) in [[17]]. [Extracted from the article]

This document provides a summary of research papers presented at a conference on mathematical optimization for fair social decisions. The conference honored Michel Balinski, a mathematician and economist known for his work in transportation problems, matching algorithms, voting theory, and fair representation. The papers covered a range of topics including optimal partisan gerrymandering, approval-based apportionment, and strategy-proof voting rules. Additionally, the document includes summaries of papers in the fields of network formation problems, game theory, and social choice theory, covering topics such as the median problem, minimum cut problems, network stability, splitting games, price of anarchy, online learning algorithms, cooperative games, and fair division. These summaries provide a quick overview of each paper's main contributions, helping library patrons determine their relevance to their research interests. [Extracted from the article]

In this paper, we point out some corrections needed in "Complexity of Stochastic Dual Dynamic Programming", a paper accepted to Mathematical Programming, 2020, online-first issue,. [ABSTRACT FROM AUTHOR]

Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller than ε in O (1 / ε 1.5) iterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger than - ε . In this paper, we study a generalization of ARC to optimization on Riemannian manifolds. In particular, we generalize the iteration complexity results to this richer framework. Our central contribution lies in the identification of appropriate manifold-specific assumptions that allow us to secure these complexity guarantees both when using the exponential map and when using a general retraction. A substantial part of the paper is devoted to studying these assumptions—relevant beyond ARC—and providing user-friendly sufficient conditions for them. Numerical experiments are encouraging. [ABSTRACT FROM AUTHOR]

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones. [ABSTRACT FROM AUTHOR]

More recently, Ahmed and co-authors invented the stochastic dual dynamic integer programming (SDDIP) algorithm [[82]], which extends the stochastic dual dynamic programming algorithm, a leading algorithm for solving multi-stage stochastic I linear i programs, to the mixed-integer setting. Zhang and Sun [[80]] present an extension of the stochastic dual dynamic integer programming algorithm for multi-stage stochastic mixed-integer nonlinear setting. Bodur, Ahmed, Boland and Nemhauser [[20]] exploit the idea of resource-directive decomposition to reformulate loosely coupled integer programs so that they can be decomposed into a resource-directive master problem and a set of multiobjective programming subproblems. Integer, stochastic, and nonconvex optimization problems enable modeling of an immense range of important and realistic settings. [Extracted from the article]

We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex conic programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order conic programs. This generalizes the algorithm proposed by Sen and Sherali [Mathematical Programming 106(2): 203–223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage solutions, and solution to an optimization problem to identify worst-case probability distribution is available. The second stage problems can be solved using a branch and cut algorithm, or a parametric cuts based algorithm presented in this paper. The decomposition algorithm is illustrated with an example. Computational results on a stochastic programming generalization of a facility location problem show significant solution time improvements from the proposed approach. Solutions for many models that are intractable for an extensive form formulation become possible. Computational results also show that for the same amount of computational effort the optimality gaps for distributionally robust instances and their stochastic programming counterpart are similar. [ABSTRACT FROM AUTHOR]

While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection. [ABSTRACT FROM AUTHOR]

We consider convex optimization problems with uncertain, probabilistically described, constraints. In this context, scenario optimization is a well recognized methodology where a sample of the constraints is used to describe uncertainty. One says that the scenario solution generalizes well, or has a high robustness level, if it satisfies most of the other constraints besides those in the sample. Over the past 10 years, the main theoretical investigations on the scenario approach have related the robustness level of the scenario solution to the number of optimization variables. This paper breaks into the new paradigm that the robustness level is a-posteriori evaluated after the solution is computed and the actual number of the so-called support constraints is assessed (wait-and-judge). A new theory is presented which shows that a-posteriori observing k support constraints in dimension $$d > k$$ allows one to draw conclusions close to those obtainable when the problem is from the outset in dimension k. This new theory provides evaluations of the robustness that largely outperform those carried out based on the number of optimization variables. [ABSTRACT FROM AUTHOR]

For two matroids M 1 and M 2 with the same ground set V and two cost functions w 1 and w 2 on 2 V , we consider the problem of finding bases X 1 of M 1 and X 2 of M 2 minimizing w 1 (X 1) + w 2 (X 2) subject to a certain cardinality constraint on their intersection X 1 ∩ X 2 . For this problem, Lendl et al. (Matroid bases with cardinality constraints on the intersection, arXiv:1907.04741v2, 2019) discussed modular cost functions: they reduced the problem to weighted matroid intersection for the case where the cardinality constraint is | X 1 ∩ X 2 | ≤ k or | X 1 ∩ X 2 | ≥ k ; and designed a new primal-dual algorithm for the case where the constraint is | X 1 ∩ X 2 | = k . The aim of this paper is to generalize the problems to have nonlinear convex cost functions, and to comprehend them from the viewpoint of discrete convex analysis. We prove that each generalized problem can be solved via valuated independent assignment, valuated matroid intersection, or M -convex submodular flow, to offer a comprehensive understanding of weighted matroid intersection with intersection constraints. We also show the NP-hardness of some variants of these problems, which clarifies the coverage of discrete convex analysis for those problems. Finally, we present applications of our generalized problems in the recoverable robust matroid basis problem, combinatorial optimization problems with interaction costs, and matroid congestion games. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The authors also consider the parametric version of the problem that has a weighted I l i SB 1 sb -regularizer and a quadratic loss function, and present a linear-step algorithm in two cases depending on whether the variables have prescribed or unknown signs. They encompass deterministic and stochastic optimization problems with complementarity or equilibrium constraints, generalized Nash equilibrium problems, bilevel programming, and applications to statistics and machine learning. Hierarchical optimization (HO) is the subfield of mathematical programming in which constraints are defined by other, lower-level optimization and/or equilibrium problems that are parametrized by the variables of the higher-level problem. [Extracted from the article]

The 'separable' uncertainty sets have been widely used in robust portfolio selection models [e.g., see Erdoğan et al. (Robust portfolio management. manuscript, Department of Industrial Engineering and Operations Research, Columbia University, New York, 2004), Goldfarb and Iyengar (Math Oper Res 28:1-38, 2003), Tütüncü and Koenig (Ann Oper Res 132:157-187, 2004)]. For these uncertainty sets, each type of uncertain parameters (e.g., mean and covariance) has its own uncertainty set. As addressed in Lu (A new cone programming approach for robust portfolio selection, technical report, Department of Mathematics, Simon Fraser University, Burnaby, 2006; Robust portfolio selection based on a joint ellipsoidal uncertainty set, manuscript, Department of Mathematics, Simon Fraser University, Burnaby, 2008), these 'separable' uncertainty sets typically share two common properties: (i) their actual confidence level, namely, the probability of uncertain parameters falling within the uncertainty set is unknown, and it can be much higher than the desired one; and (ii) they are fully or partially box-type. The associated consequences are that the resulting robust portfolios can be too conservative, and moreover, they are usually highly non-diversified as observed in the computational experiments conducted in this paper and Tütüncü and Koenig (Ann Oper Res 132:157-187, 2004). To combat these drawbacks, the author of this paper introduced a 'joint' ellipsoidal uncertainty set (Lu in A new cone programming approach for robust portfolio selection, technical report, Department of Mathematics, Simon Fraser University, Burnaby, 2006; Robust portfolio selection based on a joint ellipsoidal uncertainty set, manuscript, Department of Mathematics, Simon Fraser University, Burnaby, 2008) and showed that it can be constructed as a confidence region associated with a statistical procedure applied to estimate the model parameters. For this uncertainty set, we showed in Lu (A new cone programming approach for robust portfolio selection, technical report, Department of Mathematics, Simon Fraser University, Burnaby, 2006; Robust portfolio selection based on a joint ellipsoidal uncertainty set, manuscript, Department of Mathematics, Simon Fraser University, Burnaby, 2008) that the corresponding robust maximum risk-adjusted return (RMRAR) model can be reformulated and solved as a cone programming problem. In this paper, we conduct computational experiments to compare the performance of the robust portfolios determined by the RMRAR models with our 'joint' uncertainty set (Lu in A new cone programming approach for robust portfolio selection, technical report, Department of Mathematics, Simon Fraser University, Burnaby, 2006; Robust portfolio selection based on a joint ellipsoidal uncertainty set, manuscript, Department of Mathematics, Simon Fraser University, Burnaby, 2008) and Goldfarb and Iyengar's 'separable' uncertainty set proposed in the seminal paper (Goldfarb and Iyengar in Math Oper Res 28:1-38, 2003). Our computational results demonstrate that our robust portfolio outperforms Goldfarb and Iyengar's in terms of wealth growth rate and transaction cost, and moreover, ours is fairly diversified, but Goldfarb and Iyengar's is surprisingly highly non-diversified. [ABSTRACT FROM AUTHOR]

This is the first of a series of two papers dedicated to efficient separation heuristics for violated inequalities in the context of solving to optimality instances of the Traveling Salesman Problem via branch-and-cut. In this paper we give the basic ideas behind these heuristics and design heuristics for comb separation. The second paper will deal with more complex inequalities such as Clique Tree, Star or Path and Ladder inequalities and give computational results. [ABSTRACT FROM AUTHOR]

A foreword to "Mathematical Programming" is presented.

Introduces a series of articles on mathematical programming in biology and medicine.

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. [ABSTRACT FROM AUTHOR]

In this paper we discuss the simple bilevel programming problem (SBP) and its extension, the simple mathematical programming problem under equilibrium constraints (SMPEC). Here we first define both these problems and study their interrelations. Next we study the various types of necessary and sufficient optimality conditions for the (SMPEC) problems, which occur under various reformulations. The optimality conditions for (SBP) are special cases of the results obtained for (SMPEC) when the lower level objective is the gradient of a convex function. Among the various optimality conditions presented in this article are the sequential optimality conditions, which do not need any constraint qualification. We also present a schematic algorithm for (SMPEC), where the sequential optimality conditions play a key role in the convergence analysis. [ABSTRACT FROM AUTHOR]

A preface focusing on mathematical programming is presented.

Presents information on the symposium "New Trends in Computational and Optimization Algorithms (NTOC2001)," organized and sponsored by the Institute of Statistical Mathematics, Tokyo, Japan from December 9 to 13, 2001. Topics of the symposium; Introduction to papers presented at the symposium.

In this paper, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, the complexity of solving which is related to characterizing a suitable projection of the convex hull of the set { (x , x x ′) : x ∈ X } where X is the feasible region. In some cases, this lends itself to efficient representations that result in polynomial-time solvable instances, most notably for the distributionally robust appointment scheduling problem with random job durations as well as for computing tight bounds in the newsvendor problem, project evaluation and review technique networks and linear assignment problems. To the best of our knowledge, this is the first example of a distributionally robust optimization formulation for appointment scheduling that permits a tight polynomial-time solvable semidefinite programming reformulation which explicitly captures partially known correlation information between uncertain processing times of the jobs to be scheduled. We also discuss extensions where the random coefficients are assumed to be non-negative and additional overlapping correlation information is available. [ABSTRACT FROM AUTHOR]

Often decision makers have to cope with a programming problem with unknown quantitities. Then they will estimate these quantities and solve the problem as it then appears-the 'approximate problem'. Thus there is a need to establish conditions which will ensure that the solutions to the approximate problem will come close to the solutions to the true problem in a suitable manner. Confidence sets, i.e. sets that cover the true sets with a given prescribed probability, provide useful quantitative information. In this paper we consider multiobjective problems and derive confidence sets for the sets of efficient points, weakly efficient points, and the corresponding solution sets. Besides the crucial convergence conditions for the objective and/or constraint functions, one approach for the derivation of confidence sets requires some knowledge about the true problem, which may be not available. Therefore also another method, called relaxation, is suggested. This approach works without any knowledge about the true problem. The results are applied to the Markowitz model of portfolio optimization. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk-Kuhn-Tucker multipliers or a new gap function associated with the given problem. [ABSTRACT FROM AUTHOR]

This paper considers optimization problems with cardinality constraints. Based on a recently introduced reformulation of this problem as a nonlinear program with continuous variables, we first define some problem-tailored constraint qualifications and then show how these constraint qualifications can be used to obtain suitable optimality conditions for cardinality constrained problems. Here, the (KKT-like) optimality conditions hold under much weaker assumptions than the corresponding result that is known for the somewhat related class of mathematical programs with complementarity constraints. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such symmetric matrices. The algorithm runs in $${\rm O}(\sqrt{n}m\log n)$$ time for a symmetric matrix of order n with m nonzero entries. In addition, it is shown to be NP-complete to decide whether the inertia of a given symmetric matrix is not determined by its sign pattern. [ABSTRACT FROM AUTHOR]

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs. [ABSTRACT FROM AUTHOR]

This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their overwhelming dimensionality. In this paper we propose a new decomposition algorithm for multistage stochastic programming with a convex objective and stochastic recourse matrices, based on the path-following interior point method combined with the homogeneous self-dual embedding technique. Our preliminary numerical experiments show that this approach is very promising in many ways for solving generic multistage stochastic programming, including its superiority in terms of numerical efficiency, as well as the flexibility in testing and analyzing the model. [ABSTRACT FROM AUTHOR]

This paper studies the asymptotic behavior of the central path ( X( ν), S( ν), y( ν)) as ν↓0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” of the central path are assumed to satisfy We establish the convergence of the central path towards a primal-dual optimal solution, which is characterized as being the unique optimal solution of a certain log-barrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided. It is shown that the re-parametrization t>0→( X( t4), S( t4), y( t4)) of the central path is analytic at t=0. The limiting behavior of the derivative of the central path is also investigated and it is shown that the order of convergence of the central path towards its limit point is Finally, we apply our results to the convex quadratically constrained convex programming (CQCCP) problem and characterize the class of CQCCP problems which can be formulated as SDPs satisfying the assumptions of this paper. In particular, we show that CQCCP problems with either a strictly convex objective function or at least one strictly convex constraint function lie in this class. [ABSTRACT FROM AUTHOR]

A common question asked by users of direct search algorithms is how to use derivative information at iterates where it is available. This paper addresses that question with respect to Generalized Pattern Search (GPS) methods for unconstrained and linearly constrained optimization. Specifically, this paper concentrates on the GPS pollstep. Polling is done to certify the need to refine the current mesh, and it requires O(n) function evaluations in the worst case. We show that the use of derivative information significantly reduces the maximum number of function evaluations necessary for pollsteps, even to a worst case of a single function evaluation with certain algorithmic choices given here. Furthermore, we show that rather rough approximations to the gradient are sufficient to reduce the pollstep to a single function evaluation. We prove that using these less expensive pollsteps does not weaken the known convergence properties of the method, all of which depend only on the pollstep. [ABSTRACT FROM AUTHOR]

The paper considers an example of Wächter and Biegler which is shown to converge to a nonstationary point for the standard primal–dual interior-point method for nonlinear programming. The reason for this failure is analyzed and a heuristic resolution is discussed. The paper then characterizes the performance of LOQO, a line-search interior-point code, on a large test set of nonlinear programming problems. Specific types of problems which can cause LOQO to fail are identified. [ABSTRACT FROM AUTHOR]

This paper is the second in a series of two papers dedicated to the separation problem in the symmetric traveling salesman polytope. The first one gave the basic ideas behind the separation procedures and applied them to the separation of Comb inequalities. We here address the problem of separating inequalities which are all, in one way or another, a generalization of Comb inequalities. These are namely clique trees, path, and ladder inequalities. Computational results are reported for the solution of instances of the TSPLib using the branch and cut framework ABACUS. [ABSTRACT FROM AUTHOR]

We review two papers that are of historical interest for combinatorial optimization: an article of A.N. Tolsto... from 1930, in which the transportation problem is studied, and a negative cycle criterion is developed and applied to solve a (for that time) large-scale (10 × 68) transportation problem to optimality; and an, until recently secret, RAND report of T.E. Harris and F.S. Ross from 1955, that Ford and Fulkerson mention as motivation to study the maximum flow problem. The papers have in common that they both apply their methods to the Soviet railway network. [ABSTRACT FROM AUTHOR]

Abstract. In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an 0(square root of log epsilon[sup -1]) iteration-complexity to reduce the duality gap by a factor of epsilon, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. [ABSTRACT FROM AUTHOR]

We study a substructure appearing in mixed-integer programming reformulations of chance-constrained programs with stochastic right-hand-sides over a finite discrete distribution, which we call the mixing set with a knapsack constraint. Recently, Luedtke et al. (Math. Program. 122(2):247-272, ) and Küçükyavuz (Math Program 132(1):31-56, ) studied valid inequalities for such sets. However, most of their results were focused on the equal probabilities case (when the knapsack constraint reduces to a cardinality constraint). In this paper, we focus on the general probabilities case (general knapsack constraint). We characterize the valid inequalities that do not come from the knapsack polytope and use this characterization to generalize the results previously derived for the equal probabilities case. Our results allow for a deep understanding of the relationship that the set under consideration has with the knapsack polytope. Moreover, they allow us to establish benchmarks that can be used to identify when a relaxation will be useful for the considered types of reformulations of chance-constrained programs. [ABSTRACT FROM AUTHOR]

In this note we comment on Tind and Wolsey [11]. It seems that with a number of duality schemes in their paper neither a dual objective function, nor converse duality can properly be defined. Moreover, the paper is restricted to perturbing right-hand sides of (in)equalities only, hence to what is sometimes called 'Lagrangean duality'. We show how one can remedy these points. In doing so, everything comes close to working with modified Lagrangeans. [ABSTRACT FROM AUTHOR]

The objective of uncertainty quantification is to certify that a given physical, engineering or economic system satisfies multiple safety conditions with high probability. A more ambitious goal is to actively influence the system so as to guarantee and maintain its safety, a scenario which can be modeled through a chance constrained program. In this paper we assume that the parameters of the system are governed by an ambiguous distribution that is only known to belong to an ambiguity set characterized through generalized moment bounds and structural properties such as symmetry, unimodality or independence patterns. We delineate the watershed between tractability and intractability in ambiguity-averse uncertainty quantification and chance constrained programming. Using tools from distributionally robust optimization, we derive explicit conic reformulations for tractable problem classes and suggest efficiently computable conservative approximations for intractable ones. [ABSTRACT FROM AUTHOR]

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]

An introduction is presented in which the editor discusses various articles within the related to the field of mathematical programming.

In this paper, we study the existence of optimal solutions to a constrained polynomial optimization problem. More precisely, let $$f_0$$ and $$f_1, \ldots , f_p :{\mathbb {R}}^n \rightarrow {\mathbb {R}}$$ be convenient polynomial functions, and let $$S := \{x \in {\mathbb {R}}^n \ : \ f_i(x) \le 0, i = 1, \ldots , p\} \ne \emptyset .$$ Under the assumption that the map $$(f_0, f_{1}, \ldots , f_{p}) :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^{p + 1}$$ is non-degenerate at infinity, we show that if $$f_0$$ is bounded from below on $$S,$$ then $$f_0$$ attains its infimum on $$S.$$ [ABSTRACT FROM AUTHOR]

This paper studies the interaction between the notions of passivity of systems theory and complementarity of mathematical programming in the context of complementarity systems. These systems consist of a dynamical system (given in the form of state space representation) and complementarity relations. We study existence, uniqueness, and nature of solutions for this system class under a passivity assumption on the dynamical part. A complete characterization of the initial states and the inputs for which a solution exists is given. These initial states are called consistent states. For the inconsistent states, we introduce a solution concept in the framework of distributions. [ABSTRACT FROM AUTHOR]

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvátal 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such is significantly more tractable than a semidefinite problem. The SD condition holds for free for many problems arising in applications, in particular, when deriving robust counterparts of quadratic, or conic quadratic, constraints affected by implementation error. The proof of the hidden CQ property is constructive and does not rely on the S-lemma. This fact may be significant in discovering hidden convexity in some nonquadratic problems. [ABSTRACT FROM AUTHOR]

We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order cone programming (SOCP) representable. Our result generalizes the recent work of Ben-Tal and den Hertog (Math. Program. 143(1-2):1-29, 2014), which establishes the SOCP representability of the GTRS under the assumption of the simultaneous diagonalizability of the two matrices in the objective and constraint functions. We then derive a closed-form solution for the GTRS when the two matrices are not simultaneously diagonalizable. We further extend our method to two variants of the GTRS in which the inequality constraint is replaced by either an equality constraint or an interval constraint. [ABSTRACT FROM AUTHOR]