带范数约束的凸优化问题对偶形式推导出错排查求助
各位好,我最近在推导一个带范数约束的凸优化问题的对偶形式时,卡壳了,不确定自己的推导有没有出错,想请大家帮忙排查一下~
先把我要处理的原问题放出来(其中$y$是向量):
$$
\begin{align}
\min_y \quad &c^Ty\
s.t. \quad &\Vert y \Vert \le \kappa\
&\mathbf{1}^Ty=0\
&y\le b
\end{align}
$$
这个是凸优化问题,而且满足Slater条件——当$y=0$时第一个不等式约束是激活的,第三个约束是仿射不等式,所以强对偶性肯定是成立的,这一步应该没搞错吧?
接下来是我尝试推导对偶问题的过程:我用$\gamma, \alpha, \beta$分别对应三个约束的对偶变量,其中$\gamma\ge0$对应$\Vert y \Vert \le \kappa$这个范数约束,$\alpha$是无约束变量对应$\mathbf{1}^Ty=0$这个等式约束,$\beta\ge0$对应$y\le b$的分量不等式约束。
然后我写出了拉格朗日函数的极小极大形式:
$$
\max_{\gamma \ge 0, \beta\ge 0,\alpha} \quad \min_y \quad \gamma\Vert y\Vert + (c+\alpha\mathbf{1} +\beta)^T y -\kappa\gamma -b^T\beta
$$
之后我分析了内层关于$y$的极小值情况:
- 当$\gamma =0$时,必须满足$c+\alpha\mathbf{1} +\beta=0$,不然内层的极小值会直接趋向$-\infty$;
- 当$\gamma > 0$时,需要满足$\Vert c+\alpha\mathbf{1}+\beta \Vert_* \le \gamma$(这里$\Vert \cdot \Vert_*$是原范数的对偶范数),否则内层极小值也会是$-\infty$;
不过到这里我就有点懵了,不确定前面的推导有没有哪里出错:比如拉格朗日函数的构造是不是正确?对偶变量和约束的对应关系有没有搞反?还有内层极小值的条件分析是不是有遗漏?有没有大佬能帮忙梳理下,指出可能的错误点,或者给我补充下后续的推导方向呀?
备注:内容来源于stack exchange,提问作者唐嘉泽

