This paper presents a new primal dual simplex method and investigates the duality formation implying in classical simplex methods. We reviews classical simplex methods for linear programming problems and give a detail discussion for the relation between modern and classical algorithms. The two modified versions are present. The advantages of the new algorithms are simplicity … Read more
We adapt a method due to Nesterov so as to obtain an algorithm for solving block-angular fractional packing or covering problems to relative tolerance epsilon, while using a number of iterations that grows polynomially in the size of the problem and whose dependency on epsilon is proportional to 1/epsilon. CitationCORC report TR-2004-09, Computational Optimization Research … Read more
The DIRECT algorithm is a deterministic sampling method for bound constrained Lipschitz continuous optimization. We prove a subsequential convergence result for the DIRECT algorithm that quantifies some of the convergence observations in the literature. Our results apply to several variations on the original method, including one that will handle general constraints. We use techniques from … Read more
Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the … Read more
Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x – y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. … Read more
We study a steered sequential gradient algorithm which minimizes the sum of convex functions by proceeding cyclically in the directions of the negative gradients of the functions and using steered step-sizes. This algorithm is applied to the convex feasibility problem by minimizing a proximity function which measures the sum of the Bregman distances to the … Read more
We consider two notions for the representations of convex cones: $G$-representation and lifted-$G$-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones … Read more
The Gauss-Lucas Theorem on the roots of polynomials nicely simplifies calculating the subderivative and regular subdifferential of the abscissa mapping on polynomials (the maximum of the real parts of the roots). This paper extends this approach to more general functions of the roots. By combining the Gauss-Lucas methodology with an analysis of the splitting behavior … Read more
Extremality, stationarity and regularity notions for a system of closed sets in a normed linear space are investigated. The equivalence of different abstract “extremal” settings in terms of set systems and multifunctions is proved. The dual necessary and sufficient conditions of weak stationarity (the Extended extremal principle) are presented for the case of an Asplund … Read more
In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant … Read more