如何求解对数凸规划

Question

我有一个问题，目标函数是多项式，约束是线性的（即使约束中变量的某些系数是非正的），这个问题可以被认为是对数凸问题。 CVXPY 工具箱不直接支持线性约束中的负系数。

 Maximize:
 f(x) = x_1*x_4+x_2*x_5+x_3*x_6 
Subject to:
  a^T x + b <= 1 
    0<= x <=ub 

如果有人可以指导如何解决这个问题，我将不胜感激。

如何解决并找到我的问题的解决方案

Answer 1

指定雅可比行列式后，可以快速求解（在本例中为 10 次迭代）：

import typing

import numpy as np
import scipy.optimize


def cost(x: np.ndarray) -> float:
    # Maximise x_1*x_4 + x_2*x_5 + x_3*x_6
    return -x[:3].dot(x[3:])


JAC_IDX = np.array((3, 4, 5, 0, 1, 2))


def jacobian(x: np.ndarray) -> np.ndarray:
    return -x[JAC_IDX]


def optimise(a: np.ndarray, b: float, ub: float) -> np.ndarray:
    error = scipy.optimize.check_grad(
        func=cost, grad=jacobian,
        x0=np.linspace(start=0.5, stop=1.3, num=6),
    )
    assert np.isclose(error, 0, atol=1e-7, rtol=0)

    # a1x + a2x + a3x ... = 1 - b, one value for x
    x0 = np.full(
        shape=6, fill_value=(1 - b)/a.sum(),
    ).clip(min=0, max=ub)

    result = scipy.optimize.minimize(
        fun=cost, jac=jacobian, x0=x0,
        bounds=scipy.optimize.Bounds(lb=0, ub=ub),
        constraints=scipy.optimize.LinearConstraint(
            A=a, ub=1 - b,
        ),
    )
    if not result.success:
        raise ValueError(result.message)
    return result.x


def demo() -> None:
    print(optimise(
        a=np.array((0.5, 3.3, 3.3, 0.5, 1.1, 1.2)),
        b=-7, ub=5,
    ))


if __name__ == '__main__':
    demo()