API Reference¶

This page provides comprehensive API documentation for the DCCP package, automatically generated from numpy-style docstrings.

Main Functions¶

The main DCCP interface provides these core functions:

dccp.convexify_constr(constr: Constraint) → ConvexConstraint | None[source]¶

Convexify a constraint for DCCP problems.

For DCP constraints, returns the constraint unchanged. For non-DCP constraints, linearizes the appropriate sides and returns a convexified constraint along with any domain constraints.

Parameters:¶

constr : cp.Constraint¶

The constraint to convexify.

Returns:¶

ConvexConstraint or None – A ConvexConstraint object containing the convexified constraint and domain constraints, or None if linearization fails.

Notes

The function handles constraints by: - If the constraint is already DCP, return it unchanged - If the left side is concave, linearize it - If the right side is convex, linearize it - Collect domain constraints from linearization

dccp.convexify_obj(obj: Minimize | Maximize) → Minimize | None[source]¶

Convexify an objective function for DCCP problems.

Linearize non-DCP objectives. If the objective is already DCP, returns it unchanged. If the objective is a maximization problem, it is negated to convert it into a minimization problem.

Parameters:¶

obj : cp.Minimize | cp.Maximize¶

Objective of a problem to be convexified.

Returns:¶

cp.Minimize or None – Convexified objective if linearization is possible, None otherwise.

dccp.is_dccp(problem: Problem) → bool[source]¶

Check if a CVXPY problem is DCCP compliant.

This function verifies whether a convex optimization problem satisfies the Disciplined Convex-Concave Programming (DCCP) rules, which allow for the solution of certain non-convex problems.

Parameters:¶

problem : cp.Problem¶

A CVXPY Problem object to check for DCCP compliance.

Returns:¶

bool – True if the problem is DCCP compliant, False otherwise.

Notes

A problem is DCCP compliant if: 1. The objective function is DCCP compliant 2. All constraint arguments have known curvature (not “UNKNOWN”)

dccp.linearize(expr: Expression) → Expression | None[source]¶

Return the tangent approximation to the expression.

Linearize non-convex CVXPY expressions using first-order Taylor expansion around given points. The linearization approximates a function by:

\[f(x) ≈ f(x_0) + ∇f(x_0)^T(x - x_0)\]

Where \(x_0\) is the point of linearization, \(f(x_0)\) is the function value at that point, and \(∇f(x_0)\) is the gradient at that point.

Parameters:¶

expr : cvxpy.Expression¶

An expression to linearize.

Returns:¶

cvxpy.Expression – An affine expression representing the tangent approximation.

Raises:¶

ValueError – If the expression is non-affine and has missing variable values.

Problem Solving¶

class dccp.problem.DCCP(prob: Problem, *, settings: DCCPSettings | None = None, **kwargs: Any)[source]¶

Bases: object

Implementation of the DCCP (Disciplined Convex-Concave Programming) algorithm.

The DCCP class provides a systematic approach to solving nonconvex optimization problems that satisfy the DCCP rules. It uses an iterative convex-concave procedure (CCP) to find approximate solutions.

Parameters:¶

prob : cp.Problem¶

A CVXPY Problem that satisfies DCCP rules but not DCP rules.

settings : DCCPSettings, optional¶

Configuration settings for the DCCP algorithm. If None, default settings are used.

**kwargs: Any¶

Additional keyword arguments passed to the underlying solver.

is_maximization¶

True if the original problem is a maximization problem.

Type:¶

bool

prob_in¶

The original input problem.

Type:¶

cp.Problem

solve_args¶

Solver arguments passed to subproblems.

Type:¶

dict

conf¶

Algorithm configuration settings.

Type:¶

DCCPSettings

tau¶

Penalty parameter for constraint violations.

Type:¶

cp.Parameter

iter¶

Current iteration state and results.

Type:¶

DCCPIter

Raises:¶

NonDCCPError – If the problem is DCP compliant (should use standard solvers) or if the problem doesn’t satisfy DCCP rules.

_apply_damping() → None[source]¶

Apply damping to variable values using previous iteration values.

_store_previous_values() → None[source]¶

Store current variable values for damping.

_construct_subproblem() → None[source]¶

Construct the DCCP sub-problem.

_solve() → float[source]¶

Solve the DCCP problem.

__call__() → float[source]¶

Solve a problem using the Disciplined Convex-Concave Procedure.

solve_multi_init(num_inits: int) → float[source]¶

Solve with multiple random initializations and return the best result.

