Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems

In this paper, we propose a Newton-type method for solving a semismooth reformulation of monotone complementarity problems. In this method, a direction-finding subproblem, which is a system of linear equations, is uniquely solvable at each iteration. Moreover, the obtained search direction always affords a direction of sufficient decrease for the merit function defined as the squared residual for the semismooth equation equivalent to the complementarity problem. We show that the algorithm is globally convergent under some mild assumptions. Next, by slightly modifying the direction-finding problem, we propose another Newton-type method, which may be considered a restricted version of the first algorithm. We show that this algorithm has a superlinear, or possibly quadratic, rate of convergence under suitable assumptions. Finally, some numerical results are presented. Supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. Supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

A projected semismooth Newton method for problems of calibrating least squares covariance matrix

In this paper we propose a projected semismooth Newton method to solve the problem of calibrating least squares covariance matrix with equality and inequality constraints. The method is globally and quadratically convergent with proper assumptions. The numerical results show that the proposed method is efficient and comparable with existing methods.     

Path-following proximal approach for solving Ill-posed convex semi-infinite programming problems

For a class of ill-posed, convex semi-infinite programming problems, a regularized path-following strategy is developed. This approach consists in a coordinated application of adaptive discretization and prox-regularization procedures combined with a penalty method. At each iteration, only an approximate minimum of a strongly convex differentiable function has to be calculated, and this can be done by any fast-convergent algorithm. The use of prox-regularization ensures the convergence of the iterates to some solution of the original problem. Due to regularization, an efficient deleting rule is applicable, which excludes an essential part of the constraints in the discretized problems.This research was supported by the German Research Society (DFG).The authors are grateful to the anonymous referees for their valuable comments.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

On generalized semi-infinite programming

This paper surveys some basic properties of the class of generalized semi-infinite programming problems (GSIP) where the infinite index set of inequality constraints depends on the state variables and all emerging functions are assumed to be continuously differentiable. There exists a wide range of applications which can be modelled as a (GSIP). The paper discusses extensions of the Mangasarian-Fromovitz, Kuhn-Tucker and Abadie constraint qualification to (GSIP) and presents related first order optimality conditions of Fritz-John and Karush-Kuhn-Tucker type. By using directional differentiability properties of the optimal value function of the lower level problem, first and second order necessary and sufficient optimality conditions are discussed. Several examples illustrate the results presented. The work of this author was supported by CONACYT (México) under grant 44003.     

ON KARUSH-KUHN-TUCKER POINTS FOR A SMOOTHING METHOD IN SEMI-INFINITE OPTIMIZATION

We study the smoothing method for the solution of generalized semi-infinite optimiza-tion problems from(O.Stein,G.Still:Solving semi-infinite optimization problems withinterior point techniques,SIAM J.Control Optim.,42(2003),pp.769-788).It is shownthat Karush-Kuhn-Tucker points of the smoothed problems do not necessarily converge toa Karush-Kuhn-Tucker point of the original problem,as could be expected from resultsin(F.Facchinei,H.Jiang,L.Qi:A smoothing method for mathematical programs withequilibrium constraints,Math.Program.,85(1999),pp.107-134).Instead, they mightmerely converge to a Fritz John point.We give,however,different additional assumptionswhich guarantee convergence to Karush-Kuhn-Tucker points.     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.     

An extension of the simplex algorithm for semi-infinite linear programming

We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in . A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ^p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.     

Directional differentiability of the optimal value function in convex semi-infinite programming

In this paper, directional differentiability properties of the optimal value function of a parameterized semi-infinite programming problem are studied. It is shown that if the unperturbed semi-infinite programming problem is convex, then the corresponding optimal value function is directionally differentiable under mild regularity assumptions. A max-min formula for the directional derivatives, well-known in the finite convex case, is given.     

On the classical logarithmic barrier function method for a class of smooth convex programming problems

