# Global Sufficient Optimality Conditions for a Special Cubic Minimization Problem

Authors: Xiaomei Zhang; Yanjun Wang; Weimin Ma
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We present some sufficient global optimality conditions for a special cubic minimization problem with box constraints or binary constraints by extending the global subdifferential approach proposed by V. Jeyakumar et al.  (2006). The present conditions generalize the results developed in the work of V. Jeyakumar et al. where a quadratic minimization problem with box constraints or binary constraints was considered. In addition, a special diagonal matrix is constructed, which is used to provide a convenient method for justifying the proposed sufficient conditions. Then, the reformulation of the sufficient conditions follows. It is worth noting that this reformulation is also applicable to the quadratic minimization problem with box or binary constraints considered in the works of V. Jeyakumar et al. (2006) and Y. Wang et al. (2010). Finally some examples demonstrate that our optimality conditions can effectively be used for identifying global minimizers of the certain nonconvex cubic minimization problem.


---

## Body

## 1. Introduction

Consider the following cubic minimization problem with box constraints:(CP1)minf(x)=bTx3+12xTAx+aTx,s.t.x∈D=∏i=1n[ui,vi],
where ui,vi∈R, ui≤vi,i=1,2,…,n, and a=(a1,…,an)T∈Rn,b=(b1,…,bn)T∈Rn, A∈Sn, where Sn is the set of all symmetric n×n matrices. x3 that means (x13,…,xn3)T.The cubic optimization problem has spawned a variety of applications, especially in cubic polynomial approximation optimization [1], convex optimization [2], engineering design, and structural optimization [3]. Moreover, research results about cubic optimization problem can be applied to quadratic programming problems, which have been widely studied because of their broad applications, to enrich quadratic programming theory.Several general approaches can be used to establish optimality conditions for solutions to optimization problems. These approaches can be broadly classified into three groups: convex duality theory [4], local subdifferentials by linear functions [5–7], and global L-subdifferential and L-normal cone by quadratic functions [8–11]. The third approach, which we extend in this paper, is often adopted to develop optimality conditions for special optimization forms: quadratic minimizations with box or binary constraints, quadratic minimization with quadratic constraints, bivalent quadratic minimization with inequality constraints, and so forth.In this paper, we consider the cubic minimization problem, which generalizes the quadratic functions frequently considered in the mentioned papers. The proof method is based on extending the globalL-subdifferentials by quadratic functions [8, 12] to cubic functions. We show how an L-subdifferential can be explicitly calculated for cubic functions and then develop the global sufficient optimality conditions for (CP1). We also derive the global optimality conditions for special cubic minimization problems with binary constraints. But when we use the sufficient conditions, we have to determine whether a diagonal matrix Q exists. It is hard to identify whether the matrix Q exists. So we rewrite the sufficient conditions in an other way through constructing a certain diagonal matrix. This method is applicable to the quadratic minimization problem with box or binary constraints considered in [8, 12].This paper is organized as follows. Section2 presents the notions of L-subdifferentials and develops the sufficient global optimality condition for (CP1). The global optimality condition for special cubic minimization with binary constraints is presented in Section 3. In Section 4, numerical examples is given to illustrate the effectiveness of the proposed global optimality conditions.


## 2.L-Subdifferentials and Sufficient Conditions

