Constructing composite search directions with parameters in quadratic interpolation models

In this paper, we introduce the weighted composite search directions to develop the quadratic approximation methods. The purpose is to make fully use of the information disclosed by the former steps to construct possibly more promising directions. Firstly, we obtain these composite directions based on the properties of simplex methods and use them to construct trust region subproblems. Then, these subproblems are solved in the algorithm to find solutions of some benchmark optimization problems. The computation results show that for most tested problems, the improved quadratic approximation methods can obviously reduce the number of function evaluations compared with the existing ones. Finally, we conclude that the algorithm will perform better if the composite directions approach the previous steepest descent direction of the sub-simplex so far. We also point out the potential applications of this improved quadratic interpolation method in business intelligence systems.     

A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper.The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces,and we also proposed an adaptive rule for choosing different searching directions at each iteration.We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition.With the used nonmonotone line search,we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions.Numerical experiments show that the proposed algorithm is promising for the given test problem set.     

Lyapunov sequences for exponential dichotomies

For a linear nonautonomous dynamics with discrete time, we study the relation between nonuniform exponential dichotomies and strict Lyapunov sequences. Given such a sequence, we obtain the stable and unstable subspaces from the intersection of the images and preimages of the cones defined by each element of the sequence. The main difficulty is to extract some information about the angles between the stable and unstable subspaces (or some appropriate notion in the case of Banach spaces) from the Lyapunov sequence. In particular, for a large class of nonuniform exponential dichotomies we give a complete characterization in terms of strict quadratic Lyapunov sequences, that is, strict Lyapunov sequences defined by quadratic forms. We also construct explicitly families of strict Lyapunov sequences for each nonuniform exponential dichotomy, in terms of Lyapunov norms.     

A Method for Dimension Reduction in Quadratic Classification Problems

This article presents a dimension-reduction method in quadratic discriminant analysis (QDA). The procedure is inspired by the geometric relation that exists between the subspaces used in sliced inverse regression (SIR) and sliced average variance estimation (SAVE). A new set of directions is constructed to improve the properties of the directions associated with the eigenvectors of the matrices usually considered for dimension reduction in QDA. Illustrative examples of application with real and simulated data are discussed.     

On quasi-Newton and pseudo-Newton algorithms

This paper surveys some of the existing approaches to quasi-Newton methods and introduces a new way for constructing inverse Hessian approximations for such algorithms. This new approach is based on restricting Newton's method to subspaces over which the inverse Hessian is assumed to be known, while expanding this subspace using gradient information. It is shown that this approach can lead to some well-known formulas for updating the inverse Hessian approximation. Deriving such updates through this approach provides new understanding of these formulas and their relation to the pseudo-Newton-Raphson algorithm.     

New Bundle Methods for Solving Lagrangian Relaxation Dual Problems

Bundle methods have been used frequently to solve nonsmooth optimization problems. In these methods, subgradient directions from past iterations are accumulated in a bundle, and a trial direction is obtained by performing quadratic programming based on the information contained in the bundle. A line search is then performed along the trial direction, generating a serious step if the function value is improved by or a null step otherwise. Bundle methods have been used to maximize the nonsmooth dual function in Lagrangian relaxation for integer optimization problems, where the subgradients are obtained by minimizing the performance index of the relaxed problem. This paper improves bundle methods by making good use of near-minimum solutions that are obtained while solving the relaxed problem. The bundle information is thus enriched, leading to better search directions and less number of null steps. Furthermore, a simplified bundle method is developed, where a fuzzy rule is used to combine linearly directions from near-minimum solutions, replacing quadratic programming and line search. When the simplified bundle method is specialized to an important class of problems where the relaxed problem can be solved by using dynamic programming, fuzzy dynamic programming is developed to obtain efficiently near-optimal solutions and their weights for the linear combination. This method is then applied to job shop scheduling problems, leading to better performance than previously reported in the literature.     

Stabilization of switched systems with polytopic uncertainties via composite quadratic functions

This paper studied the stabilization of switched linear systems with polytopic uncertainties by employing the methods of nonsmooth analysis and the composite quadratic Lyapunov functions. Above all, the minimum quadratic functions and the directional derivatives along the vertex directions of subsystems are applied to construct the new switching law. Then, some sufficient conditions for stabilization of switched linear systems are established considering the sliding modes and the directional derivatives along sliding modes. Finally, numerical examples are given to demonstrate the effectiveness of the synthesis results.     

关于二次函数的约束优化的算法研究

在本篇论文中,我们尝试用共轭方向法来处理二次函数的约束优化问题．我们 首先讨论了一下正定时的情况,再讨论负定时的情况．对于正定二次函数的优化问题,我 们提出一个算法,可以构造一列收敛到最优点的数列．对于负定二次函数的优化问题,我 们给出了一些结果．     

Linearly convergent descent methods for the unconstrained minimization of convex quadratic splines

We propose two linearly convergent descent methods for finding a minimizer of a convex quadratic spline and establish global error estimates for the iterates. One application of such descent methods is to solve convex quadratic programs, since they can be reformulated as problems of unconstrained minimization of convex quadratic splines. In particular, we derive several new linearly convergent algorthms for solving convex quadratic programs. These algorithms could be classified as row-action methods, matrix-splitting methods, and Newton-type methods.     

Subsequent Convergence of Iterative Methods with Applications to Real-Time Model-Predictive Control

