Lower-Order Penalty Approach for Second-Order Cone Nonlinear Complementarity Problems

HAO Zijun(郝自军),ZHANG Yudong(张玉栋),YU Guolin(余国林)

( 1.School of Mathematics and Information Science,North Minzu University,Yinchuan 750021,China; 2.Zaozhuang Vocational College of Science and Technology,Tengzhou 277500,China)

Abstract: Lower-order penalty approach,which is the extension of the power penalty approach,is proposed for solving second-order cone nonlinear complementarity problems(SOC-NCPs).And the SOC-NCP is converted to asymptotic nonlinear equations.The merit of this approach shows that the solution sequence of the asymptotic nonlinear equations converges to the solution of the SOC-NCP at an exponential rate when the penalty parameter tends to positive infinity under mild assumptions.Numerical results are reported to examine the efficiency of the proposed approach.

Key words: Second-order cone; Nonlinear complementarity problem; Lower-order penalty algorithm; Exponential convergence rate

1.Introduction

In this paper,we consider the second-order cone nonlinear complementarity problem(SOC-NCP)[1–4],which is to find vectorx ∈Rn,such that

whereF:Rn→Rnis continuously differentiable vector-valued function,denotes the Euclidean inner product,andK ⊂Rnis a Cartesian product of second-order cones (SOCs),also called Lorentz cones.In other words,

withl,n1,··· ,nl ≥1,n1+···+nl=n,andKni ⊂Rni(i=1,··· ,l)being theni-dimensional SOC,i.e.,

where||·||denotes the Euclidean norm.If someni=1,K1denotes the set of nonnegative set of real numbers R+.It is obvious thatKis a closed,convex and self-dual cone in Rn.In this paper,if there is no ambiguity,for convenience,we use semicolon to denote the concatenation of two column vectors.Therefore,(x1;x2):=(x1,xT2)Tin (1.3)and we notex=(x1;···;xl)withxi ∈Rni(i=1,··· ,l)corresponding to the structure ofK.In particular,when the mappingFis only considered as an affine function,the SOC-NCP(1.1)reduces to the secondorder cone linear complementarity problem (SOC-LCP).More over,whenn1=···=nl=1,SOC-NCP and SOC-LCP reduce to the nonlinear complementarity problem(NCP)and linear complementarity problem (LCP)in ordinary nonnegative quadrant respectively.

For the generalized second-order cone complementarity problem (SOCCP)[1–4],which is to find vectorsu,v ∈Rnandζ ∈Rm,such that

whereE:R2n+m→Rn+mis a continuously differentiable mapping,denotes the Euclidean inner product,andKis given by (1.2).IfE(u,v,ζ)in (1.4)does not involve the variableζand has a special formE(u,v,ζ)=v−F(u),then SOCCP (1.4)reduces to SOC-NCP (1.1).Therefore,the SOC-NCP (1.1)is a special case of the SOCCP (1.4),and it seems rather restrictive.However,for the following second-order cone programming (SOCP):

wheref:Rs→R andg:Rs→Rt(including nonlinear functions)are continuously differentiable functions,andKis some Cartesian product of SOCs.It is worth noting that the Karush-Kuhn-Tucker (KKT)conditions of (1.5)can be written in the form of the SOC-NCP(1.1)(see the concluding remarks in [4]).Particularly,if the SOCP (1.5)is convex problem,then a pointz∗is one solution of (1.5)whenever the point satisfies the KKT conditions of the SOCP under appropriate constraint qualification (CQ)[5].Therefore,SOC-NCP (1.1)is closely related to the SOCP.

The SOCP and SOCCP have broad range of applications in engineering design,control,finance,management science,mechanics and economics etc.[6−7]During the last two decades,extensive researches have been done for them and various numerical approaches for solving them have been proposed,such as the interior-point approach[6],the smoothing Newton approach and the smoothing-regularization approach[1,4,8],the semismooth Newton approach[9],the merit function approach[10]and other approaches.[11−12]Some approaches are required for solving an associated Newton equations in whichO(n3)flops are involved,which might be inefficient when the dimension of the problem gets large[11].

