The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more
We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides … Read more
In this paper we propose an inexact proximal point method to solve constrained minimization problems with locally Lipschitz quasiconvex objective functions. Assuming that the function is also bounded from below, lower semicontinuous and using proximal distances, we show that the sequence generated for the method converges to a stationary point of the problem. CitationJuly 2013ArticleDownload … Read more
We consider a model in which a consumer of a resource over several periods must pay a per unit charge for the resource as well as a peak charge. The consumer has the ability to reduce his consumption in any period at some given cost, subject to a constraint on the total amount of reduction … Read more
We study equilibrium problems with strongly pseudomonotone bifunctions in real Hilbert spaces. We show the existence of a unique solution. We then propose a generalized strongly convergent projection method for equilibrium problems with strongly pseudomonotone bifunctions. The proposed method uses only one projection without requiring Lipschitz continuity. Application to variational inequalities is discussed. CitationInstitute of … Read more
We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either fi nds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the … Read more
We propose a generalized proximal point algorithm (PPA), in the generic setting of finding a zero point of a maximal monotone operator. In addition to the classical PPA, a number of benchmark operator splitting methods in PDE and optimization literatures such as the Douglas-Rachford splitting method, Peaceman-Rachford splitting method, alternating direction method of multipliers, generalized … Read more
We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more
An algorithmic framework is presented for optimising general convex functions by non synchronised parallel processes. Each process greedily picks a suitable adaptive subset of coordinates and runs a bundle method on a corresponding restricted problem stopping whenever a descent step is encountered or predicted decrease is reduced sufficiently. No prior knowledge on the dependencies between … Read more
We present new results for the conditional gradient method (also known as the Frank-Wolfe method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial … Read more