A stochastic algorithm using one sample point per iteration and diminishing stepsizes

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iteratex _i , one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1 if the sequence of iteratesx ₁,x ₂,...generated by the algorithm is bounded, then all of its accumulation points are stationary.     

Readily implementable conjugate gradient methods

Conjugate gradient methods have been extensively used to locate unconstrained minimum points of real-valued functions. At present, there are several readily implementable conjugate gradient algorithms that do not require exact line search and yet are shown to be superlinearly convergent. However, these existing algorithms usually require several trials to find an acceptable stepsize at each iteration, and their inexact line search can be very timeconsuming.In this paper we present new readily implementable conjugate gradient algorithms that will eventually require only one trial stepsize to find an acceptable stepsize at each iteration.Making usual continuity assumptions on the function being minimized, we have established the following properties of the proposed algorithms. Without any convexity assumptions on the function being minimized, the algorithms are globally convergent in the sense that every accumulation point of the generated sequences is a stationary point. Furthermore, when the generated sequences converge to local minimum points satisfying second-order sufficient conditions for optimality, the algorithms eventually demand only one trial stepsize at each iteration, and their rate of convergence isn-step superlinear andn-step quadratic.This research was supported in part by the National Science Foundation under Grant No. ENG 76-09913.     

Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

Global Convergence Analysis of Line Search Interior-Point Methods for Nonlinear Programming without Regularity Assumptions

As noted by Wächter and Biegler (Ref. 1), a number of interior-point methods for nonlinear programming based on line-search strategy may generate a sequence converging to an infeasible point. We show that, by adopting a suitable merit function, a modified primal-dual equation, and a proper line-search procedure, a class of interior-point methods of line-search type will generate a sequence such that either all the limit points of the sequence are KKT points, or one of the limit points is a Fritz John point, or one of the limit points is an infeasible point that is a stationary point minimizing a function measuring the extent of violation to the constraint system. The analysis does not depend on the regularity assumptions on the problem. Instead, it uses a set of satisfiable conditions on the algorithm implementation to derive the desired convergence property.Communicated by Z. Q. LuoThis research was partially supported by Grant R-314-000-026/042/057-112 of National University of Singapore and Singapore-MIT Alliance. We thank Professor Khoo Boo Cheong, Cochair of the High Performance Computation Program of Singapore-MIT Alliance, for his support     

An inexact restoration strategy for the globalization of the sSQP method

A globally convergent algorithm based on the stabilized sequential quadratic programming (sSQP) method is presented in order to solve optimization problems with equality constraints and bounds. This formulation has attractive features in the sense that constraint qualifications are not needed at all. In contrast with classic globalization strategies for Newton-like methods, we do not make use of merit functions. Our scheme is based on performing corrections on the solutions of the subproblems by using an inexact restoration procedure. The presented method is well defined and any accumulation point of the generated primal sequence is either a Karush-Kuhn-Tucker point or a stationary (maybe feasible) point of the problem of minimizing the infeasibility. Also, under suitable hypotheses, the sequence generated by the algorithm converges Q-linearly. Numerical experiments are given to confirm theoretical results.     

Gap Function Approach to the Generalized Nash Equilibrium Problem

We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable, but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach.     

一个关于二次规划问题的分段线性同伦算法

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。     

带有标准发生率和信息干预的随机时滞SIRS传染病模型的动力学行为

考虑了一类具有标准发生率和信息干预的随机时滞SIRS传染病模型.定义了一个停时,通过构造适当的Lyapunov函数证明了停时为无穷大,从而证明了该模型正解的全局存在性和唯一性.通过构造适当的 Lyapunov函数,研究了该模型的解在确定性模型无病平衡点和地方病平衡点附近的渐近行为,得到了在一定条件下随机系统的解分别围绕两个平衡点做随机振动.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

Analysis of direct searches for discontinuous functions

It is known that the Clarke generalized directional derivative is nonnegative along the limit directions generated by directional direct-search methods at a limit point of certain subsequences of unsuccessful iterates, if the function being minimized is Lipschitz continuous near the limit point. In this paper we generalize this result for discontinuous functions using Rockafellar generalized directional derivatives (upper subderivatives). We show that Rockafellar derivatives are also nonnegative along the limit directions of those subsequences of unsuccessful iterates when the function values converge to the function value at the limit point. This result is obtained assuming that the function is directionally Lipschitz with respect to the limit direction. It is also possible under appropriate conditions to establish more insightful results by showing that the sequence of points generated by these methods eventually approaches the limit point along the locally best branch or step function (when the number of steps is equal to two). The results of this paper are presented for constrained optimization and illustrated numerically.     

Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints

Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10     

A Differential Free Point Generation Scheme in the Differential Evolution Algorithm