It is well-known that the penalty function approach occupies an important place in solving constrained optimization problem.Thel1penalty function and lower-order penalty functions possess many nice properties and attract much attention[13].In [14],WANG and YANG proposed a power penalty approach for solving the LCPs.By this approach,LCP can be converted to asymptotic nonlinear equations.The merit of this approach shows that the solution sequence of the asymptotic nonlinear equations converge to the solution of the LCP at an exponential rate when the penalty parameter tends to positive infinity under some mild assumptions.In [15–17],the power penalty approach has been extended to solve the NCPs,SOC-LCPs and SOC-NCPs respectively,and the solution sequence of the asymptotic nonlinear equations inherit the exponential convergence rate under some assumptions.Actually,the power penalty approach is only a kind of the lower-order penalty approach.The power in the former is only the kind of 1/k(k ∈Z+),which doesn’t represent all real numbers in (0,1]corresponding to general lower-order penalty approach.Therefore,it is very necessary to extend the power like 1/k(k ∈Z+)to any real number in (0,1].The extension was already considered for the SOC-LCPs[18].In this paper,we will consider the extension for more general SOC-NCPs (1.1).

Under the assumption thatF(x)isξ-monotone,the unique solvability of SOC-NCP and asymptotic nonlinear equations are obtained,where the equivalence of the complementarity problem and some variational inequality play an important role.We prove that the solutions of asymptotic nonlinear equations converges to the solution of the SOC-NCP at an exponential rateO(σ−1/rξ)when the penalty parameterσ→+∞.If theξ-monotone ofF(x)is not satisfied,we still show that any limit point of solution sequence,if exist,solves the SOC-NCP(1.1)provided thatF(x)is continuous,but the convergence rate is unknown in this situation.The corresponding algorithm is constructed,and numerical examples indicate the feasibility of our approach.

The rest of this paper is organized as follows.Some preliminary results for SOC are presented in Section 2.In Section 3,the lower-order penalty approach is proposed for solving the SOC-NCP(1.1).An algorithm based on this approach is constructed and the convergence analysis is proved.In Section 4,some numerical implementation demonstrate our theoretical findings.Finally,we give the conclusions.Throughout this paper,we use intKand bdKto denote the interior and the boundary ofKrespectively.For anyx,yin Rn,we write(or)ifx−y ∈K,and write(or)ifx−y ∈intK.Thus,0 iffx ∈K,and0 iffx ∈intK.The notation||·||pdenotes the usuallp-norm on Rnfor anyp ≥1.In particular,it is Euclidean norm||·||whenp=2.

2.Preliminary Results

We give some preliminary results for a single block SOC in this section,i.e.,K=Kn,since our analysis can be easily extended to the general case(1.2).For anyx=(x1;x2)∈R×Rn−1andy=(y1;y2)∈R×Rn−1,their Jordan product[6,19]is defined as

We usex2to meanx◦xand usex+yto denote the usual componentwise addition of vectors.It is easy to see that the Jordan product is commutative ande=(1,0,··· ,0)T∈Rnis the identity element.The Jordan product is not associative forn >2 in general.However,we havex ◦(x ◦x)=(x ◦x)◦xfor anyx ∈Rn.Thus,for any positive integerk,the formxkis definite.We definex0=eifx0 and recursively define the powers of element asxk=x ◦xk−1for any integerk ≥1.Therefore,the equalityxm+n=xm ◦xnholds for any positive integermandn.The inverse ofxis denoted byx−1,satisfyingx ◦x−1=e.For any positive integerk,we definex−k=(xk)−1ifx ∈intKn.Note thatKnis not closed under the Jordan product forn>2 in general.The Jordan product (2.1)is associated withKnvia some useful facts,such as the trace and the determinant ofx ∈Rnas well as square root,absolute value vector.For more details of these concepts,we can refer to [1,3,6,19].By the properties of SOC,=0 if and only ifx ◦y=0 for anyx,y ∈Kn.[1,6]Thus,the complementarity conditions can be stated by the Jordan product equivalently.

