Role of copositivity in optimality criteria for nonconvex optimization problems

Second-order necessary and sufficient conditions for local optimality in constrained optimization problems are discussed. For global optimality, a criterion recently developed by Hiriart-Urruty and Lemarechal is thoroughly examined in the case of concave quadratic problems and reformulated into copositivity conditions.     

Robust truss topology optimization via semidefinite programming with complementarity constraints: a difference-of-convex programming approach

The robust truss topology optimization against the uncertain static external load can be formulated as mixed-integer semidefinite programming. Although a global optimal solution can be computed with a branch-and-bound method, it is very time-consuming. This paper presents an alternative formulation, semidefinite programming with complementarity constraints, and proposes an efficient heuristic. The proposed method is based upon the concave–convex procedure for difference-of-convex programming. It is shown that the method can often find a practically reasonable truss design within the computational cost of solving some dozen of convex optimization subproblems.     

A study of the difference-of-convex approach for solving linear programs with complementarity constraints

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.     

Testing of a large-scale network optimization program

This paper describes the experimental results of testing a large-scale program for solving minimum-cost network flow problems. With this program, general structure transshipment problems with over ten thousand nodes and thirty thousand arcs have been easily solved without resorting to auxiliary storage. The algorithm is a variant of the primal revised simplex method; the computer code is called LPNET illustrating the close connection between linear programming and network graphs. This approach substantially improves computer processing timeand core storage, especially for relatively large network problems. The results of these experiments are provided. It is emphasized that an organized experimental design and a detailed series of empirical tests are crucial for an efficient implementation.Research supported in part by TRW Systems Group and Harvard Business School.     

Perron–Frobenius property of copositive matrices, and a block copositivity criterion

Haynsworth and Hoffman proved in 1969 that the spectral radius of a symmetric copositive matrix is an eigenvalue of this matrix. This note investigates conditions which guarantee that an eigenvector corresponding to this dominant eigenvalue has no negative coordinates, i.e., whether the Perron–Frobenius property holds. Also a block copositivity criterion using the Schur complement is specified which may be helpful to reduce dimension in copositivity checks and which generalizes results proposed by Andersson et al. in 1995, and Johnson and Reams in 2005. Apparently, the latter five researchers were unaware of the more general results by the author precedingly published in 1987 and 1996, respectively.     

Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.     

Semi-Supervised Learning with the help of Parzen Windows

Semi-Supervised Learning is a family of machine learning techniques that make use of both labeled and unlabeled data for training, typically a small amount of labeled data with a large number of unlabeled data. In this paper we propose a Semi-Supervised regression algorithm by means of density estimator, generated by Parzen Windows functions under the framework of Semi-Supervised Learning. We conduct error analysis by capacity independent technique and obtain some satisfactory learning rates in terms of regularity of the target function and the decay condition on the marginal distribution near the boundary.     

判定3,4或5阶对称矩阵偕正性的算法

文献[1]给出了判定阶数不大于5的对称矩阵偕正性的充分必要条件.本文在此基础上,进一步给出了它们严格偕正的条件,并提出了三个算法,它们能够用来有效地判定3,4,5阶对称矩阵严格偕正、偕正或非偕正.     

Testing the topographical global initialization strategy in the framework of an unconstrained optimization method

In general, classical iterative algorithms for optimization, such as Newton-type methods, perform only local search around a given starting point. Such feature is an impediment to the direct use of these methods to global optimization problems, when good starting points are not available. To overcome this problem, in this work we equipped a Newton-type method with the topographical global initialization strategy, which was employed together with a new formula for its key parameter. The used local search algorithm is a quasi-Newton method with backtracking. In this approach, users provide initial sets, instead of starting points. Then, using points sampled in such initial sets (merely boxes in \({\mathbb {R}}^{n}\)), the topographical method selects appropriate initial guesses for global optimization tasks. Computational experiments were performed using 33 test problems available in literature. Comparisons against three specialized methods (DIRECT, MCS and GLODS) have shown that the present methodology is a powerful tool for unconstrained global optimization.     

Pattern recognition with the help of quadratic discriminant functions

The problem of pattern recognition with the help of spherical and elliptic discriminant functions is studied; in so doing the pattern of an object is assumed to be a vector of its characters from a finite-dimensional Euclidean space. Using a conformal mapping of a punctured sphere onto the plane as well as the inversion transformation, a criterion for the error-free recognition of two sets containing a finite number of points of training samples is obtained with the help of spherical discriminant functions. An algorithm for solving approximately a problem of construction of an ellipsoid of the minimal volume containing a given finite set of points is described. Bibliography: 5 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 80, 1996, pp. 90–105.     

Quick estimation of escape rate with the help of fractal dimension

The non-linearity caused by the application of digital control may lead to transient chaotic behaviour. In the present paper, we analyse a simple model of a digitally controlled mechanical system with dry friction, which may perform transient chaotic vibrations. As a consequence of the digital effects, the behaviour of this system can be described by a 1D piecewise linear map. The fractal dimension of the so-called chaotic repeller set is calculated and the results are used for the quick estimation of the mean lifetime of chaotic transients.     

Classification of multidimensional normal aggregates with the help of potential functions

Classification tests are constructed and their asymptotic equivalence with an optimal Bayes decision rule is shown. A sharper estimate of the upper bound of the probabilistic error classification is found.Translated from Staticheskie Metody, pp. 3–11, 1978.     

Estimation of a translation parameter with the help of order statistics

Investigation of the asymptotic behavior of estimates of the translational parameter with the help of linear combinations of order statistics for Symmetrie distributions.Translated from Staticheskie Metody, pp. 116–121, 1978.The author thanks Yu. N. Tyurin for his discussion of the results and helpful comments.     

On the construction of bimodule resolutions with the help of the Happel lemma

A criterion for the sequence obtained with the help of Happel’s lemma to be a minimal bimodule projective resolution is proved. This criterion is used to construct a bimodule resolution for a family of self-injective algebras of tree class D ₄. Bibliography: 6 titles.