Search

This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S ∩ P , where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or S-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of outer-product-free sets, where S is the set of real, symmetric matrices of the form x x T . All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (A α β x α β t d α β ) , where A α β is a 2 × 2 matrix over a field F , x α β is an indeterminate, and d α β is an integer for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν , and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial -time algorithm for computing the entire sequence of the maximum degree of minors of a (2 × 2) -type generic partitioned polynomial matrix of size 2 μ × 2 ν . We also present a minimax theorem, which can be used as a good characterization (NP ∩ co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry's theorem) for the maximum weight bipartite matching problem. [ABSTRACT FROM AUTHOR]

Even-cycle matroids are elementary lifts of graphic matroids. Pinch-graphic matroids are even-cycle matroids that are also elementary projections of graphic matroids. In this paper we analyze the structure of 1-, 2-, and 3-separations in these matroids. As a corollary we obtain a polynomial-time algorithm that reduces the problem of recognizing pinch-graphic matroids to internally 4-connected matroids. Combining this with earlier results (Guenin and Heo in Recognizing even-cycle and even-cut matroids manuscript, 2020; Guenin and Heo in Recognizing pinch-graphic matroids manuscript, 2020) we obtain a polynomial-time algorithm for recognizing even-cycle matroids and we obtain a polynomial-time algorithm for recognizing even-cut matroids. [ABSTRACT FROM AUTHOR]

Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly (n , k) time. We develop a unified algorithmic framework for solving MOT in poly (n , k) time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly (n , k) time. Second, our framework makes it much simpler to develop poly (n , k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle—which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing poly (n , k) -time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly (n , k) runtime; moreover, we provide the first poly (n , k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly (n , k) time algorithms, even for approximate computation. Together, these three structures encompass many—if not most—current applications of MOT. [ABSTRACT FROM AUTHOR]

Even-cycle matroids are elementary lifts of graphic matroids and even-cut matroids are elementary lifts of cographic matroids. We present a polynomial algorithm to check if a binary matroid is an even-cycle matroid and we present a polynomial algorithm to check if a binary matroid is an even-cut matroid. These two algorithms rely on a polynomial algorithm (to be described in a pair of follow-up papers) to check if a binary matroid is pinch-graphic. [ABSTRACT FROM AUTHOR]

Much recent research effort has been directed to the development of efficient algorithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an ε -stationary point of the objective function in O ε - 2 (resp. O ε - 4 ) iterations under nonconvex-strongly concave (resp. nonconvex–concave) setting. Moreover, its gradient complexity to obtain an ε -stationary point of the objective function is bounded by O ε - 2 (resp., O ε - 4 ) under the strongly convex–nonconcave (resp., convex–nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex–nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A α β x α β) , where A α β is a 2 × 2 matrix over a field F and x α β is an indeterminate for α = 1 , 2 , ⋯ , μ and β = 1 , 2 , ⋯ , ν . This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial O ((μ ν) 2 min { μ , ν }) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ × 2 ν . Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field F . [ABSTRACT FROM AUTHOR]

This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines m > 1 . [ABSTRACT FROM AUTHOR]

We consider the weighted k-set packing problem, where, given a collection S of sets, each of cardinality at most k, and a positive weight function w : S → Q > 0 , the task is to find a sub-collection of S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time o (k log k) -approximation unless P = N P (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6), most previous approaches rely on local search. For twenty years, Berman's algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X%5f19), which yields a polynomial-time k + 1 2 + ϵ -approximation for any fixed ϵ > 0 , has remained unchallenged. Only recently, it could be improved to k + 1 2 - 1 63 , 700 , 993 by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are "close to unweighted" in a certain sense. But for the unit weight variant, the best known approximation guarantee is k + 1 3 + ϵ (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7%5f35). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of k + ϵ k 2 , where lim k → ∞ ϵ k = 0 . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below k 2 . [ABSTRACT FROM AUTHOR]

In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem. The algorithm requires only one single pass through the input data and is free of matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm in two different models, stochastic input and random permutation, with minimal technical assumptions on the input data. The algorithm achieves O m n expected regret under the stochastic input model and O (m + log n) n expected regret under the random permutation model, and it achieves O (m n) expected constraint violation under both models, where n is the number of decision variables and m is the number of constraints. The algorithm enjoys the same performance guarantee when generalized to a multi-dimensional LP setting which covers a wider range of applications. In addition, we employ the notion of the permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound by a factor of m by paying more computational cost. Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms. [ABSTRACT FROM AUTHOR]

We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices, I p and I d , say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space by η I p and ε I d , respectively, to recover interior feasibility of both problems, where ε and η are positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio between η and ε constant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes "monotonically" from the primal optimal value to the dual optimal value as a function of θ , if we parametrize (ε , η) as (ε , η) = t (cos θ , sin θ) and let t → 0 . Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems. [ABSTRACT FROM AUTHOR]

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 ϵ -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 / ϵ 2) to reach an ϵ -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 ℓ q regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods. [ABSTRACT FROM AUTHOR]

Low rank orthogonal tensor approximation (LROTA) is an important problem in tensor computations and their applications. A classical and widely used algorithm is the alternating polar decomposition method (APD). In this paper, an improved version iAPD of the classical APD is proposed. For the first time, all of the following four fundamental properties are established for iAPD: (i) the algorithm converges globally and the whole sequence converges to a KKT point without any assumption; (ii) it exhibits an overall sublinear convergence with an explicit rate which is sharper than the usual O(1/k) for first order methods in optimization; (iii) more importantly, it converges R-linearly for a generic tensor without any assumption; (iv) for almost all LROTA problems, iAPD reduces to APD after finitely many iterations if it converges to a local minimizer. [ABSTRACT FROM AUTHOR]

In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out to be convex and hence the bilevel program can be reformulated as a difference of convex bilevel program. We propose two algorithms for solving the reformulated difference of convex program and show their convergence to stationary points under very mild assumptions. Finally we conduct numerical experiments to a bilevel model of support vector machine classification. [ABSTRACT FROM AUTHOR]

Projection-free optimization via different variants of the Frank–Wolfe method has become one of the cornerstones of large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex, making them a challenging class of functions for first-order methods. Indeed, in a number of applications, such as inverse covariance estimation or distance-weighted discrimination problems in binary classification, the loss is given by a generalized self-concordant function having potentially unbounded curvature. For such problems projection-free minimization methods have no theoretical convergence guarantee. This paper closes this apparent gap in the literature by developing provably convergent Frank–Wolfe algorithms with standard O (1 / k) convergence rate guarantees. Based on these new insights, we show how these sublinearly convergent methods can be accelerated to yield linearly convergent projection-free methods, by either relying on the availability of a local liner minimization oracle, or a suitable modification of the away-step Frank–Wolfe method. [ABSTRACT FROM AUTHOR]

In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show that using an appropriate affine-invariant smoothness condition, it is possible to implement one iteration of the Contracting-Point method by one step of the pure tensor method of degree p ≥ 1 . The resulting global rate of convergence in functional residual is then O (1 / k p) , where k is the iteration counter. It is important that all constants in our bounds are affine-invariant. For p = 1 , our scheme recovers well-known Frank–Wolfe algorithm, providing it with a new interpretation by a general perspective of tensor methods. Finally, within our framework, we present efficient implementation and total complexity analysis of the inexact second-order scheme (p = 2) , called Contracting Newton method. It can be seen as a proper implementation of the trust-region idea. Preliminary numerical results confirm its good practical performance both in the number of iterations, and in computational time. [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]

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

In this paper we provide an algorithm, similar to the simplex algorithm, which determines a rational cp-factorization of a given matrix, whenever the matrix allows such a factorization. This algorithm can be used to show that every integral completely positive 2 × 2 matrix has an integral cp-factorization. [ABSTRACT FROM AUTHOR]

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 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 O (| V | 2) time. In two companion papers we showed that the MWSS problem can be solved in O (| E | log | V |) time in claw-free graphs with α (G) ≤ 3 and in O (| V | | E |) time in {claw, net}-free graphs with α (G) ≥ 4 . These results prove that the MWSS problem in a claw-free graph can be solved in O (| V | 2 log | V |) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs. [ABSTRACT FROM AUTHOR]

The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous ℓ 0 -norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong β -Lagrangian stationarity via the Lagrangian function, and reformulate it as a system of nonlinear equations called the Lagrangian equations. The nonsingularity of the corresponding Jacobian is discussed, based on which the Lagrange–Newton algorithm (LNA) is then proposed. Under mild conditions, we establish the locally quadratic convergence and its iterative complexity estimation. To further demonstrate the efficiency and superiority of our proposed algorithm, we apply LNA to two specific problems arising from compressed sensing and sparse high-order portfolio selection, in which significant benefits accrue from the restricted Newton step. [ABSTRACT FROM AUTHOR]

In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202–228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O (m log (n C D) SF (k n , m , k)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, C is the maximum node capacity, D is the maximum edge cost, and SF (n ′ , m ′ , η) is the time complexity of solving the submodular flow problem in a network of n ′ nodes, m ′ edges, and a submodular function with η -time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function f(x), obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with high enough, but fixed, probability. Beyond these conditions, no assumptions are made on how these models and estimates are generated. Under these general conditions we show an almost sure global convergence of the method to a first order stationary point. In the second part of the paper, we present examples of generating sufficiently accurate random models under biased or unbiased noise assumptions. Lastly, we present some computational results showing the benefits of the proposed method compared to existing approaches that are based on sample averaging or stochastic gradients. [ABSTRACT FROM AUTHOR]

There has been a long history of using ordinary differential equations (ODEs) to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a suitable ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a DTA and its corresponding ODEs. In this paper, we propose a new machinery—an O (s r) -resolution ODE framework—for analyzing the behavior of a generic DTA, which (partially) answers the above two questions. The framework contains three steps: 1. To obtain a suitable ODE from a given DTA, we define a hierarchy of O (s r) -resolution ODEs of a DTA parameterized by the degree r, where s is the step-size of the DTA. We present a principal approach to construct the unique O (s r) -resolution ODEs from a DTA; 2. To analyze the resulting ODE, we propose the O (s r) -linear-convergence condition of a DTA with respect to an energy function, under which the O (s r) -resolution ODE converges linearly to an optimal solution; 3. To bridge the convergence properties of a DTA and its corresponding ODEs, we define the properness of an energy function and show that the linear convergence of the O (s r) -resolution ODE with respect to a proper energy function can automatically guarantee the linear convergence of the DTA. To better illustrate this machinery, we utilize it to study three classic algorithms—gradient descent ascent (GDA), proximal point method (PPM) and extra-gradient method (EGM)—for solving the unconstrained minimax problem min x ∈ R n max y ∈ R m L (x , y) . Their O(s)-resolution ODEs explain the puzzling convergent/divergent behaviors of GDA, PPM and EGM when L(x, y) is a bilinear function, and showcase that the interaction terms help the convergence of PPM/EGM but hurts the convergence of GDA. Furthermore, their O(s)-linear-convergence conditions not only unify the known scenarios when PPM and EGM have linear convergence, but also showcase that these two algorithms exhibit linear convergence in much broader contexts, including when solving a class of nonconvex-nonconcave minimax problems. Finally, we show how this ODE framework can help design new optimization algorithms for minimax problems, by studying the difference between the O(s)-resolution ODE of GDA and that of PPM/EGM. [ABSTRACT FROM AUTHOR]

In this paper, we study the lower iteration complexity bounds for finding the saddle point of a strongly convex and strongly concave saddle point problem: min x max y F (x , y) . We restrict the classes of algorithms in our investigation to be either pure first-order methods or methods using proximal mappings. For problems with gradient Lipschitz constants ( L x , L y and L xy ) and strong convexity/concavity constants ( μ x and μ y ), the class of pure first-order algorithms with the linear span assumption is shown to have a lower iteration complexity bound of Ω L x μ x + L xy 2 μ x μ y + L y μ y · ln 1 ϵ , where the term L xy 2 μ x μ y explains how the coupling influences the iteration complexity. Under several special parameter regimes, this lower bound has been achieved by corresponding optimal algorithms. However, whether or not the bound under the general parameter regime is optimal remains open. Additionally, for the special case of bilinear coupling problems, given the availability of certain proximal operators, a lower bound of Ω L xy 2 μ x μ y · ln (1 ϵ) is established under the linear span assumption, and optimal algorithms have already been developed in the literature. By exploiting the orthogonal invariance technique, we extend both lower bounds to the general pure first-order algorithm class and the proximal algorithm class without the linear span assumption. As an application, we apply proper scaling to the worst-case instances, and we derive the lower bounds for the general convex concave problems with μ x = μ y = 0 . Several existing results in this case can be deduced from our results as special cases. [ABSTRACT FROM AUTHOR]

A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tunçel. We specialize Tunçel's primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in a practical algorithm with good numerical performance, on level with standard symmetric cone (e.g., quadratic cone) algorithms. A significant contribution of the paper is a novel higher-order search direction, similar in spirit to a Mehrotra corrector for symmetric cone algorithms. To a large extent, the efficiency of our proposed algorithm can be attributed to this new corrector. [ABSTRACT FROM AUTHOR]

Introduces several articles on deterministic global optimization and applications. Description of the structure of convex envelopes over hyperrectangles using concepts from combinatorial geometry; Application of branch-and-cut approach for solving nonconvex integer nonlinear programs; Branch-and-bound algorithm for solving nonconvex quadratically constrained quadratic programs.

We consider continuous linear programs over a continuous finite time horizon T, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions. Specifically, we search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In previous papers we formulated a symmetric dual and have shown strong duality. We also have presented a detailed description of optimal solutions and have defined a combinatorial analogue to basic solutions of standard LP. In this paper we present an algorithm which solves this class of problems in a finite bounded number of steps, using an analogue of the simplex method, in the space of measures. [ABSTRACT FROM AUTHOR]

In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is nonsmooth. This lack of differentiability complicates the numerical approximation of the objective function as well as the numerical solution of the optimization problem. To address these challenges, we propose a primal–dual algorithm for solving large-scale nonsmooth risk-averse optimization problems. This algorithm is motivated by the classical method of multipliers and by epigraphical regularization of risk measures. As a result, the algorithm solves a sequence of smooth optimization problems using derivative-based methods. We prove convergence of the algorithm even when the subproblems are solved inexactly and conclude with numerical examples demonstrating the efficiency of our method. [ABSTRACT FROM AUTHOR]

In this paper, we consider the subcontracting and single-item lot-sizing problem with constant capacities, which is uncapacitated in subcontracting but capacitated in production. For a holistic understanding of the problem, an infinite-period model is proposed. Such a model provides a unified view of a capacitated lot-sizing problem. The usefulness of the infinite-period model is shown by the principle that the firm's production schedule drives the subcontractor's supply schedule. For efficient construction of the production schedule, an innovative technique–coined using the concept of the shadow period–is presented to designate the optimal marginal supply cost. The success of the infinite-period model is finally proved with the concept of the effective period, indicating the supply coverage over periods. This fills the gap between the uncapacitated techniques and the capacitated techniques, making it possible to apply the best techniques from the lot-sizing literature. With this novel approach, we improve existing algorithms and provide new ones for concave production and supply cost structures involving setups. [ABSTRACT FROM AUTHOR]

In the classic prophet inequality, a well-known problem in optimal stopping theory, samples from independent random variables (possibly differently distributed) arrive online. A gambler who knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet that sees all the realizations in advance gets. In the late seventies, Krengel and Sucheston (Bull Am Math Soc 83(4):745–747, 1977), established that this worst case ratio is 0.5. A particularly interesting variant is the so-called prophet secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms are known to achieve a constant of 1 - 1 / e ≈ 0.632 and very recently this barrier was slightly improved by Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018). In this paper we introduce a new type of multi-threshold strategy, called blind strategy. Such a strategy sets a nonincreasing sequence of thresholds that depends only on the distribution of the maximum of the random variables, and the gambler stops the first time a sample surpasses the threshold of the stage. Our main result shows that these strategies can achieve a constant of 0.669 for the prophet secretary problem, improving upon the best known result of Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018), and even that of Beyhaghi et al. (Improved approximations for posted price and second price mechanisms. CoRR arXiv:1807.03435, 2018) that works in the case in which the gambler can select the order of the samples. The crux of the result is a very precise analysis of the underlying stopping time distribution for the gambler's strategy that is inspired by the theory of Schur-convex functions. We further prove that our family of blind strategies cannot lead to a constant better than 0.675. Finally we prove that no algorithm for the gambler can achieve a constant better than 3 - 1 ≈ 0.732 , which also improves upon a recent result of Azar et al. (in: Proceedings of the ACM conference on economics and computation, EC, 2018). This implies that the upper bound on what the gambler can get in the prophet secretary problem is strictly lower than what she can get in the i.i.d. case. This constitutes the first separation between the prophet secretary problem and the i.i.d. prophet inequality. [ABSTRACT FROM AUTHOR]

In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytope P, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subset Q of P, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function over P is polynomially equivalent, via a fast combinatorial algorithm, to that of its graph over Q. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytope P, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions. [ABSTRACT FROM AUTHOR]

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method. [ABSTRACT FROM AUTHOR]

The Steklov function μ f (· , t) is defined to average a continuous function f at each point of its domain by using a window of size given by t > 0 . It has traditionally been used to approximate f smoothly with small values of t. In this paper, we first find a concise and useful expression for μ f for the case when f is a multivariate quartic polynomial. Then we show that, for large enough t, μ f (· , t) is convex; in other words, μ f (· , t) convexifies f. We provide an easy-to-compute formula for t with which μ f convexifies certain classes of polynomials. We present an algorithm which constructs, via an ODE involving μ f , a trajectory x(t) emanating from the minimizer of the convexified f and ending at x(0), an estimate of the global minimizer of f. For a family of quartic polynomials, we provide an estimate for the size of a ball that contains all its global minimizers. Finally, we illustrate the working of our method by means of numerous computational examples. [ABSTRACT FROM AUTHOR]

This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations (i.e., perturbations of the objective function and the right-hand-side of the constraints), the paper provides a computationally tractable formula for the calmness modulus, which goes beyond some preliminary results of the literature. Second, in the framework of full perturbations (perturbations of all coefficients), after characterizing the calmness property for the optimal set mapping, the paper provides an operative upper bound for the corresponding calmness modulus, as well as some illustrative examples. We provide two applications related to algorithms traced out from the literature: the first one to a descent method in LP, and the second to a regularization method for linear programs with complementarity constraints. [ABSTRACT FROM AUTHOR]

Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches. [ABSTRACT FROM AUTHOR]

It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting. [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]

Given a non-negative n × m real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified positive target values. The Sinkhorn–Knopp algorithm is a simple and classic procedure which alternately scales all rows and all columns to meet these targets. The focus of this paper is the worst-case theoretical analysis of this algorithm. We present an elementary convergence analysis for this algorithm that improves upon the previous best bound. In a nutshell, our approach is to show (i) a simple bound on the number of iterations needed so that the KL-divergence between the current row-sums and the target row-sums drops below a specified threshold δ , and (ii) then show that for a suitable choice of δ , whenever KL-divergence is below δ , then the ℓ 1 -error or the ℓ 2 -error is below ε . The well-known Pinsker's inequality immediately allows us to translate a bound on the KL divergence to a bound on ℓ 1 -error. To bound the ℓ 2 -error in terms of the KL-divergence, we establish a new inequality, referred to as (KL vs ℓ 1 / ℓ 2 ). This inequality is a strengthening of Pinsker's inequality and may be of independent interest. [ABSTRACT FROM AUTHOR]

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of "providing a decent linear description" for this polytope (Grötschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space. [ABSTRACT FROM AUTHOR]

One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases, such as Woodall's conjecture on packing disjoint dijoins in a directed graph, or Rota's beautiful conjecture on rearrangements of bases. In the present paper we prove that the problem is difficult under the rank oracle model, i.e., we show that there is no algorithm which decides if the common ground set of two matroids can be partitioned into k common bases by using a polynomial number of independence queries. Our complexity result holds even for the very special case when k = 2 . Through a series of reductions, we also show that the abstract problem of packing common bases in two matroids includes the NAE-SAT problem and the Perfect Even Factor problem in directed graphs. These results in turn imply that the problem is not only difficult in the independence oracle model but also includes NP-complete special cases already when k = 2 , one of the matroids is a partition matroid, while the other matroid is linear and is given by an explicit representation. [ABSTRACT FROM AUTHOR]

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

Affine variational inequalities (AVI) are an important problem class that subsumes systems of linear equations, linear complementarity problems and optimality conditions for quadratic programs. This paper describes PathAVI, a structure-preserving pivotal approach, that can efficiently process (solve or determine infeasible) large-scale sparse instances of the problem with theoretical guarantees and at high accuracy. PathAVI implements a strategy known to process models with good theoretical properties without reducing the problem to specialized forms, since such reductions may destroy sparsity in the models and can lead to very long computational times. We demonstrate formally that PathAVI implicitly follows the theoretically sound iteration paths, and can be implemented in a large scale setting using existing sparse linear algebra and linear programming techniques without employing a reduction. We also extend the class of problems that PathAVI can process. The paper illustrates the effectiveness of our approach by comparison to the Path solver used on a complementarity reformulation of the AVI in the context of applications in friction contact and Nash Equilibria. PathAVI is a general purpose solver, and freely available under the same conditions as Path. [ABSTRACT FROM AUTHOR]

The paper addresses parametric inequality systems described by polynomial functions in finite dimensions, where state-dependent infinite parameter sets are given by finitely many polynomial inequalities and equalities. Such systems can be viewed, in particular, as solution sets to problems of generalized semi-infinite programming with polynomial data. Exploiting the imposed polynomial structure together with powerful tools of variational analysis and semialgebraic geometry, we establish a far-going extension of the Łojasiewicz gradient inequality to the general nonsmooth class of supremum marginal functions as well as higher-order (Hölder type) local error bounds results with explicitly calculated exponents. The obtained results are applied to higher-order quantitative stability analysis for various classes of optimization problems including generalized semi-infinite programming with polynomial data, optimization of real polynomials under polynomial matrix inequality constraints, and polynomial second-order cone programming. Other applications provide explicit convergence rate estimates for the cyclic projection algorithm to find common points of convex sets described by matrix polynomial inequalities and for the asymptotic convergence of trajectories of subgradient dynamical systems in semialgebraic settings. [ABSTRACT FROM AUTHOR]

A strategy is proposed for characterizing the worst-case performance of algorithms for solving nonconvex smooth optimization problems. Contemporary analyses characterize worst-case performance by providing, under certain assumptions on an objective function, an upper bound on the number of iterations (or function or derivative evaluations) required until a pth-order stationarity condition is approximately satisfied. This arguably leads to conservative characterizations based on certain objectives rather than on ones that are typically encountered in practice. By contrast, the strategy proposed in this paper characterizes worst-case performance separately over regions comprising a search space. These regions are defined generically based on properties of derivative values. In this manner, one can analyze the worst-case performance of an algorithm independently from any particular class of objectives. Then, once given a class of objectives, one can obtain a tailored complexity analysis merely by delineating the types of regions that comprise the search spaces for functions in the class. Regions defined by first- and second-order derivatives are discussed in detail and example complexity analyses are provided for a few standard first- and second-order algorithms when employed to minimize convex and nonconvex objectives of interest. It is also explained how the strategy can be generalized to regions defined by higher-order derivatives and for analyzing the behavior of higher-order algorithms. [ABSTRACT FROM AUTHOR]

The stochastic Frank–Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the dependence on the optimality tolerance ε in the guaranteed convergence rate for stochastic Frank–Wolfe compared to its deterministic counterpart. In this work, we present a new generalized stochastic Frank–Wolfe method which closes this gap for the class of structured optimization problems encountered in statistical and machine learning characterized by empirical loss minimization with a certain type of "linear prediction" property (formally defined in the paper), which is typically present in loss minimization problems in practice. Our method also introduces the notion of a "substitute gradient" that is a not-necessarily-unbiased estimate of the gradient. We show that our new method is equivalent to a particular randomized coordinate mirror descent algorithm applied to the dual problem, which in turn provides a new interpretation of randomized dual coordinate descent in the primal space. Also, in the special case of a strongly convex regularizer our generalized stochastic Frank–Wolfe method (as well as the randomized dual coordinate descent method) exhibits linear convergence. Furthermore, we present computational experiments that indicate that our method outperforms other stochastic Frank–Wolfe methods for a sufficiently small optimality tolerance, consistent with the theory developed herein. [ABSTRACT FROM AUTHOR]

In this paper we study the convergence properties of a Nesterov's family of inertial schemes which is a specific case of inertial Gradient Descent algorithm in the context of a smooth convex minimization problem, under some additional hypotheses on the local geometry of the objective function F, such as the growth (or Łojasiewicz) condition. In particular we study the different convergence rates for the objective function and the local variation, depending on these geometric conditions. In this setting we can give optimal convergence rates for this Nesterov scheme. Our analysis shows that there are some situations when Nesterov's family of inertial schemes is asymptotically less efficient than the gradient descent (e.g. in the case when the objective function is quadratic). [ABSTRACT FROM AUTHOR]

This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate that the MM algorithm derived can converge to a boundary point or to one point of a continuum of minimum points. Conditions under which the minimum point is unique or occurs in the interior of parameter space are proved for geometric programming. Convergence to an interior point occurs at a linear rate. Finally, the MM framework easily accommodates equality and inequality constraints of signomial type. For the most important special case, constrained quadratic programming, the MM algorithm involves very simple updates. [ABSTRACT FROM AUTHOR]

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 our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems. [ABSTRACT FROM AUTHOR]

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of ℓ1 minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale ℓ1 minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods. [ABSTRACT FROM AUTHOR]