Upper bounds for Gaussian stochastic programs

We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only as many linear programs as the problem has variables. Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999     

Global s-type error bound for the extended linear complementarity problem and applications

For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R ₀-property. We then establish global s-type error bound for this problem with the column monotonicity or R ₀-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions. Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

Error bounds for proximal point subproblems and associated inexact proximal point algorithms

We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed. Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000     

Nonlinear error bounds for lower semicontinuous functions on metric spaces

As a development of the theory of linear error bounds for lower semicontinuous functions defined on complete metric spaces, introduced in Azé et al. (Nonlinear Anal 49, 643–670, 2002) and refined in Azé and Corvellec (ESAIM Control Optim Calc Var 10, 409–425, 2004), we propose a similar approach to nonlinear error bounds, based on the notion of strong slope, the variational principle, and the change-of-metric principle, the latter allowing to obtain sharp estimates for such error bounds through a reduction to the linear case.     

Well-posedness and porosity in optimal control without convexity assumptions

The Tonelli existence theorem in the calculus of variations and its subsequent modifications were established for integrands f which satisfy convexity and growth conditions. In [27] we considered a class of optimal control problems which is identified with the corresponding complete metric space of integrands, say . We did not impose any convexity assumptions. The main result in [27] establishes that for a generic integrand the corresponding optimal control problem is well-posed. In this paper we study the set of all integrands for which the corresponding optimal control problem is well-posed. We show that the complement of this set is not only of the first category but also a -porous set. The main result of the paper is obtained as a realization of a variational principle which can be applied to various classes of optimization problems. Received April 15, 2000 / Accepted October 10, 2000 / Published online December 8, 2000     

A branch-and-cut method for 0-1 mixed convex programming

We generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method. Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999     

Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption

A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper. Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999     

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     

Upper Lipschitz behavior of solutions to perturbed. C1,1 programs

We analyze the local upper Lipschitz behavior of critical points, stationary solutions and local minimizers to parametric C ^1,1 programs. In particular, we derive a characterization of this property for the stationary solution set map without assuming the Mangasarian–Fromovitz CQ. Moreover, conditions which also ensure the persistence of solvability are given, and the special case of linear constraints is handled. The present paper takes pattern from [21] by continuing the approach via contingent derivatives of the Kojima function associated with the given optimization problem. Received: June 10, 1999 / Accepted: November 15, 1999?Published online July 20, 2000     

Conditioning of semidefinite programs

theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case. Received November 26, 1995 / Revised version received November 1, 1998 Published online February 25, 1999     

Gaps in Convex Disc Packings with an Application to 1-Steiner Minimum Trees

 We show that if six translates of a convex disc C all touch C, and no two of the translates have interior points in common, then there are never more than two gaps, i.e., consecutive non-touching pairs of translates. We also characterize the configurations where there are two, one or no gaps. This result is then applied to show that the Steiner point in a 1-Steiner Minimum Tree in a normed plane has degree at most five if the unit ball is not an affine regular hexagon (where Steiner points of degree six exist). (Received 23 July 1999)     

Convergence of Newton's method for convex best interpolation

Summary. In this paper, we consider the problem of finding a convex function which interpolates given points and has a minimal norm of the second derivative. This problem reduces to a system of equations involving semismooth functions. We study a Newton-type method utilizing Clarke's generalized Jacobian and prove that its local convergence is superlinear. For a special choice of a matrix in the generalized Jacobian, we obtain the Newton method proposed by Irvine et al. [17] and settle the question of its convergence. By using a line search strategy, we present a global extension of the Newton method considered. The efficiency of the proposed global strategy is confirmed with numerical experiments. Received October 26, 1998 / Revised version received October 20, 1999 / Published online August 2, 2000     

Properties of an interior embedding for solving nonlinear optimization problems

The paper presents an interior embedding of nonlinear optimization problems. This embedding satisfies a sufficient condition for the success of pathfollowing algorithms with jumps being applied to one-parametric optimization problems.?The one-parametric problem obtained by the embedding is supposed to be regular in the sense of Jongen, Jonker and Twilt. This asumption is analyzed, and its genericity is proved in the space of the original optimization problems. Received May 20, 1997 / Revised version received October 6, 1998?Published online May 12, 1999     

Forcing strong convergence of proximal point iterations in a Hilbert space

This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible since it amounts, at most, to solving a linear system of two equations in two unknowns. Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

On generalized trade-off directions in nonconvex multiobjective optimization

Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a nonconvex case. Giving up convexity naturally means that we need local instead of global analysis. Received: December 2000 / Accepted: October 2001?Published online February 14, 2002     

Dual conditions characterizing optimality for convex multi-objective programs

Received June 13, 1995 / Revised version received February 6, 1998 Published online August 18, 1998     

Weighted quasi-equilibrium problems with lower and upper bounds

This paper is devoted to studying the solution existence of weighted quasi-equilibrium problems with lower and upper bounds by using maximal element theorems, a fixed point theorem of set-valued mappings and Fan–KKM theorem, respectively. Some new results are obtained.     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

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