class dccp.problem.DCCPIter(prob: ~cvxpy.problems.problem.Problem, tau: ~cvxpy.expressions.constants.parameter.Parameter = <factory>, vars_slack: list[~cvxpy.expressions.variable.Variable] = <factory>, k: int = 0, cost: float = inf)[source]¶

Bases: object

Store results of a DCCP iteration.

prob : Problem¶

tau : Parameter¶

vars_slack : list[Variable]¶

k : int = 0¶

cost : float = inf¶

property slack : float¶

Get the maximum slack variable value.

property slack_sum : float¶

Sum of all slack elements.

property cost_no_slack : float¶

Objective value minus τ * sum(slack).

solve(**kwargs: Any) → float | None[source]¶

Solve the DCCP sub-problem.

dccp.problem.dccp(prob: Problem, *, max_iter: int = 100, tau_ini: float = 0.005, mu: float = 1.2, tau_max: float = 100000000.0, k_ccp: int = 1, max_slack: float = 0.001, ep: float = 1e-05, seed: int | None = None, verify_dccp: bool = True, **kwargs: Any) → float[source]¶

Run the DCCP algorithm on the given problem.

This is the main entry point for solving DCCP problems. It creates a DCCP solver instance with the specified settings and solves the problem.

Parameters:¶

prob : cp.Problem¶

A CVXPY Problem that satisfies DCCP rules.

max_iter : int, default=100¶

Maximum number of iterations in the CCP algorithm.

tau_ini : float, default=0.005¶

Initial value for tau parameter (trades off constraints vs objective).

mu : float, default=1.2¶

Rate at which tau increases during the algorithm.

tau_max : float, default=1e8¶

Upper bound for tau parameter.

k_ccp : int, default=1¶

Number of random restarts for the CCP algorithm.

max_slack : float, default=1e-3¶

Maximum slack variable value for convergence.

ep : float, default=1e-5¶

Convergence tolerance for objective value changes.

seed : int, optional¶

Random seed for reproducible results.

verify_dccp : bool, default=True¶

Whether to verify DCCP compliance before solving.

**kwargs: Any¶

Additional keyword arguments passed to the underlying solver.

Returns:¶

float – The optimal objective value (or best found value if not converged).

Raises:¶

NonDCCPError – If the problem doesn’t satisfy DCCP rules or is already DCP compliant.

See also

DCCP

The main DCCP solver class for more advanced usage.

DCCPSettings

Configuration object for algorithm parameters.

Examples

>>> import cvxpy as cp
>>> import dccp
>>> x = cp.Variable(2)
>>> problem = cp.Problem(cp.Maximize(cp.norm(x, 2)), [cp.norm(x, 1) <= 1])
>>> result = dccp.dccp(problem, max_iter=50, k_ccp=3)

Utilities and Settings¶

class dccp.utils.DCCPSettings(*, max_iter: int = 100, max_iter_damp: int = 10, tau_ini: float = 0.005, mu: float = 1.2, tau_max: float = 100000000.0, k_ini: int = 1, k_ccp: int = 1, max_slack: float = 0.001, ep: float = 1e-05, std: float = 10.0, seed: int | None = None, verify_dccp: bool = True)[source]

Bases: object

Settings for the DCCP algorithm.

This dataclass contains all configurable parameters for the DCCP algorithm, controlling convergence criteria, algorithm behavior, and initialization.

max_iter

Maximum number of iterations in the CCP algorithm.

Type:¶

int, default=100

max_iter_damp

Maximum number of damping iterations when convergence fails.

Type:¶

int, default=10

tau_ini

Initial value for tau parameter (trades off constraints vs objective).

Type:¶

float, default=0.005

mu

Rate at which tau increases during the algorithm.

Type:¶

float, default=1.2

tau_max

Upper bound for tau parameter.

Type:¶

float, default=1e8

k_ini

Number of random projections for variable initialization.

Type:¶

int, default=1

k_ccp

Number of random restarts for the CCP algorithm.

Type:¶

int, default=1

max_slack

Maximum slack variable value for convergence.

Type:¶

float, default=1e-3

ep

Convergence tolerance for objective value changes.

Type:¶

float, default=1e-5

std

Standard deviation for random variable initialization.

Type:¶

float, default=10.0

seed

Random seed for reproducible results.

Type:¶

int, optional

verify_dccp

Whether to verify DCCP compliance before solving.

Type:¶

bool, default=True

max_iter : int = 100

max_iter_damp : int = 10

tau_ini : float = 0.005

mu : float = 1.2

tau_max : float = 100000000.0

k_ini : int = 1

k_ccp : int = 1

max_slack : float = 0.001

ep : float = 1e-05

