PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerating the DC algorithm for smooth functions

Francisco J. Aragón Artacho, Ronan M. T. Fleming, Phan T. Vuong

arXiv:1507.07375v2math.OCq-bio.MN

TL;DR

Finding steady states in biochemical reaction networks can be formulated as smooth DC minimization, but DCA may converge slowly. The paper introduces BDCA, combining DCA with a line search from the DCA point, and reports faster performance than DCA on biochemical models.

  • Problem

    DCA can converge slowly on biochemical steady-state problems, where speed matters for networks with hundreds or thousands of variables.

    Source: §1 · p. 3

  • Method

    BDCA computes a DCA point and uses the DCA direction for an Armijo line search starting from that point.

    Source: §1 · p. 2

  • Results

    On biochemical models, DCA needed five times more iterations on average and BDCA ran more than four times faster at the same accuracy.

    Source: §1 · p. 3, §6 · p. 19

  • Takeaways & Limitations

    Biochemical reaction-network steady states can be formulated as DC minimization, and real-analytic objectives in this setting satisfy the Łojasiewicz property.

    Source: §1 · p. 3

    For nonsmooth functions, the direction may be an ascent direction at the DCA point, so the proposed line-search step may not be generally extended.

    Source: §3 · p. 7

Abstract

from arXiv · show

We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the Lojasiewicz property of the objective function. We apply our algorithms to a class of smooth DC programs arising in the study of biochemical reaction networks, where the objective function is real analytic and thus satisfies the Lojasiewicz property. Numerical tests on various biochemical models clearly show that our algorithms outperforms DCA, being on average more than four times faster in both computational time and the number of iterations. Numerical experiments show that the algorithms are globally convergent to a non-equilibrium steady state of various biochemical networks, with only chemically consistent restrictions on the network topology.

1 Introduction

The paper develops boosted DC algorithms that add a line search to DCA and analyzes their convergence for smooth DC objectives. It motivates the approach with biochemical steady-state problems and reports faster numerical performance than DCA.

1 Introduction

  • BDCA computes the DCA point, then uses the DCA direction for an Armijo line search starting from that point, where the direction is descent for the objective there.Two variants use backtracking directly or quadratic interpolation with backtracking.Source: §1 · p. 2
  • The new line-search scheme is for smooth functions: for nonsmooth functions, the direction may be an ascent direction at the DCA point.The paper contrasts its approach with Fukushima–Mine's line search, which starts at the previous iterate.Source: §1 · p. 2
  • Although DCA is often valued for avoiding line searches, the authors argue that line search can improve performance even on high-dimensional problems.The motivation is slow DCA convergence on biochemical models with hundreds or thousands of variables.Source: §1 · pp. 2–3
  • The paper proves convergence and analyzes convergence rates under the objective's Łojasiewicz property.Real-analytic objective functions satisfy this property.Source: §1 · p. 3
  • On biochemical network models, BDCA needed five times fewer iterations on average and ran more than four times faster than DCA at the same accuracy.The objective functions in these applications are real analytic and satisfy the Łojasiewicz property used in the convergence analysis.Source: §1 · p. 3

2 Preliminaries

The preliminaries establish the function classes, convergence property, and iterative schemes used in the paper's DC optimization analysis.

2 Preliminaries

  • The section establishes notation and recalls convexity, strong convexity, coercivity, and Lipschitz continuity.It also defines local Lipschitz continuity.Source: §2 · pp. 3–4
  • Recon 2, cited as a comprehensive human-metabolism model for computational modeling, contains more than 4,000 molecular species and 7,000 reversible elementary reactions.Source: §2 · p. 3
  • The preliminaries state that differentiable convexity is equivalent to monotonicity of the gradient, with strong versions corresponding as well..Source: §2 · p. 4
  • Real-analytic functions satisfy the Łojasiewicz property with an exponent θ in [0,1), which the paper uses in its convergence analysis.The section introduces the property and real analyticity before stating this result.Source: §2 · p. 4
  • The DC objective is represented as a difference of convex functions, and adding the same quadratic term to both yields strongly convex components without changing their difference.The section also situates the problem among composite and DC functions.Source: §2 · p. 4
  • DCA linearizes the concave part, minimizes the resulting convex subproblem to obtain the next iterate, and stops when that point equals the current iterate.The subproblem has a unique solution under the stated strongly convex formulation.Source: §2 · pp. 4–5
  • Fukushima–Mine adds an Armijo line search along the DCA direction; when its step size is one, its iterate coincides with DCA's.The section states that this coincidence is guaranteed when α ≤ ρ.Source: §2 · p. 5

