A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

New Interior-Point Algorithm for Symmetric Optimization Based on a Positive-Asymptotic Barrier Function

Abstract

We define a new interior-point method (IPM), which is suitable for solving symmetric optimization (SO) problems. The proposed algorithm is based on a new search direction. In order to obtain this direction, we apply the method of algebraically equivalent transformation on the centering equation of the central path. We prove that the associated barrier cannot be derived from a usual kernel function. Therefore, we introduce a new notion, namely the concept of the positive-asymptotic kernel function. We conclude that this algorithm solves the problem in polynomial time and has the same complexity as the best known IPMs for SO.     

A New Full Nesterov–Todd Step Primal–Dual Path-Following Interior-Point Algorithm for Symmetric Optimization

In this paper, we generalize a primal–dual path-following interior-point algorithm for linear optimization to symmetric optimization by using Euclidean Jordan algebras. The proposed algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov–Todd steps. Moreover, we derive the currently best known iteration bound for the small-update method. This unifies the analysis for linear, second-order cone, and semidefinite optimizations.     

基于局部self-concordant障碍函数的全牛顿步多项式时间算法

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.     

On the volumetric path

We consider the logarithmic and the volumetric barrier functions used in interior point methods. In the case of the logarithmic barrier function, the analytic center of a level set is the point at which the central path intersects that level set. We prove that this also holds for the volumetric path. For the central path, it is also true that the analytic center of the optimal level set is the limit point of the central path. The only known case where this last property for the logarithmic barrier function fails occurs in case of semidefinite optimization in the absence of strict complementarity. For the volumetric path, we show with an example that this property does not hold even for a linear optimization problem in canonical form.     

Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

LMI优化的一种原对偶中心路径算法

系统和控制理论中许多重要的问题,都可转化为具有线性目标函数、线性矩阵不等式约束的LMI优化问题,从而使其在数值上易于求解.本文给出一种求解LMI优化问题的原对偶中心路径算法,该算法利用牛顿方法求解中心路径方程得到牛顿系统,并将该牛顿系统对称化以避免得到非对称化的搜索方向.文章详细分析了算法的计算复杂性.     

Efficiently solving total least squares with Tikhonov identical regularization

The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.     

A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm.     

Convergence of Numerical Approximation for Jump Models Involving Delay and Mean-Reverting Square Root Process

The mean-reverting square root process with jump has been widely used as a model on the financial market. Since the diffusion coefficient in the model does not satisfy the linear growth condition and local Lipschitz condition, we can not examine its properties by traditional techniques. To overcome the difficulties, we develop several new techniques to examine the numerical method of jump models involving delay and mean-reverting square root. We show that the numerical approximate solutions converge to the true solutions. Finally, we apply the convergence to examine a path-dependent option price and a bond in the financial pricing.     

二阶锥规划的基于自协调指数核函数的原始-对偶内点算法

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.     

On the Behavior of the Gradient Norm in the Steepest Descent Method

It is well known that the norm of the gradient may be unreliable as a stopping test in unconstrained optimization, and that it often exhibits oscillations in the course of the optimization. In this paper we present results descibing the properties of the gradient norm for the steepest descent method applied to quadratic objective functions. We also make some general observations that apply to nonlinear problems, relating the gradient norm, the objective function value, and the path generated by the iterates.     

The Complexity of Self-Regular Proximity Based Infeasible IPMs

Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting properties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to define infeasible neighborhoods. These simple but interesting properties of the proximity function indicate that, when the current iterate is in a large neighborhood of the central path, large-update IIPMs emerge as the only natural choice. Then, we apply these results to design a specific self-regularity based dynamic large-update IIPM in large neighborhood. The new dynamic IIPM always takes large-updates and does not utilize any inner iteration to get centered. An worst-case iteration bound of the algorithm is established. Finally, we report the main results of our computational experiments.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

New Self-Concordant Barrier for the Hypercube

