Search

The existing choices for the step lengths used by the classical steepest descent algorithm for minimizing a convex quadratic function require in the worst case $$ \mathcal{{O}}(C\log (1/\varepsilon )) $$O(Clog(1/ź)) iterations to achieve a precision $$ \varepsilon $$ź, where C is the Hessian condition number. We show how to construct a sequence of step lengths with which the algorithm stops in $$ \mathcal{{O}}(\sqrt{C}\log (1/\varepsilon )) $$O(Clog(1/ź)) iterations, with a bound almost exactly equal to that of the Conjugate Gradient method.

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.

We consider first the differentiable nonlinear programming problem and study the asymptotic behavior of methods based on a family of penalty functions that approximate asymptotically the usual exact penalty function. We associate two parameters to these functions: one is used to control the slope and the other controls the deviation from the exact penalty. We propose a method that does not change the slope for feasible iterates and show that for problems satisfying the Mangasarian-Fromovitz constraint qualification all iterates will remain feasible after a finite number of iterations. The same results are obtained for non-smooth convex problems under a Slater qualification condition.

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation ofp Newton steps: the first of these steps is exact, and the other are called "simplified". In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-orderp+1 in the number of master iterations, and with a complexity of $$O(\sqrt n L)$$ iterations.

We present a procedure for computing lower bounds for the optimal cost in a linear programming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no projective transformations or problem restatements are used, the method coincides with the procedures by Todd and Burrell and by de Ghellinck and Vial when these procedures are applicable. The procedure applies directly to affine potential reduction algorithms, and improves on existent techniques for finding lower bounds.

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.

The method of steepest descent with scaling (affine scaling) applied to the potential functionq logcźx -- źi=1n logxi solves the linear programming problem in polynomial time forq ź n. Ifq = n, then the algorithm terminates in no more than O(n2L) iterations; if q ź n + $$\sqrt n $$ withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n4L) and O(n3.5L) arithmetic computions.

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.