Next,we introduce the spectral factorization of vectors in Rnassociated withKn.[1,3]

For any vectorx=(x1;x2)∈R×Rn−1,the vector can be decomposed as

whereλ1,λ2are the spectral values andu(1),u(2)are the associated spectral vectors.They are respectively given by

withwbeing any unit vector in Rn−1.The decomposition (2.2)-(2.3)is unique ifx2≠0.It is obvious thate=u(1)+u(2)andλ1≤λ2.Now we give some basic properties of spectral factorization.

Property 2.1[1]For anyx=(x1;x2)∈R×Rn−1,suppose that the spectral factorization ofxis given by (2.2)-(2.3).Then the following results hold.

1)u(1)andu(2)are orthogonal under the Jordan product and have lengthi.e.,

2)u(1)andu(2)are idempotent under the Jordan product,i.e.,u(i)◦u(i)=u(i),i=1,2;

3)λ1is nonnegative (positive)if and only ifx ∈Kn(x ∈intKn).

The spectral factorization (2.2)-(2.3)and Property 2.1 provide a very useful tool for evaluating the functions defined by the powers of Jordan product.For example,we havex2=(λ1u(1)+λ2u(2))◦(λ1u(1)+λ2u(2))=λ21u(1)+λ22u(2)for anyx ∈Rn.Therefore,the spectral values ofx2are nonnegative andx2∈Kn.On the contrary,for anyx ∈Knwith spectral factorization (2.2)-(2.3),we havethenw2=x.By the uniqueness of the square root,we haveThese show that squaring or taking square-root on a vector is the same as squaring or taking square-root on the spectral values,and the associated spectral vectors remain invariant.

By using the spectral factorization (2.2)-(2.3),a scalar function:R→R can be extended to an SOC vector-valued function associated withKn(n ≥1)[1−2],which is given by

whereλ1,λ2are the spectral values andu(1),u(2)are the associated spectral vectors(see(2.3)).

For anyx ∈Rn,the nearest-point (in the Euclidean norm)ofxontoKn,denoted byPKn(x),is called the projection ofx,i.e.,PKn(x)∈Knand satisfying

Clearly,the projection (2.5)reduces to [t]+=max {0,t} fort ∈R whenn=1.The following lemma shows that|x|andPKn(x)have the form (2.4)(see [1,Proposition 3.3]).

Lemma 2.1For anyx=(x1;x2)∈R×Rn−1with spectral factorization (2.2)-(2.3),then

1)|x|=(x2)1/2=|λ1|u(1)+|λ2|u(2);

2)The projection ofxonKncan be written asPKn(x)=(x+|x|)/2=[λ1]+u(1)+[λ2]+u(2),where for any scalarα ∈R,[α]+=max {0,α}.

Similar to the concept of projection onKn,define[8]

for any vectorxwith spectral factorization(2.2)-(2.3),where[λi]−=max {0,−λi}fori=1,2.It is obvious that(x)means the projection point of−xontoKn,and it can be seen that

3.Lower-order Penalty Algorithm and Convergence Analysis

In this section,we propose the lower-order penalty algorithm for solving SOC-NCP(1.1),and the corresponding convergence analysis is also given.In the rest of this paper,unless otherwise specified,Kdenotes the Cartesian product of SOCs (1.2).

Now we consider the lower-order penalty equations (LPEs):For any power parameterr ∈(0,1],findx ∈Rn,such that

whereσ ≥1 is the penalty parameter,and (PK(z))rfor allz=(z1;···;zl)is defined as

provided that the spectral factorization forzi ∈Rnibeingzi=µ1v(1)+µ2v(2).

