帶0-1和線性約束的特殊三次規(guī)劃問題的全局最優(yōu)性條件

周 莉

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331）

帶0-1和線性約束的特殊三次規(guī)劃問題的全局最優(yōu)性條件

周 莉

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶401331）

研究了一類帶有不等式約束和0-1約束的特殊三次規(guī)劃問題的全局最優(yōu)性條件，給出了此問題的一個全局最優(yōu)性充分必要條件.同時通過數(shù)值例子來說明給出的全局最優(yōu)性充分必要條件是很容易驗證的.

三次規(guī)劃問題；全局最優(yōu)性條件；0-1約束；線性不等式約束

本文考慮如下帶有的線性約束和0-1約束的特殊三次規(guī)劃問題：

其中：a，b∈Rn，c∈Rm，B∈Rm×n，A為實(shí)對稱矩陣.令，并設(shè)S≠Φ.

三規(guī)劃問題具有很廣泛的應(yīng)用，在金融、農(nóng)業(yè)、證券投資組合等方面都有廣泛的應(yīng)用［1-3］.而三次問題的研究成果可以應(yīng)用到二次規(guī)劃問題，同時也豐富了二次規(guī)劃的理論［4-6］.文獻(xiàn)［4］是刻畫了二次背包問題的全局最優(yōu)性充分必要條件；文獻(xiàn)［7］利用拉格朗日函數(shù)和L-次微分的方法給出了帶有二次等式約束，二次不等式約束以及雙值約束的二次規(guī)劃問題的全局最優(yōu)性充分條件；文獻(xiàn)［8］利用同樣的方法給出了一類帶有二次約束的三次規(guī)劃問題的全局最優(yōu)性充分條件；文獻(xiàn)［9-10］是利用L-次微分給出了帶有箱子或雙值約束的特殊三次規(guī)劃問題的全局最優(yōu)的充分性條件和必要性條件；文獻(xiàn)［11］利用二次上下估計法給出了一類帶有箱子約束或雙值約束的特殊三次規(guī)劃問題的全局最優(yōu)條件.本文主要研究了帶有不等式約束和0-1約束的特殊三次規(guī)劃問題的全局最優(yōu)性，給出了此問題的全局最優(yōu)性充分必要條件，并利用例子與文獻(xiàn)［7-8，12-13］的所得到的全局最優(yōu)性充分條件作對比，說明本文所給出的充要條件是很容易驗證的，該充要條件僅用到了原問題的數(shù)據(jù).

1 預(yù)備知識

R表示實(shí)線性空間，Rn表示n維歐幾里得空間.對于向量x，y∈Rn，x≥y表示對于任意的i=1，2，…，n有xi≥yi，記號A?B?A-B是半正定矩陣.I為單位矩陣，對任意的x=（x1，x2，…，xn）T∈Rn，用X=diag（x1，x2，…，xn）對角元素為x1，x2，…，xn的對角矩陣，因此x=Xe，其中e為單位向量.

對于二次背包問題：其中：a∈Rn，c∈Rm，B∈Rm×n，A為實(shí)對稱矩陣.令S=｛x∈U|Bx+c≤0｝，并設(shè)S≠Φ.對于，令為了方便研究，本文引進(jìn)下面一些記號，令：

顯然Γ是有限集，它取決于n的值.

對于對稱矩陣A=（aij）n×n，a=（aj）n×1=（a1，a2，…，an）T∈Rn和γ=｛i1，i2，…，ik｝∈Γ，令：

在文獻(xiàn)［4］中，給出了問題（CKP1）的一個全局最優(yōu)性充要條件，本文將利用這個結(jié)論給出問題（CKP）的一個全局最優(yōu)性充要條件.

引理1［4］（問題（CKP1）的全局最優(yōu)充要條件）設(shè)，則是問題（CKP1）的一個全局極小點(diǎn)當(dāng)且僅當(dāng)下面的條件［NSC1］成立：

2 主要結(jié)果

證明 因為x3=x，所以，問題（CKP）問題可以轉(zhuǎn)化成（CKP1）的形式來研究，再根據(jù)引理1可以得到：如果x 是問題（CKP）的一個全局極小點(diǎn)當(dāng)且僅當(dāng)條件［NSC］成立.

在文獻(xiàn)［7］中，利用拉格朗日函數(shù)的抽象次微分研究了帶有二次約束和雙值約束的二次規(guī)劃問題的全局最優(yōu)性充分條件；文獻(xiàn)［8］中，利用拉格朗日函數(shù)的抽象次微分研究了帶有二次約束的一類特殊三次規(guī)劃問題的全局最優(yōu)性充分條件，該目標(biāo)函數(shù)和本文的一致.利用文獻(xiàn)［7-8］的方法可以得到本文問題（CKP）的一個全局最優(yōu)性充分條件，具體描述如下：對于問題（CKP），設(shè)若存在λ∈Rm+和對角矩陣Q=diag（q1， q2，…，qn），qi∈R，i=1，2，…，n，且對任意的x∈S，有下列條件成立：

