PaperlayerView exact revision on arXiv

Source-linked AI summary

Disciplined Convex-Concave Programming

Xinyue Shen, Steven Diamond, Yuantao Gu, Stephen Boyd

arXiv:1604.02639v1math.OC

TL;DR

The paper addresses how to combine disciplined convex modeling with convex-concave heuristics while handling non-full function domains and boundary nondifferentiability. It introduces DCCP, proves that its domain-aware linearized problems remain convex and DCP-compatible, and discusses initialization for maintaining differentiability. The paper also reports a circle-packing instance with n = 14 circles covering 0.73 of the square.

  • Problem

    Penalty CCP can fail when an iterate leaves a function's domain, and linearization can fail at boundary points where the function is not differentiable.

  • Method

    The paper introduces DCCP and uses domain-restricted linearizations plus interior initialization to preserve convexity and ensure linearizations exist.

  • Results

    DCCP's domain-restricted linearized problem remains convex and satisfies DCP rules, while interior iterates guarantee that gradients exist.

  • Takeaways & Limitations

    DCCP provides a standard form in which nonconvex problems can be handled through automatically solvable DCP subproblems, subject to suitable initialization.

  • Takeaways & Limitations

    Finding an initial point in the domain's interior can be very hard, and the generic averaging heuristic can still produce a boundary point.

Abstract

from arXiv · show

In this paper we introduce disciplined convex-concave programming (DCCP), which combines the ideas of disciplined convex programming (DCP) with convex-concave programming (CCP). Convex-concave programming is an organized heuristic for solving nonconvex problems that involve objective and constraint functions that are a sum of a convex and a concave term. DCP is a structured way to define convex optimization problems, based on a family of basic convex and concave functions and a few rules for combining them. Problems expressed using DCP can be automatically converted to standard form and solved by a generic solver; widely used implementations include YALMIP, CVX, CVXPY, and Convex.jl. In this paper we propose a framework that combines the two ideas, and includes two improvements over previously published work on convex-concave programming, specifically the handling of domains of the functions, and the issue of nondifferentiability on the boundary of the domains. We describe a Python implementation called DCCP, which extends CVXPY, and give examples.

1 Disciplined convex-concave programming

DCCP combines DCP's curvature-aware modeling rules with CCP's heuristic treatment of nonconvex problems. Its standard form ensures that each linearized subproblem is a DCP program that can be converted to a cone program and solved by generic solvers.

  • Difference of convex programming: DC programs express objectives and inequalities as differences of convex functions, covering applications from signal processing and machine learning to computer vision and statistics.The class includes all C2 functions and special cases such as Boolean linear programs.
  • Difference of convex programming: CCP replaces concave terms with convex upper bounds around the current point, producing a tractable restriction of the original DC problem.Penalty CCP additionally addresses infeasibility heuristically through an increasing penalty on constraint violations.
  • Difference of convex programming: Penalty CCP convexifies each concave component by first-order linearization, solves the resulting penalized convex problem, increases the penalty parameter, and repeats until stopping.The method uses slack variables for constraint violations and updates τ by τk+1 := min(µτk, τmax).
  • Disciplined convex programming: DCP restricts objectives, relations, and compositions to expressions with verifiable curvature, enabling automatic conversion of conforming problems into cone programs.Its rules require convex objectives for minimization, affine equality sides, and curvature-compatible inequality sides.
  • Disciplined convex-concave programming: DCCP permits DCP-verified expressions even when the overall objective or constraints violate DCP convexity conditions, thereby including many nonconvex problems.DCCP contains DCP as a special case and supports examples such as maximizing a convex function or using nonaffine equality constraints.
  • Disciplined convex-concave programming: The DCCP standard form is equivalent to general DC programming, and its linearized problem is DCP whenever the original problem is DCCP.This permits automatic cone-program conversion and solution with generic solvers.

2 Domain and subdifferentiability

