Linear, Cone and Semidefinite Programming

Three-dimensional quasi-static frictional contact by using second-order cone linear complementarity problem

  • Y. Kanno
  • J.A.C. Martins
  • A. Pinto da Costa
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Second-Order Cone Programming

    A new formulation is presented for the three-dimensional incremental quasi-static problems with unilateral frictional contact. Under the assumptions of small rotations and small strains, a Second-Order Cone Linear omplementarity Problem (SOCLCP) is formulated, which consists of complementarity conditions defined by the bilinear functions and the second-order cone constraints. The equilibrium configurations are obtained by using … Read more

    On Implementing Self-Regular Proximity Based Feasible IPMs

  • Jiming Peng
  • Tamás Terlaky
  • Guoqing Zhang
  • Xiaohang Zhu
    • Categories Linear Programming, Optimization Software Benchmark Tags , ,

    Self-regular based interior point methods present a unified novel approach for solving linear optimization and conic optimization problems. So far it was not known if the new Self-Regular IPMs can lead to similar advances in computational practice as shown in the theoretical analysis. In this paper, we present our experiences in developing the software package … Read more

    Semidefinite descriptions of cones defining spectral mask constraints

  • Leonid Faybusovich
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , ,

    We discuss in detail an additive structure of cones of trigonometric polynomials nonnegative on the union of finite number of pairwise disjoint segments of the unit circle. We derive new descriptions of these cones in terms of semidefinite constraints. We explain the results of M. Krein and A. Nudelman providing a description of dual cones … Read more

    A matrix generation approach for eigenvalue optimization

  • Jean-Louis Goffin
  • Mohammad R. Oskoorouchi
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We study the extension of a column generation technique to eigenvalue optimization. In our approach we utilize the method of analytic center to obtain the query points at each iteration. A restricted master problem in the primal space is formed corresponding to the relaxed dual problem. At each step of the algorithm, an oracle is … Read more

    Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

  • Bharath Kumar Rangarajan
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd, which established … Read more

    A new notion of weighted centers for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties — 1) each choice of weights uniquely determines a pair of primal-dual weighted … Read more

    Hyperbolic Programs, and Their Derivative Relaxations

  • James Renegar
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We study the algebraic and facial structures of hyperbolic programs, and examine natural relaxations of hyperbolic programs, the relaxations themselves being hyperbolic programs. CitationTR 1406, School of Operations Research, Cornell University, Ithaca, NY 14853, U.S., 3/04ArticleDownload View PDF

    Semidefinite Approximations for Global Unconstrained Polynomial Optimization

  • Dorina Jibetean
  • Monique Laurent
    • Categories Global Optimization Theory, Semi-definite Programming, Unconstrained Optimization Tags ,

    We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more

    Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more

    A moment approach to analyze zeros of triangular polynomial sets

  • Jean-Bernard Lasserre
    • Categories Nonlinear Optimization, Other Topics, Semi-definite Programming

    Let $I=(g_1,…, g_n)$ be a zero-dimensional ideal of $ \R[x_1,…,x_n]$ such that its associated set $G$ of polynomial equations $g_i(x)=0$ for all $i=1,…,n$, is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in the radical ideal of $I$. We also provide a necessary and sufficient (numerical) condition for … Read more