3 Boosted DC Algorithms

This section presents boosted DC algorithms that combine DCA with line search, using quadratic interpolation to guide the search. It establishes convergence guarantees and examines their use in finding zeros of DC-function systems, including local linear convergence under a nonsingularity condition.

3 Boosted DC Algorithms

  • BDCA-Backtracking solves the DCA subproblem, then backtracks along its direction from the computed point to select the next iterate.The line search reduces its step size until the objective satisfies an Armijo-type decrease condition.Source: §3 · p. 5
  • For differentiable g, dk is a descent direction for φ at yk, enabling a larger decrease than the DCA update.When ρ > α, BDCA-Backtracking's backtracking step terminates finitely.Source: §3 · pp. 6–7
  • If g is not differentiable, dk may instead be an ascent direction, so the backtracking step can loop indefinitely.The paper gives an example where y0 is a global minimum but d0 is an ascent direction.Source: §3 · p. 7
  • Unlike Fukushima–Mine, BDCA-Backtracking searches positive steps from yk for a decrease from φ(yk), rather than nonpositive steps from xk.Its direction is the same, but the paper states that its step choice yields a larger decrease than DCA, which uses λ = 0.Source: §3 · p. 7
  • With locally Lipschitz ∇g and the Łojasiewicz property, any cluster point of BDCA-Backtracking's iterates is the limit of the whole sequence and is stationary.The theorem also gives finite-step convergence when θ = 0 and linear convergence in a stated regime.Source: §3 · pp. 10, 12
  • In Example 3.1, the optimal step is λopt = 25/24 with x1 = 1, the global minimizer of φ.The figure illustrates the additional decrease obtained by taking a positive step from yk.Source: Figure 1 · p. 13, §3 · p. 13
  • BDCA-Quadratic Interpolation with Backtracking uses a quadratic approximation to guide step selection and inherits Theorem 3.1's convergence statements.The approximation uses φ(yk), its directional derivative, and φ(yk + λ̄dk); its step sizes are bounded above and below by constants.Source: §3 · pp. 13–14
  • The cheaper quadratic interpolation using φ(xk) instead of φ(yk + λ̄dk) usually fits φk more poorly, as illustrated for Example 3.1.This alternative avoids computing φk(λ̄).Source: §3 · p. 14, Figure 2 · p. 14
  • For the functions in Section 4, the cubic model usually fits φk worse than the quadratic model.The passage contrasts the cubic function with the quadratic function ϕk in (24).Source: §3 · p. 15
  • Algorithms 2 and 3 can also work well when Step 2 is replaced by a proximal step with positive constants ck.Source: §3 · p. 15
  • A system of DC-function equations can be reformulated as smooth DC minimization, allowing either DCA or BDCA to find a solution.The construction uses convex functions f1 and f2 formed from nonnegative convex components of p and c.Source: §3 · p. 15
  • If an accumulation point has a nonsingular Jacobian, it is a zero of the system, and the iterates converge linearly to it under the stated smoothness and Łojasiewicz conditions.The objective has Łojasiewicz exponent θ = 1/2 at that point; the local Lipschitz continuity of ∇g supports the linear-convergence guarantee.Source: §3 · p. 15

4 A DC problem in biochemistry

