An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming

We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:1–19, 1993) holds.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Smooth Convex Approximation to the Maximum Eigenvalue Function

In this paper, we consider smooth convex approximations to the maximum eigenvalue function. To make it applicable to a wide class of applications, the study is conducted on the composite function of the maximum eigenvalue function and a linear operator mapping ^m to , the space of n-by-n symmetric matrices. The composite function in turn is the natural objective function of minimizing the maximum eigenvalue function over an affine space in . This leads to a sequence of smooth convex minimization problems governed by a smoothing parameter. As the parameter goes to zero, the original problem is recovered. We then develop a computable Hessian formula of the smooth convex functions, matrix representation of the Hessian, and study the regularity conditions which guarantee the nonsingularity of the Hessian matrices. The study on the well-posedness of the smooth convex function leads to a regularization method which is globally convergent.     

The difference between doubly nonnegative and completely positive matrices

The convex cone of n×n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n×n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5×5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5×5 CP matrices.     

General Existence Theorem of Zero Points

Let X be a nonempty, compact, convex set in and let be an upper semicontinuous mapping from X to the collection of nonempty, compact, convex subsets of . It is well known that such a mapping has a stationary point on X; i.e., there exists a point X such that its image under has a nonempty intersection with the normal cone of X at the point. In the case where, for every point in X, it holds that the intersection of the image under with the normal cone of X at the point is either empty or contains the origin 0 ⁿ , then must have a zero point on X; i.e., there exists a point in X such that 0 ⁿ lies in the image of the point. Another well-known condition for the existence of a zero point follows from the Ky Fan coincidence theorem, which says that, if for every point the intersection of the image with the tangent cone of X at the point is nonempty, the mapping must have a zero point. In this paper, we extend all these existence results by giving a general zero-point existence theorem, of which the previous two results are obtained as special cases. We discuss also what kind of solutions may exist when no further conditions are stated on the mapping . Finally, we show how our results can be used to establish several new intersection results on a compact, convex set.     

Integral Representations for Continuous Linear Functionals in Operator-Initiated Topologies

On a given cone (resp. vector space) we consider an initial topology and order induced by a family of linear operators into a second cone which carries a locally convex topology. We prove that monotone linear functionals on which are continuous with respect to this initial topology may be represented as certain integrals of continuous linear functionals on . Based on the Riesz representation theorem from measure theory, we derive an integral version of the Jordan decomposition for linear functionals on ordered vector spaces.     

A nonsmooth algorithm for cone-constrained eigenvalue problems

We study several variants of a nonsmooth Newton-type algorithm for solving an eigenvalue problem of the form

$K\ni x\perp(Ax-\lambda Bx)\in K^{+}.$

Such an eigenvalue problem arises in mechanics and in other areas of applied mathematics. The symbol K refers to a closed convex cone in the Euclidean space ? ⁿ and (A,B) is a pair of possibly asymmetric matrices of order n. Special attention is paid to the case in which K is the nonnegative orthant of ? ⁿ . The more general case of a possibly unpointed polyhedral convex cone is also discussed in detail.

     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

Volumes of symmetric random polytopes

We consider the moments of the volume of the symmetric convex hull of independent random points in an n-dimensional symmetric convex body. We calculate explicitly the second and fourth moments for n points when the given body is (and all of the moments for the case q = 2), and derive from these the asymptotic behavior, as , of the expected volume of a random simplex in those bodies. Received: 5 February 2003     

Yuan's alternative theorem and the maximization of the minimum eigenvalue function

LetA ₁ andA ₂ be two symmetric matrices of ordern×n. According to Yuan, there exists a convex combination of these matrices which is positive semidefinite, if and only if the functionxR ⁿ max {x ^T A ₁ x,x ^T A ₂ x} is nonnegative. We study the case in which more than two matrices are involved. We study also a related question concerning the maximization of the minimum eigenvalue of a convex combination of symmetric matrices.This research was partially supported by Dirección General de Investigación Científica y Técnica (DGICYT) under Project PB92-0615.     

Additive Properties of the Dufresne Laws and Their Multivariate Extension

The Dufresne laws are defined on the positive line by their Mellin transform , where the a _i and b _j are positive numbers, with pq, and where (x) _s denotes (x+s)/(x). Typical examples are the laws of products of independent random variables with gamma and beta distributions. They occur as the stationary distribution of certain Markov chains (X _n) on defined by where X ₀, (A ₁, B ₁),..., (A _n, B _n),... are independent. This paper gives some explicit examples of such Markov chains. One of them is surprisingly related to the golden number. While the properties of the product of two independent Dufresne random variables are trivial, we give several properties of their sum: the hypergeometric functions are the main tool here. The paper ends with an extension of these Dufresne laws to the space of positive definite matrices and to symmetric cones.     

