A monotone semismooth Newton type method for a class of complementarity problems

In this paper, we propose a modified semismooth Newton method for a class of complementarity problems arising from the discretization of free boundary problems and establish its monotone convergence. We show that under appropriate conditions, the method reduces to semismooth Newton method. We also do some preliminary numerical experiments to show the efficiency of the proposed method.     

Randomized rounding: A technique for provably good algorithms and algorithmic proofs

We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance. This work was supported by Semiconductor Research Corporation grant SRC 82-11-008 and an IBM Doctoral Fellowship.     

Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported.     

A parametric approach for solving a class of generalized quadratic-transformable rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm is based on the so-called “optimal level solutions” method. Various global optimality conditions are discussed and implemented in order to improve the efficiency of the algorithm.     

Sufficient conditions for pseudo-Lipschitz property in convex semi-infinite vector optimization problems

This paper is devoted to the study of the pseudo-Lipschitz property of the efficient (Pareto) solution map for the perturbed convex semi-infinite vector optimization problem (CSVO). We establish sufficient conditions for the pseudo-Lipschitz property of the efficient solution map of (CSVO) under continuous perturbations of the right-hand side of the constraints and functional perturbations of the objective function. Examples are given to illustrate the obtained results.     

Error bound results for generalized D-gap functions of nonsmooth variational inequality problems

Solving a variational inequality problem can be equivalently reformulated into solving a unconstraint optimization problem where the corresponding objective function is called a merit function. An important class of merit function is the generalized D-gap function introduced in [N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92 (1997) 439-456] and Yamashita and Fukushima (1997) [17]. In this paper, we present new fractional local/global error bound results for the generalized D-gap functions of nonsmooth variational inequality problems, which gives an effective estimate on the distance between a specific point to the solution set, in terms of the corresponding function value of the generalized D-gap function. Numerical examples and a simple application to the free boundary problem are also presented to illustrate the significance of our error bound results.     

Strong pseudo-convex mappings in dual problems

In this paper some relations between strong pseudo-convexity and other generalized convexity-properties of mappings (convex-likeness, quasi -convexity) into Banach-spaces are described. Furthermore necessary and sufficient conditions for the strong pseudo-convexity of a mapping are presented. Especially, sufficient conditions for the strong pseudo-convexity of composite mappings are proved. Applying these results a correct ion of a direct duality theorem given by Chandra and Lata is formulated.     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

Two-stage stochastic hierarchical multiple risk problems: models and algorithms

In this paper, we consider a class of two-stage stochastic risk management problems, which may be stated as follows. A decision-maker determines a set of binary first-stage decisions, after which a random event from a finite set of possible outcomes is realized. Depending on the realization of this outcome, a set of continuous second-stage decisions must then be made that attempt to minimize some risk function. We consider a hierarchy of multiple risk levels along with associated penalties for each possible scenario. The overall objective function thus depends on the cost of the first-stage decisions, plus the expected second-stage risk penalties. We develop a mixed-integer 0–1 programming model and adopt an automatic convexification procedure using the reformulation–linearization technique to recast the problem into a form that is amenable to applying Benders’ partitioning approach. As a principal computational expedient, we show how the reformulated higher-dimensional Benders’ subproblems can be efficiently solved via certain reduced-sized linear programs in the original variable space. In addition, we explore several key ingredients in our proposed procedure to enhance the tightness of the prescribed Benders’ cuts and the efficiency with which they are generated. Finally, we demonstrate the computational efficacy of our approaches on a set of realistic test problems. Dr. H. D. Sherali acknowledges the support of the National Science Foundation under Grant No. DMI-0552676. Dr. J. C. Smith acknowledges the support of the Air Force Office of Scientific Research under Grant No. AFOSR/MURI F49620-03-1-0477.     

An improved Goldstein's type method for a class of variant variational inequalities