In performing online model-predictive control of dynamical systems, it is necessary to solve a sequence of optimization problems (typically quadratic programs) in real time so as to generate the best trajectory. Since only a low fixed number of iterations can be executed in real time, it is not possible to solve each quadratic program to optimality. However, numerical experiments show that, if we use information from the numerical solution of the previous quadratic program to construct a warm start for the current quadratic program, there is a time step after which the usual stopping criteria will be satisfied within the fixed number of iterations for all subsequent optimization problems. This phenomenon is called subsequent convergence and will be analyzed for families of nonlinear equations. Computational results are presented to illustrate the theory and associated computational artifacts.     

A nonlinear characterization of stable invariant subspaces

A nonlinear characterization of stable invariant subspaces for an operator on Hilbert space is given. The characterization involves the solutions to a certain quadratic operator equation. The characterization is used to give information about the stability of certain invariant subspaces of an operator.     

On the structure of the quadratic subspace in discriminant analysis

The concept of quadratic subspace is introduced as a helpful tool for dimension reduction in quadratic discriminant analysis (QDA). It is argued that an adequate representation of the quadratic subspace may lead to better methods for both data representation and classification. Several theoretical results describe the structure of the quadratic subspace, that is shown to contain some of the subspaces previously proposed in the literature for finding differences between the class means and covariances. A suitable assumption of orthogonality between location and dispersion subspaces allows us to derive a convenient reduced version of the full QDA rule. The behavior of these ideas in practice is illustrated with three real data examples.     

非线性约束最优化一族超线性收敛的可行方法

本文建立求解非线性不等式约束最优化一族含参数的可行方法．算法每次迭代仅需解一个规模较小的二次规划．在一定的假设条件下,证明了算法族的全局收敛性和超线性收敛性．     

TWO NOVEL GRADIENT METHODS WITH OPTIMAL STEP SIZES

In this work we introduce two new Barzilai and Borwein-like steps sizes for the classical gradient method for strictly convex quadratic optimization problems.The proposed step sizes employ second-order information in order to obtain faster gradient-type methods.Both step sizes are derived from two unconstrained optimization models that involve approximate information of the Hessian of the objective function.A convergence analysis of the proposed algorithm is provided.Some numerical experiments are performed in order to compare the efficiency and effectiveness of the proposed methods with similar methods in the literature.Experimentally,it is observed that our proposals accelerate the gradient method at nearly no extra computational cost,which makes our proposal a good alternative to solve large-scale problems.     

Darstellungen von SL(2,ℤ/pλℤ) und Thetafunktionen. II

If the modular group Γ=SL(2,?) operates in the usual way on complex vector spaces generated by suitably chosen theta constants of level q (i.e. modular forms for the congruence subgroup Γ(q) of Γ), then this operation defines a representation of the group SL(2,?/q?). Using this method, we construct all Weil representations of these groups for any prime-power q. It is shown how they depend on the underlying quadratic form of the theta constants and how theta relations can be used to find invariant subspaces.     

A generalized structured doubling algorithm for the numerical solution of linear quadratic optimal control problems

We propose a generalization of the structured doubling algorithm to compute invariant subspaces of structured matrix pencils that arise in the context of solving linear quadratic optimal control problems. The new algorithm is designed to attain better accuracy when the classical Riccati equation approach for the solution of the optimal control problem is not well suited because the stable and unstable invariant subspaces are not well separated (because of eigenvalues near or on the imaginary axis) or in the case when the Riccati solution does not exist at all. We analyze the convergence of the method and compare the new method with the classical structured doubling algorithm as well as some structured QR methods. Copyright © 2012 John Wiley & Sons, Ltd.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.     

Unconstrained Optimization Techniques for the Acceleration of Alternating Projection Methods

Alternating projection methods have been extensively used to find the closest point, to a given point, in the intersection of several given sets that belong to a Hilbert space. One of the characteristics of these schemes is the slow convergence that can be observed in practical applications. To overcome this difficulty, several techniques, based on different ideas, have been developed to accelerate their convergence. Recently, a successful acceleration scheme was developed specially for Cimmino's method when applied to the solution of large-scale saddle point problems. This specialized acceleration scheme is based on the use of the well-known conjugate gradient method for minimizing a related convex quadratic map. In this work, we extend and further analyze this optimization approach for several alternating projection methods on different scenarios. In particular, we include a specialized analysis and treatment for the acceleration of von Neumann-Halperin's method and Cimmino's method on subspaces, and Kaczmarz method on linear varieties. For some specific applications we illustrate the advantages of our acceleration schemes with encouraging numerical experiments.     

Minimization of extended quadratic functions with inexact line searches

An algorithm for unconstrained minimization is proposed which is invariant to the nonlinear scaling of a strictly convex quadratic function and which generates mutually conjugate directions for extended quadratic functions. It is derived for inexact line searches and is designed for general use. It compares favorably in numerical tests (eight test functions, dimensionality up to 1000) with the 1975 Dixon algorithm on which this new algorithm is based.     

不变子空间与广义不变子空间——(Ⅱ)扰动定理

关于矩阵的不变子空间,自然会提出这样一个扰动问题:设Z_1∈C~(n×l)是A∈C~(n×n)的一个特征矩阵,若E∈C~(n×n)是一个扰动矩阵,问A+B是否存在特征矩阵Z_1,使得(Z_1)靠近R(Z_1)?关于矩阵对的广义不变子空间.也可以类似地提出问题。 对于这些问题,G.W.Stewart曾经讨论过,他的方法的关键是构造一种求解二次矩阵方程的迭代过程,用来逼近矩阵的一个不变子空间;而本文建议另一种迭代格式,用这种迭代逼近一个不变(或广义不变)子空间,具有二次收敛速度。