Zhaosong Lu

An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more

    Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Arkadi Nemirovski
    • Categories Semi-definite Programming Tags , ,

    In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more

    A modified nearly exact method for solving low-rank trust region subproblem

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper we present a modified nearly exact (MNE) method for solving low-rank trust region (LRTR) subproblem. The LRTR subproblem is to minimize a quadratic function, whose Hessian is a positive diagonal matrix plus explicit low-rank update, subject to a Dikin-type ellipsoidal constraint, whose scaling matrix is positive definite and has the similar structure … Read more

    An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex QP

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    In this paper we develop an interior-point primal-dual long-step path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of an iterative (linear system) solver. We propose a new linear system, which we refer to as the \emph{augmented normal equation} (ANE), to determine the primal-dual search directions. Since the condition number … Read more

    Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more

    Error bounds and limiting behavior of weighted paths associated with the SDP map ^{1/2}SX^{1/2}$

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown … Read more