This paper aims at presenting an improved Goldstein's type method for a class of variant variational inequalities. In particular, the iterate computed by an existing Goldstein's type method [He, A Goldstein's type projection method for a class of variant variational inequalities J. Comput. Math. 17(4) (1999) 425–434]. is used to construct a descent direction, and thus the new method generates the new iterate by searching the optimal step size along the descent direction. Some restrictions on the involving functions of the existing Goldstein's type methods are relaxed, while the global convergence of the new method is proved without additional assumptions. The computational superiority of the new method is verified by the comparison to some existing methods.     

Stability of solutions for a class of nonlinear cone constrained optimization problems,part 1: Basic theory

We Gonsider a class of nonlinear cone constrained optimization problems depending on a parameter. Under the assumption of a constraint qualification, a second order sufficient optimality condition and a stability condition for the Lagrange multipliers it is shown, that for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions obey a type of Lipschitz condition.     

Farkas-type results for fractional programming problems

Considering a constrained fractional programming problem, within the present paper we present some necessary and sufficient conditions, which ensure that the optimal objective value of the considered problem is greater than or equal to a given real constant. The desired results are obtained using the Fenchel–Lagrange duality approach applied to an optimization problem with convex or difference of convex (DC) objective functions and finitely many convex constraints. These are obtained from the initial fractional programming problem using an idea due to Dinkelbach. We also show that our general results encompass as special cases some recently obtained Farkas-type results.     

A branch and bound algorithm for globally solving a class of nonconvex programming problems

A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.     

Higher-order Mond–Weir duality for set-valued optimization

In this paper, we introduce a higher-order Mond–Weir dual for a set-valued optimization problem by virtue of higher-order contingent derivatives and discuss their weak duality, strong duality and converse duality properties.     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

On the accurate identification of active set for constrained minimax problems

In this paper, the problem of identifying the active constraints for constrained nonlinear programming and minimax problems at an isolated local solution is discussed. The correct identification of active constraints can improve the local convergence behavior of algorithms and considerably simplify algorithms for inequality constrained problems, so it is a useful adjunct to nonlinear optimization algorithms. Facchinei et al. [F. Facchinei, A. Fischer, C. Kanzow, On the accurate identification of active constraints, SIAM J. Optim. 9 (1998) 14-32] introduced an effective technique which can identify the active set in a neighborhood of a solution for nonlinear programming. In this paper, we first improve this conclusion to be more suitable for infeasible algorithms such as the strongly sub-feasible direction method and the penalty function method. Then, we present the identification technique of active constraints for constrained minimax problems without strict complementarity and linear independence. Some numerical results illustrating the identification technique are reported.     

Numerical method for a class of optimal control problems subject to nonsmooth functional constraints

In this paper, we consider a class of optimal control problems which is governed by nonsmooth functional inequality constraints involving convolution. First, we transform it into an equivalent optimal control problem with smooth functional inequality constraints at the expense of doubling the dimension of the control variables. Then, using the Chebyshev polynomial approximation of the control variables, we obtain an semi-infinite quadratic programming problem. At last, we use the dual parametrization technique to solve the problem.     

On regularity and stability in semi-infinite optimization

For stationary solutions and Langrange multipliers of a semi-infinite program withC ¹ data, we study some stability behaviour which is closely related to (metric) regularity of the constraint system. The multiplier set mapping considered here has its images in a finite-dimensional space. In this framework, regularity is a necessary and sufficient condition to have bounded sets of multipliers.     

Well-posed equilibrium problems

In this paper we introduce some notions of well-posedness for scalar equilibrium problems in complete metric spaces or in Banach spaces. As equilibrium problem is a common extension of optimization, saddle point and variational inequality problems, our definitions originates from the well-posedness concepts already introduced for these problems.We give sufficient conditions for two different kinds of well-posedness and show by means of counterexamples that these have no relationship in the general case. However, together with some additional assumptions, we show via Ekeland’s principle for bifunctions a link between them.Finally we discuss a parametric form of the equilibrium problem and introduce a well-posedness concept for it, which unifies the two different notions of well-posedness introduced in the first part.