Column aggregation and primal decomposition in linear programming: some observations

In this paper we present a way to interpret column aggregation schemes in linear programming as a special kind of primal decomposition. This relation between aggregation and decomposition is obtained through a reformulation of the original problem by the introduction of auxiliary variables. The relation between aggregation and decomposition yields a natural iterative aggregation scheme, where weights updating can be done in different ways. We describe several weight updating schemes and illustrate three of them within an iterative aggregation technique with a numerical example. Finally we point out some new research issues that appear when the aggregation process is viewed in this decomposition framework     

Optimality conditions and duality models for generalized fractional programming problems containing locally subdifferentiable and ρ:-convex functions

Both parametric and nonparametric necessary and sufficient optimality conditions are established for a class of nonsmooth generalized fractional programming problems containing ρ-convex functions. Subsequently, these optimality criteria are utilized as a basis for constructing two parametric and four parameter-free duality models and proving appropriate duality theorems. Several classes of generalized fractional programming problems, including those with arbitrary norms, square roots of positive semidefinite quadratic forms, support functions, continuous max functions, and discrete max functions, which can be viewed as special cases of the main problem are briefly discussed. The optimality and duality results developed here also contain, as special cases, similar results for nonsmooth problems with fractional, discrete max, and conventional objective functions which are particular cases of the main problem considered in this paper     

Asymptotic analysis of a path-following barrier method for linearly constrained convex problems *

In the present paper the logarithmic barrier method applied to the linearly constrained convex optimization problems is studied from the view point of classical path-following algorithms. In particular, the radius of convergence of Newton's method which depends on the barrier parameter itself is estimated in standard norms, being independent of the parameter, without explicitly using self-concordance properties. The obtained results establish a parameter selection rule which guarantees the overall convergence of a barrier technique with only one Newton step at each parameter level and the complexity of the method can be estimated.     

A relaxed cutting plane algorithm for solving fuzzy inequality systems

This paper studies a system of infinitely many fuzzy inequalities with concavemembership functions. By using the tolerance approach, we show that solving such system can be reduced to a semi-infinite programming problem. A relaxed cutting plane algorithm is proposed. In each iteration, we solve a finite convex optimization problem and add one or two more constraints. The proposed algorithm chooses a point at which the infinite constraints are violated to a degree rather than at which the violation is maximized. The iterative process ends when an optimal solution is identified. A convergence proof, under some mild conditions, is given. An efficient implementation based on the "method of centres" with "entropic regularization" techniques is also included. Some computational results confirm the efficiency of the proposed method and show its potential for solving large scale problems.     

Strong duality for inexact linear programming

In this paper, we apply the Dubovitskii-Milyutin approach to derive strong duality theorems for inexact linear programming problems. Inexact linear programming deals with the standard linear problem in which the data is not well known and it is supposed to lie in certain given convex sets. The case of parametric dependence of the data is particularly analyzed and relations with semi-infinite and

semi-definite programming are also commented.     

A Semi-Infinite Programming Model In Data Envelopment Analysis

We consider a model for data envelopment analysis with infinitely many decision-making units. The determination of the relative efficiency of a given decision-making unit amounts to the solution of a semi-infinite optimization problem. We show that a decision-making unit of maximal relative efficiency exists and that it is 100% efficient. Moreover, this decision-making unit can be found by calculating a zero of the semi-infinite constraint function. For the latter task we propose a bi-level algorithm. We apply this algorithm to a problem from chemical engineering and present numerical results     

An algorithm for computing equilibria in a linear monetary economy

An algorithm is presented for computing equilibria in a linear monetary economy, that is, an exchange economy in which all individuals have linear utility functions and in which goods are bought and sold only in exchange for money. The algorithm computes the equilibrium prices by solving a finite sequence of linear programming problems.     

A global quadratic algorithm for solving a system of mixed equalities and inequalities

A new algorithm is proposed which, under mild assumptions, generates a sequence{x _i } that starting at any point inR ⁿ will converge to a setX defined by a mixed system of equations and inequalities. Any iteration of the algorithm requires the solution of a linear programming problem with relatively few constraints. By only assuming that the functions involved are continuously differentiable a superlinear rate of convergence is achieved. No convexity whatsoever is required by the algorithm.     

A construction method in parametric programming

We consider a linear programming problem, with two parameters in the objective function, and present an algorithm for finding the decomposition of the parameter space into maximal polyhedral areas in which particular basic solutions are optimal. Special attention is paid to fill up areas of degenerate solutions.