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

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

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

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

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

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

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