hynet.qcqp package

Submodules

hynet.qcqp.problem module

Representation of a hynet-specific QCQP.

class hynet.qcqp.problem.Constraint[source]

Bases: hynet.qcqp.problem.ConstraintBase

Specifies a constraint v^H C v + c^T f + a^T s + r^T z <=/== b.

Parameters:
  • name (str) – Name of the constraint and column name for the result table generation in QCQPResult.
  • table (str or None) – Name of the table with which this constraint is associated. This is used to generate the result tables in QCQPResult. Set to None to ignore the associated values during the result table generation.
  • id (hynet_id_) – Identifier of the row with which this constraint is associated. This is used to generate the result tables in QCQPResult.
  • C (hynet_sparse_ or None) – Hermitian matrix C of the constraint function or None if this term is omitted.
  • c (hynet_sparse_ or None) – Vector c of the constraint function or None if this term is omitted.
  • a (hynet_sparse_ or None) – Vector a of the constraint function or None if this term is omitted.
  • r (hynet_sparse_ or None) – Vector r of the constraint function or None if this term is omitted.
  • b (hynet_float_) – Right-hand side scalar b of the constraint.
  • scaling (hynet_float_) – Scaling factor of the constraint.
evaluate(p)[source]

Return y = v^H C v + c^T f + a^T s + r^T z - b.

Parameters:p (QCQPPoint) – Point that specifies v, f, s, and z.
Returns:y – Constraint value y at the given point p.
Return type:hynet_float_
class hynet.qcqp.problem.ObjectiveFunction(C, c, a, r, scaling)[source]

Bases: object

Specifies an objective g(v,f,s,z) = v^H C v + c^T f + a^T s + r^T z.

Parameters:
  • C (hynet_sparse_) – Hermitian matrix C of the objective function.
  • c (hynet_sparse_) – Vector c of the objective function.
  • a (hynet_sparse_) – Vector a of the objective function.
  • r (hynet_sparse_) – Vector r of the objective function.
  • scaling (hynet_float_) – Scaling factor for the objective.
evaluate(p)[source]

Evaluate the function, i.e., return y = g(v, f, s, z).

Parameters:p (QCQPPoint) – Point that specifies v, f, s, and z.
Returns:y – Function value y at the given point p.
Return type:hynet_float_
class hynet.qcqp.problem.QCQP(obj_func, eq_crt, ineq_crt, lb, ub, edges, roots, normalization=None, initial_point=None, use_buffered_vectorization=True)[source]

Bases: object

Specification of a quadratically constrained quadratic program:

  min   v^H C v + c^T f + a^T s + r^T z
v,f,s,z

  s.t.  v^H C'_i v + c'_i^T f + a'_i^T s + r'_i^T z == b'_i, i = 1,...,N
        v^H C"_j v + c"_j^T f + a"_j^T s + r"_j^T z <= b"_j, j = 1,...,M
        v_lb <= |v| <= v_ub
        f_lb <=  f  <= f_ub
        s_lb <=  s  <= s_ub
        z_lb <=  z  <= z_ub

The vector v is complex-valued, while f, s, and z are real-valued. The bounds on |v| are optional to implement by the solver. They are assumed to be captured by the inequality constraints, while v_lb and v_ub may be used to support convergence of the solver. In contrary, the bounds on f, s, and z are mandatory to implement. A bound is ignored if the respective element is set to numpy.nan.

The objective function, constraint functions, and optimization variables may be scaled to improve the numerical conditioning of the problem. All coefficient matrices, coefficient vectors, bounds as well as the initial point, if provided, must be specified for the scaled problem. The scaling factors for the objective and the constraints can be specified via their scaling attribute, while the scaling of the optimization variables is defined via normalization (see below). This scaling information is utilized in QCQPResult to adjust the optimizer, the optimal value, and the dual variables to represent the solution of the unscaled problem.

Caution: If the QCQP object is used in repeated computations with modifications of the constraints, the constraint vectorization buffering must be deactivated, see use_buffered_vectorization.

