Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization

This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved. A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.     

Maximum entropy method for solving operator equations of the first kind

The maximum entropy method for linear ill-posed problems with modeling error and noisy data is considered and the stability and convergence results are obtained. When the maximum entropy solution satisfies the “source condition”, suitable rates of convergence can be derived. Considering the practical applications, ana posteriori choice for the regularization parameter is presented. As a byproduct, a characterization of the maximum entropy regularized solution is given.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

Statistical learning control of uncertain systems: theory and algorithms

It has recently become clear that many control problems are too difficult to admit analytic solutions. New results have also emerged to show that the computational complexity of some “solved” control problems is prohibitive. Many of these control problems can be reduced to decidability problems or to optimization questions. Even though such questions may be too difficult to answer analytically, or may not be answered exactly given a reasonable amount of computational resources, researchers have shown that we can “approximately” answer these questions “most of the time”, and have “high confidence” in the correctness of the answers.     

关于q-Bernstein多项式的加速问题

In this paper,we investigate not only the acceleration problem of the q-Bernstein polynomials Bn(f,q;x)to B∞(f,q;x)but also the convergence of their iterated Boolean sum.Using the methods of exact estimate and theories of modulus of smoothness,we get the respective estimates of the convergence rate,which suggest that q-Bernstein polynomials have the similar answer with the classical Bernstein polynomials to these two problems.     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

Cache Oblivious Algorithms for the RMQ and the RMSQ Problems

In the Range Minimum/Maximum Query (RMQ) and Range Maximum-Sum Segment Query (RMSQ) problems, we are given an array which we can preprocess in order to answer subsequent queries. In the RMQ query, we are given a range on the array and we need to find the maximum/minimum element within that range. On the other hand, in RMSQ query, we need to return the segment within the given query range that gives the maximum sum. In this paper, we present cache oblivious optimal algorithms for both of the above problems. In particular, for both the problems, we have presented linear time data structures having optimal cache miss. The data structures can answer the corresponding queries in constant time with constant cache miss.     

差商变尺度法的超线性收敛性

在文[1]的基础上,本文继续研究差商变尺度法的收敛性质,从文[1]的整体收敛性出发,进一步探讨了差商变尺度法的超线性收敛的特征,同时给出了保证超线性收敛的差商步长条件。     

Henstock-Kurzweil可积函数空间的紧性特征

本文研究Henstock-Kurzweil可积(HK可积)函数空间中的一个经典问题.文章通过研究分布Henstock-Kurzweil积分(DHK积分)的性质,给出了该问题的否定答案.进一步,利用收敛性获得了函数HK可积的一个充分必要条件.最后,在上述结论的基础上刻画了HK可积函数空间的紧性.所得结果丰富和推广了HK可...     

Fifth-grade students�� approaches to and beliefs of mathematics word problem solving: a large sample Hungarian study

Mathematical word problems used in Verschaffel et al.??s (Learning and Instruction 7:339?C359, 1994) study were applied in several follow-up studies. The goal of the present study was to replicate and extend the results of this line of research in a large sample of Hungarian students using an alternative set of data-gathering and data-analysis techniques. 4,037 students forming a nationwide representative sample of the Hungarian fifth-grade student population (aged 10?C11) completed the test. The test contained five word problems from the list of 10 P(??problematic)-items from Verschaffel et al.??s test. In contrast to all previous research in this domain, we used a multiple-choice format, where three options were given for each task: (a) routine-based, non-realistic answer, (b) numerical response that does take into account realistic considerations, (c) a realistic solution stating that the task cannot be solved. The hypotheses of this study were: (1) Students?? responses will confirm previous results, i.e. upper elementary school students prefer to respond to P-items by means of the routine-based answer; (2) Most students will demonstrate a more or less consistent preference for a given answer type (a, b or c) over problems; (3) Students?? school math marks will have low correlation indices with students?? achievement on these word problems. Our results confirm student??s overall tendency to follow non-realistic approaches when doing school word problem solving. The tendency even holds when confronting students with various kinds of realistic answers. Our results show that students demonstrate response patterns over problems, and that the correlation with math school performance is significant but small.     

