## Approximate Optimality Conditions and Mixed Type Duality for a Class of Non-Convex Optimization Problems

Wang Jiaolang,, Fang Donghui,

College of Mathematics and Statistics, Jishou University, Hunan Jishou 416000

 基金资助: 国家自然科学基金.  11861033湖南省自然科学基金.  2020JJ4494吉首大学科研基金.  Jdy20069吉首大学科研基金.  JGY202139

 Fund supported: the NSFC.  11861033the NSF of Hunan Province.  2020JJ4494the Scientific Research Fund of Jishou University.  Jdy20069the Scientific Research Fund of Jishou University.  JGY202139

Abstract

By using the properties of the Fréchet subdifferentials, we first introduce a new constraint qualification and then establish some approximate optimality conditions for the non-convex constrained optimization problem with objective function and/or constraint function being α-convex function. Moreover, some results for the weak duality, strong duality and converse-like duality theorems between this non-convex optimization problem and its mixed type dual problem are also given.

Keywords： Non-convex constraint optimization problem ; Constraint qualification ; Approximate optimality conditions ; Mixed type duality

Wang Jiaolang, Fang Donghui. Approximate Optimality Conditions and Mixed Type Duality for a Class of Non-Convex Optimization Problems. Acta Mathematica Scientia[J], 2022, 42(3): 651-660 doi:

## 2 记号与定义

$X$是Banach空间, $X^\ast $$X 的对偶空间, \rm{赋予弱} ^{\ast} 拓扑 w^\ast(X^\ast, X) . \langle x^\ast, x\rangle 表示泛函 x^\ast\in X^\ast$$ x\in X$处的值, 即$\langle x^\ast, x\rangle = x^\ast(x)$. ${\Bbb B}^\ast$表示$X^\ast$上的闭单位球. 记$\xi\in X$的范数为$\|\xi\|$, 定义为

$T$是任意(可能无限)指标集, 记${\Bbb R}^{(T)}: = \{\lambda = (\lambda_t)_{t\in T}:\rm{只有有限多个}\lambda_t\neq0\}, $${\Bbb R}_+^{(T)} 表示 {\Bbb R}^{(T)} 上的非负锥, 即 f:X\rightarrow \overline{{{\Bbb R}}} 为真凸函数. 定义 f 的有效定义域, 上图和共轭函数分别为 定义函数 f 在点 x\in {\rm dom}f 处的次微分为 $$\partial f(x): = \{x^\ast\in X^\ast:f(x)+\langle x^\ast, y-x\rangle\leq f(y), \forall y\in X\}.$$ 由定义可知, Young-Fenchel不等式和Young等式成立, 即 $$f(x)+f^\ast(x^\ast)\geq\langle x^\ast, x\rangle,\ \ \forall(x, x^\ast)\in X\times X^\ast,$$ $$f(x)+f^\ast(x^\ast) = \langle x^\ast, x\rangle\Leftrightarrow x^\ast\in\partial f(x).$$ 定义集合 C 在点 x_0 处的法锥为 \varphi:X\rightarrow \overline{{{\Bbb R}}} 为实值延拓函数, x\in {\rm dom}\varphi 满足 |\varphi(x)|<\infty , 定义 \varphi 在点 x 处的Fréchet次微分为(参看文献[14]): 注意到, 当 \varphi 为凸函数时, 则 \hat{\partial}\varphi(x) = \partial\varphi(x) , \forall x\in {\rm dom}\varphi . \varphi 在点 x 处Fréchet可微, 且梯度为 \nabla\varphi(x) , 则 \hat{\partial}\varphi(x) 是单点集, 记为 \{\nabla\varphi(x)\} . 显然, 由Fréchet次微分的定义可知 $$x_0 \rm{是} \varphi \rm{的最小值点}\Rightarrow 0\in\hat{\partial}\varphi(x_0).$$ 定义2.1[15] 令 \alpha\geq0, f:X\rightarrow \overline{{{\Bbb R}}} 为真函数. 若对任意的 x, y\in X$$ \lambda\in[0, 1],$

## 3 近似最优性条件

