Some applications of optimization in matrix theory

We apply a recent characterization of optimality for the abstract convex program with a cone constraint to three matrix theory problems: (1) a generalization of Farkas's lemma; (2) paired duality in linear programming over cones; (3) a constrained matrix best approximation problem. In particular, these results are not restricted to polyhedral or closed cones.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

No Gap Second-Order Optimality Conditions for Circular Conic Programs

In this article, we study the second-order optimality conditions for a class of circular conic optimization problem. First, the explicit expressions of the tangent cone and the second-order tangent set for a given circular cone are derived. Then, we establish the closed-form formulation of critical cone and calculate the “sigma” term of the aforementioned optimization problem. At last, in light of tools of variational analysis, we present the associated no gap second-order optimality conditions. Compared to analogous results in the literature, our approach is intuitive and straightforward, which can be manipulated and verified. An example is illustrated to this end.     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

Conic formulations of graph homomorphisms

Given graphs X and Y, we define two conic feasibility programs which we show have a solution over the completely positive cone if and only if there exists a homomorphism from X to Y. By varying the cone, we obtain similar characterizations of quantum/entanglement-assisted homomorphisms and three previously studied relaxations of these relations. Motivated by this, we investigate the properties of these “conic homomorphisms” for general (suitable) cones. We also consider two generalized versions of the Lovász theta function, and how they interact with these conic homomorphisms. We prove analogs of several results on classical graph homomorphisms as well as some monotonicity theorems. We also show that one of the generalized theta functions is multiplicative on lexicographic and disjunctive graph products.     

Intersection probabilities and kinematic formulas for polyhedral cones

For polyhedral convex cones in \({\mathbb{R}^d}\), we give a proof for the conic kinematic formula for conic curvature measures, which avoids the use of characterization theorems. For the random cones defined as typical cones of an isotropic random central hyperplane arrangement, we find probabilities for non-trivial intersection, either with a fixed cone, or for two independent random cones of this type.     

Centers of sets with symmetry or cyclicity properties

We introduce an axiomatic formalism for the concept of the center of a set in a Euclidean space. Then we explain how to exploit possible symmetries and possible cyclicities in the set in order to localize its center. Special attention is paid to the determination of centers in cones of matrices. Despite its highly abstract flavor, our work has a strong connection with convex optimization theory. In fact, computing the so-called “incenter” of a solid closed convex cone is a matter of solving a nonsmooth convex optimization program. On the other hand, the concept of the incenter of a solid closed convex cone has a bearing on the complexity analysis and design of algorithms for convex optimization programs under conic constraints.     

Information Geometry and Interior-Point Algorithms in Semidefinite Programs and Symmetric Cone Programs

We develop an information geometric approach to conic programming. Information geometry is a differential geometric framework specifically tailored to deal with convexity, naturally arising in information science including statistics, machine learning and signal processing etc. First we introduce an information geometric framework of conic programming. Then we focus on semidefinite and symmetric cone programs. Recently, we demonstrated that the number of iterations of Mizuno–Todd–Ye predictor–corrector primal–dual interior-point methods is (asymptotically) expressed with an integral over the central trajectory called “the curvature integral”. The number of iterations of the algorithm is approximated surprisingly well with the integral even for fairly large linear/semidefinite programs with thousands of variables. Here we prove that “the curvature integral” admits a rigorous differential geometric expression based on information geometry. We also obtain an interesting information geometric global theorem on the central trajectory for linear programs. Together with the numerical evidence in the aforementioned work, we claim that “the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.”     

二阶锥规划的基于自协调指数核函数的原始-对偶内点算法

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.     

Optimality conditions for maximizations of set-valued functions

The maximization with respect to a cone of a set-valued function into possibly infinite dimensions is defined, and necessary and sufficient optimality conditions are established. In particular, an analogue of the Fritz John necessary optimality conditions is proved using a notion of derivative defined in terms of tangent cones.     

First order optimality conditions in vector optimization involving stable functions

We study a nonsmooth vector optimization problem with an arbitrary feasible set or a feasible set defined by a generalized inequality constraint and an equality constraint. We assume that the involved functions are nondifferentiable. First, we provide some calculus rules for the contingent derivative in which the stability (a local Lipschitz property at a point) of the functions plays a crucial role. Second, another calculus rules are established for steady functions. Third, necessary optimality conditions are stated using tangent cones to the feasible set and the contingent derivative of the objective function. Finally, some necessary and sufficient conditions are presented through Lagrange multiplier rules.     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Comments on: Farkas’ Lemma: three decades of generalizations for mathematical optimization

In these comments on the excellent survey by Dinh and Jeyakumar, we briefly discuss some recently developed topics and results on applications of extended Farkas’ lemma(s) and related qualification conditions to problems of variational analysis and optimization, which are not fully reflected in the survey. They mainly concern: Lipschitzian stability of feasible solution maps for parameterized semi-infinite and infinite programs with linear and convex inequality constraints indexed by arbitrary sets; optimality conditions for nonsmooth problems involving such constraints; evaluating various subdifferentials of optimal value functions in DC and bilevel infinite programs with applications to Lipschitz continuity of value functions and optimality conditions; calculating and estimating normal cones to feasible solution sets for nonlinear smooth as well as nonsmooth semi-infinite, infinite, and conic programs with deriving necessary optimality conditions for them; calculating coderivatives of normal cone mappings for convex polyhedra in finite and infinite dimensions with applications to robust stability of parameterized variational inequalities. We also give some historical comments on the original Farkas’ papers.     

Analytic centers and repelling inequalities

The new concepts of repelling inequalities, repelling paths, and prime analytic centers are introduced. A repelling path is a generalization of the analytic central path for linear programming, and we show that this path has a unique limit. Furthermore, this limit is the prime analytic center if the set of repelling inequalities contains only those constraints that “shape” the polytope. Because we allow lower dimensional polytopes, the proof techniques are non-standard and follow from data perturbation analysis. This analysis overcomes the difficulty that analytic centers of lower dimensional polytopes are not necessarily continuous with respect to the polytope's data representation. A second concept introduced here is that of the “prime analytic center”, in which we establish its uniqueness in the absence of redundant inequalities. Again, this is well known for full dimensional polytopes, but it is not immediate for lower dimensional polytopes because there are many different data representations of the same polytope, each without any redundant inequalities. These two concepts combine when we introduce ways in which repelling inequalities can interact.     

Construction of proximal distances over symmetric cones

Abstract

This paper is devoted to the study of proximal distances defined over symmetric cones, which include the non-negative orthant, the second-order cone and the cone of positive semi-definite symmetric matrices. Specifically, our first aim is to provide two ways to build them. For this, we consider two classes of real-valued functions satisfying some assumptions. Then, we show that its corresponding spectrally defined function defines a proximal distance. In addition, we present several examples and some properties of this distance. Taking into account these properties, we analyse the convergence of proximal-type algorithms for solving convex symmetric cone programming (SCP) problems, and we study the asymptotic behaviour of primal central paths associated with a proximal distance. Finally, for linear SCP problems, we provide a relationship between the proximal sequence and the primal central path.     

集值映射多目标规划的K-T最优性条件

讨论集值映射多目标规划(VP)的最优性条件问题.首先,在没有锥凹的假设下,利用集值映射的相依导数,得到了(VP)的锥--超有效解要满足的必要条件和充分条件.其次,在锥凹假设和比推广了的Slater规格更弱的条件下,给出了(VP)关于锥--超有效解的K--T型最优性必要条件和充分条件.