Exact penalties for optimization problems with 2-regular equality constraints

A new first-order sufficient condition for penalty exactness that includes neither the standard constraint qualification requirement nor the second-order sufficient optimality condition is proposed for optimization problems with equality constraints.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002     

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     

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     

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     

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 error bounds with fractional exponents

Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic functions. Received: August 20, 1999 / Accepted: March 20, 2000?Published online July 20, 2000     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

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     

On the rate of convergence of sequential quadratic programming with nondifferentiable exact penalty function in the presence of constraint degeneracy

We analyze the convergence of a sequential quadratic programming (SQP) method for nonlinear programming for the case in which the Jacobian of the active constraints is rank deficient at the solution and/or strict complementarity does not hold for some or any feasible Lagrange multipliers. We use a nondifferentiable exact penalty function, and we prove that the sequence generated by an SQP using a line search is locally R-linearly convergent if the matrix of the quadratic program is positive definite and constant over iterations, provided that the Mangasarian-Fromovitz constraint qualification and some second-order sufficiency conditions hold. Received: April 28, 1998 / Accepted: June 28, 2001?Published online April 12, 2002     

A non-interior continuation method for generalized linear complementarity problems

In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported. Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999     

Perturbation analysis of global error bounds for systems of linear inequalities

This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000     

Inverse functions of pseudo regular mappings and regularity conditions

We show that, even for monotone directionally differentiable Lipschitz functionals on Hilbert spaces, basic concepts of generalized derivatives identify only particular pseudo regular (or metrically regular) situations. Thus, pseudo regularity of (multi-) functions will be investigated by other means, namely in terms of the possible inverse functions. In this way, we show how pseudo regularity for the intersection of multifunctions can be directly characterized and estimated under general settings and how contingent and coderivatives may be modified to obtain sharper regularity conditions. Consequences for a concept of stationary points as limits of Ekeland points in nonsmooth optimization will be studied, too. Received: May 20, 1999 / Accepted: February 15, 2000?Published online July 20, 2000     

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     

A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999     

Error bounds for euler approximation of a state and control constrained optimal control problem 1

We examine convergence of the Euler approximation to a nonlinear optimal control problem subject to mixed state-control and pure state constraints. We prove that under smoothness, independence, controllability and coercivity conditions at a reference solution of the continuous problem, there exists a locally unique solution to the Euler approximation, for sufficiently fine discretization, which converges to the reference solution with rate proportional to the mesh size.     

Q-superlinear convergence of the iterates in primal-dual interior-point methods

Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent. Received: February 9, 2000 / Accepted: February 20, 2001?Published online May 3, 2001     

Kernel estimates of functions and their derivatives with applications

The problem of the estimation of functions and their derivatives from noisy observations is considered. The new kernel estimate is shown to be consistent in the mean square sense and an exact bound on the uniform mean squared error is given. An application to the system identification is discussed.     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

Discretization in semi-infinite programming: the rate of convergence

The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary and for generalized semi-infinite problems. Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001