Parameters:
  • obj_func (ObjectiveFunction) – Specification of the objective function.
  • eq_crt (numpy.ndarray[Constraint]) – Specification of the equality constraints.
  • ineq_crt (numpy.ndarray[Constraint]) – Specification of the inequality constraints.
  • lb (QCQPPoint) – Specification of the lower bounds on |v|, f, s, and z.
  • ub (QCQPPoint) – Specification of the upper bounds on |v|, f, s, and z.
  • edges ((numpy.ndarray[hynet_int_], numpy.ndarray[hynet_int_])) – Specification of the sparsity pattern of the lower-triangular part of the constraint matrices via the edges (edge_src, edge_dst) of an undirected graph. The constraint matrices may only have nonzero entries in row/column edge_src[i] and column/row edge_dst[i], with i in range(K) where K = len(edge_src) = len(edge_dst), as well as on the diagonal. The edges specified in edges must be unique, i.e., there must not exist any parallel or anti-parallel edges, and must refer to the lower-triangular part, i.e., edges[0] > edges[1]. If case of any doubts, call hynet.utilities.graph.eliminate_parallel_edges before assigning.
  • roots (numpy.ndarray[hynet_int_]) – Root nodes of the undirected graph defined by edges that specifies the sparsity pattern. At these root nodes the absolute angle of the optimal v is set to zero. (Note that, due to the quadratic form in v, the optimal objective value is invariant w.r.t. an absolute phase shift within a connected component of the sparsity-defining graph.)
  • normalization (QCQPPoint) – The attributes v, f, s, and z specify the scaling of the corresponding optimization variable. This scaling is considered in the creation of the QCQP result, where the optimal value as well as the dual variables of the box constraints are adjusted accordingly.
  • initial_point (QCQPPoint or None) – Initial point for the solver or None if omitted. (The initial point is typically only utilized in solvers for the nonconvex QCQP, but ignored in SDR and SOCR solvers.)
  • use_buffered_vectorization (bool) – If True (default), the constraint vectorization is buffered to avoid its repeated computation. This QCQP object supports a vectorized representation, which is primarily intended for solver interfaces of relaxations, cf. get_vectorization. As the vectorization of the constraints is computationally demanding, the result is buffered and reused if called repeatedly. If the constraints are modified between the calls, the buffering must be deactivated to update the vectorization.
dim_f

Return the dimension of the ambient space of f.

dim_s

Return the dimension of the ambient space of s.

dim_v

Return the dimension of the ambient space of v.

dim_z

Return the dimension of the ambient space of z.

get_constraint_vectorization()[source]

Return a vectorized representation of the constraints.

This class supports a vectorized representation of the QCQP, see get_vectorization for more details. This method returns the parameters for the vectorization of the equality and inequality constraints, i.e., Ax == b and Bx <= d.

See also

hynet.qcqp.problem.QCQP.get_vectorization()

Returns:A, b, B, d – Vectorization of the equality and inequality constraints.
Return type:tuple
get_vectorization()[source]

Return a vectorized representation of this QCQP:

min   c^T x   s.t.   Ax == b,  Bx <= d,  x_lb <= x <= x_ub
 x

