On estimation of the optimal parameter of the modulus-based matrix splitting algorithm for linear complementarity problems on second-order cones

There are many studies on the well-known modulus-based matrix splitting (MMS) algorithm for solving complementarity problems, but very few studies on its optimal parameter, which is of theoretical and practical importance. Therefore and here, by introducing a novel mapping to explicitly cast the implicit fixed point equation and thus obtain the iteration matrix involved, we first present the estimation approach of the optimal parameter of each step of the MMS algorithm for solving linear complementarity problems on the direct product of second-order cones (SOCLCPs). It also works on single second-order cone and the non-negative orthant. On this basis, we further propose an iteration-independent optimal parameter selection strategy for practical usage. Finally, the practicability and effectiveness of the new proposal are verified by comparing with the experimental optimal parameter and the diagonal part of system matrix. In addition, with the optimal parameter, the effectiveness of the MMS algorithm can indeed be greatly improved, even better than the state-of-the-art solvers SCS and SuperSCS that solve the equivalent SOC programming.     

Fast First-Order Methods for Composite Convex Optimization with Backtracking

We propose new versions of accelerated first-order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular, we show that a full backtracking strategy can be used within the FISTA and FALM algorithms while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon })$ . In the original versions of FISTA and FALM the prox parameter value on each iteration must be bounded from above by its value on prior iterations. The complexity of the algorithm then depends on the smallest value of the prox parameter encountered by the algorithm. The theoretical implications of using full backtracking in the framework of accelerated first-order and alternating linearization methods allow for better complexity estimates that depend on the “average” prox parameter value. Moreover, we show that in the case of compressed sensing problem and Lasso, the additional cost of the new backtracking strategy is negligible compared to the cost of the original FISTA iteration. Our computational results show the benefit of the new algorithm.     

A Neural Network-Based Policy Iteration Algorithm with Global $$H^2$$ -Superlinear Convergence for Stochastic Games on Domains

In this work, we propose a class of numerical schemes for solving semilinear Hamilton–Jacobi–Bellman–Isaacs (HJBI) boundary value problems which arise naturally from exit time problems of diffusion processes with controlled drift. We exploit policy iteration to reduce the semilinear problem into a sequence of linear Dirichlet problems, which are subsequently approximated by a multilayer feedforward neural network ansatz. We establish that the numerical solutions converge globally in the \(H^2\)-norm and further demonstrate that this convergence is superlinear, by interpreting the algorithm as an inexact Newton iteration for the HJBI equation. Moreover, we construct the optimal feedback controls from the numerical value functions and deduce convergence. The numerical schemes and convergence results are then extended to oblique derivative boundary conditions. Numerical experiments on the stochastic Zermelo navigation problem are presented to illustrate the theoretical results and to demonstrate the effectiveness of the method.

     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

Models and algorithms for skip-free Markov decision processes on trees

We introduce a class of models for multidimensional control problems that we call skip-free Markov decision processes on trees. We describe and analyse an algorithm applicable to Markov decision processes of this type that are skip-free in the negative direction. Starting with the finite average cost case, we show that the algorithm combines the advantages of both value iteration and policy iteration—it is guaranteed to converge to an optimal policy and optimal value function after a finite number of iterations but the computational effort required for each iteration step is comparable with that for value iteration. We show that the algorithm can also be used to solve discounted cost models and continuous-time models, and that a suitably modified algorithm can be used to solve communicating models.     

Adaptive smoothing algorithms for nonsmooth composite convex minimization

We propose an adaptive smoothing algorithm based on Nesterov’s smoothing technique in Nesterov (Math Prog 103(1):127–152, 2005) for solving “fully” nonsmooth composite convex optimization problems. Our method combines both Nesterov’s accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriate choice of smoothing functions, we develop a new algorithm that has the \(\mathcal {O}\left( \frac{1}{\varepsilon }\right) \)-worst-case iteration-complexity while preserves the same complexity-per-iteration as in Nesterov’s method and allows one to automatically update the smoothness parameter at each iteration. Then, we customize our algorithm to solve four special cases that cover various applications. We also specify our algorithm to solve constrained convex optimization problems and show its convergence guarantee on a primal sequence of iterates. We demonstrate our algorithm through three numerical examples and compare it with other related algorithms.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

A parallel multisplitting solution of the least squares problem

The linear least squares problem, min_x∥Ax − b∥₂, is solved by applying a multisplitting (MS) strategy in which the system matrix is decomposed by columns into p blocks. The b and x vectors are partitioned consistently with the matrix decomposition. The global least squares problem is then replaced by a sequence of local least squares problems which can be solved in parallel by MS. In MS the solutions to the local problems are recombined using weighting matrices to pick out the appropriate components of each subproblem solution. A new two-stage algorithm which optimizes the global update each iteration is also given. For this algorithm the updates are obtained by finding the optimal update with respect to the weights of the recombination. For the least squares problem presented, the global update optimization can also be formulated as a least squares problem of dimension p. Theoretical results are presented which prove the convergence of the iterations. Numerical results which detail the iteration behavior relative to subproblem size, convergence criteria and recombination techniques are given. The two-stage MS strategy is shown to be effective for near-separable problems. © 1998 John Wiley & Sons, Ltd.     

Interval methods for fixed-point problems

