QcqpProblem - GTSAM Docs

Overview¶

QcqpProblem represents a quadratically constrained quadratic program over vector or matrix variables. It uses QpCost for quadratic objectives, LinearConstraint and QuadraticConstraint for scalar constraints, and the standard ConstrainedOptProblem interface for evaluation and optimization.

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

try:
    import google.colab
    %pip install --quiet gtsam-develop
except ImportError:
    pass

import gtsam
import numpy as np

Key Concepts¶

QcqpProblem is a thin ConstrainedOptProblem specialized for QCQP costs plus linear and quadratic equality/inequality constraints.
QpCost(keys, Q, columnDim) stores a row-space quadratic objective $\tfrac{1}{2}\sum_{ij}\operatorname{tr}(X_i^\top Q_{ij}X_j)$ and linearizes exactly to a HessianFactor.
The leading $\tfrac{1}{2}$ follows GTSAM’s factor-error convention. To represent a QCQP objective written without that factor, pass twice the row-space $Q$ blocks.
QuadraticConstraint stores a scalar quadratic relation $\operatorname{tr}(X^\top A X)-b$ with equal, less-equal, or greater-equal sense.
Variables are stored in Values as direct Vector or dynamic Matrix entries.

Mathematical Formulation¶

For vector variables, take $d=1$ . For matrix variables $X_i \in \mathbb{R}^{r_i \times d}$ , row-space blocks $Q_{ij}$ , and per-variable constraint matrices $A_{k,j}$ , QcqpProblem represents:

\min_{X_i} \; \frac{1}{2}\sum_{ij}\operatorname{tr}(X_i^\top Q_{ij}X_j) \quad \text{s.t.} \; \operatorname{tr}(X_k^\top A_{k,j}X_k) \; {\sim}_{k,j} \; b_{k,j}, \quad {\sim}_{k,j}\in\{=,\le,\ge\}.

(1)

Key C++ API¶

QcqpProblem(costs, equalityConstraints) or QcqpProblem(costs, equalityConstraints, inequalityConstraints)
QcqpProblem::addConstraint(LinearConstraint) and QcqpProblem::addConstraint(QuadraticConstraint)
QpCost(keys, Q, columnDim) for row-space quadratic objectives; omit columnDim for vector variables
QuadraticConstraint::Equal(key, A, b), QuadraticConstraint::LessEqual(key, A, b), and QuadraticConstraint::GreaterEqual(key, A, b)
inherited ConstrainedOptProblem accessors such as costs(), eConstraints(), and evaluate(values)

Concise C++ Example¶

#include <gtsam/constrained/QuadraticConstraint.h>
#include <gtsam/constrained/QcqpProblem.h>
#include <gtsam/constrained/QpCost.h>
#include <gtsam/inference/Symbol.h>
#include <gtsam/nonlinear/Values.h>

using namespace gtsam;

Key x = Symbol('x', 0);
Matrix Q = Matrix::Identity(2, 2);
QcqpProblem problem;
problem.addCost(QpCost(KeyVector{x}, SymmetricBlockMatrix({2}, Q)));

problem.addConstraint(QuadraticConstraint::Equal(x, Matrix::Identity(2, 2), 1.0));
Values values;
values.insert(x, Vector2(1.0, 0.0));

auto [cost, eqViolation, ineqViolation] = problem.evaluate(values);

Minimal Python Example¶

from gtsam.symbol_shorthand import X

x = X(0)
Q = np.eye(2)

problem = gtsam.QcqpProblem()
problem.addCost(gtsam.QpCost(gtsam.KeyVector([x]), gtsam.SymmetricBlockMatrix([2], Q)))
problem.addConstraint(gtsam.QuadraticConstraint.Equal(x, Q, 1.0))

values = gtsam.Values()
values.insert(x, np.array([1.0, 0.0]))
problem.evaluate(values)

(0.5, 0.0, 0.0)

Current Scope¶

QcqpProblem assembles quadratic costs plus linear and quadratic constraints.
QpCost and QuadraticConstraint operate on direct vector or matrix values already inserted into Values.