A generalized Newton method for absolute value equations

A direct generalized Newton method is proposed for solving the NP-hard absolute value equation (AVE) Ax − |x| = b when the singular values of A exceed 1. A simple MATLAB implementation of the method solved 100 randomly generated 1,000-dimensional AVEs to an accuracy of 10⁻⁶ in less than 10 s each. Similarly, AVEs corresponding to 100 randomly generated linear complementarity problems with 1,000 × 1,000 nonsymmetric positive definite matrices were also solved to the same accuracy in less than 29 s each.     

A partial order for the set of meanders

In this paper, we present a new approach for studying meanders in terms of noncrossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.     

Theory and method for updating least-squares finite element model of symmetric generalized centro-symmetric matrices

Let X,F$X,F$ be a displacement matrix and load matrix, respectively. C (obtained by calculations or measurements) is an estimate matrix of the analytical model. A method is presented for correction of the model C, based on the theory of inverse problem of matrices. The corrected model is symmetric generalized centro-symmetric with specified displacements and loads, satisfying the mechanics characters of finite-element model. The application of the method is illustrated. It is more important that a perturbation analysis is given, which is not given in the earlier papers. Numerical results show that the method is feasible and effective.     

Riordan arrays associated with Laurent series and generalized Sheffer-type groups

A relationship between a pair of Laurent series and Riordan arrays is formulated. In addition, a type of generalized Sheffer groups is defined by using Riordan arrays with respect to power series with non-zero coefficients. The isomorphism between a generalized Sheffer group and the group of the Riordan arrays associated with Laurent series is established. Furthermore, Appell, associated, Bell, and hitting-time subgroups of the groups are defined and discussed. A relationship between the generalized Sheffer groups with respect to different type of power series is presented. The equivalence of the defined Riordan array pairs and generalized Stirling number pairs is given. A type of inverse relations of various series is constructed by using pairs of Riordan arrays. Finally, several applications involving various arrays, polynomial sequences, special formulas and identities are also presented as illustrative examples.     

Max-algebraic attraction cones of nonnegative irreducible matrices

It is known that the max-algebraic powers A^r of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λ^t(A)A^r⊗x=A^r+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.     

Solvability of Newton equations in smoothing-type algorithms for the SOCCP

In this paper, we first investigate the invertibility of a class of matrices. Based on the obtained results, we then discuss the solvability of Newton equations appearing in the smoothing-type algorithm for solving the second-order cone complementarity problem (SOCCP). A condition ensuring the solvability of such a system of Newton equations is given. In addition, our results also show that the assumption that the Jacobian matrix of the function involved in the SOCCP is a P₀-matrix is not enough for ensuring the solvability of such a system of Newton equations, which is different from the one of smoothing-type algorithms for solving many traditional optimization problems in ℜⁿ.     

On the Newton method for set-valued maps

The Newton method is one of the most powerful tools used to solve systems of nonlinear equations. Its set-valued generalization, considered in this work, allows one to solve also nonlinear equations with geometric constraints and systems of inequalities in a unified manner. The emphasis is given to systems of linear inequalities. The study of the well-posedness of the algorithm and of its convergence is fulfilled in the framework of modern variational analysis.     

Maximal exponents of polyhedral cones (II)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rⁿ. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that the maximum value of γ(K) as K runs through all n-dimensional minimal cones (i.e., cones having n+1 extreme rays) is n²-n+1 if n is odd, and is n²-n if n is even, the maximum value of the exponent being attained by a minimal cone with a balanced relation for its extreme vectors. The K-primitive matrices A such that γ(A) attain the maximum value are identified up to cone-equivalence modulo positive scalar multiplication.     

Polyhedral combinatorics of UPGMA cones

Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm. The partition lattice informs the study of UPGMA trees. We give a closed form for the extreme rays of UPGMA cones on n taxa, and compute the spherical volumes of the UPGMA cones for small n.     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

Log-Sigmoid nonlinear Lagrange method for nonlinear optimization problems over second-order cones

This paper analyzes the rate of local convergence of the Log-Sigmoid nonlinear Lagrange method for nonconvex nonlinear second-order cone programming. Under the componentwise strict complementarity condition, the constraint nondegeneracy condition and the second-order sufficient condition, we show that the sequence of iteration points generated by the proposed method locally converges to a local solution when the penalty parameter is less than a threshold and the error bound of solution is proportional to the penalty parameter. Finally, we report numerical results to show the efficiency of the method.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

Filled function method for nonlinear equations

Systems of nonlinear equations are ubiquitous in engineering, physics and mechanics, and have myriad applications. Generally, they are very difficult to solve. In this paper, we will present a filled function method to solve nonlinear systems. We will first convert the nonlinear systems into equivalent global optimization problems with the property: x^∗ is a global minimizer if and only if its function value is zero. A filled function method is proposed to solve the converted global optimization problem. Numerical examples are presented to illustrate our new techniques.     

Lie point symmetries for systems of second order linear ordinary differential equations

Abstract

The equations for the Lie point symmetries of autonomous systems of second order linear ordinary differential equations are derived. The results for a two dimensional system are treated in detail and some consideration is extended to higher dimensional systems. The effect of the introduction of time-dependent elements into the coefficient matrix is briefly discussed.     

Global optimization for sum of generalized fractional functions

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.