The penalty termσ(PK(−x))rin LPEs(3.1)penalizes the negative part ofxwhenx ∈Kis violated.It’s easy to see thatF(x)∈Kis always satisfied due toσ(PK(−x))r ∈K.Supposexσbeing the solution of LPEs(3.1)aboutσ.We expect the solution sequence {xσ}converges to the solution of SOC-NCP (1.1)whenσ→+∞,and the convergence rate clearly depends on the power parameterr.Thus,we convert SOC-NCP (1.1)into asymptotic LPEs.Based on this idea,an algorithm for solving SOC-NCP (1.1)is suggested as following:

Algorithm 3.1

Step 0 Given a continuous functionF=(F1;···;Fl)and variablex=(x1;···;xl)withFi:Rn→Rni,xi ∈Rni,i=1,··· ,lfor SOC-NCP (1.1).Set ˜x=0 in Rn;

Step 1 IfF(0)∈K,stop,and go to Step 5; else,go to Step 2;

Step 2 Given a power parameter 01,select an initial pointwithand takewhenfor convenience.

Step 3 For penalty parameterσand initial iteration pointx(0),solve LPEs (3.1).Suppose thatxσis the solution of this equations.Let Tol=|xTσF(xσ)|.

Step 4 If Tol≤eps,set=xσ,stop,and go to Step 5; else,letx(0)=xσ,σ=cσ,and go to Step 3.

Next,we discuss the theoretical properties and convergence analysis of Algorithm 3.1.We consider it in two cases,one is under monotonic assumption,and the other without monotonic assumption.Some numerical implementation of Algorithm 3.1 will be presented in next section.

ⅠConvergence analysis under monotonic assumption

An assumption is given first,then on the basis of this assumption,the unique solvability of the SOC-NCP (1.1)and the LPEs (3.1)are shown.Finally,the upper bound for the distance between the solution of LPEs (3.1)and that of SOC-NCP (1.1)is established.

Assumption 3.1Fisξ-monotone on Rn,i.e.,there exist constantsα >0 andξ >1,such that

It is obvious that strongly monotonic function must beξ-monotone function,but the inverse is not true.It is well-known that the SOC-NCP (1.1)is equivalent to the following variational inequality (VI(K,F))[7]:Findx∗∈K,such that

By Theorem 2.3.3 in [7],the VI(K,F)admits a unique solution whileF(x)is continuous andξ-monotone.Therefore,the SOC-NCP (1.1)is unique solvable under Assumption 3.1.Note that nonlinear equations being special case of variational inequality,thus,the unique solvability of LPEs (3.1)can be considered by variational inequality.By Proposition 4.1 in[17],the function (PK(z))1/kis monotone on Rnfork ≥1.Similarly,by replacing 1/kwithrin the proof,we can get (PK(z))ris also monotone on Rnfor any parameterr ∈(0,1].

Proposition 3.1Suppose that Assumption 3.1 holds.Then,for any parametersσ ≥1 andr ∈(0,1],the LPEs (3.1)admit a unique solution.

ProofDue to theξ-monotone ofF,there exist constantsα >0 andξ >1,such that(3.3)holds for anyx,y ∈Rn.For any parametersσ ≥1 andr ∈(0,1],by the monotonicity of (PK(·))r,we have

This formula indicates that the functionF(x)−σ(PK(−x))risξ-monotone.Therefore,LPEs(3.1)admit a unique solution.

Under Assumption 3.1,SOC-NCP(1.1)and LPEs(3.1)all have a unique solution.Next,we establish some upper bound for the distance between the unique solution of SOC-NCP(1.1)and that of LPEs (3.1).For convenience,the block component form ofxσ,which is the unique solution of LPEs (3.1)for any parametersσ ≥1 andr ∈(0,1],is denoted by

Proposition 3.2For anyσ ≥1 andr ∈(0,1],the solution of LPEs (3.1)is bounded,i.e,there exists a positive constantM,independent ofxσ,σandr,such that||xσ||≤M.

The proof is similar to Proposition 4.3 in [17]by replacing 1/kwithr,and we omit the detail.By Proposition 3.2 and the continuity ofF(x),||F(xσ)||is also bounded for anyσ ≥1 andr ∈(0,1],i.e.,there exists a positive constantL,independent ofxσ,σandr,such that

