Convergence properties of trust-region methods for unconstrained nonconvex optimization is considered in the case where information on the objective function's local curvature is incomplete, in the sense that it may be restricted to a fixed set of "test directions" and may not be available at every iteration. It is shown that convergence to local "weak" minimizers can still be obtained under some additional but algorithmically realistic conditions. These theoretical results are then applied to recursive multigrid trust-region methods, which suggests a new class of algorithms with guaranteed second-order convergence properties.  

The monotone variational inequalities VI$(\Omega,F)$ have vast applications, including optimal controls and convex programming. In this paper we focus on the VI problems that have a particular splitting structure and in which the mapping $F$ does not have an explicit form, therefore only its function values can be employed in the numerical methods for solving such problems. We study a set of numerical methods that are easily implementable. Each iteration of the proposed methods consists of two procedures. The first (prediction) procedure utilizes alternating projections to produce a predictor. The second (correction) procedure generates the new iterate via some minor computations. Convergence of the proposed methods is proved under mild conditions. Preliminary numerical experiments for some traffic equilibrium problems illustrate the effectiveness of the proposed methods.

A mapping $f:Z^n\rightarrow R^n$ is said to possess the direction preserving property if $f_i(x)\gt 0$ implies $f_i(y)\geq 0$ for any integer points $x$ and $y$ with $\|x-y\|_{\infty}\leq 1$. In this paper, a simplicial algorithm is developed for computing an integer zero point of a mapping with the direction preserving property. We assume that there is an integer point $x^0$ with $c\leq x^0\leq d$ satisfying that $\max_{1\leq i\leq n}(x_i-x^0_i)f_i(x)\ge0$ for any integer point $x$ with $f(x)\neq 0$ on the boundary of $H=\{x\in R^n\;|\;c-e\leq x\leq d+e\}$, where $c$ and $d$ are two finite integer points with $c\leq d$ and $e=(1,1,\cdots,1)^{\top}\in R^n$. This assumption is implied by one of two conditions for the existence of an integer zero point of a mapping with the preserving property in van der Laan et al. (2004). Under this assumption, starting at $x^0$, the algorithm follows a finite simplicial path and terminates at an integer zero point of the mapping. This result has applications in general economic equilibrium models with indivisible commodities.

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

In this paper, we propose a Sample Average Approximation (SAA) method for a class of Stochastic Mathematical Programs with Complementarity Constraints (SMPCC) recently considered by Birbil, Gürkan and Listes [3]. We study the statistical properties of obtained SAA estimators. In particular we show that under moderate conditions a sequence of weak stationary points of SAA programs converge to a weak stationary point of the true problem with probability approaching one at exponential rate as the sample size tends to infinity. To implement the SAA method more efficiently, we incorporate the method with some techniques such as Scholtes' regularization method and the well known smoothing NCP method. Some preliminary numerical results are reported.

An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing $n$ discrete constraints in the original problem with one single continuous constraint. A feasible direction method is designed to solve the resulting nonlinear programming problem. The method employs only the gradient evaluations of the objective function, and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method, and is suitable for the solution of large size max-cut problems. The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed. If the solution obtained by the proposed method is a global solution of the nonlinear programming problem, the solution will provide an upper bound on the max-cut value. Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value. Numerical experiments and comparisons on some max-cut test problems (small and large size) show that the proposed algorithm is efficient to get the exact solutions for all small test problems and well satisfied solutions for most of the large size test problems with less calculation costs.

In this paper, an algorithm for unconstrained optimization that employs both trust region techniques and curvilinear searches is proposed. At every iteration, we solve the trust region subproblem whose radius is generated adaptively only once. Nonmonotonic backtracking curvilinear searches are performed when the solution of the subproblem is unacceptable. The global convergence and fast local convergence rate of the proposed algorithms are established under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithms.

Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. Nonconvex Optimization and Its Applications, Springer-Verlag, (2006) 83, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.