Processing math: 0%

数学物理学报, 2025, 45(2): 630-639

一类不确定分式多项式优化问题的鲁棒最优解研究

冉波,, 孙祥凯,*, 郭晓乐,

重庆工商大学数学与统计学院, 统计智能计算与监测重庆市重点实验室 重庆 400067

On Robust Optimal Solutions for a Class of Uncertain Fractional Polynomial Optimization Problems

Ran Bo,, Sun Xiangkai,*, Guo Xiaole,

Chongqing Key Laboratory of Statistical Intelligent Computing and Monitoring, School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067

通讯作者: * 孙祥凯,E-mail:sunxk@ctbu.edu.cn

收稿日期: 2024-04-11   修回日期: 2024-09-18  

基金资助: 重庆市自然科学基金(CSTB2024NSCQ-MSX0651)
重庆市研究生导师团队建设项目(yds223010)

Received: 2024-04-11   Revised: 2024-09-18  

Fund supported: Natural Science Foundation of Chongqing(CSTB2024NSCQ-MSX0651)
Team Building Project for Graduate Tutors in Chongqing(yds223010)

作者简介 About authors

冉波,E-mail:1308355153@qq.com;

郭晓乐,E-mail:xlguocqu1@163.com

摘要

不确定数据处理过程中常常会涉及到平方和凸凹多项式结构的分式优化问题. 该文旨在研究它的鲁棒最优解. 首先, 借助鲁棒优化方法和一类法锥型约束规格条件, 建立该不确定分式多项式优化问题的鲁棒最优解的最优性条件. 随后, 引入该不确定分式多项式优化问题的鲁棒对偶问题, 并研究它们之间的鲁棒弱对偶与强对偶性质. 最后, 刻画该不确定分式多项式优化问题的精确平方和松弛性质.

关键词: 分式优化; 鲁棒最优性; 鲁棒对偶性

Abstract

Fractional optimization with sum of squares convex-concave polynomials is often involved in the uncertain data processing. This paper is concerned with its robust optimal solutions. We first give optimality conditions of robust optimal solutions for the uncertain fractional polynomial optimization problem in terms of robust optimization and a normal cone constraint qualification condition. Then, we give a robust dual problem to this uncertain fractional polynomial optimization problem and establish robust weak and strong duality properties between them. Moreover, we obtain exact sum of squares relaxation results for this uncertain fractional polynomial optimization problem.

Keywords: fractional optimization; robust optimality; robust duality