In this paper, we describe a natural implementation of the classical logarithmic barrier function method for smooth convex programming. It is assumed that the objective and constraint functions fulfill the so-called relative Lipschitz condition, with Lipschitz constantM>0.In our method, we do line searches along the Newton direction with respect to the strictly convex logarithmic barrier function if we are far away from the central trajectory. If we are sufficiently close to this path, with respect to a certain metric, we reduce the barrier parameter. We prove that the number of iterations required by the algorithm to converge to an -optimal solution isO((1+M ²) log) orO((1+M ²)nlog), depending on the updating scheme for the lower bound.on leave from Eötvös University, Budapest, Hungary.     

A logarithmic barrier cutting plane method for convex programming

The paper presents a logarithmic barrier cutting plane algorithm for convex (possibly non-smooth, semi-infinite) programming. Most cutting plane methods, like that of Kelley, and Cheney and Goldstein, solve a linear approximation (localization) of the problem and then generate an additional cut to remove the linear program's optimal point. Other methods, like the central cutting plane methods of Elzinga-Moore and Goffin-Vial, calculate a center of the linear approximation and then adjust the level of the objective, or separate the current center from the feasible set. In contrast to these existing techniques, we develop a method which does not solve the linear relaxations to optimality, but rather stays in the interior of the feasible set. The iterates follow the central path of a linear relaxation, until the current iterate either leaves the feasible set or is too close to the boundary. When this occurs, a new cut is generated and the algorithm iterates. We use the tools developed by den Hertog, Roos and Terlaky to analyze the effect of adding and deleting constraints in long-step logarithmic barrier methods for linear programming. Finally, implementation issues and computational results are presented. The test problems come from the class of numerically difficult convex geometric and semi-infinite programming problems.This work was completed under the support of a research grant of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.     

广义拟牛顿算法对一般目标函数的收敛性

本文证明了求解无约束最优化的广义拟牛顿算法在Goldstein非精确线搜索下对一般目标函数的全局收敛性，并在一定条件下证明了算法的局部超线性收敛性。     

An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution

This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any bigM initialization assumption. The complexity of the algorithm is sensitive to and is dependent on the quality of the starting point, as assessed by suitable measures of the extent of infeasibility and the extent of nonoptimality of the starting point. Two new measures of the extent of infeasibility and of nonoptimality of a starting point are developed. We then present an algorithm for solving LP whose complexity depends explicitly and only on how close the starting point is to the set of LP feasible and optimal solutions (using these and other standard measures), and also onn (the number of inequalities). The complexity results using these measures of infeasibility and nonoptimality appear to be consistent with the observed practical sensitivity of interior-point algorithms to certain types of starting points. The starting point can be any pair of primal and dual vectors that may or may not be primal and/or dual feasible, and that satisfies a simple condition that typically arises in practice or is easy to coerce.Research supported in part by the MIT-NTU Collaboration Agreement.     

The Model for Two-dimensional Layout Optimization Problem with Performance Constraints and Its Optimality Function

This paper studies the two-dimensional layout optimization problem.An optimization model withperformance constraints is presented.The layout problem is partitioned into finite subproblems in terms ofgraph theory,in such a way of that each subproblem overcomes its on-off nature optimal variable.A minimaxproblem is constructed that is locally equivalent to each subproblem.By using this minimax problem,we presentthe optimality function for every subproblem and prove that the first order necessary optimality condition issatisfied at a point if and only if this point is a zero of optimality function.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

Conditions for the uniqueness of the optimal solution in linear semi-infinite programming

In this paper, we establish different conditions for the uniqueness of the optimal solution of a semi-infinite programming problem. The approach here is based on the differentiability properties of the optimal value function and yields the corresponding extensions to the general linear semi-infinite case of many results provided by Mangasarian and others. In addition, detailed optimality conditions for the most general problem are supplied, and some features of the optimal set mapping are discussed. Finally, we obtain a dimensional characterization of the optimal set, provided that a usual closedness condition (Farkas-Minkowski condition) holds.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.