Cutting plane algorithms for robust conic convex optimization

In the paper we study some well-known cases of nonlinear programming problems, presenting them as instances of Inexact Linear Programming. The class of problems considered contains, in particular, semidefinite programming, second order cone programming and special cases of inexact semidefinite programming. Strong duality results for the nonlinear problems studied are obtained via the Lagrangian duality. … Read more

Mean-risk objectives in stochastic programming

Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criteria. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk criterion, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various … Read more

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to eigenvalue optimization. In our approach we utilize the method of analytic center to obtain the query points at each iteration. A restricted master problem in the primal space is formed corresponding to the relaxed dual problem. At each step of the algorithm, an oracle is … 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 DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization

We introduce an algorithm to minimize a function of several variables with no convexity nor smoothness assumptions. The main peculiarity of our approach is the use of an the objective function model which is the difference of two piecewise affine convex functions. Bundling and trust region concepts are embedded into the algorithm. Convergence of the … Read more

Using selective orthonormalization to update the analytic center after the addition of multiple cuts

We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more

STRONG LOWER BOUNDS FOR THE PRIZE COLLECTING STEINER PROBLEM IN GRAPHS

Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. … Read more

Minimizing nonconvex nonsmooth functions via cutting planes and proximity control

We describe an extension of the classical cutting plane algorithm to tackle the unconstrained minimization of a nonconvex, not necessarily differentiable function of several variables. The method is based on the construction of both a lower and an upper polyhedral approximation to the objective function and it is related to the use of the concept … Read more

Search and Cut: New Class of Cutting Planes for 0-1 Programming

The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory’s cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description … Read more

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient … Read more