self-concordance

Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier

  • Robert M. Freund
  • Renbo Zhao
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P): F*:= min_x f(Ax) + h(x), where f is a \theta-logarithmically-homogeneous self-concordant barrier and the function h has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((Gap_0 + \theta + Var_h)\ln(\delta_0) + (\theta + Var_h)^2/\epsilon) … Read more

    Universal Barrier is n-Self-Concordant

  • Yin Tat Lee
  • Man-Chung Yue
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    This paper shows that the self-concordance parameter of the universal barrier on any n-dimensional proper convex domain is upper bounded by n. This bound is tight and improves the previous O(n) bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for s-concave distributions, which could … Read more

    Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss

  • Lin Xiao
  • Yuchen Zhang
    • Categories Convex Optimization, Statistics Tags , , , ,

    We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to … Read more

    Matrix monotonicity and self-concordance:how to handle quantum entropy in optimization problems

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Let $g$ be a continuously differentiable function whose derivative is matrix monotone on positive semi-axis. Such a function induces a function $\phi (x)=tr(g(x))$ on the cone of squares of an arbitrary Euclidean Jordan algebra. We show that $\phi (x) -\ln \det(x)$ is a self-concordant function on the interior of the cone. We also show that … Read more

    Composite Self-concordant Minimization

  • Volkan Cevher
  • Quoc Tran-Dinh
  • Anastasios Kyrillidis
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Statistics Tags , , , ,

    We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function endowed with a computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new … Read more

    Two theoretical results for sequential semidefinite programming

  • Rodrigo Garcés
  • Walter Gómez
  • Florian Jarre
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    We examine the local convergence of a sequential semidefinite programming approach for solving nonlinear programs with nonlinear semidefiniteness constraints. Known convergence results are extended to slightly weaker second order sufficient conditions and the resulting subproblems are shown to have local convexity properties that imply a weak form of self-concordance of the barrier subproblems. Citation Preprint, … Read more