Solution of projection problems over polytopes

Summary In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytope. By using the special struture of the projection problems, an iterative algorithm with constant step-size is given, which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimums norm problems over transportation or general network polytopes onlyO(n) additions andO(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems.     

Further Developments in an Iterative Projection and Contraction Method for Linear Programming

A linear programming problem can be translated into an equivalent general linear complementarity problem, which can be solved by an iterative projection and contraction (PC) method [6]. The PC method requires only two matrix-vector multiplications at each iteration and the efficiency in practice usually depends on the sparsity of the constraint-matrix. The prime PC algorithm in [6] is globally convergent; however, no statement can be made about the rate of convergence. Although a variant of the PC algorithm with constant step-size for linear programming [7] has a linear speed of convergence, it converges much slower in practice than the prime method [6]. In this paper, we develop a new step-size rule for the PC algorithm for linear programming such that the resulting algorithm is globally linearly convergent. We present some numerical experiments to indicate that it also works better in practice than the prime algorithm.     

A globally convergent method for semi-infinite linear programming

This paper presents a globally convergent method for solving a general semi-infinite linear programming problem. Some important features of this method include: It can solve a semi-infinite linear program having an unbounded feasible region. It requires an inexact solution to a nonlinear subproblem at each iteration. It allows unbounded index sets and nondifferentiable constraints. The amount of work at each iteration k does not increase with k.     

A non-interior continuation method for second-order cone programming

We extend the smoothing function proposed by Huang, Han and Chen [Journal of Optimization Theory and Applications, 117 (2003), pp. 39–68] for the non-linear complementarity problems to the second-order cone programming (SOCP). Based on this smoothing function, a non-interior continuation method is presented for solving the SOCP. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that our algorithm is globally and locally superlinearly convergent in absence of strict complementarity at the optimal solution. Numerical results indicate the effectiveness of the algorithm.     

A globally convergent non-interior point algorithm with full Newton step for second-order cone programming

A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of A to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.     

Computing nonlinear network equilibria

This paper examines the problem of computing nonlinear network equilibria using a ‘Newton’ iteration. By exploiting the network structure, we are able to show that the iteration is globally convergent, monotonic, and (locally) quadratically convergent using only simple algebraic arguments.     

离散空间分数阶非线性薛定谔方程的MHSS型迭代方法

利用隐式守恒型差分格式来离散空间分数阶非线性薛定谔方程,可得到一个离散线性方程组.该离散线性方程组的系数矩阵为一个纯虚数复标量矩阵、一个对角矩阵与一个对称Toeplitz矩阵之和.基于此,本文提出了用一种\textit{修正的埃尔米特和反埃尔米特分裂}(MHSS)型迭代方法来求解此离散线性方程组.理论分析表明,MHSS型迭代方法是无条件收敛的.数值实验也说明了该方法是可行且有效的.     

A full-Newton step non-interior continuation algorithm for a class of complementarity problems

In this paper, we investigate a class of nonlinear complementarity problems arising from the discretization of the free boundary problem, which was recently studied by Sun and Zeng [Z. Sun, J. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math. 235 (5) (2011) 1261–1274]. We propose a new non-interior continuation algorithm for solving this class of problems, where the full-Newton step is used in each iteration. We show that the algorithm is globally convergent, where the iteration sequence of the variable converges monotonically. We also prove that the algorithm is globally linearly and locally superlinearly convergent without any additional assumption, and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate the effectiveness of the proposed algorithm.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

On solutions to coupled multiparameter nonlinear Sturm- Liouville boundary value problems whose state components have a specified nodal structure

In preceding articles ([3] and [5]), we began an examination of the structure of the solution set to the two-parameter system \(\matrix{\qquad\qquad-(p_{1}(x)u^{\prime})^{\prime}+q_1(x)u= \lambda u+f(u,v)u\cr \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad in (a,b)\cr \qquad(*)\ \ -(p_{2}(x)v^{\prime})^\prime+ q_{2}(x)v=\mu v+g(u,v)v\cr \qquad\qquad u(a)=u(b)=0=v(a)=v(b).}\) In this article, we treat the case left uncovered in our previous analysis; namely, we assume f (s,0) = 0 and g(0,t) = 0 for all s, t ∈ ?. In this situation, solutions to (*) of the form (λ, μ, u, 0) or (λ, μ,0,v lie in linear subspaces of ?.² dx (C01 [a, b] 2. As such, they are neither locally expressable as functions of (λ, μ) nor are à priori bounded in terms of (λ, μ), as was crucial to the analysis in [3] and [5]. Nevertheless, we demonstrate that solutions to (*) of the form (λ, μ, u, v) with u having n ? 1 simple zeros in (a, b) and v having m ? 1 simple zeros in (a, b), where n and m are positive integers, arise as global secondary bifurcations from solutions of the form (λ,μ,u,0) with u having n ? 1 simple zeros in (a, b) and from solutions of the form (λ, μ, o, v) with v having m ? 1 simple zeros in (a, b). Moreover, we establish that solutions to (*) of the form (λ,μ,u,v) with u having n ? 1 simple zeros in (a, b) and v having m ? 1 simple zeros in (a, b) serve as a link between solutions of the form (λ, μ, u, 0) with u having n ? 1 simple zeros in (a,b) and solutions of the form (λ, μ, 0, v) with v having m ? 1 simple zeros in (a, b). The analysis in this article when combined with that in [3] and [5] provides a fairly comprehensive examination of the structure of the solution set to (*).     

Several variants of the Hermitian and skew‐Hermitian splitting method for a class of complex symmetric linear systems

This paper is concerned with several variants of the Hermitian and skew‐Hermitian splitting iteration method to solve a class of complex symmetric linear systems. Theoretical analysis shows that several Hermitian and skew‐Hermitian splitting based iteration methods are unconditionally convergent. Numerical experiments from an n‐degree‐of‐freedom linear system are reported to illustrate the efficiency of the proposed methods. Copyright © 2014 John Wiley & Sons, Ltd.     

An Efficient Hybrid Conjugate Gradient Method for Unconstrained Optimization

Recently, we propose a nonlinear conjugate gradient method, which produces a descent search direction at every iteration and converges globally provided that the line search satisfies the weak Wolfe conditions. In this paper, we will study methods related to the new nonlinear conjugate gradient method. Specifically, if the size of the scalar _k with respect to the one in the new method belongs to some interval, then the corresponding methods are proved to be globally convergent; otherwise, we are able to construct a convex quadratic example showing that the methods need not converge. Numerical experiments are made for two combinations of the new method and the Hestenes–Stiefel conjugate gradient method. The initial results show that, one of the hybrid methods is especially efficient for the given test problems.     

Lineability of sets of nowhere analytic functions

Although the set of nowhere analytic functions on [0,1] is clearly not a linear space, we show that the family of such functions in the space of C^∞-smooth functions contains, except for zero, a dense linear submanifold. The result is even obtained for the smaller class of functions having Pringsheim singularities everywhere. Moreover, in spite of the fact that the space of differentiable functions on [0,1] contains no closed infinite-dimensional manifold in C([0,1]), we prove that the space of real C^∞-smooth functions on (0,1) does contain such a manifold in C((0,1)).     

A homogeneous smoothing-type algorithm for symmetric cone linear programs

In this paper, we investigate a smoothing-type algorithm for solving the symmetric cone linear program （（SCLP） for short） by making use of an augmented system of its optimality conditions. The algorithm only needs to solve one system of linear equations and to perform one line search at each iteration. It is proved that the algorithm is globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, the algorithm may correctly detect solvability of （SCLP）. Furthermore, if （SCLP） has a solution, then the algorithm will generate a solution of （SCLP）, and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of （SCLP）.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

<Emphasis Type="Italic">f</Emphasis>-Vectors of barycentric subdivisions

For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney–Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope. For a general (d − 1)-dimensional simplicial complex Δ the h-polynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this h-polynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d. F. Brenti and V. Welker are partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

广义非线性互补问题的投影收缩法

广义非线性互补问题的投影收缩法孙德锋（中国科学院应用数学研究所）ＡＰＲＯＪＥＣＴＩＯＮＡＮＤＣＯＮＴＲＡＣＴＩＯＮＭＥＴＨＯＤＦＯＲＴＨＥＮＯＮＬＩＮＥＡＲＣＯＭＰＬＥＭＥＮＴＡＲＩＴＹＰＲＯＢＬＥＭＡＮＤＩＴＳＥＸＴＥＮＳＩＯＮＳ￥ＳｕｎＤｅ－ｆｅ...