central path

On the Convergence of the Entropy-Exponential Penalty Trajectories and Generalized Proximal Point Methods in Semidefinite Optimization

  • Orizon Pereira Ferreira
  • Paulo Roberto Oliveira
  • R. C. M. Silva
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. As an application, the proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered, and the convergence of primal and dual sequences is proved. CitationJournal of Global … Read more

    Central Paths in Semidefinite Programming, Generalized Proximal Point Method and Cauchy Trajectories in Riemannian Manifolds

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Paulo Roberto Oliveira
  • R. C. M. Silva
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The relationships among central path in the context of semidefinite programming, generalized proximal point method and Cauchy trajectory in Riemannian manifolds is studied in this paper. First it is proved that the central path associated to the general function is well defined. The convergence and characterization of its limit point is established for functions satisfying … Read more

    A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , , , , , , , ,

    The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

    A NEW BARRIER FOR A CLASS OF SEMIDEFINITE PROBLEMS

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Semi-definite Programming Tags , , ,

    We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and … Read more

    Invariance and efficiency of convex representations

  • Chek Beng Chua
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    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 … Read more

    Asymptotic behavior of the central path for a special class of degenerate SDP problems

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \|X_{\cT}(\nu)\|, \|S_{\cT}(\nu)\| \} … Read more

    Asymptotic Behavior of Continuous Trajectories for Primal-Dual Potential-Reduction Methods

  • Reha H. Tütüncü
    • Categories Linear Programming Tags , , , ,

    This article considers continuous trajectories of the vector fields induced by primal-dual potential-reduction algorithms for solving linear programming problems. It is known that these trajectories converge to the analytic center of the primal-dual optimal face. We establish that this convergence may be tangential to the central path, tangential to the optimal face, or in between, … Read more

    Characterization of the limit point of the central path in semidefinite programming

  • Anders Forsgren
  • Göran Sporre
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    In linear programming, the central path is known to converge to the analytic center of the set of optimal solutions. Recently, it has been shown that this is not necessarily true for linear semidefinite programming in the absence of strict complementarity. The present paper deals with the formulation of a convex problem whose solution defines … Read more

    Analyticity of the central path at the boundary point in semidefinite programming

  • Margaréta Halická
    • Categories Semi-definite Programming Tags , ,

    In this paper we study the limiting behavior of the central path for semidefinite programming. We show that the central path is an analytic function of the barrier parameter even at the limit point, provided that the semidefinite program has a strictly complementary solution. A consequence of this property is that the derivatives – of … Read more