Primal and polar approach for computing the symmetric diagonally dominant projection

We solve the problem of minimizing the distance from a given matrix to the cone of symmetric and diagonally dominant matrices with positive diagonal (SDD⁺). Using the extreme rays of the polar cone we project onto the supporting hyperplanes of the faces of SDD⁺ and then, applying the cyclic Dykstra's algorithm, we solve the problem. Similarly, using the extreme rays of SDD⁺ we characterize the projection onto the polar cone, which also allows us to obtain the projection onto SDD⁺ by means of the orthogonal decomposition theorem for convex cones. In both cases the symmetry and the sparsity pattern of the given matrix are preserved. Preliminary numerical experiments indicate that the polar approach is a promising one. Copyright © 2002 John Wiley & Sons, Ltd.     

Alternating convex projection methods for discrete-time covariance control design

The problem of designing a controller for a linear, discretetime system is formulated as a problem of designing an appropriate plant-state covariance matrix. Closed-loop stability and multiple-output performance constraints are expressed geometrically as requirements that the covariance matrix lies in the intersection of some specified closed, convex sets in the space of symmetric matrices. We solve a covariance feasibility problem to determine the existence and compute a covariance matrix to satisty assignability and output-norm performance constraints. In addition, we can treat a covariance optimization problem to construct an assignable covariance matrix which satisfies output performance constraints and is as close as possible to a given desired covariance. We can also treat inconsistent constraints, where we look for an assignable covariance which best approximates desired but unachievable output performance objectives; we call this the infeasible covariance optimization problem. All these problems are of a convex nature, and alternating convex projection methods are proposed to solve them, exploiting the geometric formulation of the problem. To this end, analytical expressions for the projections onto the covariance assignability and the output covariance inequality constraint sets are derived. Finally, the problem of designing low-order dynamic controllers using alternating projections is discussed, and a numerical technique using alternating projections is suggested for a solution, although convergence of the algorithm is not guaranteed in this case. A control design example for a fighter aircraft model illustrates the method.This research was completed while the first author was with the Space Systems Control Laboratory at Purdue University. Support from the Army Research Office Grant ARO-29029-EG is gratefully acknowledged.     

Isotone retraction cones in Hilbert spaces

A mapping is called isotone if it is monotone increasing with respect to the order induced by a pointed closed convex cone. Finding the pointed closed convex generating cones for which the projection mapping onto the cone is isotone is a difficult problem which was analyzed in Isac and Németh (1986, 1990, 1992) [1], [2], [3], [4] and [5]. Such cones are called isotone projection cones. In particular it was shown that any isotone projection cone is latticial (Isac (1990) [2]). This problem is extended by replacing the projection mapping with continuous retractions onto the cone. By introducing the notion of sharp mappings, it is shown that a pointed closed convex generating cone is latticial if and only if there is a continuous retraction onto the cone whose complement is sharp. Several particular cases are considered and examples are given.     

Description of a Class of Solids in ℝ3

Let be a compact convex body such that for each parallel projection onto any plane no two opposite faces of Q are projected strictly inside the projection of the entire Q. Then Q is either a cone, or a frustum of a trihedral pyramid, or a prism (possibly with nonparallel bases). Bibliography: 1 title.     

Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

A Markoff-type chain for the view-obstruction problem for spheres in ℝ4

In the view-obstruction problem, congruent, closed, convex bodies centred at the points in ⁿ are expanded uniformly until they block all rays from the origin into the open positive cone. The central problem is to determine the minimal blocking size. In the case of spheres of diameter 1, this value is denoted byv(n) and is known for dimensionsn=2,3. Here we show that and obtain a Markoff type chain of isolated extreme values.     

On a Class of Convex Sets and Functions

Given a convex subset C of ⁿ, the set-valued mapping C (where 0C is, by convention, the recession cone of C) is increasing on ₊ if and only if C contains the origin, and decreasing on ₊ if and only if C is contained in its recession cone. This simple fact enables us to define a binary operation which combines a concave or convex function on ^m with a convex subset of ⁿ to produce a convex subset of ^n+m. This binary operation is the set theoretic counterpart of a functional operation introduced by the author. In this paper, we present a detailed study of the class of convex subsets which are contained in their recession cones, and we establish some remarkable properties of our binary operation.Mathematics Subject Classifications (2000) 26A51, 26B25, 26E25.     

Optimizing a polyhedral-semidefinite relaxation of completely positive programs

It has recently been shown (Burer, Math Program 120:479–495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPs while simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.