The paper addresses two failures in CCP when convex functions have non-full domains: linearized iterates can leave the domain, and boundary points can lack subgradients. It introduces domain-restricted linearization and damped steps while preserving convexity and DCP compatibility.

  • Domain failures: Non-full domains can make penalty CCP fail when an iterate leaves a function’s domain, causing the convexification step to fail.This issue is distinct from the handling of non-full domains for the f_i functions, which cone-program conversion handles automatically.
  • Domain failures: Direct Taylor linearization can leave the domain, and adding domain constraints can still produce a boundary point where the objective is not differentiable.At such a point, the next linearization may not exist.
  • Domain-restricted linearization: The domain is handled by adding the indicator function of the intersection of all g_i domains to each linearization.Any feasible point of the resulting linearized problem lies in the common domain D.
  • Domain-restricted linearization: Because domain indicators are convex, the domain-restricted linearization remains concave, so the linearized optimization problem remains convex.The construction therefore preserves the algorithm’s convex subproblem structure.
  • Domain in DCCP: The domain-indicator construction satisfies DCP rules for atomic functions and compositions, preserving automatic DCP treatment of the linearized DCCP problem.For compositions, the indicator inherits the relevant monotonicity properties, and an inductive argument establishes DCP compliance for composed domains.
  • Boundary subdifferentiability: Damped steps keep iterates in the domain interior when the initial point is interior, ensuring subgradients exist even if the algorithm converges to the boundary.The damped update is used when a subgradient at the undamped iterate does not exist.

3 Initialization

Initialization is heuristic and generally depends on starting values, which should lie in the interior of the domain. Random Gaussian points are projected onto the domain and averaged to seek an interior starting point, though boundary outcomes remain possible.

  • Initialization generally affects the result, and initial variable values should lie in the domain's interior.
  • The generic method draws random points with independent standard Gaussian entries and projects them onto the domain.
  • Averaging the projected points heuristically seeks an interior starting point, but the average can still lie on the boundary and be unacceptable.

4 Implementation

DCCP extends CVXPY with domain and gradient information and automates convexification, damping, initialization, and iterative solution of DCCP problems. Its interface verifies problem structure, linearizes needed expressions, and solves each convexified problem with CVXPY.

  • DCCP extends CVXPY with expression domains and gradients, while handling linearization, damping, and initialization.
  • The solver verifies DCCP compliance, splits non-affine equalities into inequalities, and linearizes non-affine objective or constraint terms when needed.
  • At each iteration, linearization values and gradients are updated from the current variables, and the convexified problem is solved using CVXPY.
  • The package provides checks for DCCP compliance, expression gradients and domains, linearization, and a solve method using randomized initialization.

5 Examples

The examples apply DCCP to circle packing, Boolean least squares, and path planning using default solver settings. The circle-packing instance achieves 0.73 square coverage, while Boolean least-squares results closely match global MOSEK results in bit error rate.

  • The examples use the default solve method without tuning or adjustment of algorithm parameters.
  • Circle packing: Circle packing minimizes the enclosing square for nonoverlapping circles with fixed radii and represents the square through the maximum infinity norm of circle centers plus radii.
  • Circle packing: 0.73 is the fraction of the square covered by 14 circles in the reported circle-packing instance.
  • Boolean least squares: Boolean least squares estimates a binary transmitted signal from noisy channel observations using a squared objective and elementwise square constraints.
  • Boolean least squares: The DCCP and globally solved Boolean least-squares results are very similar when judged by averaged bit error rate across the numerical instances.

5.3 Path planning

The paper applies DCCP to path planning and collision-avoiding control, formulating nonconvex distance constraints and solving illustrative instances.

  • Path planning: Path planning minimizes the discretized path length while connecting fixed endpoints and avoiding circular obstacles.The variables are the discretized points and path-length bound; obstacle centers and radii are given.
  • Path planning: The path-planning problem is implemented in CVXPY and solved with DCCP.The implementation creates variables, adds endpoint and obstacle constraints, and calls solve(method = ’dccp’).
  • Path planning: A two-dimensional instance with 50 discretization points is shown in Figure 3.The example is described with d = 2 and n = 50.
  • Control with collision avoidance: Collision-avoiding control requires outputs to maintain distance dmin while minimizing the sum of input ℓ1 norms under dynamic and input constraints.The formulation fixes initial and terminal states, bounds inputs, and enforces pairwise output separation over time.
  • Control with collision avoidance: The control example uses two systems with dmin = 0.6, fmax = 0.5, and T = 100, and reports trajectories with and without collision avoidance.Figure 4 also plots output distance over time and marks dmin.

5.5 Sparse recovery using ℓ1/2 ‘norm’

