complexity

Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks

  • Martine Labbé
  • Martin Schmidt
  • Johannes Thürauf
  • Fränk Plein
    • Categories Applications - OR and Management Sciences, Network Optimization Tags , , , , ,

    We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow … Read more

    Minimizing Airplane Boarding Time

  • Andreas M. Tillmann
  • Felix J. L. Willamowski
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    The time it takes passengers to board an airplane is known to influence the turn-around time of the aircraft and thus bears a significant cost-saving potential for airlines. Although minimizing boarding time therefore is the most important goal from an economic perspective, previous efforts to design efficient boarding strategies apparently never tackled this task directly. … Read more

    Vertex ordering with optimal number of adjacent predecessors

  • Tangi Migot
  • Jérémy Omer
    • Categories Combinatorial Optimization Tags , , ,

    In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function.Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such … Read more

    Inexact proximal stochastic second-order methods for nonconvex composite optimization

  • Xiao Wang
  • Hongchao Zhang
    • Categories Nonlinear Optimization Tags , , , , , ,

    In this paper, we propose a framework of Inexact Proximal Stochastic Second-order (IPSS) methods for solving nonconvex optimization problems, whose objective function consists of an average of finitely many, possibly weakly, smooth functions and a convex but possibly nons- mooth function. At each iteration, IPSS inexactly solves a proximal subproblem constructed by using some positive … Read more

    An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

  • Robert M. Freund
  • Michael J. Todd
  • Jourdain Lamperski
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , ,

    The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more

    A family of multi-parameterized proximal point algorithms

  • Jianchao Bai
  • Ke Guo
  • Xiaokai Chang
    • Categories Convex Optimization Tags , , ,

    In this paper, a multi-parameterized proximal point algorithm combining with a relaxation step is developed for solving convex minimization problem subject to linear constraints. We show its global convergence and sublinear convergence rate from the prospective of variational inequality. Preliminary numerical experiments on testing a sparse minimization problem from signal processing indicate that the proposed … Read more

    Complexity and performance of an Augmented Lagrangian algorithm

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , , ,

    Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM Journal on Optimization 18, pp. 1286-1309, 2008]. Complexity results that report its worst-case behavior in terms of iterations and evaluations of functions and … Read more

    Accelerated Symmetric ADMM and Its Applications in Signal Processing

  • Jianchao Bai
  • Ke Guo
  • Yang Jing
  • Junli Liang
    • Categories Constrained Nonlinear Optimization, Other Topics Tags , , , ,

    The alternating direction method of multipliers (ADMM) were extensively investigated in the past decades for solving separable convex optimization problems. Fewer researchers focused on exploring its convergence properties for the nonconvex case although it performed surprisingly efficient. In this paper, we propose a symmetric ADMM based on different acceleration techniques for a family of potentially … Read more

    A linearly convergent stochastic recursive gradient method for convex optimization

  • Tiande Guo
  • Yan Liu
  • Xiao Wang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    The stochastic recursive gradient algorithm (SARAH) [8] attracts much interest recently. It admits a simple recursive framework for updating stochastic gradient estimates. Motivated by this, in this paper, we propose a SARAH-I method incorporating importance sampling, whose linear conver- gence rate of the sequence of distances between iterates and the optima set is proven under … Read more

    High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

  • Xiaojun Chen
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Data-Mining, Statistics Tags , , , , ,

    This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a $p$-th order Taylor model and show that the algorithm can produce an (epsilon,delta)-approximate q-th-order stationary point in at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the objective … Read more