Rates of convergence for adaptive Newton methods

We consider Newton-type methods for constrained optimization problems in infinite-dimensional spaces, where at each iteration the first and second derivatives and the feasible set are approximated. The approximations can change at each iteration and conditions are given under which linear and superlinear rates of convergence of the iterates to the optimal point hold. Several applications are discussed.     

Behind the scenes of pseudo-proportionality

In this study, we attempt to put in question students’ spontaneous and uncritical application of the simple and neat mathematical formula of linearity. This is impelled with the help of a written test involving geometrical problems, which is based on an original experimental setting. In this setting, grade 9 and 10 students were instructed first to solve all the geometrical problems and then to select only one problem as the appropriate for a given numerical answer. The difficulty of this choice lied in fact that a superficial handling of each problem would resolve to the same numerical answer as the one given. The results show that students’ choices are systematic and based on the solutions given to the tasks. However, the experimental setting has managed to help students question in some degree the applicability of the linear model in situations that appear to be linear but are not.     

Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

A globally convergent Newton method for solving strongly monotone variational inequalities

Variational inequality problems have been used to formulate and study equilibrium problems, which arise in many fields including economics, operations research and regional sciences. For solving variational inequality problems, various iterative methods such as projection methods and the nonlinear Jacobi method have been developed. These methods are convergent to a solution under certain conditions, but their rates of convergence are typically linear. In this paper we propose to modify the Newton method for variational inequality problems by using a certain differentiable merit function to determine a suitable step length. The purpose of introducing this merit function is to provide some measure of the discrepancy between the solution and the current iterate. It is then shown that, under the strong monotonicity assumption, the method is globally convergent and, under some additional assumptions, the rate of convergence is quadratic. Limited computational experience indicates the high efficiency of the proposed method.     

一个求解P0函数非线性互补问题的非内部连续化算法

基于黄正海等2001年提出的光滑函数,本文给出一个求解P0函数非线性互补问题的非内部连续化算法.所给算法拥有一些好的特性.在较弱的条件下,证明了所给算法或者是全局线性收敛,或者是全局和局部超线性收敛.给出了所给算法求解两个标准测试问题的数值试验结果.     

关于不等式约束的信赖域算法

对于具有不等式约束的非线性优化问题，本文给出一个依赖域算法，由于算法中依赖区域约束采用向量的∞范数约束的形式，从而使子问题变二次规划，同时使算法变得更实用。在通常假设条件下，证明了算法的整体收敛性和超线性收敛性。     

Globally convergent algorithm for solving nonlinear equations

A general iterative method is proposed for finding the maximal rootx _max of a one-variable equation in a given interval. The method generates a monotone-decreasing sequence of points converging tox _max or demonstrates the nonexistence of a real root. It is globally convergent. A concrete realization of the general algorithm is also given and is shown to be locally quadratically convergent. Computational experience obtained for eight test problems indicates that the new method is comparable to known methods claiming global convergence.     

Penalized Likelihood-type Estimators for Generalized Nonparametric Regression

We consider the asymptotic analysis of penalized likelihood type estimators for generalized nonparametric regression problems in which the target parameter is a vector-valued function defined in terms of the conditional distribution of a response given a set of covariates. A variety of examples including ones related to generalized linear models and robust smoothing are covered by the theory. Linear approximations to the estimator are constructed using Taylor expansions in Hilbert spaces. An application which is treated is upper bounds on rates of convergence for the penalized likelihood-type estimators.     

Sequences generating permutations

Linear recurring sequences generating permutations of the elements of a finite ring are introduced and examined. A complete answer to the discussed problems is given for the second-order sequences over Z_M. The possibilities for applications are also discussed.