易知，本文所給出的全局最優(yōu)性充要條件［NSC］是條件［SC-CKP］的推廣.一方面，條件［NSC］僅用到了原問題的數(shù)據(jù)，而條件［SC-CKP］要討論λ∈Rm+和對角矩陣Q的存在性；另一方面，［NSC］是全局最優(yōu)性充分必要條件，而［SC-CKP］僅是全局最優(yōu)性充分條件.下面通過如下例子來說明.

例1

令a=（1，-1）T，b=（-3，8）T，r=（3，3）T，A=diag（r）T，B=（1，-1）T，c=-2，下面考慮點(diǎn)

下面用充分條件［SC-CKP］來判斷.

設(shè)對角矩陣Q=diag（q1，q2），qi∈R，i=1，2，λ∈Rm+，這里m=1.因為x=（1，0）T，所以diag（x）=diag（1，-1），計算可得A-Q=diag（3-q1，3-q2），則：

假設(shè)A-Q?0可得：q1≤3，q2≤3，由

綜上可以得到λ≤-5/2，λ≥1/2.因此，不存在拉格朗日參數(shù)λ＞0，使得條件成立.但由本文的方法知x=（1，0）T是全局最優(yōu)解.所以，條件 ［SC-CKP］只是充分條件，而不是必要條件.

［1］ HENIN C，DOUTRIAU J.A specia1ization of the convex simp1ex method to cubic programming［J］.Decis Econ Finance，1980，3：61-72.

［2］ HANOCH G，LEVY H.Efficient portfo1io with quadratic and cubic uti1ity［J］.J Bus，1970，43：181-189.

［3］ Levy H，Sarnat M.Investment and portfo1io ana1ysis［M］.New York：Wi1ey，1972.

［4］ WU Z Y，YANG Y J，BAI F S，et a1.G1oba1 optima1ity conditions and optimization oethods for quadratic knapsack prob1em［J］.Journa1 of Optimization Theory and App1ications，2011，151（2）：241-259.

［5］ LI G Q，WU Z Y，uan J.A new 1oca1 and g1oba1 optimization method for mixed integer quadratic programming prob1ems［J］.App1ied Mathematics and Computation，2010，217（6）：2501-2512.

［6］ WU Z Y，LI G Q，Quan J.G1oba1 optima1ity conditions and optimization methods for quadratic integer programming prob1ems［J］.Journa1 of G1oba1 Optimization，2011，51：549-568.

［7］ WU Z Y，JEYAKUMAR V，Rubinov A M.Sufficient conditions for g1oba1 optima1ity of biva1ent nonconvex quadratic programs with inequa1ity constraints［J］.Journa1 of Optimization Theory and App1ications，2007，133：123-130.

［8］ 葉敏，李國權(quán).帶有二次約束的一類特殊多項式規(guī)劃問題的全局最優(yōu)性充分條件［J］.重慶師范大學(xué)（自然科學(xué)版），2014，31（3）：17-20.

［9］ WANG Y J，LIANG Z A.G1oba1 optima1ity conditions for cubic minimization prob1em with box or binary constraints［J］.Journa1 of G1oba1 Optimization，2010，47：583-595.

［10］ ZHANG X M，WANG Y J，Ma W M.G1oba1 sufficient optima1ity conditions for a specia1 cubic minimization prob1em［J］.Mathematica1 Prob1ems in Engineering，2012，3（7）：178-192.

［11］ 周雪剛.具有超矩形約束的三次規(guī)劃的全局最優(yōu)性條件［J］.重慶師范大學(xué)學(xué)報（自然科學(xué)版），2014，31（4）：21-25.

［12］ 周莉，李國權(quán).帶混合約束的特殊三次規(guī)劃問題的全局最優(yōu)性充分條件［J］.重慶工商大學(xué)學(xué)報（自然科學(xué)版），2015，32（9）：16-19.

［13］ 葉敏.雙值約束三次規(guī)劃問題的全局最優(yōu)性充分條件［J］.重慶工商大學(xué)學(xué)報（自然科學(xué)版），2015，32（7）：48-51.

責(zé)任編輯：時 凌

Global OPtimalitY Conditions for a SPecial Cubic Minimization Problem with 0-1 and Linear Constraints

ZHOU Li
（Schoo1 of Mathematics，Chongqing Norma1 University，Chongqing 401331，China）

In this artic1e，we considered a specia1 cubic optimization prob1em with 0-1 and 1inear inequa1ity constraints.We give necessary and sufficient conditions of g1oba1 optima1ity for this specia1 cubic optimization prob1em.Numerica1 examp1es are a1so presented to show that the proposed optima1ity conditions are efficient.

cubic minimization prob1em；g1oba1 optima1ity conditions；0-1constraints；1inear inequa1ity constraints

O221

A

1008-8423（2016）02-0153-03

10.13501/j.cnki.42-1569/n.2016.06.010

2016-01-21.

重慶市自然科學(xué)基金項目（CSTC2013JLYJa00021）；重慶師范大學(xué)校級研究生科研創(chuàng)新項目（YKC15012）.

周莉（1990-），女，碩士生，主要從事最優(yōu)化理論與算法的研究.