Verifiable Outsourcing Of Particle Swarm Optimization In Cloud

In the age of cloud computing,computation outsourcing has become a prevalent and beneficial solution for resource-limited clients to perform expensive computations.Nonlinear programming(NLP)has been widely used in real life.However,there is no general effective algorithm to solve NLP problems,each method has its own practicable application scope and constraints condition.Particle swarm optimization(PSO)algorithm as a heuristic algorithm,is growingly being applied to solve real-parameter optimization problems,for its flexibility in dealing with NLP problems.When a client with limited resources has a complicated problem,e.g.an optimization problem,to compute,he can outsource the computation to the cloud which has the powerful computational resources.Actually,the client,at least partly,gets out of control over his data and computation in outsourced computing environments.Although computation outsourcing has various attractive benefits,it induces a serious problem: how can the client verify the result from the cloud?First,this dissertation introduces the background on nonlinear programming with PSO algorithm,KKT conditions,and approximate KKT conditions.Nevertheless,the extent of violation of KKT conditions at points close to the KKT point may not reduce smoothly,thus making the KKT conditions hard to directly evaluate the optimality of an optimization algorithm.The approximate KKT optimality conditions are defined to overcome the difficulty.This dissertation also analyses recent researches on verifiable computation.Verifiable computation is trying to verify the result of any computations using one general algorithm.The theoretical solutions based on heavy cryptographic operations make it hard in truly practical verifiable computing as they require extremely large quantity of storage and computing resources in implementations to verifiably execute even simple computations.Then,a verifiable PSO algorithm(VPSO)and its verification algorithm are proposed to solve the problem mentioned above.The computational efficiency of traditional PSO algorithm is almost inherited in the verifiable PSO algorithm,in which parameters that need to be transferred can also be verified.The client signs the input arguments,then verifiable PSO algorithm verifies whether the signature is valid,if not,stop running as soon as possible.After cloud completes computing and returns result,the client works the verification algorithm to disturb the received solution and check whether it is still optimal.If the verification fails,the client could consider the cloud may cheat in extremely high probability.Finally,this dissertation focus on the verifiable outsourcing of NLP problems being solved by PSO algorithm,i.e.making sure that the cloud executes PSO algorithm as requested and returns an acceptable solution.The client needs to reformulate the original problem by a penalty function so that it can be settled by PSO algorithm,then the cloud runs computation.The proposed framework removes the signature part in VPSO and verifies solutions by making use of approximate KKT conditions with the ?-KKT point.In addition,the extensive experiments on PSO benchmarks and NLP test problems with high successful verification ratios demonstrate that it is efficient and effective for our schemes to verify the honesty of the cloud.