PDF (604KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

冉波, 孙祥凯, 郭晓乐. 一类不确定分式多项式优化问题的鲁棒最优解研究[J]. 数学物理学报, 2025, 45(2): 630-639

Ran Bo, Sun Xiangkai, Guo Xiaole. On Robust Optimal Solutions for a Class of Uncertain Fractional Polynomial Optimization Problems[J]. Acta Mathematica Scientia, 2025, 45(2): 630-639

1 引言

作为凸多项式的重要子类, 平方和凸多项式近些年引起学者们的极大兴趣, 因为它不仅在信号处理和自动控制系统等方面有着重要的应用, 而且它可以转化为半定线性规划问题, 从而借助经典的内点法求解[1]. 进一步地, 平方和凸多项式优化具有精确的半定规划松弛, 即该问题与其半定规划松弛问题之间存在零对偶间隙, 详见文献 [2],[3],[4].

值得注意的是, 上述文献在研究平方和凸多项式优化问题时, 需要假定模型的数据是事先给定的. 近些年来, 带有不确定参数的平方和凸多项式优化问题引起国内外学者的关注, 并取得了一定的前期成果. 譬如, 借助一类法锥型约束规格条件和平方和条件, Jeyakumar 等[5]刻画了不确定平方和凸多项式优化问题的鲁棒最优解的必要和充分最优性条件, 并给出了精确的半定规划松弛性质. Jeyakumar 和李国胤[6]借助鲁棒优化方法和择一性定理, 研究了不确定平方和凸多项式优化问题与它的半定规划松弛问题之间的零对偶间隙性质, 并在不借助任何约束规格条件的前提下, 建立了不确定多目标平方和凸多项式优化问题的鲁棒有效解的最优性条件. Chuong[7] 借助鲁棒优化方法、线性矩阵不等式和平方和条件, 首先研究了一类带有谱面体不确定集的不确定多目标平方和凸多项式优化问题的鲁棒有效解和鲁棒弱有效解的必要和充分最优性条件. 随后建立了该优化问题的平方和松弛对偶问题, 并得到了精确的平方和松弛性结果. 借助标量化方法, 矫立国和 Lee[8] 刻画了不确定多目标平方和凸多项式优化问题的鲁棒有效解, 并证明了与其对应的标量优化问题与松弛对偶问题之间的零对偶间隙性质. 借助上图类约束规格条件与平方和条件, 孙祥凯等[9]刻画了带有谱面体不确定集合的不确定多目标平方和凸多项式优化问题的鲁棒有效解的最优性条件, 并得到了精确的平方和松弛性结果.

据我们所知, 对于平方和凸多项式结构的分式优化问题少有研究. 详细来讲, 借助 Slater 型条件, Jeyakumar 和李国胤[10]研究了带有平方和凸多项式结构的分式半定规划问题的半定规划松弛问题, 并刻画了它们之间的零对偶间隙. Lee 和矫立国[11]借助约束标量化方法, 研究了一类平方和凸凹多项式结构的多目标优化问题鲁棒有效解与其对应的标量化问题的鲁棒最优解之间的关系, 并给出了求解鲁棒有效解的计算方法. 受上述文献的启发, 本文将引入一类带有平方和凸凹多项式结构的分式优化问题, 并借助鲁棒优化方法和更弱的次微分约束规格条件研究它的鲁棒最优解相关性质, 包括最优性条件、对偶性理论以及精确的平方和松弛性质, 推广和改进相关文献的结论.

全文的大致框架如下: 第二章引入该分式多项式优化问题的鲁棒对等问题, 并利用 Dinkelbach 参数化方法[12], 将其转化为一般的优化问题. 第三章研究该分式多项式优化问题的鲁棒最优解的必要和充分最优性条件的等价刻画. 第四章研究该分式多项式优化问题的鲁棒对偶性和精确的平方和松弛性结果.

2 预备知识

本文假设 Rn 为赋予欧氏范数 n 维向量空间. \mathbb{R} {_+^n}\mathbb{R}^{n} 的非负象限. \mathbb{R}[x]\mathbb{R}^{n} 中所有多项式组成的集合. \mathbb{R}[x]_d\mathbb{R}^{n} 上所有最高次数不超过 d 的全体实多项式组成的集合. \text{deg} f 为实多项式 f 的次数. 若存在实多项式 f_i, i=1,\cdots,m, 使得 f=\Sigma^m_{i=1}f_i^2, 则称实多项式 f 是平方和多项式. 对于任意的 x\in\mathbb{R}^{n}, 所有次数不超过 d 的平方和多项式组成的集合记为 \Sigma_d^2[x]. 设 f:\mathbb{R}^{n}\rightarrow\mathbb{R} 为实多项式. 若 f(x)-f(y)-\nabla f(y)^T (x-y) \mathbb{R}[x,y] (关于 xy) 上的平方和多项式, 则称多项式 f\mathbb{R}^{n} 上是平方和凸多项式. 进一步地, 若 -f:\mathbb{R}^{n}\rightarrow \mathbb{R}\mathbb{R}^{n} 上是平方和凸多项式, 则称 f\mathbb{R}^{n} 上是平方和凹多项式. 显然, 平方和凸多项式是凸多项式, 反之则不一定成立, 详见文献 [3],[4]. 此外, 凸二次函数和凸可分离多项式也是平方和凸多项式.

引理2.1 [1]f:\mathbb{R}^{n}\rightarrow\mathbb{R}\mathbb{R}^{n} 上是平方和凸多项式. 若存在 y\in\mathbb{R}, 使得 f(y)=0\nabla f(y)=0, 则 f 是平方和多项式.

本文考虑如下不确定分式多项式优化问题

\begin{eqnarray*} (\mathrm{UFP}) \left\{ \begin{aligned} &\min_{x\in \mathbb{R}^{n}} \frac{f(x)}{g(x)} \\ & s.t. h_j(x,w_j)\leq 0, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

其中 f:\mathbb{R}^{n}\rightarrow\mathbb{R} 是平方和凸多项式, g:\mathbb{R}^{n}\rightarrow\mathbb{R} 是平方和凹多项式, 以及对于任意的 w_j\in W_j\subseteq \mathbb{R}^{q}, h_j(\cdot,w_j) 是平方和凸多项式. 对于任意的 x\in\mathbb{R}^{n}, 本文总是假定 f(x)\geq0g(x)>0.

借助鲁棒优化方法[13], [14], [15], 引入 (\mathrm{UFP}) 的鲁棒对等问题

\begin{eqnarray*} (\mathrm{RFP}) \left\{ \begin{aligned} &\min_{x\in \mathbb{R}^{n}} \frac{f(x)}{g(x)} \\ & s.t. h_j(x,w_j)\leq 0, \forall w_j\in W_j, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

定义2.1 (\mathrm{UFP}) 的鲁棒可行集定义为

\begin{eqnarray*} C:=\left\{x\in \mathbb{R}^{n}| h_j(x,w_j)\leq 0, \forall w_j\in W_j, j=1,\cdots,s \right\}. \end{eqnarray*}

定义2.2 \bar{x}\in C(\mathrm{RFP}) 的最优解, 即

\begin{eqnarray*} \frac{f(x)}{g(x)}\geq \frac{f(\bar {x})}{g(\bar{x})}, \forall x\in C, \end{eqnarray*}

则称 \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解.

假定 \mu\geq0, 借助 Dinkelbach 参数化方法[12], 将 (\mathrm{RFP}) 转化为

\begin{eqnarray*} (\mathrm{NFP})_{\mu} \left\{ \begin{aligned} &\min_{x\in \mathbb{R}^{n}} f(x)-\mu g(x) \\ & s.t. h_j(x,w_j)\leq 0, \forall w_j\in W_j, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

类似于定义 2.2 的方法, 可引入 (\mathrm{NFP})_\mu 的最优解概念. 此处, 不再赘述.

下述命题建立了 (\mathrm{UFP}) 的鲁棒最优解与 (\mathrm{NFP})_\mu 的最优解之间的等价关系.

命理2.1 \bar{x}\in C\bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}. 则 \bar{x}(\mathrm{UFP}) 的鲁棒最优解当且仅当 \bar{x}(\mathrm{NFP})_{\bar{\mu}} 的最优解.

3 最优性刻画

本节建立 (\mathrm{UFP}) 的鲁棒最优解的必要和充分最优性条件. 为刻画 (\mathrm{UFP}) 的鲁棒最优解的必要最优性条件, 首先引入下述法锥型约束规格条件.

定义3.1 [5] 考虑 (\mathrm{UFP}). 设 \bar{x}\in C. 若

\begin{eqnarray*} N_C(\bar{x}):=\left\{\sum_{j=1}^s\lambda_j \nabla_1 h_j(\bar{x},w_j)\mid \lambda_j\geq 0, w_j\in W_j, \lambda_jh_j(\bar{x},w_j)=0 \right\}, \end{eqnarray*}

则称法锥型约束规格条件 (\mathrm{NCQ})\bar{x}\in C 处成立. 此处 N_C(\bar{x}) 表示集合 C\bar{x} 处的法锥, \nabla_1 h_j(\bar{x},w_j) 表示 h_j 关于变量 \bar{x} 的梯度.

注3.1 显然, 若如下鲁棒 Slater 条件成立, 即

\left\{x\in \mathbb{R}^{n}\mid h_j(x,w_j)< 0, \forall w_j\in W_j, j=1,\cdots,s \right\}\neq \emptyset,
(3.1)

(\mathrm{NCQ}) 成立. 因此, (\mathrm{NCQ}) 弱于鲁棒 Slater 条件 (3.1).

接下来, 借助 (\mathrm{NCQ}), 刻画 (\mathrm{UFP}) 的鲁棒最优性条件.

定理3.1 考虑 (\mathrm{UFP}). 令 \bar{x}\in C 以及 \bar{\mu}=\frac{f(\bar {x})}{g(\bar{x})}. 假定 (\mathrm{NCQ})\bar{x} 处成立. 则下列命题等价

(i) \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解.

(ii) 存在 \bar{\lambda}_j\geq0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

\nabla f(\bar{x})-\bar{\mu} \nabla g(\bar{x})+\sum_{j=1}^{s} \bar{\lambda}_{j} \nabla_{1} h_{j}\left(\bar{x}, \bar{w}_{j}\right)=0 \text { 和 } \bar{\lambda}_{j} h_{j}\left(\bar{x}, \bar{w}_{j}\right)=0.

(iii) 存在 \bar{\lambda}_j\geq0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

f-\bar{\mu} g+\sum_{j=1}^s\bar{\lambda}_j h_j(\cdot,\bar{w}_j)\in \Sigma_d^2[x],

其中, d\geq \max\{\text{deg} f,\text{deg} g,\mathop{\max}\limits_{1\leq j\leq s}h_j\}.

\mbox{(i)} \Rightarrow \mbox{(ii)}: 设 \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解. 则由命题 2.1 可知 \bar{x}\in C(\mathrm{NFP})_{\bar{\mu}} 的最优解, 即 f(\bar{x})-\bar{\mu} g(\bar{x})=\min_{x\in C} (f(x)-\bar{\mu}g(x)). 从而

-\nabla (f-\bar{\mu} g)(\bar{x})\in N_C(\bar{x}).

又因为 (\mathrm{NCQ})\bar{x}\in C 处成立, 所以存在满足 \bar{\lambda}_j h_j(\bar{x},\bar{w}_j)=0\bar{\lambda}_j\geq0\bar{w}_j\in W_j 使得

-\nabla (f-\bar{\mu} g)(\bar{x})=\sum_{j=1}^s\bar{\lambda}_j \nabla_1 h_j(\bar{x},\bar{w}_j),

\nabla f(\bar{x})-\bar{\mu} \nabla g(\bar{x})+\sum_{j=1}^s\bar{\lambda}_j\nabla_1 h_j(\bar{x},\bar{w})_j=0. 因此, (ii) 成立.

\mbox{(ii)}\Rightarrow \mbox{(iii)}: 由 \mbox{(ii)} 可知, 存在 \bar{\lambda}_j\geq0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

\nabla f(\bar{x})-\bar{\mu}\nabla g(\bar{x})+\sum_{j=1}^s\bar{\lambda}_j \nabla_1 h_j(\bar{x},\bar{w}_j)=0\left. \text{和} \begin{array}{l}\bar{\lambda}_j h_j(\bar{x},\bar{w}_j)=0.\end{array}\right.
(3.2)

L(x)= f(x)-\bar{\mu} g(x)+\sum_{j=1}^s\bar{\lambda}_jh_j(x,w_j). 因为 \bar{\lambda}_j h_j(\bar{x},\bar{w}_j)=0\bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}, 所以

L(\bar{x})= f(\bar{x})-\bar{\mu} g(\bar{x})+\sum_{j=1}^s\bar{\lambda}_jh_j(\bar{x},\bar{w}_j)=0.
(3.3)

从而, 结合 (3.2) 式可得

\nabla L(\bar{x})= 0.
(3.4)

此外, 由 f h_j(\cdot,\bar{w}_j) 是平方和凸多项式以及 g 是平方和凹多项式可知, L 为平方和凸多项式. 从而, 由 (3.3) 式, (3.4) 式和引理 2.1 可得 L 为平方和多项式, 即

f-\bar{\mu} g+\sum_{j=1}^s\bar{\lambda}_j h_j(\cdot,\bar{w}_j)\in \Sigma_d^2[x].

因此, \mbox{(iii)} 成立.

\mbox{(iii)} \Rightarrow \mbox{(i)}: 由 \mbox{(iii)} 可知

f(x)-\bar{\mu} g(x)+\sum_{j=1}^s\bar{\lambda}_j h_j(x,\bar{w}_j)\geq 0, \forall x\in \mathbb{R}^{n}.
(3.5)

又因为 h(x,\bar{w}_j)\leq 0, \forall x\in C, 所以由 (3.5)) 式可得 f(x)-\bar{\mu} g(x)\geq 0. 从而, 结合 \bar{\mu}=\frac{f(\bar {x})}{g(\bar{x})} 可知

\begin{eqnarray*} f(x)-\bar{\mu} g(x)\geq f(\bar{x})-\bar{\mu} g(\bar{x}), \forall x\in C. \end{eqnarray*}

因此, \bar{x}\in C(\mathrm{NFP})_{\bar{\mu}} 的最优解. 故, 由命题 2.1 可得 \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解. 命题得证.

接下来, 借助下例解释定理 3.1.

例3.1 x\in \mathbb{R}w_1\in W_1:=[0,+\infty). 令 f(x)=x^4+2x^2+1, g(x)=-x^4-x^2+2, 以及 h_1(x,w_1)=w_1(x-2)^2-4w_1. 考虑

\begin{eqnarray*} (\mathrm{UFP}) \left\{ \begin{aligned} &\min_{x\in \mathbb{R}} \frac{x^4+2x^2+1}{-x^4-x^2+2} \\ & s.t. w_1(x-2)^2-4w_1\leq 0. \end{aligned} \right. \end{eqnarray*}

则, (\mathrm{UFP}) 的鲁棒对等问题为

\begin{eqnarray*} (\mathrm{RFP}) \left\{ \begin{aligned} &\min_{x\in \mathbb{R}} \frac{x^4+2x^2+1}{-x^4-x^2+2} \\ & s.t. w_1(x-2)^2-4w_1\leq 0, \forall w_1\in W_1. \end{aligned} \right. \end{eqnarray*}

不难计算, (\mathrm{UFP}) 的鲁棒可行集 C=[0,4] 以及最优解为 \bar{x}=0. 因此, \bar{\mu}=\frac{1}{2}. 进一步地,

\begin{eqnarray*} N_C(\bar{x}):=\left\{ \lambda_1 \nabla_1 h_1(\bar{x},w_1)\mid\lambda_1\geq 0, w_1\in W_1,\lambda_1h(\bar{x},w_1)=0 \right\}=(-\infty,0]. \end{eqnarray*}

故, (\mathrm{NCQ})\bar{x}=0 处成立.

另一方面,

f(x)-\mu g(x)+\lambda_1 h_1(x,w_1)=x^4+2x^2+1-\mu (-x^4-x^2+2)+\lambda_1(w_1(x-2)^2-4w_1).
(3.6)

对 (3.6) 式求关于变量 x 的梯度可得

\nabla f(x)-\mu \nabla g(x)+\lambda_1\nabla_1 h_1(x,w_1)=4x^3(\mu +1)+2x(\mu +2)+2\lambda_1 w_1(x-2).
(3.7)

显然, 存在 \bar{\lambda}_1=0 以及 \bar{w}_1=1 使得 \nabla f(\bar{x})-\bar{\mu} \nabla g(\bar{x})+\bar{\lambda}_1\nabla_1 h_1(\bar{x},\bar{w}_1)=0 \bar{\lambda}_1 h_1(\bar{x},\bar{w}_1)=0. 故, \mathrm{(ii)} 成立.

最后, 结合 (3.6) 式以及 \bar{\mu}=\frac{1}{2}, \bar{\lambda}_1=0, \bar{w}_1=1 可得

f(x)-\bar{\mu} g(x)+\bar{\lambda}_1 h_1(x,\bar{w}_1)=\frac{3}{2} x^4+\frac{5}{2} x^2\in \Sigma_1^2[x].

因此, \mathrm{(iii)} 成立.

借助注 3.1 和定理 3.1, 易得如下推论成立.

推论3.1 考虑 (\mathrm{UFP}). 令 \bar{x}\in C\bar{\mu}=\frac{f(\bar {x})}{g(\bar{x})}. 若鲁棒 Slater 条件 (3.1) 成立. 则下列命题等价

(i) \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解.

(ii) 存在 \bar{\lambda}_j\geq0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

\nabla f(\bar{x})-\bar{\mu} \nabla g(\bar{x})+\sum_{j=1}^{s} \bar{\lambda}_{j} \nabla_{1} h_{j}\left(\bar{x}, \bar{w}_{j}\right)=0 \text { 和 } \bar{\lambda}_{j} h_{j}\left(\bar{x}, \bar{w}_{j}\right)=0.

(iii) 存在 \bar{\lambda}_j\geq0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

\begin{eqnarray*} f-\bar{\mu} g+\sum_{j=1}^s\bar{\lambda}_j h_j(\cdot,\bar{w}_j)\in \Sigma_d^2[x], \end{eqnarray*}

其中, d\geq \max\{\text{deg} f,\text{deg} g,\mathop{\max}\limits_{1\leq j\leq s}h_j\}.

注3.2 若函数 g\equiv 1, 则推论 3.1 的 (i) 和 (iii) 退化为文献 [5,定理 2.1]. 因此, 推论 3.1 推广和改进了文献 [5] 的相应结果.

4 对偶性与平方和松弛性质刻画

本节旨在借助法锥型次微分约束规格条件, 刻画 (\mathrm{UFP}) 的鲁棒对偶性质和平方和松弛性质.

y\in \mathbb{R}^{n}, \mu \geq 0\lambda_j\geq 0. 对于固定的 w_j\in W_j, j=1,\cdots,s, (\mathrm{UFP}) 的 Wolfe 型对偶问题为

\begin{eqnarray*} (\mathrm{UFD}) \left\{ \begin{aligned} &\max \mu \\ & s.t. \nabla f(y)-\mu \nabla g(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)=0, \\ & f(y)-\mu g(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\geq 0, \\ & y\in \mathbb{R}^{n}, \mu \geq 0, \lambda_j \geq 0, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

(\mathrm{UFD}) 的最优对等问题, 即 (\mathrm{UFP}) 的 Wolfe 型鲁棒对偶问题 (\mathrm{OFD}) 定义如下

\begin{eqnarray*} (\mathrm{OFD}) \left\{ \begin{aligned} &\max \mu \\ & s.t. \nabla f(y)-\mu \nabla g(y)+\sum_{j=1}^s\lambda_j \nabla_1h_j(y,w_j)=0, \\ & f(y)-\mu g(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\geq 0, \\ & y\in \mathbb{R}^{n}, \mu \geq 0, \lambda_j \geq 0, w_j\in W_j, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

注4.1 若函数 g\equiv 1, 则 (\mathrm{UFP}) 退化为经典的不确定凸多项式优化问题

\begin{eqnarray*} (\mathrm{UCP}) \left\{ \begin{aligned} &\min_{x\in \mathbb{R}^{n}} f(x) \\ & s.t. h_j(x,w_j)\leq0,j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

(\mathrm{UFD}) 退化为 (\mathrm{UCP}) 的 Wolfe 型对偶问题

\begin{eqnarray*} \left\{\begin{aligned} &\max f(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\\ & s.t. \nabla f(y)+\sum_{j=1}^s\lambda_j \nabla_1 h_j(y,w_j)=0, \\ & y\in\mathbb{R}^n, \lambda_j \geq 0, j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

(\mathrm{OFD}) 退化为 (\mathrm{UCP}) 的 Wolfe 型鲁棒对偶问题

\begin{eqnarray*} \left\{ \begin{aligned} &\max f(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\\ & s.t. \nabla f(y)+\sum_{j=1}^s\lambda_j \nabla_1 h_j(y,w_j)=0, \\ & y\in\mathbb{R}^n,\lambda_j \geq 0,w_j\in W_j,j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

当前, 借助不同的约束规格条件, 学者们研究了 (\mathrm{UCP}) 及其相关问题的 Wolfe 型鲁棒对偶问题, 得到了鲁棒对偶性结果, 如文献 [9],[16],[17],[18].

接下来, 给出 (\mathrm{UFD}) 的鲁棒可行集和鲁棒最优解的定义. 方便起见, 记 w:=(w_1,\cdots,w_s)\in\prod_{j=1}^sW_j 以及 \lambda:=(\lambda_1,\cdots,\lambda_s)\in \mathbb{R}^s.

定义4.1 (\mathrm{UFD}) 的鲁棒可行集定义为

\tilde{C}:=\left\{\begin{aligned} \begin{array}{c|l} &\nabla f(y)-\mu \nabla g(y)+\sum_{j=1}^s\lambda_j \nabla_1h_j(y,w_j)=0, \\ (y,\mu,\lambda,w) &f(y)-\mu g(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\geq 0,\\ & y\in \mathbb{R}^{n}, \mu \geq 0, \lambda_j \geq 0, w_j\in W_j, j=1,\cdots,s \end{array} \end{aligned}\right\}.

定义4.2 (\bar{y},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}(\mathrm{OFD}) 的最优解, 即 \mu \leq \bar{\mu}, \forall(y,\mu,\lambda,w)\in \tilde{C}, 则称 (\bar{y},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}(\mathrm{UFD}) 的鲁棒最优解.

接下来, 建立 (\mathrm{UFP})(\mathrm{UFD}) 之间的鲁棒对偶性, 即 (\mathrm{RFP})(\mathrm{OFD}) 之间的对偶性质.

定理4.1 (鲁棒弱对偶性) 设 x\in C 以及 (y,\mu,\lambda,w)\in \tilde{C}. 则

\frac{f(x)}{g(x)}\geq\mu.

因为 (y,\mu,\lambda,w)\in \tilde{C}, 所以 y\in \mathbb{R}^{n}, \mu \geq 0, \lambda_j \geq 0, w_j\in W_j, j=1,\cdots,s,

\nabla f(y)-\mu \nabla g(y)+\sum_{j=1}^s\lambda_j \nabla_1h_j(y,w_j)=0,
(4.1)
f(y)-\mu g(y)+\sum_{j=1}^s\lambda_j h_j(y,w_j)\geq 0.
(4.2)

又由凸函数梯度的定义可知, 对于任意的 x\in C, f(x)-f(y)\geq \langle \nabla f(y),x-y\rangle, -g(x)+g(y)\geq \langle -\nabla g(y),x-y\rangle, 以及 h_j(x,w_j)-h_j(y,w_j)\geq \langle \nabla h_j(y,w_j),x-y\rangle, j=1,\cdots,s. 从而, 结合 (4.1) 式可知, 对于任意的 x\in C,

\begin{eqnarray*} &&f(x)-f(y) -\mu g(x)+\mu g(y)+\sum_{j=1}^s\lambda_jh_j(x,w_j)-\sum_{j=1}^s\lambda_jh_j(y,w_j)\\ &\geq& \left\langle \nabla f(y)-\mu\nabla g(y)+\sum_{j=1}^s\lambda_j\nabla h_j(y,w_j),x-y\right\rangle=0. \end{eqnarray*}

注意到 h_j(x,w_j)\leq 0, \forall x\in C. 从而, 由 (4.2) 式可知 f(x)-\mu g(x)\geq 0, \forall x\in C,

\begin{eqnarray*} \frac{f(x)}{g(x)}\geq \mu,\quad \forall x\in C. \end{eqnarray*}

故结论得证.

下述定理给出了 (\mathrm{UFP})(\mathrm{UFD}) 之间的鲁棒强对偶关系.

定理4.2 (鲁棒强对偶性) 设 (\mathrm{NCQ})\bar{x}\in C 处成立. 若 \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解, 则存在 \bar{\lambda}_j\geq 0\bar{w}_j\in W_j, j=1,\cdots,s, 使得 (\bar{x},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}(\mathrm{UFD}) 的鲁棒最优解, 其中 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}.

\bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解. 令 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}. 则由定理 3.1 可知, 存在 \bar{\lambda}_j\geq 0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

\nabla f(\bar{x})-\bar{\mu}\nabla g(\bar{x})+\sum_{j=1}^s\bar{\lambda}_j \nabla_1 h_j(\bar{x},\bar{w}_j)=0\left. \text{和} \begin{array}{l}\bar{\lambda}_j h_j(\bar{x},\bar{w}_j)=0.\end{array}\right.

\bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})} 可知

f(\bar{x})-\bar{\mu}g(\bar{x})+\sum_{j=1}^s\bar{\lambda}_j h_j(\bar{x},\bar{w}_j)= 0.

因此, (\bar{x},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}.

进一步地, 对于任意的 (y,\mu,\lambda,w)\in \tilde{C}, 由定理 4.1 可知 \mu-\bar{\mu}=\mu-\frac{f(\bar{x})}{g(\bar{x})}\leq 0. 从而, (\bar{x},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}(\mathrm{UFD}) 的鲁棒最优解. 故定理得证.

借助注 3.1 和定理 4.2, 下述推论自然成立.

推论4.1 假定鲁棒 Slater 条件 (3.1) 成立. 若 \bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解, 则存在 \bar{\lambda}_j\geq 0\bar{w}_j\in W_j, j=1,\cdots,s, 使得 (\bar{x},\bar{\mu},\bar{\lambda},\bar{w})\in \tilde{C}(\mathrm{UFD}) 的鲁棒最优解, 其中 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}.

本节的最后, 研究 (\mathrm{UFP}) 的精确平方和松弛性质, 即(\mathrm{UFP}) 与其平方和松弛对偶问题之间的强对偶性质.

\mu \in\mathbb{R}\lambda_j\geq 0, j=1,\cdots,s, 引入 (\mathrm{UFP}) 的平方和松弛对偶问题

\begin{eqnarray*} \mathrm{(D_{SOS})} \left\{ \begin{aligned} &\max \mu \\ & s.t. f-\mu g+\sum_{j=1}^s\lambda_j h_j(\cdot,w_j)\in \Sigma_d^2[x], \\ & \mu \geq 0,\lambda_j \geq 0,w_j\in W_j,j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

注4.2 若函数 g\equiv 1, 则 (\mathrm{D_{SOS}}) 退化为 (\mathrm{UCP}) 的平方和松弛对偶问题, 即

\begin{eqnarray*} \left\{ \begin{aligned} &\max \mu \\ & s.t. f +\sum_{j=1}^s\lambda_j h_j(\cdot,w_j)-\mu\in \Sigma_d^2[x], \\ & \mu \geq 0,\lambda_j \geq 0,w_j\in W_j,j=1,\cdots,s. \end{aligned} \right. \end{eqnarray*}

(\mathrm{UCP}) 的平方和松弛对偶问题已得到了学者们的广泛研究, 如文献 [5],[6],[19].

为刻画 (\mathrm{UFP})(\mathrm{D_{SOS}}) 之间的对偶性质, 首先给出 (\mathrm{D_{SOS}}) 的可行集和最优解的概念.

定义4.3 (\mathrm{D_{SOS}}) 的可行集为

\bar{C}:=\left\{\begin{aligned} (\mu,\lambda,w)\mid f-\mu g+\sum_{j=1}^s\lambda_j h_j(y,w_j)\in\Sigma_d^2[x],\mu \geq 0,\lambda_j \geq 0,w_j\in W_j,j=1,\cdots,s \end{aligned}\right\}.

定义4.4 (\bar{\mu},\bar{\lambda},\bar{w})\in \bar{C}. 若对于任意的 (\mu,\lambda,w)\in \bar{C}, \mu\leq \bar{\mu}, 则称 (\bar{\mu},\bar{\lambda},\bar{w})\in \bar{C}(\mathrm{D_{SOS}}) 的最优解.

接下来, 研究 (\mathrm{UFP})(\mathrm{D_{SOS}}) 之间的对偶性质.

定理4.3 x\in C(\mu,\lambda,w)\in \bar{C}. 则

\frac{f(x)}{g(x)}\geq\mu.

因为 (\mu,\lambda,w)\in \bar{C}, 所以 \mu \geq 0, \lambda_j\geq 0, w_j\in W_j, j=1,\cdots,s, 并且存在 \sigma\in \Sigma_d^2[x] , 使得

f(x)-\mu g(x)+\sum_{j=1}^s\lambda_j h_j(x,w_j)=\sigma(x), \forall x\in \mathbb{R}^n.

又因为 \sigma(x)\geq 0, 所以

f(x)-\mu g(x)+\sum_{j=1}^s\lambda_j h_j(x,w_j)\geq 0, \forall x\in \mathbb{R}^n.
(4.3)

注意到 h_j(x,w_j)\leq 0, \forall x\in C. 故, 由 (4.3) 式可知 f(x)-\mu g(x)\geq 0, \forall x\in C. 因此, \frac{f(x)}{g(x)}\geq\mu. 定理证毕.

定理4.4 (精确平方和松弛) 设 (\mathrm{NCQ})\bar{ x}\in C 处成立. 若 \bar{ x}\in C(\mathrm{UFP}) 的鲁棒最优解, 则存在 \bar{\lambda}_j\geq 0\bar{w}_j\in W_j, j=1,\cdots,s, 使得 (\bar{\mu},\bar{\lambda},\bar{w})\in \bar{C}(\mathrm{D_{SOS}}) 的鲁棒最优解, 其中 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}.

\bar{x}\in C(\mathrm{UFP}) 的鲁棒最优解. 则由定理 3.1(iii) 可知, 存在 \bar{\lambda}_j\geq 0\bar{w}_j\in W_j, j=1,\cdots,s, 使得

f-\bar{\mu}g +\sum_{j=1}^s\bar{\lambda}_j h_j(\cdot,\bar{w}_j)\in \Sigma_d^2[x],

其中 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}. 故, (\bar{\mu},\bar{\lambda},\bar{w})(\mathrm{D_{SOS}}) 的可行解.

下证 (\bar{\mu},\bar{\lambda},\bar{w})(\mathrm{D_{SOS}}) 的最优解. 事实上, 对于 (\mathrm{D_{SOS}}) 的任意可行解 (\mu,\lambda,w), 由定理 4.3 可知

\bar{\mu}-\mu=\frac{f(\bar{x})}{g(\bar{x})}-\mu\geq 0.

因此, (\bar{\mu},\bar{\lambda},\bar{w})(\mathrm{D_{SOS}}) 的最优解. 定理得证.

借助注 3.1 和定理 4.4, 下述推论自然成立.

推论4.2 假定鲁棒 Slater 条件 (3.1) 成立. 若 \bar{ x}\in C(\mathrm{UFP}) 的鲁棒最优解, 则存在 \bar{\lambda}_j\geq 0 以及 \bar{w}_j\in W_j, j=1,\cdots,s, 使得 (\bar{\mu},\bar{\lambda},\bar{w})\in \bar{C}(\mathrm{D_{SOS}}) 的鲁棒最优解, 其中 \bar{\mu}=\frac{f(\bar{x})}{g(\bar{x})}.

注4.3 当函数 g\equiv 1 时, 借助鲁棒 Slater 条件 (3.1), 文献 [5,定理 2.3] 也刻画了类似的平方和松弛性质. 由于 (\mathrm{NCQ}) 弱于鲁棒 Slater 条件 (3.1), 故定理 4.4 和推论 4.2 推广和改进了文献 [5,定理 2.3].

5 总结

本文主要对一类带不确定参数的分式多项式优化问题展开了研究. 首先借助法锥约束规格条件, 研究了该不确定分式多项式问题的鲁棒最优解的 KKT 条件刻画和平方和条件刻画. 随后给出了该不确定分式多项式优化问题的鲁棒 Wolfe 对偶问题, 并研究了它们之间的鲁棒弱对偶与强对偶性质. 最后, 借助平方和条件, 建立了该不确定分式多项式优化问题的平方和松弛对偶问题, 并研究了它的精确平方和松弛性质.

另一方面, 带有不确定参数的多目标多项式优化问题是当前多项式优化问题的一大研究热点. 因此, 能否借助本文的方法, 刻画多目标分式多项式优化问题的鲁棒有效解或者鲁棒弱有效解, 并得到相应的最优性和对偶性理论, 这将是我们进一步要研究和考虑的问题.

参考文献

Helton J W, Nie J.

Semidefinite representation of convex sets

Mathematical Programming, 2010, 122(1): 21-64

[本文引用: 2]

Lasserre J B. Moments, Positive Polynomials and Their Applications. London: Imperial College Press, 2009

[本文引用: 1]

Ahmadi A A, Parrilo P A.

A convex polynomial that is not sos-convex

Mathematical Programming, 2012, 135(1): 275-292

[本文引用: 2]

Ahmadi A A, Parrilo P A.

A complete characterization of the gap between convexity and SOS-convexity

SIAM Journal on Optimization, 2013, 23(2): 811-833

[本文引用: 2]

Jeyakumar V, Li G, Vicente-Pérez J.

Robust SOS-convex polynomial optimization problems: Exact SDP relaxations

Optimization Letters, 2015, 9(1): 1-18

[本文引用: 7]

Jeyakumar V, Li G.

A new class of alternative theorems for SOS-convex inequalities and robust optimization

Applicable Analysis, 2015, 94(1): 56-74

[本文引用: 2]

Chuong T D.

Linear matrix inequality conditions and duality for a class of robust multiobjective convex polynomial programs

SIAM Journal on Optimization, 2018, 28(3): 2466-2488

[本文引用: 1]

Jiao L, Lee J H.

Finding efficient solutions for multicriteria optimization problems with SOS-convex polynomials

Taiwanese Journal of Mathematics, 2019, 23(6): 1535-1550

[本文引用: 1]

Sun X K, Tan W, Teo, K L.

Characterizing a class of robust vector polynomial optimization via sum of squares conditions

Journal of Optimization Theory and Applications, 2023, 197(2): 737-764

[本文引用: 2]

Jeyakumar V, Li G.

Exact SDP relaxations for classes of nonlinear semidefinite programming problems

Operations Research Letters, 2012, 40(6): 529-536

[本文引用: 1]

Lee J H, Jiao L.

Solving fractional multicriteria optimization problems with sum of squares convex polynomial data

Journal of Optimization Theory and Applications, 2018, 176(2): 428-455

[本文引用: 1]

Dinkelbach W.

On nonlinear fractional programming

Management Science, 1967, 13: 492-498

[本文引用: 2]

Ben-Tal A, Nemirovski A.

Robust optimization-methodology and applications

Mathematical Programming, 2002, 92(3): 453-480

[本文引用: 1]

Ben-Tal A, Ghaoui L E, Nemirovski A. Robust Optimization. Princeton: Princeton University Press, 2009

[本文引用: 1]

Gabrel V, Murat C, Thiele A.

Recent advances in robust optimization: an overview

European Journal of Operational Research, 2014, 235(3): 471-483

[本文引用: 1]

叶冬平, 方东辉.

鲁棒复合优化问题的 Lagrange 对偶

数学物理学报, 2020, 40A(4): 1095-1107

[本文引用: 1]

Ye D P, Fang D H.

Lagrange dualities for robust composite optimization problems

Acta Math Sci, 2020, 40A(4): 1095-1107

[本文引用: 1]

刘娟, 龙宪军.

非光滑多目标半无限规划问题的混合型对偶

应用数学和力学, 2021, 42(6): 595-601

[本文引用: 1]

Liu J, Long X J.

Mixed type duality for nonsmooth multiobjective semi-infinite programming problems

Applied Mathematics and Mechanics, 2021, 42(6): 595-601

[本文引用: 1]

黄嘉译, 孙祥凯.

一类两阶段自适应鲁棒多目标规划的对偶性刻画

数学物理学报, 2024, 44A(1): 185-194

[本文引用: 1]

Huang J Y, Sun X K.

Duality characterizations for a class of two-stage adjustable robust multiobjective programming

Acta Mathematica Scientia, 2024, 44A(1): 185-194

[本文引用: 1]

Chuong T D, Jeyakumar V.

Tight SDP relaxations for a class of robust SOS-convex polynomial programs with out the Slater condition

Journal of Convex Analysis, 2018, 25(4): 1159-1182

[本文引用: 1]

/