Springer Science and Business Media LLC

We present an algorithm for the minimization of a nonconvex quadratic function subject to linear inequality constraints and a two-sided bound on the 2-norm of its solution. The algorithm minimizes the objective using an active-set method by solving a series of trust-region subproblems (TRS). Underpinning the efficiency of this approach is that the global solution of the TRS has been widely studied in the literature, resulting in remarkably efficient algorithms and software. We extend these results by proving that nonglobal minimizers of the TRS, or a certificate of their absence, can also be calculated efficiently by computing the two rightmost eigenpairs of an eigenproblem. We demonstrate the usefulness and scalability of the algorithm in a series of experiments that often outperform state-of-the-art approaches; these include calculation of high-quality search directions arising in Sequential Quadratic Programming on problems of the CUTEst collection, and Sparse Principal Component Analysis on a large text corpus problem (70 million nonzeros) that can help organize documents in a user interpretable way.

This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a ‘‘central’’ dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newton’s method to calculate the new analytic centre after branching. Second, we discuss the integration of ACCPM within the branch-and-price algorithm. We detail the use of ACCPM as the search goes deep in the branch and bound tree, making full utilization of past information as a warm start. We exploit dual information from ACCPM to generate incumbent feasible solutions and to guide branching. Finally, the overall approach is implemented and tested for the bin-packing problem and the capacitated facility location problem with single sourcing. We compare against Cplex-MIP 7.5 as well as a classical branch-and-price algorithm.

The optimal flow problem in networks with gains is presented through the simplex method. Out of simple theorical conditions, a method is built which needs only a relatively small number memory and quite a short calculation time by computer. Large examples are given; e.g., one test-example of 1000 nodes and 3000 arcs, and one real problem leading to a linear program of 3000 constraints and 8000 arcs.

We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy, and robustness to gradient inaccuracy. We also provide feasible points for this LMI and obtain theoretical formulas that quantify the convergence properties of biased SGD under various assumptions on the loss functions.

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 \cap 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 \cap X_2|\le k$$ or $$|X_1 \cap X_2|\ge k$$ ; and designed a new primal-dual algorithm for the case where the constraint is $$|X_1 \cap 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 $$\mathrm {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.