Null space conditions and thresholds for rank minimization

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm—equal to the sum of the singular values—of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to infinity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic’s performance in non-asymptotic scenarios.     

带不等式约束的线性模型中非齐次线性预测的可容许性

本文针对带不等式约束的线性模型,在矩阵损失下研究了线性预测的可容许性,得到了条件线性可预测变量的非齐次线性预测Lys α是可容许线性预测的充要条件.     

Numerical methods for solving some matrix feasibility problems

In this paper, we design two numerical methods for solving some matrix feasibility problems, which arise in the quantum information science. By making use of the structured properties of linear constraints and the minimization theorem of symmetric matrix on manifold, the projection formulas of a matrix onto the feasible sets are given, and then the relaxed alternating projection algorithm and alternating projection algorithm on manifolds are designed to solve these problems. Numerical examples show that the new methods are feasible and effective.     

Convergence of an augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints

An augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints is proposed based on a Löwner operator associated with a potential function for the optimization problems with inequality constraints. The favorable properties of both the Löwner operator and the corresponding augmented Lagrangian are discussed. And under some mild assumptions, the rate of convergence of the augmented Lagrange algorithm is studied in detail.     

Admissibility of linear estimators with respect to inequality constraints under some loss functions

In this paper, we study the issue of admissibility of linear estimated functions of parameters in the multivariate linear model with respect to inequality constraints under a matrix loss and a matrix balanced loss. Under the matrix loss, when the model is not constrained, the results in the class of non-homogeneous linear estimators [Xie, 1989, Chinese Sci. Bull., 1148–1149; Xie, 1993, J. Multivariate Anal., 1071–1074] showed that the admissibility under the matrix loss and the trace loss is equivalent. However, when the model is constrained by the inequality constraints, we find this equivalency is not tenable, our result shows that the admissibility of linear estimator does not depend on the constraints again under this matrix loss, but it is contrary under the trace loss [Wu, 2008, Linear Algebra Appl., 2040–2048], and it is also relative to the constraints under another matrix loss [He, 2009, Linear Algebra Appl., 241–250]. Under the matrix balanced loss, the necessary and sufficient conditions that the linear estimators are admissible in the class of homogeneous and non-homogeneous linear estimators are obtained, respectively. These results will support the theory of admissibility on the linear model with inequality constraints.     

Un modèle ES–BGK pour des mélanges de gaz

In this note, we derive an ES–BGK model for gas mixtures that is able to give the correct Prandtl number obtained from the true Boltzmann equation. The derivation principle is based on the resolution of an entropy minimisation problem under moments constraints. The set of constraints is constructed by introducing a relaxation of some non-conserved moments. The non-conserved moments are dissipated according to some relaxation rates. Finally the BGK model that is obtained satisfies the classical properties of the Boltzmann operator for inert gas mixtures.     

On interdependence between invariant factors of a block-triangular matrix and its diagonal blocks

Mathematical Notes - The interdependence between the invariant factors of a block-triangular matrix and its diagonal blocks is established under some constraints on its canonical diagonal form.     

A GENERALIZATION OF FINSLER'S THEOREM FOR QUADRATIC INEQUALITIES AND EQUALITIES

ABSTRACT

A generalization is given of Finsler's theorem on the positivity of a quadratic form subject to a quadratic equality. The generalized result is, under a certain assumption, a set of necessary and sufficient conditions for non-negativity of a quadratic form subject to an arbitrary number of quadratic inequality and equality constraints. Certain properties of matrix inverses are deduced using the conditions.     

An interior-point affine-scaling trust-region method for semismooth equations with box constraints

An algorithm for the solution of a semismooth system of equations with box constraints is described. The method is an affine-scaling trust-region method. All iterates generated by this method are strictly feasible. In this way, possible domain violations outside or on the boundary of the box are avoided. The method is shown to have strong global and local convergence properties under suitable assumptions, in particular, when the method is used with a special scaling matrix. Numerical results are presented for a number of problems arising from different areas.     

Preconditioned conjugate gradient algorithms for nonconvex problems with box constraints