Suppose that the vectorx∗is the exact solution of SOC-NCP (1.1).We expect thatxσ→x∗asσ→+∞.Notingx∗∈K,we expectPK(−xσ)→0,which plays an important role in the convergence analysis.The following proposition gives an upper bound of||PK(−xσ)||.The detailed proof,which we omit,is similar to Proposition 4.4 in [17]by replacing 1/kwithr.

Proposition 3.3For anyσ ≥1 andr ∈(0,1],there exists a positive constantC,independent ofxσandσ,such that

Based on Propositions 3.2 and 3.3,the following theorem gives the desired result.

Theorem 3.1For anyσ ≥1 andr ∈(0,1],there exists a positive constantC,independent ofxσandσ,such that

ProofFollowing from (3.5),x∗−xσcan be decomposed as

Now we consider the estimation of the||x∗−xσ||.Ifrσ=0,the inequality (3.8)is trivially satisfied due to (3.7)and (3.9).In the following,we only considerrσ≠0.Noting(−xσ)∈K,from (3.10),replacingxin VI(K,F)(3.4)by(−xσ)yields

By left-multiplying both sides of LPEs (3.1)byrσ,we have

Adding up (3.11)and (3.12),we get

From (3.10)and the definition of (PK(−xσ))rin (3.2),we have

Applying this inequality to (3.13)yieldsrTσ(F(xσ)−F(x∗))≥0,i.e.,rTσ(F(x∗)−F(xσ))≤0.Yetrσ=x∗−xσ−PK(−xσ)from (3.9),then

From the last inequality,Assumption 3.1,the Cauchy-Schwarz inequality,triangle inequality and (3.6),there exist constantsα>0 andξ >1,such that

By dividingαon both sides of (3.14),we get

Finally,by Proposition 3.3,||PK(−xσ)||≤C′/σ1/rfor some constantC′.SetC:=which is obvious independent ofxσandσ.Takingξ-root on both sides of (3.15)yields (3.8).This completes the proof.

From Theorem 3.1,we see that the solution sequence{xσ} of LPEs (3.1)converges to the solution of SOC-NCP (1.1)at an exponential rate whenσ→+∞provided thatFis continuous andξ-monotone.

ⅡConvergence analysis without monotonic assumption

We give the convergence analysis without monotonic Assumption 3.1 for the continuous functionF(x).For any penalty parameterσisatisfying limi→∞σi=+∞,suppose that the solution of LPEs (3.1)exists.We will show that any limit point of solution sequence solves SOC-NCP (1.1),which is given in the following theorem.

Theorem 3.2For any power parameter 0< r ≤1,let{σi} be a sequence of positive numbers satisfyingσi >1 for anyi=1,2,···andσi→∞asi→∞.For anyσi,suppose that the solution of LPEs (3.1)exists and is denoted byxσi.IfF(x)is continuous,then any limit point of{xσi} solves SOC-NCP (1.1).

ProofFor anyσi >1,sincexσiis the solution of LPEs (3.1)aboutσi,we have

From (3.16),we haveF(xσi)=σi(PK(−xσi))r ∈K.By takingi→∞in this formula,from the continuity ofF(x)and the closeness ofK,we have

Next,we prove

Suppose to the contrary that there exists at least an indexj ∈{1,··· ,l},such that/∈Knj.By settingε:=||(PKnj(−))r||,thenε >0.Therefore,from (3.18),wheniis sufficiently large,xσij ∈/KnjandAt the same time,from (3.16),we have

which contradicts (3.17).Thus (3.20)is true.

Now let us show that

By takingi→∞on both sides of (3.22)and denoting limi→∞(σi[−µ1(i)]r+)=c ≥0,we haveFj()=cv(1).Therefore,

Three cases from above,we get ()TFj()=0 for everyj=1,··· ,l.Thus,(3.21)holds.

Finally,it follows from (3.19),(3.20)and (3.21)thatsolves SOC-NCP (1.1).Since the limit pointis taken arbitrary,therefore,any limit point of{xσi} solves SOC-NCP (1.1).