Interval analysis is applied to the fixed-point problem x=?(x) for continuous ?:S→S, where the space S is constructed from Cartesian products of the set R of real numbers, with componentwise definitions of arithmetic operations, ordering, and the product topology. With the aid of an interval inclusion φ:IS → IS in the interval space IS corresponding to S, interval iteration is used to establish the existence or nonexistence of a fixed point x^? of ? in the initial interval X₀. Each step of the interval iteration provides lower and upper bounds for fixed points of ? in the initial interval, from which approximate values and guaranteed error bounds can be obtained directly. In addition to interval iteration, operator equation and dissection methods are considered briefly.

The theory of interval iteration applies directly when only finite subsets of S, IS are used, so this method is adaptable immediately to actual computation. A numerical example is given of the use of interval iteration for the computational solution of a nonlinear integral equation of radiative transfer. It is shown that numerical results with acceptable, guaranteed accuracy can be obtained with a modest amount of computation for an extended range of the parameter involved.     

A modified SSOR iterative method for augmented systems

Golub, Wu and Yuan [G.H. Golub, X. Wu, J.Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001) 71–85] have presented the SOR-like algorithm to solve augmented systems. In this paper, we present the modified symmetric successive overrelaxation (MSSOR) method for solving augmented systems, which is based on Darvishi and Hessari’s work above. We derive its convergence under suitable restrictions on the iteration parameter, determine its optimal iteration parameter and the corresponding optimal convergence factor under certain conditions. Finally, we apply the MSSOR method to solve augmented systems.     

A semi-smooth Newton method for an inverse problem in option pricing

We present an optimal control approach using a Lagrangian framework to identify local volatility functions from given option prices. We employ a globalized sequential quadratic programming (SQP) algorithm and implement a line search strategy. The linear-quadratic optimal control problems in each iteration are solved by a primal-dual active set strategy which leads to a semi-smooth Newton method. We present first- and second-order analysis as well as numerical results. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Adaptive Newton Algorithm for Optimal Control Problems with Application to Optimal Electrode Design

In this work, we present an adaptive Newton-type method to solve nonlinear constrained optimization problems, in which the constraint is a system of partial differential equations discretized by the finite element method. The adaptive strategy is based on a goal-oriented a posteriori error estimation for the discretization and for the iteration error. The iteration error stems from an inexact solution of the nonlinear system of first-order optimality conditions by the Newton-type method. This strategy allows one to balance the two errors and to derive effective stopping criteria for the Newton iterations. The algorithm proceeds with the search of the optimal point on coarse grids, which are refined only if the discretization error becomes dominant. Using computable error indicators, the mesh is refined locally leading to a highly efficient solution process. The performance of the algorithm is shown with several examples and in particular with an application in the neurosciences: the optimal electrode design for the study of neuronal networks.     

ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊

In this paper, we consider the solution of the standard linear programming [Lt＇）. A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan [19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan＇s face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.     

Implementation of an optimal first-order method for strongly convex total variation regularization

We present a practical implementation of an optimal first-order method, due to Nesterov, for large-scale total variation regularization in tomographic reconstruction, image deblurring, etc. The algorithm applies to μ-strongly convex objective functions with L-Lipschitz continuous gradient. In the framework of Nesterov both μ and L are assumed known—an assumption that is seldom satisfied in practice. We propose to incorporate mechanisms to estimate locally sufficient μ and L during the iterations. The mechanisms also allow for the application to non-strongly convex functions. We discuss the convergence rate and iteration complexity of several first-order methods, including the proposed algorithm, and we use a 3D tomography problem to compare the performance of these methods. In numerical simulations we demonstrate the advantage in terms of faster convergence when estimating the strong convexity parameter μ for solving ill-conditioned problems to high accuracy, in comparison with an optimal method for non-strongly convex problems and a first-order method with Barzilai-Borwein step size selection.     

A new penalty function algorithm for convex quadratic programming

In this paper, we develop an exterior point algorithm for convex quadratic programming using a penalty function approach. Each iteration in the algorithm consists of a single Newton step followed by a reduction in the value of the penalty parameter. The points generated by the algorithm follow an exterior path that we define. Convergence of the algorithm is established. The proposed algorithm was motivated by the work of Al-Sultan and Murty on nearest point problems, a special quadratic program. A preliminary implementation of the algorithm produced encouraging results. In particular, the algorithm requires a small and almost constant number of iterations to solve the small to medium size problems tested.     

Convergence of an adaptive Ka?anov FEM for quasi-linear problems

We design an adaptive finite element method to approximate the solutions of quasi-linear elliptic problems. The algorithm is based on a Ka?anov iteration and a mesh adaptation step is performed after each linear solve. The method is thus inexact because we do not solve the discrete nonlinear problems exactly, but rather perform one iteration of a fixed point method (Ka?anov), using the approximation of the previous mesh as an initial guess. The convergence of the method is proved for any reasonable marking strategy and starting from any initial mesh. We conclude with some numerical experiments that illustrate the theory.     

A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems.     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems.     

一种改进的GDF多目标优化算法

本文提出一种交互式非线性多目标优化算法，该算法是ＧＤＦ多目标优化算法的改进，具有这样的特点：算法采用了既约设计空间策略，具有良好的收敛性；算法生成的迭代点是有效解；算法具有多种一维搜索准则；对于线性多目标问题，算法只需一次交互迭代即可示出多目标问题的最优解。