The paper describes new conjugate gradient algorithms for large scale nonconvex problems with box constraints. In order to speed up convergence the algorithms employ scaling matrices which transform the space of original variables into the space in which Hessian matrices of the problem’s functionals have more clustered eigenvalues. This is done by applying limited memory BFGS updating matrices. Once the scaling matrix is calculated, the next few conjugate gradient iterations are performed in the transformed space. The box constraints are treated efficiently by the projection. We also present a limited memory quasi-Newton method which is a special version of our general algorithm. The presented algorithms have strong global convergence properties, in particular they identify constraints active at a solution in a finite number of iterations. We believe that they are competitive to the L-BFGS-B method and present some numerical results which support our claim.     

Finding Symmetry Groups of Some Quadratic Programming Problems

Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a knowledge of the symmetries may help decrease the problem dimension, reduce the size of the search space by means of linear cuts. While the previous studies of symmetries in the mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study a special case of the quadratic programming problem, where the objective function and constraints are given by quadratic forms. We formulate conditions, which allow us to transform the original problem to a new system of coordinates, such that the symmetries may be sought only among orthogonal transformations. In particular, these conditions are satisfied if the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. We describe the structure and some useful properties of the group of symmetries of the problem. Besides that, the methods of detection of such symmetries are outlined for different special cases as well as for the general case.     

无严格互补松驰条件的序列线性方程组新算法

该文通过构造特殊形式的有效集来逼近KKT点处的有效集，给出了一个任意初始点下的序列线性方程组新算法，并证明了该算法在没有严格互补松驰条件的情况下具有全局收敛性和一步超线性收敛性。      

一个线性约束优化问题的广义梯度投影法

本文对线性约束优化问题提出了一个新的广义梯度投影法，该算法采用了非精确线性搜索，并在每次迭代运算中结合了广义投影矩阵和变尺度方法的思想确定其搜索方向．在通常的假设条件下，证明了该算法的整体收敛性和超线性收敛速度．     

Balance constraints reduction of large-scale linear programming problems

This paper describes a method and the corresponding algorithms for simplification of large-scale linear programming models. It consists of the elimination of the balance constraints (i.e. constraints with zero RHS term). The idea is to apply some linear transformations to the original problem in order to nullify the balance constraints. These transformations are able to simultaneously eliminate more balance rows. The core of this contribution is the introduction of the reduction matrix and the associated theorems on the equivalent linear programs (original and reduced). The numerical experiments with this method of simplification proved this approach to be beneficial for a large class of LP problems.This research work was done while the first author was at Duisburg University, Mess-, Steuer und Regelungstechnik, Germany, under the greatly appreciated financial assistance given by the Alexander-von-Humboldt Foundation.     

Hölder Continuity of Adjoint States and Optimal Controls for State Constrained Problems

We investigate Hölder regularity of adjoint states and optimal controls for a Bolza problem under state constraints. We start by considering any optimal solution satisfying the constrained maximum principle in its normal form and we show that whenever the associated Hamiltonian function is smooth enough and has some monotonicity properties in the directions normal to the constraints, then both the adjoint state and optimal trajectory enjoy Hölder type regularity. More precisely, we prove that if the state constraints are smooth, then the adjoint state and the derivative of the optimal trajectory are Hölder continuous, while they have the two sided lower Hölder continuity property for less regular constraints. Finally, we provide sufficient conditions for Hölder type regularity of optimal controls.     

Confidence regions in a multivariate regression model with constraints II

The multivariate model, where not only parameters of the mean value of the observation matrix, but also some other parameters occur in constraints, is considered in the paper. Some basic inference is presented under the condition that the covariance matrix is either unknown, or partially unknown, or known. Supported by the grant of the Council of Czech Republic MSM 6 198 959 214.     

The equal award principle in problems with constraints and claims

In this paper we study how, under the equal award principle, to distribute a resource among different agents with a claim on it, when there are some constraints in the problem. Some properties of the rule are given as well as an axiomatic characterisation.     

Global minimization of rational functions and the nearest GCDs

This paper discusses the global minimization of rational functions with or without constraints. We propose sum of squares relaxations to solve these problems, and study their properties. Some special features are discussed. First, we consider minimization of rational functions without constraints. Second, as an application, we show how to find the nearest common divisors of polynomials via unconstrained minimization of rational functions. Third, we discuss minimizing rational functions under some constraints which are described by polynomials.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.     

Dual approaches to finite element model updating

The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods.