primal-dual interior-point method

An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

  • Takashi Tsuchiya
  • Yu Xia
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more

    Generating and Measuring Instances of Hard Semidefinite Programs, SDP

  • Hua Wei
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

    A primal-dual interior point method for nonlinear optimization over second order cones

  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming Tags , ,

    In this paper, we are concerned with nonlinear minimization problems with second order cone constraints. A primal-dual interior point method is proposed for solving the problems. We also propose a new primal-dual merit function by combining the barrier penalty function and the potential function within the framework of the line search strategy, and show the … Read more

    Interior-Point l_2 Penalty Methods for Nonlinear Programming with Strong Global Convergence Properties

  • Lifeng Chen
  • Donald Goldfarb
    • Categories Nonlinear Optimization Tags , , , , ,

    We propose two line search primal-dual interior-point methods that approximately solve a equence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an $\ell_2$-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, … Read more

    Constraint Reduction for Linear Programs with Many Inequality Constraints

  • Pierre-Antoine Absil
  • André L. Tits
  • William P. Woessner
    • Categories Linear Programming Tags , , , , ,

    Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce … Read more

    Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more

    An (\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems

  • Wenbao Ai
  • Shuzhong Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more

    An Adaptive Self-Regular Proximity Based Large-Update IPM for LO

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best … Read more

    An interior-point L1-penalty method for nonlinear optimization

  • Nicholas I. M. Gould
  • Dominique Orban
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization Tags , , ,

    A mixed interior/exterior-point method for nonlinear programming is described, that handles constraints by an L1-penalty function. A suitable decomposition of the penalty terms and embedding of the problem into a higher-dimensional setting leads to an equivalent, surprisingly regular, reformulation as a smooth penalty problem only involving inequality constraints. The resulting problem may then be tackled … Read more

    A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Graphs and Matroids, Parallel Algorithms, Semi-definite Programming Tags , , , , ,

    A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more