Degeneracy: Resolve or Avoid?

Two projected gradient algorithms for linear programming are discussed. The first uses a conventional enough steepest edge approach, and implements a version of Wolfe's method for resolving any problems of degeneracy. The second makes use of a steepest descent direction which is calculated by solving a linear least squares problem subject to bound constraints, and avoids problems of degeneracy altogether. They are compared using randomly generated problems which permit the specification of (known) degenerate minima. The results appear to favour the more conventional method as problem sizes get larger.     

Stabilized dynamic constraint aggregation for solving set partitioning problems

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solving linear programs. The first uses a projection to reduce the primal space whereas the second acts in the dual space. In this paper, we develop a new method, called stabilized dynamic constraint aggregation (SDCA), that combines DCA and DVS for solving set partitioning problems. It allows to fight degeneracy from both primal and dual perspectives simultaneously. To assess the effectiveness of SDCA, we report computational results obtained for highly degenerate multi-depot vehicle scheduling problem instances solved by column generation. These results indicate that SDCA can reduce the average computational time of the master problem by a factor of up to 7 with respect to the best of the two combined methods. Furthermore, they show that its performance is robust with regard to increasing levels of degeneracy in test problems.     

Degenerate parabolic equations with initial data measures

We address the problem of existence of solutions to degenerate (and nondegenerate) parabolic equations under optimal assumptions on the initial data, which are assumed to be measures. The requirements imposed on the initial data are connected both with the degeneracy of the principal part of the equation, and with the form of the nonlinear forcing term. The latter depends on the space gradient of a power of the solution. Applications to related problems are also outlined.

     

An inverse problem of identifying the coefficient of first-order in a degenerate parabolic equation

This work studies an inverse problem of determining the first-order coefficient of degenerate parabolic equations using the measurement data specified at a fixed internal point. Being different from other ordinary parameter identification problems in parabolic equations, in our mathematical model there exists degeneracy on the lateral boundaries of the domain, which may cause the corresponding boundary conditions to go missing. By the contraction mapping principle, the uniqueness of the solution for the inverse problem is proved. A numerical algorithm on the basis of the predictor-corrector method is designed to obtain the numerical solution and some typical numerical experiments are also performed in the paper. The numerical results show that the proposed method is stable and the unknown function is recovered very well. The results obtained in the paper are interesting and useful, and can be extended to other more general inverse coefficient problems of degenerate PDEs.     

A Projected Gradient Method for Vector Optimization Problems

Vector optimization problems are a significant extension of multiobjective optimization, which has a large number of real life applications. In vector optimization the preference order is related to an arbitrary closed and convex cone, rather than the nonnegative orthant. We consider extensions of the projected gradient gradient method to vector optimization, which work directly with vector-valued functions, without using scalar-valued objectives. We provide a direction which adequately substitutes for the projected gradient, and establish results which mirror those available for the scalar-valued case, namely stationarity of the cluster points (if any) without convexity assumptions, and convergence of the full sequence generated by the algorithm to a weakly efficient optimum in the convex case, under mild assumptions. We also prove that our results still hold when the search direction is only approximately computed.     

SU(2)-equivariantk-theory of a class ofC*-algebras and nonhomogeneous random walks

The SU(2) equivariantK ₀-Theory of a class ofC*-algebras is studied. These algebras arise from nonhomogeneous actions of SU(2) or SO(3) on uniformly hyperfinite algebras. The problems are shown to be equivalent to studying nonhomogeneous random walks associated with infinite products of characters — in particular, properties related to unimodality and positivity. Concrete sufficient conditions are developed for reducing the problem to the maximal torus action, for which extensive results are known; these become necessary and sufficient when there is a bound on the degree of the characters, or a strong unimodality assumption is made. When the degrees are unbounded, examples are constructed to indicate the range of behavior possible when reduction to the maximal torus is impossible. Finally, limit ratio theorems are obtained for the distribution of irreducibles in products of characters having a unimodality property.Supported in part by an operating grant from NSERC, Canada.     

