Theorv And Algorithms For Non-convex Constrained Optimization Problems

Non-convex constrained optimization problems are important optimiza-tion problems,and many practical problems can be converted into them.Con-vex optimization problems have some good properties,for example,it can be solved in polynomial time in general.However,these good properties of con-vex optimization problems disappear for non-convex constrained optimization problems.Therefore,it is usually more complicated to solve non-convex con-strained optimization problems than convex ones.And it is difficult to design efficient algorithms for non-convex constrained optimization problems.In this dissertation,two kinds of important non-convex constrained opti-mization problems were studied:non-convex extended trust-region subprob-lems with two linear inequalities,and non-convex extended trust-region sub-problems with a general quadratic constraint(i.e.the generalized non-convex Celis-Dennis-Tapia,CDT problems).These problems are widely used.And it is necessary to solve these problems in each iteration of the trust-region method for solving some non-convex constrained optimization problems.These two kinds of problems may have positive dual gaps with their Lagrangian dual problems,and admit the same gap with their semi-definite programming(SDP)relaxation problems.As both types of problems contain ball constraints,they can be re-formulated with second-order cone(SOC).The contributions of this dissertation are mainly on narrowing or even eliminating the duality gaps of these problems by SOC reformulation techniques.A non-convex extended trust-region subproblem with two linear inequal-ities is minimizing a non-convex quadratic function subject to a ball constraint and two linear inequalities.A verified sufficient and necessary condition is pre-sented for its Semi-Definite Programming Relaxation with Second-Order-Cone Reformulation(SDPR-SOCR)to be a tight relaxation.That is,for non-convex extended trust-region subproblems with two linear inequalities which have pos-itive duality gaps,a sufficient and necessary condition is proposed under which the gaps are eliminated by the SOC reformulation technique.As an application of this condition,it is verified easily that the "nonintersecting" SDPR-SOCR is a tight relaxation indeed.Furthermore,as another application of the condition,it is proved that there exist at least three regions among the four regions in the trust-region ball divided by the two intersecting linear cuts,on which the SDPR-SOCR must be a tight relaxation.Meanwhile,the results of numerical exper-iments show that the SDPR-SOCR can work efficiently in decreasing or even eliminating the duality gap of the nonconvex extended trust-region subproblem with two intersecting linear inequalities indeed.It is necessary to emphasize that,even if a gap-existing SDPR-SOCR instance appears unfortunately,this gap is often highly less than the duality gap.Though the SDPR-SOCR can sometimes eliminate the duality gaps of non-convex extended trust-region subproblems with two intersecting linear inequal-ities,there still exist instances that their duality gaps do not vanish by the SDPR-SOCR and the left gaps are defined as SDPR-SOCR gaps.So an efficient al-gorithm is proposed to find their global solutions.By adding a new appropriate SOC constraint,the problem is divided into two separate subproblems and a sufficient and necessary condition is presented to characterize when the new SOC constraint is valid to narrow the SDPR-SOCR gap.By this condition,there exists a particular SOC constraint which minimizes the SDPR-SOCR gap and a bisection method is proposed to find this SOC constraint.However,the SDPR-SOCR gap cannot always be eliminated using this SOC constraint.So another algorithm called a multiple bisection method is established and a se-quence of second-order-cone programming problems are used to approximate the original problem.And the results of numerical experiments show that the multiple bisection method works efficiently in eliminating the SDPR-SOCR gaps indeed.A generalized CDT problem is minimizing a quadratic function subject to a ball constraint and a general quadratic constraint.A non-convex generalized CDT problem may admit a positive duality gap with its Lagrangian dual prob-lem,which causes challenges in solving its global solutions.In this dissertation,the generalized CDT problem is considered to have a positive duality gap.It is presented in theory that this positive duality gap can be narrowed by adding an appropriate SOC constraint,which may lead to dividing the problem into two separate subproblems.More concretely,for any generalized CDT problem with a positive duality gap,it is proved that one SOC constraint is valid to narrow the positive duality gap if and only if the corresponding hyperplane intersects the"open optimal line segment".In special,when the second constraint function consists of the product of two linear functions,it is proved that the positive du-ality gap can be eliminated thoroughly by solving two subproblems with SOC constraints.A classical CDT problem is minimizing a quadratic function subject to a ball constraint and an ellipsoidal constraint.For any classical CDT problem with a positive duality gap,a new model with two SOC constraints is proposed,and a sufficient condition is presented under which this positive duality gap can be eliminated thoroughly.In particular,based on the sufficient condition,it is proved that the positive duality gaps of any two-dimensional classical CDT problem and a class of three-dimensional classical CDT problems can be elim-inated thoroughly.Numerical results of some gap-existing examples coming from other papers show that their positive duality gaps are indeed eliminated by our SOC reformulation technique.