Month: February 2018

Cubic Regularization Method based on Mixed Factorizations for Unconstrained Minimization

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

    Newton’s method for unconstrained optimization, subject to proper regularization or special trust-region procedures, finds first-order stationary points with precision $\varepsilon$ employing, at most, $O(\varepsilon^{-3/2})$ functional and derivative evaluations. However, the computer work per iteration of the best-known implementations may need several factorizations per iteration or may use rather expensive matrix decompositions. In this paper, we … Read more

    Algorithms and Convergence Results of Projection Methods for Inconsistent Feasibility Problems: A Review

  • Yair Censor
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    The convex feasibility problem (CFP) is to find a feasible point in the intersection of finitely many convex and closed sets. If the intersection is empty then the CFP is inconsistent and a feasible point does not exist. However, algorithmic research of inconsistent CFPs exists and is mainly focused on two directions. One is oriented … Read more

    Concise Complexity Analyses for Trust-Region Methods

  • Frank E. Curtis
  • Daniel P. Robinson
  • Zachary Lubberts
    • Categories Unconstrained Optimization Tags , , , , , ,

    Concise complexity analyses are presented for simple trust region algorithms for solving unconstrained optimization problems. In contrast to a traditional trust region algorithm, the algorithms considered in this paper require certain control over the choice of trust region radius after any successful iteration. The analyses highlight the essential algorithm components required to obtain certain complexity … Read more

    Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting

  • Ernest K. Ryu
    • Categories Convex Optimization

    Given the success of Douglas-Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there are other 2 operator splittings? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 … Read more

    The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method

  • Douglas Alem
  • Jonathan De La Vega
  • Jacek Gondzio
  • Reinaldo Morabito
  • Pedro Munari
  • Alfredo Moreno
    • Categories Applications - OR and Management Sciences, Robust Optimization, Transportation

    We address the robust vehicle routing problem with time windows (RVRPTW) under customer demand and travel time uncertainties. As presented thus far in the literature, robust counterparts of standard formulations have challenged general-purpose optimization solvers and specialized branch-and-cut methods. Hence, optimal solutions have been reported for small-scale instances only. Additionally, although the most successful methods … Read more

    Generalization Bounds for Regularized Portfolio Selection with Market Side Information

  • Thierry Bazier-Matte
  • Erick Delage
    • Categories Applications - OR and Management Sciences, Finance and Economics

    Drawing on statistical learning theory, we derive out-of-sample and suboptimal guarantees about the investment strategy obtained from a regularized portfolio optimization model which attempts to exploit side information about the financial market in order to reach an optimal risk-return tradeoff. This side information might include for instance recent stock returns, volatility indexes, financial news indicators, … Read more

    An exact algorithm to find non-dominated facets of Tri-Objective MILPs

  • Ali Fattahi
  • Metin Turkay
  • Seyyed Amir Babak Rasmi
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , ,

    Many problems in real life have more than one decision criterion, referred to as multi-objective optimization (MOO) problems, and the objective functions of these problems are conflicting in most cases. Hence, finding non-dominated solutions is very critical for decision making process. Tri-objective mixed-integer linear programs (TOMILP) are an important subclass of MOOs that are applicable … Read more

    Local attractors of newton-type methods for constrained equations and complementarity problems with nonisolated solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares

    For constrained equations with nonisolated solutions, we show that if the equation mapping is 2-regular at a given solution with respect to a direction in the null space of the Jacobian, and this direction is interior feasible, then there is an associated domain of starting points from which a family of Newton-type methods is well-de ned … Read more

    Mathematical Programming Formulations for Piecewise Polynomial Functions

  • Bjarne Grimstad
  • Brage Rugstad Knudsen
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. … Read more

    Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control

  • Sebastian Sager
  • Tobias Weber
  • Clemens Zeile
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , , , ,

    Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal … Read more