The sparse-recovery example compares convex ℓ1 recovery with a nonconvex square-root ℓ1/2 objective for recovering nonnegative signals from underdetermined measurements.

  • Problem formulation: The task recovers a sparse nonnegative signal from y = Ax0 with a known underdetermined sensing matrix.The convex baseline minimizes the ℓ1 norm subject to measurement equality and nonnegativity.
  • Problem formulation: The proposed alternative minimizes the square root of the ℓ1/2 ‘norm’, which is nonconvex and is directly expressible in DCCP.Nonnegativity is implicit through the objective domain.
  • Implementation: The implementation initializes x and solves the equality-constrained square-root objective with DCCP.The code uses Minimize(sum_entries(sqrt(x))) and the constraint A*x == y.
  • Numerical experiment: Recovery is evaluated over 100 random instances using relative error below 0.01 as the success criterion.Signal cardinality ranges from 30 to 50 and the measurement dimension ranges from 50 to 80.

5.6 Phase retrieval

The phase-retrieval example recovers a complex signal from magnitudes of inner products by expressing the constraints in a DCCP-compatible real formulation.

  • Problem formulation: Phase retrieval seeks x from magnitudes of complex inner products with known measurement vectors.The measurements are |x∗ak| = yk for k = 1, . . . , m.
  • Problem formulation: The magnitude constraints are convex quadratic functions of real and imaginary parts that are linear in the optimization variable.This structure places the problem within the nonconvex formulation handled by DCCP.
  • Implementation: Because complex variables are unsupported, the implementation expands complex quantities into real and imaginary parts.The code represents each measurement with a two-dimensional auxiliary variable and enforces its norm equal to yk.
  • Numerical experiment: With n = 128 and m = 3n, the reported result recovers the phase up to a global constant.The real and imaginary entries of the signal and measurement vectors are sampled independently from N(0, 1).

5.7 Magnitude filter design

The paper formulates low-pass magnitude filter design as minimizing the stopband bound subject to passband and stopband frequency-response limits.

  • Problem formulation: A filter is represented by impulse-response coefficients whose frequency response is evaluated over [0, π].The response is a complex-valued function determined by the impulse response.
  • Problem formulation: Low-pass design seeks coefficients meeting prescribed magnitude specifications on the frequency response.The objective and constraints separately control passband and stopband magnitudes.
  • Optimization model: The optimization minimizes Ustop while enforcing passband lower and upper limits and stopband upper limits.Ustop is an optimization variable, while Lpass and Upass are given passband bounds.
  • Implementation: The implementation samples frequencies on a grid, adds the corresponding norm constraints, and solves the problem with DCCP.The example uses omega = linspace(0, π, N) and calls solve(method = ’dccp’).
  • Numerical example: An instance with n = 10 and N = 100 is shown with upper and lower frequency-response magnitude limits.The figure caption identifies the plotted limits for the low-pass design.

5.8 Sparse singular vectors

The paper constructs sparse singular vectors by combining a unit-norm constraint with an ℓ1 sparsity limit, then solves the resulting problems using DCCP. Varying the sparsity parameter traces solutions from cardinality one toward less sparse vectors.

  • Sparse singular vectors: Sparse singular vectors seek unit-norm vectors that make ∥Ax∥2 small or large while limiting the ℓ1-norm to induce sparsity.The sparsity parameter µ controls this trade-off, with µ ∈ [1, √n].
  • Implementation: The minimization problem is implemented in CVXPY with norm(A*x), ∥x∥2 = 1, and ∥x∥1 ≤ µ, solved using DCCP.The code directly encodes the objective and both constraints.
  • Numerical example: For a random 100 × 100 matrix, µ is swept from 1 to 10 in increments of 0.2, with each solution plotted as a red dot.At µ = 1, the constraint gives cardinality 1; in this instance, that solution attains the global optimum.

5.9 Gaussian covariance matrix estimation

The paper estimates a Gaussian covariance matrix when the signs of its off-diagonal entries are known. It reformulates the resulting difference-of-convex maximum-likelihood problem as a DCCP problem and reports a much better estimate of the true covariance matrix.

  • Problem: The covariance-estimation problem assumes known signs for positive, negative, and zero off-diagonal entries of Σ.These signs encode which components are positively correlated, negatively correlated, or uncorrelated.
  • DCCP formulation: Because the objective is a difference of convex functions, the maximum-likelihood problem is transformed into a DCCP formulation with an additional variable t.The formulation includes the constraint trace_val ≤ t.
  • Implementation: The DCCP implementation maximizes a cost involving -log_det(Σ) and t while enforcing the sign constraints on Σ.The code separately imposes nonnegative, nonpositive, and zero constraints for the corresponding index sets.
  • Result: For n = 20 and N = 30, knowing the signs of Σ's entries produces a much better estimate of the true covariance matrix.The example is shown in figure 9.
Loading 1604.02639v1…