$f, h_t:X\rightarrow \overline{{{\Bbb R}}}, t\in T$为真函数, $A: = \{x\in C:h_t(x)\leq0, t\in T\}$为问题$(P)$的可行集. 令$x\in A$, 定义$A(x): = \{\lambda\in {\Bbb R}_+^{(T)}:\lambda_th_t(x) = 0, t\in T\}$, $T(x): = \{t\in T:h_t(x) = 0\}.$注意到, 为简化问题的处理, 文献[17-19] 均假设$A$是凸集, 并在此假设下建立了约束优化问题的KKT类最优性条件. 受上述文献的启发, 本文总假设$A$是凸集. 类似于文献[20]中的定义3.2, 我们引入如下约束规范条件.

$$$N(x;A)\subseteq N(x;C)+\bigcup\limits_{\lambda\in A(x)}\sum\limits_{t\in T}\lambda_t\hat{\partial}h_t(x),$$$

$\rm(ii) $$f(x_0)\leq f(x)+\varepsilon\|x-x_0\| , 则称 x_0 是问题 (P) 的拟 \varepsilon -最优解. 下述定理分别建立了问题 (P) 的近似最优性条件成立的必要条件和充分条件. 定理3.3 令 \varepsilon\geq0 , x_0\in A . 假设 f 在点 x_0 处Fréchet可微, 且系统 \{\delta_C; h_t:t\in T\} 在点 x_0 处满足 (ABCQ) 条件. 若 x_0 是问题 (P) 的拟 \varepsilon -最优解, 则存在 \bar{\lambda}\in A(x_0) , 使得 $$-\nabla f(x_0)\in N(x_0;C)+\sum\limits_{t\in T}\bar{\lambda}_t\hat{\partial}h_t(x_0)+\varepsilon{\Bbb B}^\ast.$$ 设 x_0 是问题 (P) 的拟 \varepsilon -最优解, 则对任意的 x\in A , 有 x_0 是以下问题的最优解 因此 由于 f 在点 x_0 处Fréchet可微, 由引理2.4可知 由于 \|\cdot-x_0\| 是凸函数, 且集合 A 是凸集, 从而可得 \|\cdot-x_0\| 是连续函数, 故由引理2.3可知 从而由系统 \{\delta_C;h_t:t\in T\} 在点 x_0 处满足 (ABCQ) 条件可知, 存在 \bar{\lambda}\in A(x_0) 使得(3.2) 式成立. 定理3.4 令 x_0\in A, \varepsilon, \alpha, \alpha_t\geq0, t\in T . 假设 f$$ \alpha$ -凸函数, $h_t $$\alpha_t -凸函数. 若存在 \bar{\lambda}\in A(x_0) 使得下式成立 $$0\in\hat{\partial}f(x_0)+N(x_0;C)+\sum\limits_{t\in T}\bar{\lambda}_t\hat{\partial}h_t(x_0)+\varepsilon{\Bbb B}^\ast,$$ x_0 是问题 (P) 的拟 (\varepsilon+2\alpha+2\sum\limits_{t\in T}\bar{\lambda}_t\alpha_t) -最优解. 设存在 \bar{\lambda}\in A(x_0) 使得(3.3) 式成立. 故存在 \xi\in\hat{\partial}f(x_0), \gamma\in N(x_0;C), \eta_t\in\hat{\partial}h_t(x_0), t\in T$$ b\in {\Bbb B}^\ast$使得

$$$\xi+\gamma+\sum\limits_{t\in T}\bar{\lambda}_t\eta_t+\varepsilon b = 0.$$$

