Primal-Dual Interior Point Methods In Mathematical Programming

In this paper, we consider the primal-dual interior point methods tosolve general non-convex nonlinear programming problems and the filledfunction method to solve the global optimization problems. For the non-linear programming problem we propose a primal-dual infeasible interiorpoint method and a primal-dual quasi-feasible interior point method. Forthe global optimization problem we propose a simple type filled function anda new class of functions. The general non-convex nonlinear programmingproblem is:where f:Rⁿ→R, c_j:Rⁿ→R,j=1,2,…, m_e, d_j:Rⁿ→R,j=1, 2,…,m_i,are continuously differentiable. Let X is the feasible region of (NP). Iⁱ(x)is the active index set of inequality constraints. The paper include mainlythree parts.一,In chapter 2, we make the following assumptions:(A1) f(x) is bounded from below, that is (?)(?),(?)x∈Rⁿ, f(x)≥(?).(A2) X is a nonempty set.(A3) (?)x∈(?),{â–½c_j(x):j∈I^e(x)} and {â–½d_j(x):j∈Iⁱ(x)} are linearindependent. (A4) (?)x∈Rⁿ, there exist constants 0 < C₁,C₂ <∞,(A5) The minima of problem (NP) satisfy the standard second order optimalityconditions.(A6) Hessianâ–½²f(x),â–½²c_i(x),i=1,2,…,m_e, andâ–½²d_j(x), j=1,2,…,m_isatisfy Lipschitz condition on Rⁿ.(A7) For anyμ> 0,the minima of problem (P_ρ,u satisfy standard secondorder optimality conditions.We combile ideas of Mayne, Polak [51] with Griva [39] and propose aprimal-dual infeasible algorithm (PDM algorithm 1). At first, we convertproblem (NP) to a sequence of inequality constrained optimization problemsof the type :whereρ> 0. (P_ρ) shows that large values ofρpenalize iterates satisfyingc_j(x) > 0, for any j, while feasibility for the modified problem ensures thatc_j{x)≥0. Thus, intuitively, for large values ofρ, iterates generated by afeasible-iterate algorithm will tend towards feasibility for the original problem(NP).Let c(x)=(c₁(x),c₂(x),…,c_me(x))', d(x)=(d₁(x),d₂(x),…,d_mi(x))',A(x) denote the Jacobian of c(x), B(x) denote the Jacobian of d(x). Letg(x) denote the Jacobian of f(x). C(x)=diag(c_j(x)), D(x)=diag(d_j(x)). The relation of problem (NP) and (P_ρ) is:Theorem 1 Letρ> 0 be given. If x is stationary point for (P_ρ) withmultiplier vectors y and z, and c(x)=0, then it is stationary point forproblem (NP) with multiplier vectors y-ρe₁ and z. Furthermore, if z≥0,x is a KKT point for (NP).Based on the infeasible algorithm in Chen and Goldfarb [19], let h(x)=(c_i(x),…, c_me(x), d₁(x),…, d_mi(x))^T. Let m = m_e+m_i. By adding slack variables,we can transfer problem (P_ρ) to problem:We take the slacks as a barrier term:where w = (w₁, w₂,…,w_m).μ> 0 is a barrier parameter.Let E(x) is the Jacobian of h(x). The solution of (P_ρ,u) satisfies thefollowing primal-dual system:where y = (y₁,…, y_m)' is a vector of the Lagrange multipliers or dual variablesfor problem (P_ρ,μ) (x,w are primal variables). Y = diag(y₁,…,y_m), W =diag(w₁,…, w_m), e₁= (1,1,…,1)∈R^m_e,e = (1,1,…, 1)∈R^m.We use Newton's method to solve (1), and make the Newton's directions(â–³x,â–³w,â–³y) by solving the following linear system: where H(x,y) is the Hessian of the Lagrange of problemFor simplying, we use the following notations :Because the core problem of the primal-dual interior point methods is: The solution that satisfies KKT condition can't sure sufficiently to convergenceto a local minimal point in any nonlinear programming problem besidesthe problem is convex. Otherwise problem can converge to saddle points orlocal maximal points. So we use the following merit functions whose actionis making iteration of the algorithm to a local minimal point:We proof lemmas and make the convergence theorem in section 3:Theorem 2: Under assumptions (A1)-(A7), PDM algorithm 1 generates aprimal-dual sequence {z^s = (x^s,w^s,y^s)} such that any limit point (?) of theprimal sequence {x^s} is a KKT point for the minimization of the l₂ norm ofthe vector w-h(x), i.e.Particularly, if S((?)) = 0, (?) is KKT point of problem (P_ρ).二,In chapter 3, we propose a primal-dual quasi-feasible method (PDMalgorithm 2) that is strictly feasible with respect to the inequality constraints. At each iterate we "approximately" solve the following type of an equalityconstrained barrier sub-problem for a fixed barrier parameterμ:In this chapter we make the following assumptions:(B1) F is nonempty.(B2) Functions f, d, c are real valued and twice continuously differentiableon F.(B3) The primal iterate sequence {x^k} lies in a bounded set.(B4) The modified Hessian sequence {H^k} is bounded.We use penalty barrier function as merit function, where penalty termis the norm of the equality constraints to the power a. We consider problem:where r is the penalty parameter, 0 j, the outer algorithm terminates finitelywith either an approximate KKT point of problem (NP) or an approximateFJ point of problem (NP) failing to satisfy the MFCQ. In the latter case or ifthe inner algorithm converges to such a point, this indicates that locally theremay be no feasible KKT points. Otherwise the inner algorithm converges toa FJ point of problem (FNP). This indicates that problem (NP) appears tobe locally infeasible. We make a convergence theorem:Theorem 3: Suppose assumptions (B1) and (B2) hold. (B3) holds with thesame bound for everyμ_j and (B4) holds for eachμ_j. Moreover, suppose theMFCQ holds on the feasible region and problem (NP) is not locally infeasibleon F; i.e., there are no FJ points of problem (FNP) on F that are infeasibleto (NP). Then ignoring the termination condition of PDM algorithm 2, thepenalty parameter is uniformly bounded and any limit point of the sequence{x^j,w^j,y^j} generated by PDM algorithm 2 satisfies the KKT conditions.Moreover we propose algorithm steps and numerical examples to thealgorithms in chapter 2 and chapter 3.三,In chapter 4 we consider the global optimization methods to solveunstrained problems. We discuss mainly filled functions method.We construct a simple type of filled function with a parameter:and proof it satisfy the filled function definition of Ge Renpu. Some numericalresults show the rationality of the filled function.In section 3, for any r > 0 , letFurthermore, we suppose the functions G_r(t) and F_r(t) satisfy the followingconditions:(1) G_r(t) and F_r(t) are continuously differentiable.(2)(?)t∈(-r,0), g'_r(t)>0, f'_r(t)>0. We suppose the function (?)(t) satisfies the following conditions:(1) (?)(t) is continuously differentiable.(2) (?)t∈[0,∞), (?)(t)>0.(3) (?)t∈[0,∞), (?)'(t)≤0 and (?)'(t) = 0 if and only if t=0.We construct a new class of filled functions:We proof this class of functions satisfying the definition of the filled functionsof Wu Zhiyou and give some special functions which have these properties.