std : float = 10.0

seed : int | None = None

verify_dccp : bool = True

class dccp.utils.NonDCCPError(message: str = 'Problem is not DCCP compliant.')[source]¶

Bases: Exception

Exception raised when a problem is not DCCP compliant.

This exception is raised when: - A problem is already DCP compliant (should use standard solvers) - A problem doesn’t satisfy DCCP rules (has unknown curvature) - Linearization fails during the algorithm

dccp.utils.is_dccp(problem: Problem) → bool[source]¶

Check if a CVXPY problem is DCCP compliant.

This function verifies whether a convex optimization problem satisfies the Disciplined Convex-Concave Programming (DCCP) rules, which allow for the solution of certain non-convex problems.

Parameters:¶

problem : cp.Problem¶

A CVXPY Problem object to check for DCCP compliance.

Returns:¶

bool – True if the problem is DCCP compliant, False otherwise.

Notes

A problem is DCCP compliant if: 1. The objective function is DCCP compliant 2. All constraint arguments have known curvature (not “UNKNOWN”)

Linearization¶

dccp.linearize.linearize(expr: Expression) → Expression | None[source]¶

Return the tangent approximation to the expression.

Linearize non-convex CVXPY expressions using first-order Taylor expansion around given points. The linearization approximates a function by:

\[f(x) ≈ f(x_0) + ∇f(x_0)^T(x - x_0)\]

Where \(x_0\) is the point of linearization, \(f(x_0)\) is the function value at that point, and \(∇f(x_0)\) is the gradient at that point.

Parameters:¶

expr : cvxpy.Expression¶

An expression to linearize.

Returns:¶

cvxpy.Expression – An affine expression representing the tangent approximation.

Raises:¶

ValueError – If the expression is non-affine and has missing variable values.

Objective Convexification¶

dccp.objective.convexify_obj(obj: Minimize | Maximize) → Minimize | None[source]¶

Convexify an objective function for DCCP problems.

Linearize non-DCP objectives. If the objective is already DCP, returns it unchanged. If the objective is a maximization problem, it is negated to convert it into a minimization problem.

Parameters:¶

obj : cp.Minimize | cp.Maximize¶

Objective of a problem to be convexified.

Returns:¶

cp.Minimize or None – Convexified objective if linearization is possible, None otherwise.

Constraint Convexification¶

class dccp.constraint.ConvexConstraint(constr: Constraint, domain: list[Constraint])[source]

Bases: object

A class to represent a convex constraint with domain constraints.

constr

The convexified constraint.

Type:¶

cp.Constraint

domain

Additional domain constraints from linearization.

Type:¶

list[cp.Constraint]

constr : Constraint

domain : list[Constraint]

dccp.constraint.convexify_constr(constr: Constraint) → ConvexConstraint | None[source]¶

Convexify a constraint for DCCP problems.

For DCP constraints, returns the constraint unchanged. For non-DCP constraints, linearizes the appropriate sides and returns a convexified constraint along with any domain constraints.

Parameters:¶

constr : cp.Constraint¶

The constraint to convexify.

Returns:¶

ConvexConstraint or None – A ConvexConstraint object containing the convexified constraint and domain constraints, or None if linearization fails.

Notes

The function handles constraints by: - If the constraint is already DCP, return it unchanged - If the left side is concave, linearize it - If the right side is convex, linearize it - Collect domain constraints from linearization

Variable Initialization¶

dccp.initialization.initialize(prob: Problem, k_ini: int = 1, seed: int | None = None, solver: str | None = None, std: float = 10.0, mean: float = 0.0, *, random: bool = False) → None[source]¶

Set initial values for DCCP problem variables.

This function initializes variables in a DCCP problem by solving auxiliary optimization problems. It can perform multiple random projections and average the results to obtain better initial values.

Parameters:¶

prob : Problem¶

The CVXPY Problem instance to initialize.

k_ini : int, default=1¶

Number of random projections for each variable. Higher values may lead to better initialization but increase computation time.

random : bool, default=False¶

If True, forces random initial values for all variables, overriding any user-provided initial values.

seed : int or None, default=None¶

Random seed for reproducible initialization. If None, uses system entropy for random number generation.

solver : str or None, default=None¶

Solver to use for the initialization subproblems. If None, uses CVXPY’s default solver selection.

std : float, default=10.0¶

Standard deviation for the random initialization. This scales the random values generated for the variables.

mean : float, default=0.0¶

Mean for the random initialization. This shifts the random values generated for the variables.

Returns:¶

None – This function modifies the problem variables in-place by setting their .value attributes.