python - 使用 CVXPY 的解决方案不一致

问题描述

请考虑以下优化问题。具体来说，x和b是(1,n)向量，C是(n,n)对称矩阵，k是任意常数并且i是 1 的(1,n)向量。

请同时考虑以下等效优化问题。在这种情况下，k在优化过程中确定，因此无需按比例缩放值x来获得解y。

请同时考虑以下代码来解决cvxpy.

import cvxpy as cp
import numpy as np

def problem_1(C):
    n, t = np.shape(C)
    
    x = cp.Variable(n)
    b = np.array([1 / n] * n)
    
    obj =  cp.quad_form(x, C)
    constraints = [b.T @ cp.log(x)>=0.5, x >= 0]
    cp.Problem(cp.Minimize(obj), constraints).solve()

    return (x.value / (np.ones(n).T @ x.value))

def problem_2(C):
    n, t = np.shape(C)
    
    y = cp.Variable(n)
    k = cp.Variable()
    b = np.array([1 / n] * n)
    
    obj =  cp.quad_form(y, C)
    constraints = [b.T @ cp.log(y)>=k, np.ones(n)@y.T==1, y >= 0]
    cp.Problem(cp.Minimize(obj), constraints).solve()
    
    return y.value

虽然第一个函数确实为我正在使用的一组数据样本提供了正确的解决方案，但第二个函数却没有。具体来说，在y使用第二个函数时，其中一些值为零（这不可能，因为所有值b都是正数且大于零）。我想知道第二个函数是否也最小化k。它的值不应该被最小化，相反，它应该在优化问题期间被确定为导致目标函数最小化的解决方案。

更新_1

我刚刚发现，我用问题的第二个公式得到的解等于用以下方程和函数得出的解。似乎k忽略了对数障碍和变量的约束。

def problem_3(C):
    n, t = np.shape(C)
    
    y = cp.Variable(n)
    k = cp.Variable()
    b = np.array([1 / n] * n)
    
    obj =  cp.quad_form(y, C)
    constraints = [np.ones(n)@y.T==1, y >= 0]
    cp.Problem(cp.Minimize(obj), constraints).solve()
    
    return y.value

更新_2

这是示例输入的链接C- https://www.dropbox.com/s/kaa7voufzk5k9qt/matrix_.csv?dl=0。在这种情况下，两者的正确输出problem_1和problem_2大约等于，[0.0659 0.068 0.0371 0.1188 0.1647 0.3387 0.1315 0.0311 0.0441]因为它们在定义上是等效的。我只能通过求解来获得正确的输出problem_1。解决problem_2哪个[0.0227 0. 0. 0.3095 0.3392 0.3286 0. 0. 0. ]是错误的，因为它恰好是problem_3.

更新_3

需要明确的是，根据定义，problem_2解等于problem_3参数k变为负无穷大时的解。

UPDATE_4

problem_1请考虑以下使用 SciPy Optimize 代替 CVXPY求解的代码。通过施加k=9正确的最优解仍然可以达到与problem_1参数无关的一致。

import scipy.optimize as opt

def obj(x, C):
    return x.T @ C @ x

def problem_1_1(C):
    n, t = np.shape(C)

    b = np.array([1 / n] * n)
        
    constraints = [{"type": "eq", "fun": lambda x: (b * np.log(x)).sum() - 9}]
    
    res = opt.minimize(
        obj,
        x0 = np.array([1 / n] * n),
        args = (C),
        bounds = ((0, None),) * n, 
        constraints = constraints
    )
    
    return (res['x'] / (np.ones(n).T @ res['x']))

UPDATE_5

通过考虑 UPDATE_4 中的代码，只要k设置为 10，仍然可以实现正确的解决方案，但是会出现以下警告。我想这是由于优化过程中可能出现的舍入误差。

Untitled.py:56: RuntimeWarning: divide by zero encountered in
log {"type": "eq", "fun": lambda x: (b * np.log(x)).sum() - 10}

我想知道是否有办法对 CVXPY 施加严格的不等式约束或在对数参数上应用条件。请考虑以下修改后的代码problem_1_1。

import scipy.optimize as opt

def obj(x, C):
    return x.T @ C @ x

def problem_1_1(C):
    n, t = np.shape(C)

    b = np.array([1 / n] * n)
        
    constraints = [{"type": "eq", "fun": lambda x: (b * np.log(x if x.all() > 0 else 1e-100)).sum() - 10}]
    
    res = opt.minimize(
        obj,
        x0 = np.array([1 / n] * n),
        args = (C),
        bounds = ((0, None),) * n, 
        constraints = constraints
    )
    
    return (res['x'] / (np.ones(n).T @ res['x']))

UPDATE_6

彻底地说，最佳值的正确值k是近似的-2.4827186402337564。

标签： pythonnumpyoptimizationcvxpy

python - 使用 CVXPY 的解决方案不一致

问题描述

解决方案

推荐阅读