$\gamma\in N(x_0;C)$可知, 对任意的$x\in C $$\langle\gamma, x-x_0\rangle\leq0 . 结合(3.4) 式, 有 因此, 由Cauchy-Schwarz不等式可得 $$\langle \xi, x-x_0\rangle+\sum\limits_{t\in T}\bar{\lambda}_t\langle\eta_t, x-x_0\rangle+\varepsilon\|x-x_0\|\geq0, \forall x\in C.$$ 由于 f$$ \alpha$ -凸函数, $h_t $$\alpha_t -凸函数, 且 \xi\in\hat{\partial}f(x_0), \eta_t\in\hat{\partial}h_t(x_0), t\in T , 由引理2.2有 $$f(x)-f(x_0)+2\alpha\|x-x_0\|\geq\langle\xi, x-x_0\rangle,\ \ \forall x\in X,$$ $$\sum\limits_{t\in T}\bar{\lambda}_th_t(x)-\sum\limits_{t\in T}\bar{\lambda}_th_t(x_0)+2\sum\limits_{t\in T}\bar{\lambda}_t\alpha_t\|x-x_0\|\geq\sum\limits_{t\in T}\bar{\lambda}_t\langle\eta_t, x-x_0\rangle,\ \ \forall x\in X.$$ 显然, A\subseteq C\subseteq X . 于是由(3.5)–(3.7) 式可得 注意到, 对任意的 x\in A , \bar{\lambda}_th_t(x)\leq0$$ \bar{\lambda}_th_t(x_0) = 0$. 故由上式有

$f, h_t, t\in T$均为凸函数, 我们引入如下约束规范条件.

$$$\partial(f+\delta_A)\subseteq \partial f(x)+N(x;C)+\bigcup\limits_{\lambda\in A(x)}\sum\limits_{t\in T}\lambda_t\partial h_t(x),$$$

$\varepsilon = 0$. 由定理3.7可得如下推论.

$$$f(x)\geq L(y, \lambda)-(\varepsilon+2\alpha+2\sum\limits_{t\in T}(\lambda_t+\mu_t)\alpha_t)\|x-y\|.$$$

任取$x\in A $$(y, \lambda, \mu)\in F(D) . 则有 故存在 \xi\in\hat{\partial}f(y), \eta_t\in\hat{\partial}h_t(y), t\in T, \gamma\in N(y;C)$$ b\in {\Bbb B}^\ast$使得

$$$\xi+\sum\limits_{t\in T}(\lambda_t+\mu_t)\eta_t+\gamma+\varepsilon b = 0.$$$

$\gamma\in N(y;C)$, $x\in A\subseteq C$可知, $\langle\gamma, x-y\rangle\leq0$. 结合(4.2) 式和Cauchy-Schwarz不等式可得

设$(x_0, \bar{\lambda}, 0) $$(x_0, 0, \bar{\lambda})\in F(D) 满足 \bar{\lambda}_th_t(x_0) = 0 , 则存在 \xi\in\hat{\partial}f(x_0), \gamma\in N(x_0;C), \eta_t\in\hat{\partial}h_t(x_0), t\in T$$ b\in {\Bbb B}^\ast$使得(3.4) 式成立. 假设$x_0\in A$不是问题$(P)$的拟$(\varepsilon+2\alpha+2\sum\limits_{t\in T}\bar{\lambda}_t\alpha_t)$ -最优解, 则存在$\bar{x}\in A$使得

$$$f(x_0)>f(\bar{x})+(\varepsilon+2\alpha+2\sum\limits_{t\in T}\bar{\lambda}_t\alpha_t)\|\bar{x}-x_0\|.$$$

$$$f(\bar{x})-f(x_0)+2\alpha\|\bar{x}-x_0\|\geq\langle\xi, \bar{x}-x_0\rangle, \forall x\in X,$$$

$$$\sum\limits_{t\in T}\bar{\lambda}_th_t(\bar{x})-\sum\limits_{t\in T}\bar{\lambda}_th_t(x_0)+2\sum\limits_{t\in T}\bar{\lambda}_t\alpha_t\|\bar{x}-x_0\|\geq\sum\limits_{t\in T}\bar{\lambda}_t\langle\eta_t, \bar{x}-x_0\rangle, \forall x\in X.$$$

$$$\langle \gamma, \bar{x}-x_0\rangle\leq0.$$$

设$\bar{\lambda}\in A(x_0)$使得(3.3) 式成立. 故由定理3.4可知$x_0$是问题$(P)$的拟$(\varepsilon+2\alpha)$ -最优解, 且$(x_0, \bar{\lambda}, 0) $$(x_0, 0, \bar{\lambda}) 是问题 (D) 的可行解. 注意到, 对任意的 (y, \lambda, \mu)\in F(D) , (x_0, \bar{\lambda}, 0) \rm{和} (x_0, 0, \bar{\lambda}) 是问题 (D) 的拟 (\varepsilon+2\alpha) -最优解. \mu_t = 0, t\in T 时, 问题 (D) 转化为Wolfe型对偶问题, 即 F(D^W) 为问题 (D^W) 的可行集. 故由定理4.2和定理4.3, 我们可得以下推论. 推论4.5 令 \varepsilon\geq0 . 则对任意的 x\in A$$ (y, \lambda)\in F(D^W)$

