Zhaosong Lu

Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Ming Yuan
    • Categories Convex Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more

    Smooth Optimization Approach for Covariance Selection

  • Zhaosong Lu
    • Categories Convex and Nonsmooth Optimization, Statistics Tags , ,

    In this paper we study a smooth optimization approach for solving a class of non-smooth {\it strongly} concave maximization problems. In particular, we apply Nesterov’s smooth optimization technique \cite{Nest83-1,Nest05-1} to their dual counterparts that are smooth convex problems. It is shown that the resulting approach has $\cO(1/{\sqrt{\epsilon}})$ iteration complexity for finding an $\epsilon$-optimal solution to … Read more

    A New Cone Programming Approach for Robust Portfolio Selection

  • Zhaosong Lu
    • Categories Applications - Science and Engineering, Finance and Economics, Robust Optimization Tags ,

    The robust portfolio selection problems have recently been studied by several researchers (e.g., see \cite{GoIy03,ErGoIy04,HaTu04,TuKo04}). In their work, the “separable” uncertainty sets of the problem parameters (e.g., mean and covariance of the random returns) were considered. These uncertainty sets share two common drawbacks: i) the actual confidence level of the uncertainty set is unknown, and … Read more

    Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

  • Guanghui Lan
  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more

    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