Degenerate Dirichlet Problems Related to the Invariant Measure of Elasto-Plastic Oscillators

A stochastic variational inequality is proposed to model a white noise excited elasto-plastic oscillator. The solution of this inequality is essentially a continuous diffusion process for which a governing diffusion equation is obtained to study the evolution in time of its probability distribution. The diffusion equation is degenerate, but using the fact that the degeneracy occurs on a bounded region we are able to show the existence of a unique solution satisfying the desired properties. We prove the ergodic properties of the process and characterize the invariant measure. Our approach relies on extending Khasminskii’s method (Stochastic Stability of Differential Equations, Sijthoff and Noordhoff, 1980), which in the present context leads to the study of degenerate Dirichlet problems with nonlocal boundary conditions. This research was partially supported by a grant from CEA, Commissariat à l’énergie atomique and by the National Science Foundation under grant DMS-0705247.     

Exact and stable least squares solution to the linear programming problem

A linear programming problem is transformed to the finding an element of polyhedron with the minimal norm. According to A. Cline [6], the problem is equivalent to the least squares problem on positive ortant. An orthogonal method for solving the problem is used. This method was presented earlier by the author and it is based on the highly developed least squares technique. First of all, the method is meant for solving unstable and degenerate problems. A new version of the artifical basis method (M-method) is presented. Also, the solving of linear inequality systems is considered.     

关于L_p球的几个新不等式和性质(英文)

本文研究了L_p球的相关问题.利用对偶混合体积、球面Radon变换和Fourier变换的方法,获得了关于L_p球的几个新不等式和性质,其中一个不等式与著名的最大切片猜想有关.     

Degeneracy graphs: theory and application an updated survey

A survey of various aspects of the theory and application of degeneracy graphs (DGs for short) is given. The notion and some basic properties of DGs are introduced, cycling of the simplex method is discussed, the neighborhood problem is tackled, and the application of the so-called optimum DGs to particular problems which are connected with optimal degenerate solutions of a linear programming problem is presented. The impact of weakly redundant constraints on various postoptimal analyses under degeneracy is briefly described.     

Bivariate Sign Tests Based on the Sup, L 1 and L 2 Norms

The bivariate location problem is considered. The sup, L ₁ and L ₂ norms are used to construct bivariate sign tests from the univariate sign statistics computed on the projected observations on all lines passing through the origin. The tests so obtained are affine-invariant and distribution-free under the null hypothesis. The sup-norm gives rise to Hodges' test. A class of tests derived from the L ₂-norm, with Blumen's test as a member, is seen to be related to a class proposed by Oja and Nyblom (1989, J. Amer. Statist. Assoc., 84, 249-259). The L ₁-norm gives rise to a new test. Its asymptotic null distribution is seen to be the same as that of the L ₁-norm of a certain normal process related to the standard Wiener process. An explicit expression of its cumulative distribution function is given. A simulation study will examine the merits of the three approaches.     

An investigation of feasible descent algorithms for?estimating the condition number of a matrix

Techniques for estimating the condition number of a nonsingular matrix are developed. It is shown that Hager??s 1-norm condition number estimator is equivalent to the conditional gradient algorithm applied to the problem of maximizing the 1-norm of a matrix-vector product over the unit sphere in the 1-norm. By changing the constraint in this optimization problem from the unit sphere to the unit simplex, a new formulation is obtained which is the basis for both conditional gradient and projected gradient algorithms. In the test problems, the spectral projected gradient algorithm yields condition number estimates at least as good as those obtained by the previous approach. Moreover, in some cases, the spectral gradient projection algorithm, with a careful choice of the parameters, yields improved condition number estimates.     

Projected gradient methods for linearly constrained problems

