convex-optimization - Q >= 0 的二次函数中等式约束“A x = 0”的拉格朗日松弛

Question

我有以下代码：

class LagrangianEqualityConstrainedQuadratic:
    """
    Construct the lagrangian dual relaxation of an equality constrained quadratic function defined as:

            1/2 x^T Q x + q^T x : A x = b = 0
    """

    def __init__(self, Q, q, A):
        self.Q = Q
        self.q = q
        self.A = A
        self.last_rnorm = None
    
    def _solve_sym_nonposdef(self, Q, q):

        # `min ||Qx - q||` is formally equivalent to solve the linear system:
        #                   (Q^T Q) x = (Q^T q)^T x

        Q, q = np.inner(Q, Q), Q.T.dot(q)

        x = minres(Q, q)[0]

        self.last_rnorm = np.linalg.norm(q - Q.dot(x))  # || q - Qx ||

        return x

    def function(self, lmbda):
        """
        Compute the value of the lagrangian relaxation defined as:

        L(x, lambda) = 1/2 x^T Q x + q^T x - lambda^T A x
         L(x, lambda) = 1/2 x^T Q x + (q - lambda A)^T x

        where lambda is constrained to be >= 0.

        Taking the derivative of the Lagrangian wrt x and settings it to 0 gives:

                Q x + (q - lambda A) = 0

        so, the optimal solution of the Lagrangian relaxation is the solution of the linear system:

                Q x = - (q - lambda A)

        :param lmbda: the dual variable wrt evaluate the function
        :return: the function value wrt lambda
        """
        ql = self.q - lmbda.dot(self.A)
        x = self._solve_sym_nonposdef(self.Q, -ql)
        return 0.5 * x.dot(self.Q).dot(x) + ql.dot(x)

    def jacobian(self, lmbda):
        """
        With x optimal solution of the minimization problem, the jacobian
        of the Lagrangian dual relaxation at lambda is:

                                [-A x]

        However, we rather want to maximize the Lagrangian dual relaxation,
        hence we have to change the sign of gradient entries:

                                 [A x]

        :param lmbda: the dual variable wrt evaluate the gradient
        :return: the gradient wrt lambda
        """
        ql = self.q - lmbda.dot(self.A)
        x = self._solve_sym_nonposdef(self.Q, -ql)
        return self.A * x

结果，我得到以下作为原始结果：

表面

但当然，我希望在线性约束上找到我的约束最小值Ax=0，即沿着右图中的蓝线。黑星所在的位置。

我应该如何更改我的代码来获得这个？

根据：

双重的

我认为我应该强加解决方案x必须与 Q 矩阵的零空间正交（？）

标签： convex-optimizationconvex