Convergence of a simple subgradient level method

Received December 3, 1996 / Revised version received January 29, 1998 Published online October 21, 1998     

Analytical properties of the central path at boundary point in linear programming

Received October 15, 1996 / Revised version received January 28, 1998 Published online October 21, 1998     

Characterization of the smoothness and curvature of a marginal function for a trust-region problem

Received May 28, 1996 / Revised version received May 1, 1998 Published online October 9, 1998     

Intersection theorems on polytopes

Received June 6, 1995 / Revised version received May 26, 1998 Published online October 9, 1998     

A note on “On Pareto optima, the Fermat-Weber problem, and polyhedral gauges”

Received September 3, 1997 / Revised version received March 20, 1998 Published online October 9, 1998     

Sample-path solution of stochastic variational inequalities

Received July 30, 1997 / Revised version received June 4, 1998 Published online October 21, 1998     

Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on the Kojima-Shindoh-Hara family of directions

Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998     

Degeneracy in the multi-source Weber problem

Received June 10, 1996 / Revised version received May 20, 1997 Published online October 21, 1998     

Metric regularity and quantitative stability in stochastic programs with probabilistic constraints

Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998     

Stability in the presence of degeneracy and error estimation

Received February 10, 1997 / Revised version received June 6, 1998 Published online October 9, 1998     

Approximating quadratic programming with bound and quadratic constraints

Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998     

Asymptotic constraint qualifications and global error bounds for convex inequalities

Received October 26, 1996 / Revised version received October 1, 1997 Published online October 9, 1998     

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 a homogeneous algorithm for the monotone complementarity problem

Received May 15, 1995 / Revised version received May 20, 1998 Published online October 21, 1998     

The role of linear objective functions in barrier methods

Received December 10, 1994 / Revised version received April 29, 1998 Published online October 21, 1998     

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions, tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational effort. We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct, at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the basic subgradient scheme. Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999     

The volume algorithm: producing primal solutions with a subgradient method

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location. Received: June 15, 1998 / Accepted: November 15, 1999?Published online March 15, 2000     

Properties of the Moreau-Yosida regularization of a piecewise C2 convex function

Received December 14, 1995 / Revised version received May 7, 1998 Published online October 21, 1998     

Set-valued approximations and Newton’s methods

n to R^m. Under the assumption of semi-smoothness of the mapping, we prove that the approximation can be obtained through the Clarke generalized Jacobian, Ioffe-Ralph generalized Jacobian, B-subdifferential and their approximations. As an application, we propose a generalized Newton’s method based on the point-based set-valued approximation for solving nonsmooth equations. We show that the proposed method converges locally superlinearly without the assumption of semi-smoothness. Finally we include some well-known generalized Newton’s methods in our method and consolidate the convergence results of these methods. Received October 2, 1995 / Revised version received May 5, 1998 Published online October 9, 1998     

Nonlinear programming algorithms using trust regions and augmented Lagrangians with nonmonotone penalty parameters

The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998