The aim of this paper is to study the convergence properties of the gradient projection method and to apply these results to algorithms for linearly constrained problems. The main convergence result is obtained by defining a projected gradient, and proving that the gradient projection method forces the sequence of projected gradients to zero. A consequence of this result is that if the gradient projection method converges to a nondegenerate point of a linearly constrained problem, then the active and binding constraints are identified in a finite number of iterations. As an application of our theory, we develop quadratic programming algorithms that iteratively explore a subspace defined by the active constraints. These algorithms are able to drop and add many constraints from the active set, and can either compute an accurate minimizer by a direct method, or an approximate minimizer by an iterative method of the conjugate gradient type. Thus, these algorithms are attractive for large scale problems. We show that it is possible to develop a finite terminating quadratic programming algorithm without non-degeneracy assumptions. Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38. Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

CONVERGENCE OF NUMERICAL SCHEMES FOR A CONSERVATION EQUATION WITH CONVECTION AND DEGENERATE DIFFUSION

The approximation of problems with linear convection and degenerate nonlinear difFusion,which arise in the framework of the transport of energy in porous media with thermodynamic transitions,is done usingθ-scheme based on the centred gradient discretisation method.The convergence of the numerical scheme is proved,although the test functions which can be chosen are restricted by the weak regularity hypotheses on the convection field,owing to the application of a discrete Gronwall lemma and a general result for the time translate in the gradient discretisation setting.Some numerical examples,using both the Control Volume Finite Element method and the Vertex Approximate Gradient scheme,show the role ofθfor stabilising the scheme.     

Gevrey regularity of subelliptic Monge–Ampère equations in the plane

In this paper, we establish the Gevrey regularity of solutions for a class of degenerate Monge–Ampère equations in the plane. Under the assumptions that one principal entry of the Hessian is strictly positive and the coefficient of the equation is degenerate with appropriately finite type degeneracy, we prove that the solution of the degenerate Monge–Ampère equation will be smooth in Gevrey classes.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

A strictly improving linear programming Phase I algorithm

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called basic) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs.When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.     

求解界约束优化的一种新的非单调谱投影梯度法

本文给出求解界约束优化问题的一种新的非单调谱投影梯度算法. 该算法是将谱投影梯度算法与Zhang and Hager [SIAM Journal on Optimization,2004,4（4）：1043-1056]提出的非单调线搜索结合得到的方法. 在合理的假设条件下,证明了算法的全局收敛性.数值实验结果表明,与已有的界约束优化问题的谱投影梯度法比较,利用本文给出的算法求解界约束优化问题是有竞争力的.     

A SUBSPACE PROJECTED CONJUGATE GRADIENT ALGORITHM FOR LARGE BOUND CONSTRAINED QUADRATIC PROGRAMMING

A subspace projected conjugate gradient method is proposed for solving large bound constrained quadratic programming. The conjugate gradient method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At every iterative level, the search direction consists of two parts, one of which is a subspace trumcated Newton direction, another is a modified gradient direction. With the projected search the algorithm is suitable to large problems. The convergence of the method is proved and same numerical tests with dimensions ranging from 5000 to 20000 are given.     

Degeneracy in linear complementarity problems: a survey

Given a square matrixM of ordern and a vectorq ⁿ , the linear complementarity problem is the problem of either finding aw ⁿ and az ⁿ such thatw–Mz=q,w0,z0 andw ^T z=0 or showing that no such (w, z) exists. This problem is denoted asLCP(q, M). We say that a solution (w, z) toLCP(q, M) is degenerate if the number of positive coordinates in (w, z) is less thann. As in linear programming, degeneracy may cause cycling in an adjacent vertex following methods like Lemke's algorithm. Moreover, ifLCP(0,M) has a nontrivial solution, a condition related to degeneracy, then unless certain other conditions are satisfied, the algorithm may not be able to decide about the solvability of the givenLCP(q, M). In this paper we review the literature on the implications of degeneracy to the linear complementarity theory.