$$$f(x)\geq f(y)-(\varepsilon+2\alpha+2\sum\limits_{t\in T}\mu_t\alpha_t)\|x-y\|.$$$

$x_0$$(x_0, \bar{\mu})$分别是问题$(P)$和问题$(D^M)$的拟$(\varepsilon+2\alpha+2\sum\limits_{t\in T}\bar{\mu}_t\alpha_t)$ -最优解.

## 参考文献 原文顺序 文献年度倒序 文中引用次数倒序 被引期刊影响因子

Ben-Tal A , Kerzner L , Zlobec S .

Optimality conditions for convex semi-infinite programming problems

Nav Res Logist, 1980, 27, 413- 435

Boţ R I , Grad S M .

Wolfe duality and Mond-Weir duality via perturbations

Nonlinear Anal, 2010, 73, 374- 384

Dinh N , Goberna M A , Lopez M A , Son T Q .

New Farkas-type constraint qualifications in convex infinite programming

ESAIM Control Optim Calc Var, 2007, 13, 580- 597

Fang D H , Li C , Ng K F .

Constraint qualifications for extended Farkas's lemmas and Lagrangian dualities in convex infinite programming

SIAM J Optim, 2009, 20, 1311- 1332

Fang D H , Li C , Ng K F .

Constraint qualifications for optimality conditions and total Lagrangian dualities in convex infinite programming

Nonlinear Anal, 2010, 73, 1143- 1159

Lee J H , Lee G M .

On ε-solutions for convex optimization problems with uncertainty data

Positivity, 2012, 16, 509- 526

Lee J H , Jiao L G .

On quasi ε-solution for robust convex optimization problems

Optim Lett, 2017, 11, 1609- 1622

Sun X K , Fu H Y , Zeng J .

Robust approximate optimality conditions for uncertain nonsmooth optimization with infinite number of constraints

Mathematics, 2019, 7, 12- 25

Ye D P , Hu L L , Fang D H .

ε-Optimality conditions And ε-saddle point theorems for robust conical programming problems

J Nonlinear Convex Anal, 2020, 21, 835- 850

Sun X K , Teo K L , Long X J .

Characterizations of robust ε-quasi optimal solutions for nonsmooth optimization problems with uncertain data

Optim, 2021, 70, 1- 24

Zhong L N , Jin Y F .

Optimality conditions for minimax optimization problems with an infinite number of constraints and related applications

Acta Math Appl Sin-E, 2021, 37, 251- 263

Mishra S K , Laha V .

On Minty variational principle for nonsmooth vector optimization problems with approximate convexity

Optim Lett, 2016, 10, 577- 898

Son T Q , Kim D S .

ε-Mixed type duality for nonconvex multiobjective programs with an infinite number of constraints

J Glob Optim, 2013, 57, 447- 465

Mordukhovich B S , Nam N M , Yen N D .

Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming

Optim, 2006, 55, 685- 708

Alejandro J , Dinh T L , Michel T R .

ε-Subdifferential and ε-monotonicity

Nonlinear Anal Theory, 1998, 33, 71- 90

Zǎlinescu C . Convex Analysis in General Vector Spaces. New Jersey: World Scientific, 2002

Lasserre J B .

On representations of the feasible set in convex optimization

Optim Lett, 2010, 4, 1- 5

Dutta J , Lalitha C S .

Optimality conditions in convex optimization revisited

Optim Lett, 2013, 7, 221- 229

Chieu N H , Jeyakumar V , Li G Y , Mohebi H .

Constraint qualifications for convex optimization without convexity of constraints: new connections and applications to best approximation

European J Oper Res, 2018, 265, 19- 25

Chuong T D , Kim D S .

Nonsmooth semi-infinite multiobjective optimization problems

J Optim Theory Appl, 2014, 160, 748- 762

/

 〈 〉