计算科学 - 如何使用 minFunc 或 minConf 解决约束优化问题 - 吾爱随笔录

如何使用 minFunc 或 minConf 解决约束优化问题

计算科学 matlab 凸优化线性规划非线性规划

2021-12-05 17:39:26

我正在尝试解决以下优化问题：其中可以是 Frobenius 范数或 -norm。

\begin{aligned} min_{s} t r (S^{T} S) + t r ({(S^{T} S)}^{- 2}) \\ subject to {‖ S^{T} S - Z^{T} Z ‖}_{n o r m} \leq ϵ \end{aligned}

$\begin{align} &\min\limits_{s} \rm{tr}\left(S^T S\right) + \mathrm{tr}\left(\left(S^T S\right)^{-2}\right)\\ &\text{subject to }\rm\left\|S^TS-Z^TZ\right\|_{norm}\leq \epsilon\end{align}$

‖ \cdot ‖_{n o r m}

$\rm \|\cdot\|_{norm}$

ℓ_{1}

$\ell_1$

也就是说， $\rm S^TS$ 属于半径为 $\epsilon$ 且中心为 $\rm Z^TZ$ 的球。实际上，我想用 $\rm Q = S^TS$ 来解决我的问题，它是一个对称的半正定矩阵，因此，这是一个要解决的凸问题，但我找不到另一种方法来将该属性强加到我的解决方案中。

因此，我首先使用工具箱尝试使用拉格朗日表达式和约束minFunc的 Frobenius 范数，即， $\rm \|\cdot\|_{norm}$

min_{s} t r (S^{T} S) + t r ({(S^{T} S)}^{- 2}) + λ \cdot t r ((S^{T} S - Z^{T} Z) {(S^{T} S - Z^{T} Z)}^{T})

$\min\limits_{s} \rm \mathrm{tr}\left(S^T S\right) + \mathrm{tr}\left(\left(S^T S\right)^{-2}\right) + \lambda\cdot\mathrm{tr}\left(\left(S^T S - Z^TZ\right)\left(S^T S - Z^TZ\right)^T\right)$

但它在几次迭代后停止，对于一个小的 } 。 $10^{2}$ $S\in\mathrm{R}^{10\times10}$

这是我的代码：

options.Method = 'cg';%'lbfgs'; 
options.maxIter = 100000000;
options.MaxFunEvals = 20000000000000;
lambda = 0.001;
x0 = rand(100,1);
Z = rand(15,10);
funObj = @(x)myfunc(x, lambda, Z);
[sol, f_val] = minFunc(funObj,x0,options);

function [f,g] = myfunc(x, lambda, Z)
s = reshape(x, [sqrt(numel(x)),sqrt(numel(x))]);
f = trace(s'*s) + trace(inv(s'*s)^2) + lambda* trace((s'*s - Z'*Z)*(s'*s - Z'*Z)');
g = 2*s -4*s*(inv(s'*s))^3 + lambda*(2*s*s'*s + 2*s'*s*s -2*s*Z'*Z -2*Z'*Z*s);
g = g(:);
end

我也尝试过minConf_PQN使用 $\ell_1$ -norm 约束，但返回此错误：

close to singular or badly scaled. Results may be inaccurate. RCOND = NaN

这是我使用的代码：

funObj = @(x)myfunc(x);

Z = rand(15,10);
S0 = load('S_true.mat')
L=S0'*S0-Z'*Z; 
tau = sum(abs(L(:))); %true tau
r = reshape(Z'*Z, [size(Z,2)^2,1]);
funProj = @(w)sign(w).*projectRandom2C(abs(w'w-r),tau);
sol = minConf_PQN(funObj,x0,funProj,options);

function [f,g] = myfunc(x)

s = reshape(x, [sqrt(numel(x)),sqrt(numel(x))]);

f = trace(s'*s) + trace(inv(s'*s)^2);

g = 2*s -4*s*(inv(s'*s))^3;
g = g(:);

end

任何解决我的问题的帮助将不胜感激。

2个回答

不是直接回答你的标题问题，但我认为你最好从半定域来解决这个问题。简单的方法是在一些初始猜测处线性化目标，解决线性化问题，沿着计算的方向执行线搜索，然后重复直到目标没有改善。下面的代码在使用 YALMIP 的实现中执行此操作（免责声明：由我开发）。它使用 Mosek 或 SDPT3 等 SDP 求解器在一秒钟左右结束。

Z = rand(15,10);

% Take a step D from current solution Qi, Q = Qi+D
D = sdpvar(10);
% Initial guess Q = Qi = Z'*Z
Qi = Z'*Z;
% Values to test in brute-force line-search
alpha = logspace(-4,3,100);
% Run some iterations
for i = 1:10
    % Linearized objective
    Objective = trace(Qi + D) + trace(Qi^-2 - Qi^-2*D*Qi^-1 - Qi^-1*D*Qi^-2)
    % Solve linear SDP
    optimize([Qi+D>=0, norm(Qi + D - Z'*Z,'fro') <= .01],Objective)
    % Perform naive line-search
    for j = 1:length(alpha)
        Qtest = Qi + alpha(j)*value(D);
        if min(eig(Qtest))>0  && norm(Qtest - Z'*Z,'fro')<=0.01
            Objtest(j) = trace(Qtest) + trace(Qtest^-2);
        else
            Objtest(j) = inf;
        end
    end
    if all(Objtest >= trace(Qi) + trace(Qi^-2))
        break
    end
    plot(alpha,Objtest)
    % Pick best step
    [~,best] = min(Objtest);
    % Update solution
    Qi = Qi + alpha(best)*value(D);
end

添加另一个答案，因为我刚刚意识到问题很容易作为线性 SDP 解决。让你有目标。引入一个上限并最小化。在最佳状态下，您将拥有。约束和使用 Schur 补码转换为 LMI，目标是凸二次的。 $Q=S^TS$ $\mathrm{trace}~Q + \mathrm{trace}~Q^{-2}$ $X\succeq Q^{-1}$ $\mathrm{trace}~Q + \mathrm{trace}~X^{2}$ $X= Q^{-1}$ $X\succeq Q^{-1}$ $Q\succeq 0$

这里也在 YALMIP 中实现

Q = sdpvar(n);
X = sdpvar(n);
Model = [[X eye(n);eye(n) Q]>=0, norm(Q-Z'*Z)<= .01]
Objective = trace(Q) + trace(X*X);
optimize(Model,Objective)

其它你可能感兴趣的问题

上一篇如何在不使用符号计算的情况下解决问题下一篇用于分子动力学模拟的优秀台式电脑