In this paper we derive the probability distribution of trial points in the differential evolution (de) algorithm, in particular the probability distribution of points generated by mutation. We propose a point generation scheme that uses an approximation to this distribution. The scheme can dispense with the differential vector used in the mutation of de. We propose a de algorithm that replaces the differential based mutation scheme with a probability distribution based point generation scheme. We also propose a de algorithm that uses a probabilistic combination of the point generation by the probability distribution and the point generation by mutation. A numerical study is carried out using a set of 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the new algorithms are superior to the original version both in terms of the number of function evaluations and cpu times.     

具有标准发生率的随机SIR传染病模型的建立及平稳分布与疾病灭绝研究

研究了一类具有标准发生率以及考虑随机扰动与系统变量成正比的随机SIR传染病模型.首先,对于任意的正的初值,系统存在唯一的全局正解以及通过构造合适的随机李雅普诺夫函数,得到了模型遍历平稳分布存在的充分条件.其次,给出了疾病灭绝的充分条件,并与模型遍历平稳分布存在的充分条件作对比,得出了在特定条件下随机SIR模型的阈值.最后通过数值模拟验证了结果的正确性.     

Stochastic approximation algorithm for minimax problems

A stochastic approximation algorithm for minimax optimization problems is analyzed. At each iterate, it performs one random experiment, based on which it computes a direction vector. It is shown that, under suitable conditions, it a.s. converges to the set of points satisfying necessary optimality conditions. The algorithm and its analysis bring together ideas from stochastic approximation and nondifferentiable optimization.     

A stochastic algorithm for optimization problems with continua of inequalities

Optimization algorithms for solving mathematical programming problems involving continua of inequalities are presented. The algorithms use an outer-approximation method, by which they attempt to approximate, at each point, the maxima of sets of inequality constraints. They do so by performing random experiments, resulting in a finite number of points, over which the maximum is taken. They use constraint-dropping schemes, by which they eliminate points from the constraint set at hand, which are felt to be irrelevant. At each point that the algorithms construct, they evaluate a measure of optimality, which indicates the distance of the point from the set of solutions of the optimization problem. They use this measure to determine the number of random experiments performed. Thus, the number of such experiments tends to be small initially, when the points at hand are far from optimal, and they tend to increase when an optimal point is approached.     

Conjugate gradient versus steepest descent

It is known that the conjugate-gradient algorithm is at least as good as the steepest-descent algorithm for minimizing quadratic functions. It is shown here that the conjugate-gradient algorithm is actually superior to the steepest-descent algorithm in that, in the generic case, at each iteration it yields a lower cost than does the steepest-descent algorithm, when both start at the same point.Thanks are due to Professor R. W. Sargent, Imperial College, London, England, for suggestions concerning presentation.     

Mann-Type Steepest-Descent and Modified Hybrid Steepest-Descent Methods for Variational Inequalities in Banach Spaces

In this paper, we propose three different kinds of iteration schemes to compute the approximate solutions of variational inequalities in the setting of Banach spaces. First, we suggest Mann-type steepest-descent iterative algorithm, which is based on two well-known methods: Mann iterative method and steepest-descent method. Second, we introduce modified hybrid steepest-descent iterative algorithm. Third, we propose modified hybrid steepest-descent iterative algorithm by using the resolvent operator. For the first two cases, we prove the convergence of sequences generated by the proposed algorithms to a solution of a variational inequality in the setting of Banach spaces. For the third case, we prove the convergence of the iterative sequence generated by the proposed algorithm to a zero of an operator, which is also a solution of a variational inequality.     

A Proximal Point-Type Method for Multicriteria Optimization

In this paper, we present a proximal point algorithm for multicriteria optimization, by assuming an iterative process which uses a variable scalarization function. With respect to the convergence analysis, firstly we show that, for any sequence generated from our algorithm, each accumulation point is a Pareto critical point for the multiobjective function. A more significant novelty here is that our paper gets full convergence for quasi-convex functions. In the convex or pseudo-convex cases, we prove convergence to a weak Pareto optimal point. Another contribution is to consider a variant of our algorithm, obtaining the iterative step through an unconstrained subproblem. Then, we show that any sequence generated by this new algorithm attains a Pareto optimal point after a finite number of iterations under the assumption that the weak Pareto optimal set is weak sharp for the multiobjective problem.     

Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

Simulated annealing for discrete optimization with estimation

We extend the basic convergence results for the Simulated Annealing (SA) algorithm to a stochastic optimization problem where the objective function is stochastic and can be evaluated only through Monte Carlo simulation (hence, disturbed with random error). This extension is important when either the objective function cannot be evaluated exactly or such an evaluation is computationally expensive. We present a modified SA algorithm and show that under suitable conditions on the random error, the modified SA algorithm converges in probability to a global optimizer. Computational results and comparisons with other approaches are given to demonstrate the performance of the proposed modified SA algorithm.