Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

On convergence rates of subgradient optimization methods

Rates of convergence of subgradient optimization are studied. If the step size is chosen to be a geometric progression with ratio the convergence, if it occurs, is geometric with rate. For convergence to occur, it is necessary that the initial step size be large enough, and that the ratio be greater than a sustainable ratez(), which depends upon a condition number, defined for both differentiable and nondifferentiable functions. The sustainable ratez() is closely related to the rate of convergence of the steepest ascent method for differentiable functions: in fact it is identical if the function is not too well conditioned.This research was supported in part by the D.G.E.S. (Quebec) and the N.R.C. of Canada under grants A8970 and A4152.     

On finite convergence and constraint identification of subgradient projection methods

This paper deals with a continuous time, subgradient projection algorithm, shown to generate trajectories that accumulate to the solution set. Under a strong convexity assumption we show that convergence is exponential in norm. A sharpness condition yields convergence in finite time, and the necessary lapse is estimated. Invoking a constraint qualification and a non-degeneracy assumption, we demonstrate that optimally active constraints are identified in finite time.This research has been partially supported by Rutgers University, RUTCOR, New Brunswick, NJ 08903, USA, and by the Memorial Fund of Wilhelm Kheilhau.     

On the computational efficiency index and some iterative methods for solving systems of nonlinear equations

In this paper two new iterative methods are built up and analyzed. A generalization of the efficiency index used in the scalar case to several variables in iterative methods for solving systems of nonlinear equations is revisited. Analytic proofs of the local order of convergence based on developments of multilineal functions and numerical concepts that will be used to illustrate the analytic results are given. An approximation of the computational order of convergence is computed independently of the knowledge of the root and the necessary time to get one correct decimal is studied in our examples.     

On the computational efficiency index and some iterative methods for solving systems of nonlinear equations

In this paper two new iterative methods are built up and analyzed. A generalization of the efficiency index used in the scalar case to several variables in iterative methods for solving systems of nonlinear equations is revisited. Analytic proofs of the local order of convergence based on developments of multilineal functions and numerical concepts that will be used to illustrate the analytic results are given. An approximation of the computational order of convergence is computed independently of the knowledge of the root and the necessary time to get one correct decimal is studied in our examples.     

Applications of matrix methods to the theory of lower bounds in computational complexity

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn ^(logn) for the function MINIMUM COVER using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.     

On the efficiency of a class of a-stable methods

The numerical solution of systems of differential equations of the formB dx/dt=σ(t)Ax(t)+f(t),x(0) given, whereB andA (withB and —(A+A ^T) positive definite) are supposed to be large sparse matrices, is considered.A-stable methods like the Implicit Runge-Kutta methods based on Radau quadrature are combined with iterative methods for the solution of the algebraic systems of equations.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

On the computational methods in axisymmetric electrodynamics problems

The integral currents method is actively used at present to solve problems of electrical sounding. Its application requires calculation of the integrals of the kernel of an integrated equation and the function of conversion. In this work, the computational aspects of calculating such integrals for an axisymmetric case are considered, and a method that allows such calculations to be performed up to the asymptotic zone is proposed. The asymptotics of the conversion function are also studied.     

On Lagrangian duality in vector optimization: applications to the linear case

We recall a general scheme for vector problems based on separation arguments and alternative theorems, and then, this approach is exploited to study Lagrangian duality in vector optimization. We show that the vector linear duality theory due to Isermann can be embedded in this separation approach. The theoretical part of this paper serves the purpose of introducing two possible applications. Some well-known classical applications in economics are the minimization of costs and the maximization of profit for a firm. We extend these two examples to the multiobjective framework in the linear case, exploiting the duality theory of Isermann. For the former, we consider the minimization of costs and of pollution as two different and conflicting goals; for the latter, we introduce as second objective function the profit for a competitor firm. This allows us to study the relationships between the shadow prices referred to the two different goals and to introduce a new representation of the feasible region of the dual problem.     

On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming

In this paper, we present new convergence properties of the augmented Lagrangian method for nonlinear semidefinite programs (NSDP). Convergence to the approximately global solutions and optimal values of NSDP is first established for a basic augmented Lagrangian scheme under mild conditions, without requiring the boundedness condition of the multipliers. We then propose four modified augmented Lagrangian methods for NSDP based on different algorithmic strategies. We show that the same convergence of the proposed methods can be ensured under weaker conditions.     

On sharp quadratic convergence bounds for the serial Jacobi methods

Summary Using a new technique we derive sharp quadratic convergence bounds for the serial symmetric and SVD Jacobi methods. For the symmetric Jacobi method we consider the cases of well and poorely separated eigenvalues. Our result implies the result proposed, but not correctly proved, by Van Kempen. It also extends the well-known result of Wilkinson to the case of multiple eigenvalues.This work was supported in part by the U.S. Army. Contract DAAL03-89-C-0038     

On the convergence properties of modified augmented Lagrangian methods for mathematical programming with complementarity constraints

In this paper, we present new convergence results of augmented Lagrangian methods for mathematical programs with complementarity constraints (MPCC). Modified augmented Lagrangian methods based on four different algorithmic strategies are considered for the constrained nonconvex optimization reformulation of MPCC. We show that the convergence to a global optimal solution of the problem can be ensured without requiring the boundedness condition of the multipliers.     

On the computational utility of posynomial geometric programming solution methods

Ten codes or code variants were used to solve the five equivalent posynomial GP problem formulations. Four of these codes were general NLP codes; six were specialized GP codes. A total of forty-two test problems was solved with up to twenty randomly generated starting points per problem. The convex primal formulation is shown to be intrinsically easiest to solve. The general purpose GRG code called OPT appears to be the most efficient code for GP problem solution. The reputed superiority of the specialized GP codes GGP and GPKTC appears to be largely due to the fact that these codes solve the convex primal formulation. The dual approaches are only likely to be competitive for small degree of difficulty, tightly constrained problems.     

Stopping criteria for inner iterations in inexact potential reduction methods: a computational study

We focus on the use of adaptive stopping criteria in iterative methods for KKT systems that arise in Potential Reduction methods for quadratic programming. The aim of these criteria is to relate the accuracy in the solution of the KKT system to the quality of the current iterate, to get computational efficiency. We analyze a stopping criterion deriving from the convergence theory of inexact Potential Reduction methods and investigate the possibility of relaxing it in order to reduce as much as possible the overall computational cost. We also devise computational strategies to face a possible slowdown of convergence when an insufficient accuracy is required.     

Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study

Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the optimal linear outer-approximation approach by Ben-Tal and Nemirovski (Math Oper Res 26:193–205, 2001) from which we derive an optimal inner approximation of the second-order cone. We examine the performance of this approach on various benchmark sets including portfolio optimization instances as well as (robustified versions of) the MIPLIB and the SNDlib.     

Partial fractions expansion: a review of computational methodology and efficiency

Nine methods for expressing a proper rational function in terms of partial fractions are presented for the case where the denominator polynomial has been reduced to linear factors. Only those methods which are amenable to computation algorithms are considered. To the extent possible, Newton's divided difference formula is used to provide a uniform derivational tool. Each method is illustrated numerically. The efficiency of the methods are compared on the basis of the number of multiplications and divisions required in the computation.