The section formulates biochemical steady-state finding as minimizing a smooth DC objective. It connects the model’s reaction kinetics and mass-conservation assumptions to convergence properties and their limits.

4 A DC problem in biochemistry

  • Forward and reverse elementary reaction rates use mass-action kinetics, while the network is assumed to conserve mass and has specified stoichiometric structure.The model assumes nonnegative kinetic parameters; each row of F and R has at least one nonzero entry, and each column of R − F has at least two, usually three.Source: §4 · p. 16
  • A steady state is a zero of f, so finding one is recast as minimizing the DC function φ(x) = f1(x) − f2(x), equivalent to minimizing ∥f(x)∥².The concentrations are represented on a logarithmic scale, and a zero of f corresponds to a steady state of the dynamical equation.Source: §4 · pp. 16–17
  • The DC components are smooth and convex, and the resulting objective is real analytic, so it satisfies the Łojasiewicz property.The analyticity argument uses nonnegative integer stoichiometric entries.Source: §4 · pp. 16–17
  • For bounded iterates, the stated convergence results apply, but mass conservation prevents guaranteeing linear convergence for these biochemical problems.Mass conservation implies that ∇f(x) is singular for every x, so the linear-convergence reasoning from Example 3.2 does not apply.Source: §4 · p. 17
  • If f is strictly duplomonotone, any stationary point of ∥f(x)∥² is a steady state; experiments support this property for many networks.The passage describes the empirical support as a hypothesis, not a universal guarantee.Source: §4 · p. 17

5 Numerical Experiments

The experiments compare DCA with BDCA, particularly Algorithm 3, on biochemical-network steady-state problems. They examine convergence across models and values of the parameter ρ.

5 Numerical Experiments

  • The experiments used MATLAB R2014b on a desktop Intel Core i7-4770 CPU with 16 GB RAM under Windows 8.1 64-bit.The subproblems were approximately solved with fminunc using the trust-region algorithm and function and variable tolerances of 1e-8.Source: §5 · p. 18
  • For the 14-model comparison, the authors report results for BDCA with quadratic interpolation (Algorithm 3) against DCA, using α = 0.4, β = 0.5, λ̄ = 50, and ρ = 100.Algorithm 3 is reported because it normally gives better results than Algorithm 2 for biochemical models.Source: §5 · p. 18
  • For large models, ρ values between 50 and 100 normally accelerated the convergence of both DCA and BDCA in the reported experiments.The authors observed that DCA's behavior was usually similar for ρ between 0 and 100; this was not the case for all reported comparisons.Source: §5 · p. 18
  • The comparisons cover Ecoli_core, iJO1366, and the human metabolism model Recon205_20150128, with model sizes specified for each.Figure 3 compares DCA at ρ = 0 and 100 with BDCA Algorithms 2 and 3 at ρ = 100; Figure 4 compares DCA and BDCA Algorithm 3 at different ρ values.Source: Figure 3 · p. 18, Figure 4 · p. 19

6 Concluding Remarks

The paper introduces BDCA, which combines DCA with a line search using the DCA-generated point to define a descent direction. Across biochemical-network models, BDCA achieves the same objective decrease with fewer iterations and less time than DCA.

6 Concluding Remarks

  • BDCA uses the DCA-generated point to define a line-search direction that descends at that point, and every cluster point is stationary.Under the Łojasiewicz property, the algorithms are globally convergent and have established convergence rates; the descent-direction result does not directly generalize to nonsmooth functions.Source: §6 · p. 19
  • BDCA required, on average, five times fewer iterations and ran more than four times faster than DCA while achieving the same decrease in the DC function.The slowest BDCA instance was still at least three times faster than DCA.Source: §6 · p. 19
  • The experiments evaluate steady-state finding on biochemical reaction-network models, including random kinetic parameters and initial points.For each initial point, BDCA ran for 1000 iterations, while DCA ran until it reached the same objective value as BDCA.Source: §6 · pp. 19–20
Loading 1507.07375v2…