In this section, basic definitions and notations that will be used throughout the paper are given. The real line is denoted byR and the n-dimensional Euclidean space is denoted by Rn. For vectors x,y∈Rn, x≥y means that xi≥yi, for i=1,…,n. A≽B means that the matrix A-B is a positive semidefinite. A diagonal matrix with diagonal elements α1,…,αn is denoted by diag(α1,…,αn). Let L be a set of real-valued functions defined on Rn.Definition 2.1 (L-subdifferentials [13]).
LetL be a set of real-valued functions. Let f:Rn→R. An element l∈L is called an L-subgradient of f at a point x0∈Rn if
(2.1)f(x)≥f(x0)+l(x)-l(x0),∀x∈Rn.
The set∂Lf(x) of all L-subgradients of f at x0 is referred to as L-subdifferential of f at x0.
Throughout the rest of the paper, we use the specific choice ofL defined by
(2.2)L={bTx3+12xTQx+βTx∣Q=diag(α1,…,αn),αi∈R,β∈Rn}.Proposition 2.2.
Letf(x)=bTx3+(1/2)xTAx+aTx and x-=(x-1,…,x-n)T∈Rn. Then
(2.3)∂Lf(x-)={bTx3+12xTQx+βTx|β=(AQ)x-+a,αi∈RA-Q≽0,Q=diag(α1,…,αn)}.Proof.
Suppose that there exists a diagonal matrixQ=diag(α1,…,αn), such that A-Q≽0. Let
(2.4)l(x)=bTx3+12xTQx+βTx,β=(A-Q)x-+a.
Then it suffices to prove that l(x)∈∂Lf(x-). Let
(2.5)ϕ(x)=f(x)-l(x)=12xT(A-Q)x+(a-β)Tx.
Since ∇2ϕ(x)=A-Q≽0, for all x∈Rn, we know that ϕ(x) is a convex function on Rn. Note that ∇ϕ(x-)=(A-Q)x-+(a-β)=0, and so x- is a global minimizer of ϕ(x), that is, ϕ(x)≥ϕ(x-), for all x∈Rn. This means that l(x)∈∂Lf(x-).
Next we prove the converse.
Letl(x)∈∂Lf(x-),l(x)=bTx3+(1/2)xTQx+βTx. By definition,
(2.6)f(x)≥f(x-)+l(x)-l(x-),∀x∈Rn.
Hence
(2.7)ϕ(x)=f(x)-l(x)=12xT(A-Q)x+(a-β)Tx≥f(x-)-l(x-),∀x∈Rn.
Thus, x- is a global minimizer of ϕ(x). So, ∇ϕ(x-)=0 and ∇2ϕ(x-)≽0, that is,
(2.8)A-Q≽0,(A-Q)x-+(a-β)=0,
hence β=(A-Q)x-+a.Forx-=(x-1,…,x-n)T∈D, define
(2.9)x~i={-1ifx-i=ui,1ifx-i=vi,(Ax-)i+aiifx-i∈(ui,vi).X~=diag(x~1,…,x~n).
For Q=diag(α1,…,αn),αi∈R,i=1,…,n, define
(2.10)α^i=min{0,αi},Q^=diag(α^1,…,α^n).By Proposition2.2, we obtain the following sufficient global optimality condition for (CP1).Theorem 2.3.
For(CP1), let x-=(x-1,…,x-n)T∈D and u=(u1,…,un)T,v=(v1,…,vn)T. Suppose that there exists a diagonal matrix Q=diag(α1,…,αn),αi∈R,i=1,…,n, such that A-Q≽0, and for all x∈D, bi(xi-x-i)≥0,(i=1,…,n). If
(2.11)X~(Ax-+a)-12Q^(v-u)≤0,
then x- is a global minimizer of problem (CP1).Proof.
Suppose that condition (2.11) holds. Let
(2.12)l(x)=bTx3+12xTQx+βTx,β=(A-Q)x-+a.
Then, by Proposition 2.2, l(x)∈∂Lf(x-), that is,
(2.13)f(x)-f(x-)≥l(x)-l(x-),∀x∈Rn.
Obviously if l(x)-l(x-)≥0 for each x∈D, then x- is a global minimizer of (CP1).
Note that(2.14)l(x)-l(x-)=∑i=1n‍αi2(xi-x-i)2+(Ax-+a)T(x-x-)+bT(x3-x-3).
If each term in the right side of the above equation satisfies
(2.15)αi2(xi-x-i)2+(Ax-+a)i(xi-x-i)+bi(xi3-x-i3)≥0,i=1,…,n,xi∈[ui,vi],
then, from (2.14), it holds that l(x)-l(x-)≥0. So x- is a global minimizer of l(x) over box constraints.
On the other hand, suppose thatx- is a global minimizer of l(x),x∈D. Then it holds that
(2.16)l(x)-l(x-)=∑i=1n‍αi2(xi-x-i)2+(Ax-+a)T(x-x-)+bT(x3-x-3)≥0,∀x∈D.
When x is chosen as a special point x~∈D as follows:
(2.17)x~=(x-1,x-2,…,x-i-1,xi,x-i+1,…,x-n),xi∈[ui,vi],xi≠x-i,i=1,…,n,
we still have
(2.18)l(x~)-l(x-)=αi2(xi-x-i)2+(Ax-+a)T(x-x-)+bT(x3-x-3)≥0,i=1,…,n.
This means that if x- is a global minimizer of l(x) over box constraints. Then (2.15) holds.
Combining the above discussion, we can conclude thatx- is a global minimizer of l(x) over box constraints if and only if (2.15) holds. So next, we just need to prove (2.15) in order to show that x- is a global minimizer of l(x).
We first see from (2.11), for each i=1,…,n, that
(2.19)-α^i2(vi-ui)+x~i(Ax-+a)i≤0.
Sinceα^i≤0, then for each xi∈[ui,vi],i=1,…,n,
(2.20)-α^i2(xi-ui)+x~i(Ax-+a)i≤0,
and
(2.21)α^i2(xi-vi)+x~i(Ax-+a)i≤0.
For eachi=1,…,n, we consider the following three cases.
Case1. (If x-i∈(ui,vi), then x~i=(Ax-+a)i). By (2.20),
(2.22)-α^i2(xi-ui)+(Ax-+a)i2≤0.
So,α^i=0 and (Ax-+a)i=0, and then
(2.23)αi2(xi-x-i)2+(Ax-+a)i(xi-x-i)+bi(xi3-x-i3)≥α^i2(xi-x-i)2+bi(xi3-x-i3)=bi(xi-x-i)(xi2+xix-i+x-i2)≥0.
Case2. (If x-i=ui, then x~i=-1). By (2.20),
(2.24)α^i2(xi-ui)+(Ax-+a)i≥0.
So we have(2.25)αi2(xi-x-i)2+(Ax-+a)i(xi-x-i)+bi(xi3-x-i3)≥α^i2(xi-ui)2+(Ax-+a)i(xi-ui)+bi(xi3-ui3)={α^i2(xi-ui)+(Ax-+a)i}(xi-ui)+bi(xi3-ui3)≥0.
Case3. (If x-i=vi, then x~i=1). By (2.21),
(2.26)α^i2(xi-vi)+(Ax-+a)i≤0.
Then
(2.27)αi2(xi-x-i)2+(Ax-+a)i(xi-x-i)+bi(xi3-x-i3)≥α^i2(xi-vi)2+(Ax-+a)i(xi-vi)+bi(xi3-vi3)≥0.
So, if condition (2.11) holds, then (2.15) holds. And, from (2.14), we can conclude that x- is a global minimizer of (CP1).Theorem2.3 shows that the existence of diagonal matrix Q plays a crucial role because if this diagonal matrix Q does not exist, then we have no way to use this theorem. If the diagonal matrix Q exists, then the key problem is how to find it. These questions also exist in [8, 12].The following corollary will answer the questions above.Corollary 2.4.
For(CP1), let x-∈D. Assume that, for all x∈D, it holds that bi(xi-x-i)≥0(i=1,…,n). Then one has the following conclusion.(1)
WhenA is a positive semidefinite matrix, if
(2.28)X~(Ax-+a)≤0,then x- is a global minimizer of (CP1).(2)
WhenA is not a positive semidefinite matrix, if there exists an index i0,1≤i0≤n, such that
(2.29)x~i0(Ax-+a)i0>0,then there is no such diagonal matrix Q that meets the requirements of the Theorem 2.3.(3)
Let(2.30)αi=2x~i(Ax-+a)ivi-ui,i=1,…,n,Q=diag(α1,…,αn).
WhenA is not a positive semidefinite matrix and the condition X~(Ax-+a)≤0 holds, if A-Q≽0 holds, then x- is a global minimizer of (CP1). Otherwise, one can conclude that there is no such diagonal matrix Q that meets the requirements of the Theorem 2.3.Proof.
(1) Suppose thatA≽0 and the condition X~(Ax-+a)≤0 holds. Choosing Q=Q^=0, by Theorem 2.3, we can conclude that x- is a global minimizer of (CP1).
(2) WhenA is not a positive semidefinite matrix, if there exists an index i0,1≤i0≤n, such that
(2.31)x~i0(Ax-+a)i0>0,
then
(2.32)2x~i0(Ax-+a)i0vi0-ui0>0.
Suppose there exists a diagonal matrixQ that meets all conditions in Theorem 2.3. Condition (2.11) can be rewritten in the following form:
(2.33)x~i(Ax-+a)i-12α^i(vi-ui)≤0,i=1,…,n.
Then it follows that
(2.34)α^i≥2x~i(Ax-+a)ivi-ui,i=1,…,n.
For the indexi0, we still have the following inequality:
(2.35)α^i0≥2x~i0(Ax-+a)i0vi0-ui0>0.
This conflicts with the fact that α^i=min{0,αi}≤0,i=1,…,n.
(3) Next we will consider the case thatA is not a positive semidefinite matrix, and condition X~(Ax-+a)≤0 holds.
We construct a diagonal matrixQ=diag(α1,…,αn) where αi=2x~i(Ax-+a)i/(vi-ui),i=1,…,n, and A-Q≽0. Then it suffices to show that condition (2.11) in Theorem 2.3 hold.
Note thatx~i(Ax-+a)i≤0,i=1,…,n, and then
(2.36)αi=2x~i(Ax-+a)ivi-ui≤0,i=1,…,n.
Since αi≤0, we have α^i=αi. So
(2.37)α^i=2x~i(Ax-+a)ivi-ui≤0,i=1,…,n.
Rewriting the above inequality, we have
(2.38)x~i(Ax-+a)i-12α^i(vi-ui)=0,i=1,…,n.
Apparently this means that the constructed diagonal matrix Q also satisfies condition (2.11). According to Theorem 2.3, we can conclude that x- is a global minimizer of (CP1).
If the constructed diagonal matrixQ does not meet the condition A-Q≽0, then we can conclude that there is no such diagonal matrix Q that can meet the requirements of Theorem 2.3.
To show this, suppose that there exists a diagonal matrixQ*=diag(α1*,…,αn*), which satisfies A-Q*≽0 and (2.11).
From (2.11), we have
(2.39)0≥αi*≥2x~i(Ax-+a)ivi-ui=αi,i=1,…,n.
Obviously if A-Q*≽0, then there must exist a diagonal matrix Q=diag(α1,…,αn) such that A-Q≽0. This conflicts the assumption.We now consider a special case of(CP1):
(CP2)minf(x)=∑i=1nbixi3+∑i=1nri2xi2+∑i=1naixis.t.x∈D=∏i=1n[ui,vi],
where ui,vi,ai,bi,ri∈R and ui≤vi,i=1,2,…,n.Corollary 2.5.
For(CP2), let x-∈D. If, for each i=1,…,n,
(2.40)x~i(rix-i+ai)-12r^i(vi-ui)≤0,bi(xi-x-i)≥0,
then x- is a global minimizer of (CP2), where r^i=min{0,ri}.Proof.
For(CP2), choose Q=A=diag(r1,…,rn). If (2.40) holds, then, by Theorem 2.3, x- is a global minimizer of (CP2).


## 3. Sufficient Conditions of Bivalent Programming

In this section, we will consider the following bivalent programming:(CP3)minf(x)=bTx3+12xTAx+aTxs.t.x∈DB=∏i=1n{ui,vi},
where A,a,b, and ui, vi, i=1,…,n are the same as in (CP1).Similar to Theorem2.3, we will obtain the global sufficient optimality conditions for (CP3).Theorem 3.1.
For(CP3), let x-=(x-1,…,x-n)T∈DB. Suppose that there exists a diagonal matrix Q=diag(α1,…,αn),αi∈R,i=1,…,n such that A-Q≽0, and for all x∈DB, bi(xi-x-i)≥0(i=1,…,n). If
(3.1)X~(Ax-+a)-12Q(v-u)≤0,
then x- is a global minimizer of problem (CP3).Proof.
Suppose that condition (3.1) holds. Let
(3.2)l(x)=bTx3+12xTQx+βTx,β=(A-Q)x-+a.
Then
(3.3)f(x)-f(x-)≥l(x)-l(x-),∀x∈Rn.
Obviously if l(x)-l(x-)≥0 for each x∈DB, then x- is a global minimizer of (CP3).
Note that(3.4)l(x)-l(x-)=∑i=1n‍αi2(xi-x-i)2+(Ax-+a)T(x-x-)+bT(x3-x-3).
Thus,x- is a global minimizer of l(x) with binary constraints if and only if, for each i=1,…,n,xi∈{ui,vi},
(3.5)αi2(xi-x-i)2+(Ax-+a)i(xi-x-i)+bi(xi3-x-i3)≥0.
Firstly, we note from (3.1), for each  i=1,…,n, that
(3.6)-αi2(vi-ui)+x~i(Ax-+a)i≤0.
Next we only show it from the following two cases.
Case1. (If x-i=ui), then (3.6) is equivalent to
(3.7)αi2(vi-ui)+(Ax-+a)i≥0.
It is obvious that, for each xi∈{ui,vi},
(3.8)αi2(xi-ui)2+bi(xi3-ui3)+(Ax-+a)i(xi-ui)≥0.
So (3.5) holds.
Case2. (If x-i=vi), then (3.6) is equivalent to
(3.9)-αi2(vi-ui)+(Ax-+a)i≤0.
It is obvious that, for each xi∈{ui,vi},
(3.10)αi2(vi-xi)2-bi(vi3-xi3)-(Ax-+a)i(vi-xi)≥0.
So (3.5) holds.
From (3.5), we can conclude that x- is a global minimizer of problem (CP3)Similar to Corollary2.4, we have the following corollary.Corollary 3.2.
For(CP3), let x-∈DB. Suppose that, for all x∈DB, bi(xi-x-i)≥0(i=1,…,n).
(1) WhenA is a positive semidefinite matrix, if
(3.11)X~(Ax-+a)≤0,
then x- is a global minimizer of (CP3).
(2) Let(3.12)αi=2x~i(Ax-+a)ivi-ui,i=1,…,n,Q=diag(α1,…,αn).
When A is not a positive semidefinite matrix, if A-Q≽0 holds, then x- is a global minimizer of (CP3). Otherwise, one can conclude that there is no such diagonal matrix Q that meets the requirements of Theorem 3.1.We just show the proof of (2).Proof.
We construct the diagonal matrixQ=diag(α1,…,αn), where αi=2x~i(Ax-+a)i/(vi-ui), i=1,…,n. If A-Q≽0, we just need to test condition (3.1).
Because(3.13)αi=2x~i(Ax-+a)ivi-ui,i=1,…,n,
then rewriting the above equations, we have
(3.14)x~i(Ax-+a)i-12αi(vi-ui)=0,i=1,…,n.
It obviously means that the diagonal matrix Q also satisfies condition (3.1). According to Theorem 3.1, x- is a global minimizer of (CP3).Note that there is difference between formula (3.1) and formula (2.11). In formula (3.1), the diagonal elements αi of a diagonal matrix Q are allowed to be positive or nonpositive. But in formula (2.11), the diagonal elements α^i of a diagonal matrix Q^ must meet the conditions α^i≤0. So we have to discuss the sign of the terms x~i(Ax-+a)i(i=1,…,n) in Corollary 3.2.We now consider a special case of(CP3):
(CP4)minf(x)=∑i=1nbixi3+∑i=1nri2xi2+∑i=1naixis.t.x∈DB=∏i=1n{ui,vi},
where bi,ri,ai,ui,vi∈R and ui≤vi,i=1,…,n.Corollary 3.3.
For(CP4), let x-∈DB. If, for each i=1,…,n,
(3.15)x~i(rix-i+ai)-ri2(vi-ui)≤0,bi(xi-x-i)≥0,
then x- is a global minimizer of (CP4).Proof.
For(CP4), choose Q=A=diag(r1,…,rn). If conditions (3.15) hold, then, by Theorem 3.1, x- is a global minimizer of (CP4).


## 4. Numerical Examples

In this section, six examples are given to test the proposed global sufficient optimality condition.Example 4.1.
Consider the following problem:(4.1)min73x13+5x23+2x33+32x12+x22+12x32+2x1x2+x1x3+x2x3+32x1+5x2+3x3s.t.x∈D=∏i=13[1,2].
Let(4.2)A=[321221111]
and a=(3/2,5,3)T,b=(7/3,5,2)T. Obviously A is a positive semidefinite matrix.
Consideringx-=(1,1,1)T, obviously we have, for each xi∈[1,2],  bi(xi-x-i)≥0(i=1,2,3). Note that Ax-+a=(15/2,10,6)T and X~=diag(-1,-1,-1), and so
(4.3)X~(Ax-+a)=[-152-10-6]<0.
According to Corollary 2.4(1), x-=(1,1,1) is a global minimizer.Example 4.2.
Consider the following problem:(4.4)min-x13-3x23+12x43-x12-x22+32x32-12x42-2x1x2+x1x4+2x2x4-x1-4x2+5x4s.t.x∈D=∏i=14[-1,1].
Let(4.5)A=[-2-201-2-2020030120-1]
and a=(-1,-4,0,5)T,b=(-1,-3,0,1/2)T. Obviously A not is a positive semidefinite matrix.
Consideringx-=(1,1,0,-1)T, obviously we have, for each xi∈[-1,1], bi(xi-x-i)≥0(i=1,2,3,4).
Note thatAx-+a=(-6,-10,0,9)T. Then letting X~=diag(1,1,0,-1), we have X~(Ax-+a)=(-6,-10,0,-9)T≤0. Let α1=2x~1(Ax-+a)1/(v1-u1)=-6, α2=-10,α3=0 and α4=-9. Then Q=diag(-6,-10,0,-9), which satisfies A-Q≻0. According to Corollary 2.4(3), x-=(1,1,0,-1) is a global minimizer.Example 4.3.
Consider the following problem:(4.6)min-x13+23x23-3x33-2x12-35x22-4x32+12x42-2x1+5x2-3x3s.t.x∈D=∏i=14[-1,1].
LetA=diag(-4,-6/5,-8,1) and a=(-2,5,-3,0)T,b=(-1,2/3,-3,0)T,r=(-4,-6/5,-8,1)T.
Considerx-=(1,-1,1,0)T.
LetX~=diag(1,-1,1,0),r^=(-4,-6/5,-8,0)T. Then
(4.7)x~1(r1x-1+a1)-12r^1(v1-u1)=-2<0,x~2(r2x-2+a2)-12r^2(v2-u2)=-5<0,x~3(r3x-3+a3)-12r^3(v3-u3)=-3<0,x~4(r4x-4+a4)-12r^4(v4-u4)=0,xi∈[-1,1],bi(xi-x-i)≥0,(i=1,2,3,4).
According to Corollary 2.5, x-=(1,-1,1,0) is a global minimizer.Example 4.4.
Consider the following problem:(4.8)min4x13+52x23-3x33-83x43-32x12-32x22+3x32-x42+2x1x2+x1x4+x2x3-x3x4+5x1+92x2-2x3-2x4s.t.x∈DB=∏i=14{-1,1}.
Let(4.9)A=[-32012-310016-110-1-2]
and a=(5,9/2,-2,-2)T,b=(4,5/2,-3,-8/3)T. Obviously A not is a positive semidefinite matrix.
Consideringx-=(-1,-1,1,1)T, it follows that, for each x∈DB, bi(xi-x-i)≥0(i=1,2,3,4). Note that Ax-+a=(7,13/2,2,-6)T and X~=diag(-1,-1,1,1). Let α1=(2x~1(Ax-+a)1)/(v1-u1)=-7. Similarly we have, α2=-13/2,α3=2 and α4=-6. Then Q=diag(-7,-13/2,2,-6), which satisfies A-Q≻0. According to Theorem 3.1(2), x-=(-1,-1,1,1) is a global minimizer.Example 4.5.
Consider the following problem:(4.10)min3x13-8x23+5x33+12x43-x12+4x22-53x32-3x42+x1-2x2+3x3+4x4s.t.x∈DB=∏i=14{-1,0}.
Leta=(1,-2,3,4)T,b=(3,-8,5,1/2)T, and r=(-2,8,-10/3,-6)T.
Considerx-=(-1,0,-1,-1)T.
LetX~=diag(-1,1,-1,-1). Then
(4.11)x~1(r1x-1+a1)-12r1(v1-u1)=-2<0,x~2(r2x-2+a2)-12r2(v2-u2)=-6<0,x~3(r3x-3+a3)-12r3(v3-u3)=-143<0,x~4(r4x-4+a4)-12r4(v4-u4)=-7<0,x∈DB,bi(xi-x-i)≥0,(i=1,2,3,4).
According to Corollary 3.3, x-=(-1,0,-1,-1) is a global minimizer.Example 4.6.
Consider the following problem:(4.12)min3x13-8x23+5x33+12x43-x12-4x22+53x32-3x42-x1+2x2+3x3+4x4s.t.x∈DB=∏i=14{-1,0}.
Let a=(-1,2,3,4)T,b=(3,-8,5,1/2)T and r=(-2,-8,10/3,-6)T.
Considerx-=(-1,0,-1,-1)T.
LetX~=diag(-1,1,-1,-1). Then
(4.13)x~1(r1x-1+a1)-12r1(v1-u1)=0,x~2(r2x-2+a2)-12r2(v2-u2)=6>0,x~3(r3x-3+a3)-12r3(v3-u3)=-43<0,x~4(r4x-4+a4)-12r4(v4-u4)=-7<0.
We can see that the conditions are not true inx-=(-1,0,-1,-1)T in Corollary 3.3. But x-=(-1,0,-1,-1) is a global minimizer. This fact exactly shows that the conditions are just sufficient.



---

*Source: 871741-2012-09-06.xml*