Multipoint secant and interpolation methods with nonmonotone line search for solving systems of nonlinear equations

  • Oleg Burdakov
  • Ahmad Kamandi
    • Categories Nonlinear Optimization Tags , , , , ,

    Multipoint secant and interpolation methods are effective tools for solving systems of nonlinear equations. They use quasi-Newton updates for approximating the Jacobian matrix. Owing to their ability to more completely utilize the information about the Jacobian matrix gathered at the previous iterations, these methods are especially efficient in the case of expensive functions. They are … Read more

    On the local stability of semidefinite relaxations

  • Sameer Agarwal
  • Diego Cifuentes
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions … Read more

    Network-based Approximate Linear Programming for Discrete Optimization

  • Andre Augusto Cire
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Linear Programming Tags , ,

    We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more

    MILP feasibility by nonlinear programming

  • Leo Liberti
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Quadratic Programming Tags , ,

    We discuss a tightly feasible mixed-integer linear programs arising in the energy industry, for which branch-and-bound appears to be ineffective. We consider its hardness, measure the probability that randomly generated instances are feasible or almost feasible, and introduce heuristic solution methods based on relaxing different constraints of the problem. We show the computational efficiency of … Read more

    Sparse principal component analysis and its l1-relaxation

  • Santanu S. Dey
  • Rahul Mazumder
  • Marco Molinaro
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining

    Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component … Read more

    Two-level value function approach to nonsmooth optimistic and pessimistic bilevel programs

  • Stephan Dempe
  • Boris S. Mordukhovich
  • Alain Zemkoho
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The authors’ paper in Ref. [5], was the first one to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analyzed in Ref. [4], for the case of optimistic bilevel programs. One of the basic assumptions in both of these … Read more

    Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng’s F-B four-operator splitting method for solving monotone inclusions

  • M. Marques Alves
  • Marina Geremia
    • Categories Convex and Nonsmooth Optimization

    In this paper, we propose and study the iteration complexity of an inexact Douglas-Rachford splitting (DRS) method and a Douglas-Rachford-Tseng’s forward-backward (F-B) splitting method for solving two-operator and four-operator monotone inclusions, respectively. The former method (although based on a slightly different mechanism of iteration) is motivated by the recent work of J. Eckstein and W. … Read more

    An algorithm for binary chance-constrained problems using IIS

  • Gianpiero Canessa
  • Lewis Ntaimo
  • Bernardo K. Pagnoncelli
  • Julián Gallego
    • Categories 0-1 Programming, Stochastic Programming

    We propose an algorithm based on infeasible irreducible subsystems (IIS) to solve general binary chance-constrained problems. By leverag- ing on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete do- main is used to guide us eciently in the search of … Read more

    Linear Convergence Rate of the Generalized Alternating Direction Method of Multipliers for a Class of Convex Optimization Problems

  • Peng Jian-Wen
  • Xue-Qing Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Rencently, the generalized aternating direction method of multipliers (GADMM) proposed by Eckstein and Bertsekas has received intensive attention from a broad spectrum of areas. In this paper, we consider the convergence rate of GADMM when applying to the convex optimization problems that the subdifferentials of the underlying functions are piecewise linear multifunctions, including LASSO, a … Read more

    Efficient Convex Optimization for Linear MPC

  • Stephen Wright
    • Categories Control Applications, Quadratic Programming Tags ,

    Model predictive control (MPC) formulations with linear dynamics and quadratic objectives can be solved efficiently by using a primal-dual interior-point framework, with complexity proportional to the length of the horizon. An alternative, which is more able to exploit the similarity of the problems that are solved at each decision point of linear MPC, is to … Read more