nondifferentiable optimization

Generalized Bundle Methods for Sum-Functions with Easy” Components: Applications to Multicommodity Network Design

  • Antonio Frangioni
  • Enrico Gorgone
    • Categories Convex and Nonsmooth Optimization, Linear Programming, Network Optimization Tags , , , ,

    We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are “easy”, that is, they are Lagrangian functions of explicitly known convex programs with “few” variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In … Read more

    Piecewise quadratic approximations in convex numerical optimization

  • Annabella Astorino
  • Antonio Frangioni
  • Manlio Gaudioso
  • Enrico Gorgone
    • Categories Convex Optimization Tags , ,

    We present a bundle method for convex nondifferentiable minimization where the model is a piecewise quadratic convex approximation of the objective function. Unlike standard bundle approaches, the model only needs to support the objective function from below at a properly chosen (small) subset of points, as opposed to everywhere. We provide the convergence analysis for … Read more

    Bundle Methods for Convex Minimization with Partially Inexact Oracles

  • Krzysztof C. Kiwiel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Recently the proximal bundle method for minimizing a convex function has been extended to an inexact oracle that delivers function and subgradient values of unknown accuracy. We adapt this method to a partially inexact oracle that becomes exact only when an objective target level for a descent step is met. In Lagrangian relaxation, such oracles … Read more

    Approximate Primal Solutions and Rate Analysis in Dual Subgradient Methods

  • Angelia Nedich
  • Asuman Ozdaglar
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We study primal solutions obtained as a by-product of subgradient methods when solving the Lagrangian dual of a primal convex constrained optimization problem (possibly nonsmooth). The existing literature on the use of subgradient methods for generating primal optimal solutions is limited to the methods producing such solutions only asymptotically (i.e., in the limit as the … Read more

    An interior point cutting plane method for convex feasibility problem with second-order cone inequalities

  • Jean-Louis Goffin
  • Mohammad R. Oskoorouchi
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Convex feasibility problem in general, is a problem of finding a point in a convex set contains a full dimensional ball and is contained in a compact convex set. We assume that the outer set is described by second-order cone inequalities and propose an analytic center cutting plane technique to solve this problem. We discuss … Read more

    A unifying framework for several cutting plane algorithms for semidefinite programming

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Nonsmooth Optimization, Semi-definite Programming, Semi-infinite Programming Tags , , ,

    Cutting plane methods provide the means to solve large scale semidefinite programs (SDP) cheaply and quickly. They can also conceivably be employed for the purposes of re-optimization after branching, or the addition of cutting planes. We give a survey of various cutting plane approaches for SDP in this paper. These cutting plane approaches arise from … Read more