An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

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.     

A Logarithmic-Quadratic Proximal Prediction-Correction Method for Structured Monotone Variational Inequalities

Inspired by the Logarithmic-Quadratic Proximal (LQP) method for variational inequalities, we present a prediction-correction method for structured monotone variational inequalities. Each iteration of the new method consists of a prediction and a correction. Both the predictor and the corrector are obtained easily with tiny computational load. In particular, the LQP system that appears in the prediction is approximately solved under significantly relaxed inexactness restriction. Global convergence of the new method is proved under mild assumptions. In addition, we present a self-adaptive version of the new method that leads to easier implementations. Preliminary numerical experiments for traffic equilibrium problems indicate that the new method is effectively applicable in practice. Presented at the 6th International conference on Optimization: Techniques and Applications, Ballarat Australia, December 9–11, 2004. This author was supported by NSFC Grant 10571083, the MOEC grant 20020284027 and Jiangsu NSF grant BK2002075     

A generalized Newton method for absolute value equations associated with second order cones

In this paper, we introduce the absolute value equations associated with second order cones (SOCAVE in short), which is a generalization of the absolute value equations discussed recently in the literature. It is proved that the SOCAVE is equivalent to a class of second order cone linear complementarity problems (SOCLCP in short). In particular, we propose a generalized Newton method for solving the SOCAVE and show that the proposed method is globally linearly and locally quadratically convergent under suitable assumptions. We also report some preliminary numerical results of the proposed method for solving the SOCAVE and the SOCLCP, which show the efficiency of the proposed method.     

A self-adaptive trust region method with line search based on a simple subproblem model

In this paper, based on a simple model of the trust region subproblem, we propose a new self-adaptive trust region method with a line search technique for solving unconstrained optimization problems. By use of the simple subproblem model, the new method needs less memory capacitance and computational complexity. And the trust region radius is adjusted with a new self-adaptive adjustment strategy which makes full use of the information at the current point. When the trial step results in an increase in the objective function, the method does not resolve the subproblem, but it performs a line search technique from the failed point. Convergence properties of the method are proved under certain conditions. Numerical experiments show that the new method is effective and attractive for large-scale optimization problems.     

A simple feasible SQP method for inequality constrained optimization with global and superlinear convergence

In this paper, a simple feasible SQP method for nonlinear inequality constrained optimization is presented. At each iteration, we need to solve one QP subproblem only. After solving a system of linear equations, a new feasible descent direction is designed. The Maratos effect is avoided by using a high-order corrected direction. Under some suitable conditions the global and superlinear convergence can be induced. In the end, numerical experiments show that the method in this paper is effective.     

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.     

Distribution sensitivity in stochastic programming

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.This research was presented in parts at the 4th International Conference on Stochastic Programming held in Prague in September 1986.     

A filled function method applied to nonsmooth constrained global optimization

The filled function method is an effective approach to find a global minimizer. In this paper, based on a new definition of the filled function for nonsmooth constrained programming problems, a one-parameter filled function is constructed to improve the efficiency of numerical computation. Then a corresponding algorithm is presented. It is a global optimization method which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Illustrative examples are provided to demonstrate the efficiency and reliability of the proposed filled function method.     

A filled function method for global optimization

A novel filled function with one parameter is suggested in this paper for finding a global minimizer for a general class of nonlinear programming problems with a closed bounded box. A new algorithm is presented according to the theoretical analysis. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

AUGMENTED LAGRANGEAN RELAXATIONS IN GENERAL MIXED INTEGER PROGRAMMING

Abstract

A new relaxation is presented for the general mixed integer programing problem. It is proved that this relaxation is always at least as good, end in one demonstrated case better, than some other known relaxations. Various aspects of the implementation of the relaxation in a branch-and-bound algorithm are discussed. Numerical examples are given to demonstrate the feasibility of the approach.     

Projection algorithms for solving a system of general variational inequalities

In this paper, we introduce and consider a new system of general variational inequalities involving four different operators. Using the projection operator technique, we suggest and analyze some new explicit iterative methods for this system of variational inequalities. We also study the convergence analysis of the new iterative method under certain mild conditions. Since this new system includes the system of variational inequalities involving three operators, variational inequalities and related optimization problems as special cases, results obtained in this paper continue to hold for these problems. Our results can be viewed as a refinement and improvement of the previously known results for variational inequalities.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

Characterization of vector strict global minimizers of order 2 in differentiable vector optimization problems under a new approximation method

In this paper, a new approximation method is introduced to characterize a so-called vector strict global minimizer of order 2 for a class of nonlinear differentiable multiobjective programming problems with (F,ρ)-convex functions of order 2. In this method, an equivalent vector optimization problem is constructed by a modification of both the objectives and the constraint functions in the original multiobjective programming problem at the given feasible point. In order to prove the equivalence between the original multiobjective programming problem and its associated F-approximated vector optimization problem, the suitable (F,ρ)-convexity of order 2 assumption is imposed on the functions constituting the considered vector optimization problem.     

A new Lagrangian net algorithm for solving max-bisection problems

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions.     

Accelerating method of global optimization for signomial geometric programming

Signomial geometric programming (SGP) has been an interesting problem for many authors recently. Many methods have been provided for finding locally optimal solutions of SGP, but little progress has been made for global optimization of SGP. In this paper we propose a new accelerating method for global optimization algorithm of SGP using a suitable deleting technique. This technique offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of SGP does not exist, and can be seen as an accelerating device for global optimization algorithm of SGP problem. Compared with the method of Shen and Zhang [Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput. 150 (2004) 99–114], numerical results show that the computational efficiency is improved obviously by using this new technique in the number of iterations, the required saving list length and the execution time of the algorithm.     

Optimality conditions and duality for nondifferentiable multiobjective programming problems involving d-r-type I functions

In this paper, new classes of nondifferentiable functions constituting multiobjective programming problems are introduced. Namely, the classes of d$d$-r$r$-type I objective and constraint functions and, moreover, the various classes of generalized d$d$-r$r$-type I objective and constraint functions are defined for directionally differentiable multiobjective programming problems. Sufficient optimality conditions and various Mond–Weir duality results are proved for nondifferentiable multiobjective programming problems involving functions of such type. Finally, it is showed that the introduced d$d$-r$r$-type I notion with r≠0$r\ne 0$ is not a sufficient condition for Wolfe weak duality to hold. These results are illustrated in the paper by suitable examples.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

Filled function method for nonlinear equations

Systems of nonlinear equations are ubiquitous in engineering, physics and mechanics, and have myriad applications. Generally, they are very difficult to solve. In this paper, we will present a filled function method to solve nonlinear systems. We will first convert the nonlinear systems into equivalent global optimization problems with the property: x^∗ is a global minimizer if and only if its function value is zero. A filled function method is proposed to solve the converted global optimization problem. Numerical examples are presented to illustrate our new techniques.     

Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds

Local convergence analysis of the proximal point method for a special class of nonconvex functions on Hadamard manifold is presented in this paper. The well definedness of the sequence generated by the proximal point method is guaranteed. Moreover, it is proved that each cluster point of this sequence satisfies the necessary optimality conditions and, under additional assumptions, its convergence for a minimizer is obtained.