We describe a steepest-descent potential reduction method for linear and convex minimization over a simplex in Rn and its precise complexity analysis. In this method, no matrix needs to be ever inversed so that it is a pure first-order method. 1 Convex optimization over the simplex constraint We consider the following optimization problem over the simplex: Minimize f(x) Subject to eTx = 1; x ≥ 0, (1) where e is the vector of all ones. Such a problem in considered in [7], where function f(x) does not need to be convex and a FPTAS algorithm was developed for computing an approximate KKT point of general quadratic programming. The following algorithm and analysis resemble those in [7]. We assume that f(x) is a convex function in x ∈ Rn and f(x...
This paper shows that error bounds can be used as effective tools for deriving complexity results fo...
In this note we show that a simple modification of Ye's "affinely scaled potential reduction" algori...
We characterize the property of obtaining a solution to a convex program by minimizing over the feas...
We provide a survey of interior-point methods for linear programming and its extensions that are bas...
This is a short tutorial on complexity studies for differentiable convex optimization. A complexity ...
Abstract—The problem of optimizing a linear objective func-tion, given a number of linear constraint...
. We describe an algorithm for optimization of a smooth function subject to general linear constrain...
Includes bibliographical references (p. 16-17).Supported by a Presidential Young Investigator Award....
AbstractWe propose a new polynomial potential-reduction method for linear programming, which can als...
This paper develops a potential reduction algorithm for solving a linear-programming problem directl...
Code available at https://github.com/AdrienTaylor/GreedyMethodsInternational audienceWe describe a n...
In this paper, we introduce a potential reduction method for harmonically convex programming. We sho...
Written for specialists working in optimization, mathematical programming, or control theory. The ge...
Motivated by recent work of Renegar, we present new computational methods and associated computation...
AbstractIn this note we show that a simple modification of Ye's “affinely scaled potential reduction...
This paper shows that error bounds can be used as effective tools for deriving complexity results fo...
In this note we show that a simple modification of Ye's "affinely scaled potential reduction" algori...
We characterize the property of obtaining a solution to a convex program by minimizing over the feas...
We provide a survey of interior-point methods for linear programming and its extensions that are bas...
This is a short tutorial on complexity studies for differentiable convex optimization. A complexity ...
Abstract—The problem of optimizing a linear objective func-tion, given a number of linear constraint...
. We describe an algorithm for optimization of a smooth function subject to general linear constrain...
Includes bibliographical references (p. 16-17).Supported by a Presidential Young Investigator Award....
AbstractWe propose a new polynomial potential-reduction method for linear programming, which can als...
This paper develops a potential reduction algorithm for solving a linear-programming problem directl...
Code available at https://github.com/AdrienTaylor/GreedyMethodsInternational audienceWe describe a n...
In this paper, we introduce a potential reduction method for harmonically convex programming. We sho...
Written for specialists working in optimization, mathematical programming, or control theory. The ge...
Motivated by recent work of Renegar, we present new computational methods and associated computation...
AbstractIn this note we show that a simple modification of Ye's “affinely scaled potential reduction...
This paper shows that error bounds can be used as effective tools for deriving complexity results fo...
In this note we show that a simple modification of Ye's "affinely scaled potential reduction" algori...
We characterize the property of obtaining a solution to a convex program by minimizing over the feas...