This representation is primarily intended for solver interfaces to relaxations of the QCQP and based on a reformulation in three steps, i.e.,

  1. The complex-valued optimization variable v is replaced by a matrix V:

    v^H C v = tr(v^H C v) = tr(Cvv^H) = tr(CV) with V = vv^H

    For equivalence to the original problem, V must be Hermitian (V = V^H), positive semidefinite (V >= 0) and have rank 1 (rank(V) = 1). Note that this vectorization does not take care of this, it only reformulates the problem in in terms of ``V``. (For example, the semidefinite relaxation will include the psd constraint but omit the rank constraint.)

  2. The sparsity of the constraint matrices is utilized to reduce the number of effective variables and vectorize the matrices, i.e.,

    tr(CV) = c_vec^T v_tld

    where c_vec = self._mtx2vec(C) and

    v_tld = [V_{1,1}                       ^
         ...                           | N = self.dim_v
         V_{N,N}                       v
         real(V_{e_src(1),e_dst(1)}    ^
         ...                           | K = self.num_edges
         real(V_{e_src(K),e_dst(K)}    v
         imag(V_{e_src(1),e_dst(1)}    ^
         ...                           | K = self.num_edges
         imag(V_{e_src(K),e_dst(K)}]   v

  3. All optimization variables are stacked, i.e.,

    x = [v_tld^T, f^T, s^T, z^T]^T

    and the objective as well as the equality, inequality, and box constraints are adapted accordingly.

Caution: This representation is only reasonable with additional constraints on the v_tld-part of x. For example, psd constraints on principal submatrices for the SOC relaxation or a psd constraint on the “reassembled” matrix V for the SDR.

Returns:(c, A, b, B, d, x_lb, x_ub) – Parameters of the vectorized QCQP representation.
Return type:tuple
num_edges

Return the number of edges in the sparsity-defining graph.

split_vectorization_bound_dual(dual_var)[source]

Return the dual variable of a bound on x as a QCQP point.

Splits the dual variable of a bound on the optimization variable x of the vectorized problem (x >= x_lb or x <= x_ub) into the dual variables of the respective bound on f, s, and z and returns them as a QCQP point (with v set to None as the respective magnitude bounds are optional).

Parameters:dual_var (numpy.ndarray[hynet_float_]) – Dual variable of a bound on x of the vectorized problem.
Returns:point – QCQP point with the dual variables of the respective bounds on |v|, f, s, and z.
Return type:QCQPPoint
split_vectorization_optimizer(x)[source]

Return (V, f, s, z) for the optimizer x of the vectorized problem.

The partitioning in x is assumed as defined in get_vectorization. The vectorized representation v_tld of V is retracted, i.e., V is populated with the diagonal and off-diagonal elements specified by v_tld.

class hynet.qcqp.problem.QCQPPoint(v, f, s, z)[source]

Bases: object

Point in the space of the optimization variables of the QCQP problem.

Parameters:
  • v (numpy.ndarray[hynet_complex_] or numpy.ndarray[hynet_float_]) –
  • f (numpy.ndarray[hynet_float_]) –
  • s (numpy.ndarray[hynet_float_]) –
  • z (numpy.ndarray[hynet_float_]) –
copy()[source]

Return a deep copy of this point.

reciprocal()[source]

Set the point to the element-wise reciprocal of the variables.

scale(scaling)[source]

Scale the point by scaling.

Parameters:scaling (QCQPPoint or hynet_float_) – Scaling factor, which can either be a numeric value, to scale all variables equally, or a QCQP point, to scale the variables individually, where the attributes v, f, s, and z specify the scaling factor for the corresponding variable.

hynet.qcqp.rank1approx module

Rank-1 approximation of partial Hermitian matrices.

This module provides an object-oriented representation of the rank-1 approximation functionality provided in hynet’s utilities.

See also

hynet.utilities.rank1approx, hynet.qcqp.solver

class hynet.qcqp.rank1approx.GraphTraversalRank1Approximator[source]

Bases: hynet.qcqp.rank1approx.Rank1Approximator

Graph traversal based rank-1 approximation of partial Hermitian matrices.

Please refer to rank1approx_via_traversal for more details.

See also

hynet.utilities.rank1approx.rank1approx_via_traversal

class hynet.qcqp.rank1approx.LeastSquaresRank1Approximator(grad_thres=1e-07, mse_rel_thres=0.002, max_iter=300, show_convergence_plot=False)[source]

Bases: hynet.qcqp.rank1approx.Rank1Approximator

Graph traversal based rank-1 approximation of partial Hermitian matrices.

Please refer to rank1approx_via_least_squares for more details.

Parameters:
  • grad_thres (hynet_float_) –
  • mse_rel_thres (hynet_float_) –
  • max_iter (hynet_int_) –
  • show_convergence_plot (bool) –

See also

hynet.utilities.rank1approx.rank1approx_via_least_squares

class hynet.qcqp.rank1approx.Rank1Approximator[source]

Bases: abc.ABC

Abstract base class for rank-1 approximators for partial Hermitian matrices.

Derived classes implement a rank-1 approximation for partial Hermitian matrices, where the sparsity pattern of the latter is defined by its associated undirected graph.

static calc_mse(V, v, edges)[source]

Calculate the mean squared error for the rank-1 approximation.

static calc_rel_err(V, v, edges)[source]

Calculate the relative reconstruction error for all edges.

hynet.qcqp.result module

Representation of the result of a hynet-specific QCQP.

class hynet.qcqp.result.QCQPResult(qcqp, solver, solver_status, solver_time, optimizer=None, V=None, optimal_value=None, dv_lb=None, dv_ub=None, dv_eq=None, dv_ineq=None)[source]

Bases: object

Solution of a quadratically constrained quadratic program.

Caution: The constructor adjusts the optimal objective value, the optimizer, and the dual variables according to the scaling of the problem, i.e., the properties of the result correspond to the unscaled QCQP.

Parameters:
  • qcqp (QCQP) – Problem specification.
  • solver (SolverInterface) – Solver object by which the result was obtained.
  • solver_status (SolverStatus) – Status reported by the solver after performing the optimization.
  • solver_time (float) – Duration of the call to the solver in seconds.
  • optimizer (QCQPPoint or None) – Optimal optimization variable (v^*, f^*, s^*, z^*) or None if the solver failed. In case of a relaxation, v^* is the rank-1 approximation of V^*.
  • V (hynet_sparse_ or None) – Optimal optimization variable V^* in case of a relaxation or None if the solver failed or a nonconvex-QCQP solver was employed.
  • optimal_value (float) – Optimal objective value or numpy.nan if the solver failed.
  • reconstruction_mse (float) – The mean squared error of the reconstructed v^* in case of a relaxation or numpy.nan if the solver failed or a nonconvex-QCQP solver was employed.
  • dv_lb (QCQPPoint or None) – Optimal dual variables of the lower bounds on f, s, and z or None if the solver failed. The attribute v is set None as these bounds are optional, cf. the QCQP specification.
  • dv_ub (QCQPPoint or None) – Optimal dual variables of the upper bounds on f, s, and z or None if the solver failed. The attribute v is set None as these bounds are optional, cf. the QCQP specification.
  • dv_eq (numpy.ndarray or None) – Optimal dual variables of the equality constraints or None if the solver failed.
  • dv_ineq (numpy.ndarray or None) – Optimal dual variables of the inequality constraints or None if the solver failed.
empty

Return True if the QCQP result does not contain an optimizer.

get_result_tables(tables=None, dual_prefix='dv_', value_prefix='cv_')[source]

Return a dictionary of data frames with the dual and constraint result.

According to the table and ID information of the constraint objects, a dictionary of data frames is assembled that contains the dual variables and the equality constraint function values with the right hand side subtracted.

hynet.qcqp.solver module

Solver interface for a hynet-specific QCQP.

class hynet.qcqp.solver.SolverInterface(verbose=False, param=None, rank1approx=None)[source]

Bases: abc.ABC

Abstract base class for QCQP solvers.

Derived classes implement a solver for the hynet-specific quadratically constrained quadratic program specified by an object of the class QCQP. A solver may solve the nonconvex QCQP, its semidefinite relaxation (SDR), or its second-order cone relaxation (SOCR).

Parameters:
  • verbose (bool, optional) – If True, the logging information of the solver is printed to the standard output.
  • param (dict[str, object], optional) – Dictionary of parameters ({'parameter_name': value}) to modify the solver’s default settings.
  • rank1approx (Rank1Approximator, optional) – Rank-1 approximator for partial Hermitian matrices. This approximator is used in relaxation-based solvers.

See also

hynet.qcqp.rank1approx
Rank-1 approximators.
static adjust_absolute_phase(qcqp, v)[source]

Return v with absolute phase adjustment according to the root nodes.

Due to the quadratic form in v, the solution of the QCQP is ambiguous w.r.t. a common phase shift of the elements in v associated with a connected component in the sparsity pattern. This method adjusts the absolute phase such that it is zero at the root node of the respective components.

Remark: This method should be used in QCQP solvers. In SDR and SOCR solvers, the rank-1 approximation takes care of the absolute phase adjustment.

Parameters:v (numpy.ndarray[hynet_complex_]) – Optimizer v for the solved QCQP.
Returns:v – Optimizer v with absolute phase adjustment.
Return type:numpy.ndarray[hynet_complex_]
name

Return the name of the solver.

solve(qcqp)[source]

Solve the given QCQP and return a QCQPResult object.

Parameters:qcqp (QCQP) – Specification of the quadratically-constrained quadratic problem.
Returns:result – Solution of the QCQP.
Return type:QCQPResult
type

Return the type of the solver as a SolverType.

Module contents

Representation of a hynet-specific quadratically constrained quadratic program.