We introduce a new barrier function to build new interior-point algorithms to solve optimization problems with bounded variables. First, we show that this function is a (3/2)n-self-concordant barrier for the unitary hypercube [0,1] ⁿ , assuring thus the polynomial property of related algorithms. Second, using the Hessian metric of that barrier, we present new explicit algorithms from the point of view of Riemannian geometry applications. Third, we prove that the central path defined by the new barrier to solve a certain class of linearly constrained convex problems maintains most of the properties of the central path defined by the usual logarithmic barrier. We present also a primal long-step path-following algorithm with similar complexity to the classical barrier. Finally, we introduce a new proximal-point Bregman type algorithm to solve linear problems in [0,1] ⁿ and prove its convergence. P.R. Oliveira was partially supported by CNPq/Brazil.     

The dual reciprocity boundary elements method for the linear and nonlinear two‐dimensional time‐fractional partial differential equations

In this paper, we apply the dual reciprocity boundary elements method for the numerical solution of two‐dimensional linear and nonlinear time‐fractional modified anomalous subdiffusion equations and time‐fractional convection–diffusion equation. The fractional derivative of problems is described in the Riemann–Liouville and Caputo senses. We employ the linear radial basis function for interpolation of the nonlinear, inhomogeneous and time derivative terms. This method is improved by using a predictor–corrector scheme to overcome the nonlinearity which appears in the nonlinear problems under consideration. The accuracy and efficiency of the proposed schemes are checked by five test problems. The proposed method is employed for solving some examples in two dimensions on unit square and also in complex regions to demonstrate the efficiency of the new technique. Copyright © 2016 John Wiley & Sons, Ltd.     

Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier

We propose a new primal-dual infeasible interior-point method for symmetric optimization by using Euclidean Jordan algebras. Different kinds of interior-point methods can be obtained by using search directions based on kernel functions. Some search directions can be also determined by applying an algebraic equivalent transformation on the centering equation of the central path. Using this method we introduce a new search direction, which can not be derived from a usual kernel function. For this reason, we use the new notion of positive-asymptotic kernel function which induces the class of corresponding barriers. In general, the main iterations of the infeasible interior-point methods are composed of one feasibility and several centering steps. We prove that in our algorithm it is enough to take only one centering step in a main iteration in order to obtain a well-defined algorithm. Moreover, we conclude that the algorithm finds solution in polynomial time and has the same complexity as the currently best known infeasible interior-point methods. Finally, we give some numerical results.     

A Newton-type univariate optimization algorithm for locating the nearest extremum

This paper introduces an algorithm for univariate optimization using linear lower bounding functions (LLBF's). An LLBF over an interval is a linear function which lies below the given function over an interval and matches the given function at one end point of the interval. We first present an algorithm using LLBF's for finding the nearest root of a function in a search direction. When the root-finding method is applied to the derivative of an objective function, it is an optimization algorithm which guarantees to locate the nearest extremum along a search direction. For univariate optimization, we show that this approach is a Newton-type method, which is globally convergent with superlinear convergence rate. The applications of this algorithm to global optimization and other optimization problems are also discussed.     

An approach for solving of a moving boundary problem

In this paper we shall study moving boundary problems, and we introduce an approach for solving a wide range of them by using calculus of variations and optimization. First, we transform the problem equivalently into an optimal control problem by defining an objective function and artificial control functions. By using measure theory, the new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; then we obtain an optimal measure which is then approximated by a finite combination of atomic measures and the problem converted to an infinite-dimensional linear programming. We approximate the infinite linear programming to a finite-dimensional linear programming. Then by using the solution of the latter problem we obtain an approximate solution for moving boundary function on specific time. Furthermore, we show the path of moving boundary from initial state to final state.     

Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem

In this paper we propose a weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, we only use full-Newton step. Finally, the currently best known iteration bound for the algorithm with a small-update method, namely, O(√nlog n/ε) is derived, which is as good as the bound for the linear optimization analogue.