4.Numerical Experiments

In this section,some numerical implementation for SOC-NCP(1.1)will be studied based on Algorithm 3.1.In the following tables of test results,IP(x0),Val,Iter and CPU(s)denote the initial points,the|xTσF(xσ)|,the iteration and the CPU time for solving problem respectively.The discrete Newton method is used to solve nonlinear equations for all examples,all the program codes are written in MATLAB and run in MATLAB7.8 environment,all numerical experiments are done at a PC with Inter(R)Core(TM)i5-2410M CPU of 2.3 GHz and RAM of 1 GB.

First,we consider Example 4.1[4,20]by fixing a power parameterr ∈(0,1](takingr=for example)and using different initial points.

Example 4.1Consider the SOC-NCP (1.1)onK3,the test functionF:R3→R3is given as

It can be seen thatFisξ-monotone but not strong monotone,sinceFcomprised of cubic and constant terms and it’s JacobianF′(x)=diag(0.21x21,0.12x22,0.09x23)is only positive semidefinite.This example has a unique solutionx∗=(5,3,4)T.[20]In numerical tests,we choose initialσ=1000,multiple parameterc=10 and employ|xTσF(xσ)| <1e-6 as the termination criterion.For different initial points,the test results are listed in Tab.4.1,which show that Algorithm 3.1 is insensitive for initial points.

Tab.4.1 Numerical results for Example 4.1(r=/3)

Tab.4.1 Numerical results for Example 4.1(r=/3)

IP(x0)Val Iter CPU(s)(1,1,1)1.4957e-7 3 1.4−(1,1,1)1.4433e-7 3 1.4(10,10,10)1.8747e-7 3 1.4−(10,10,10)2.8094e-7 3 1.5(103,103,103)6.1152e-8 3 1.8(106,106,106)1.9472e-7 3 2.2

Next,we consider Example 4.2[17]by fixing an initial point and using different power parametersr ∈(0,1].

Example 4.2Consider the following SOC-NCP (1.1)onK=K4×K4:

wherea=(10,5,−4,−8)T,c=(6,2,−3,−5)T,d=(6,3.5,−7.5,−3.5)T,b=(1,0,0,0)Tand the diagonal matrixA=diag(5/3,1,−4,2).

This example has one solutionx∗=(x∗1,x∗2)withx∗1=(3,−2,1,2)Tandx∗2=(3,1,2,−2)T.In numerical tests,we choose fixed initial point (10,··· ,10)T∈R8,initial penalty parameterσ=10,multiple parameterc=4,and employ|xTσ(F(xσ))| <1e-5 as the termination criterion.For different power parametersr ∈(0,1],the test results are listed in Tab.4.2.

Tab.4.2 Numerical results for Example 4.2

We see from Tab.4.2 that,with the decrease of parameterr,Algorithm 3.1 requires lesser iteration,which is coincide with the theoretical result.But meanwhile,Algorithm 3.1 requires more computing time.

Finally,we note that the numerical performance of the power penalty approach[16]is comparable with smoothing F-B merit method(SMFM)[1].The lower-order penalty approach is the extension of the power penalty approach,in which the range of power parameters is much broader.Therefore the numerical performance of the lower-order penalty approach is at least comparable with SMFM.

5.Conclusions

Based on the LPEs(3.1),we extend the power penalty approach to the general lower-order penalty approach for solving SOC-NCPs(1.1).Under the assumption thatF(x)is continuous andξ-monotone,the SOC-NCP (1.1)and the LPEs (3.1)are all uniquely solvable,and the solution sequence of LPEs converges to the solution of the SOC-NCP at an exponential rate.IfF(x)is only continuous,then any limit point of solution sequence to LPEs solves the SOCNCP,but the convergence rate is unknown in this situation.The numerical examples shows the feasibility of our approach,and the numerical performance of the lower-order penalty approach is at least comparable with SFBM used by Fukushima et al.[1]