A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones

In this paper, we introduce a one-parametric class of smoothing functions which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve linear programming over symmetric cones. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.     

A new class of complementarity functions for symmetric cone complementarity problems

A popular approach to solving the complementarity problem is to reformulate it as an equivalent equation system via a complementarity function. In this paper, we propose a new class of functions, which contains the penalized natural residual function and the penalized Fischer–Burmeister function for symmetric cone complementarity problems. We show that this class of functions is indeed a class of complementarity functions. We finally prove that the merit function of this new class of complementarity functions is coercive.     

Penalized complementarity functions on symmetric cones

We show that penalized functions of the Fischer–Burmeister and the natural residual functions defined on symmetric cones are complementarity functions. Boundedness of the solution set of a symmetric cone complementarity problem, based on the penalized natural residual function, is proved under monotonicity and strict feasibility. The proof relies on a trace inequality on Euclidean Jordan algebras.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

Smoothing algorithms for complementarity problems over symmetric cones

There recently has been much interest in studying optimization problems over symmetric cones. In this paper, we first investigate a smoothing function in the context of symmetric cones and show that it is coercive under suitable assumptions. We then extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones, and prove the proposed algorithms are globally convergent under suitable assumptions. We also give a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for second-order cone complementarity problems are reported.     

EXTENSION OF SMOOTHING FUNCTIONS TO SYMMETRIC CONE COMPLEMENTARITY PROBLEMS

The paper uses Euclidean Jordan algebras as a basic tool to extend smoothing functions, which include the Chen-Mangasarian class and the Fischer-Burmeister smoothing functions, to symmetric cone complementarity problems. Computable formulas for these functions and their Jacobians are derived. In addition, it is shown that these functions are Lipschitz continuous with respect to parameter # and continuously differentiable on J × J for any μ 〉 0.     

A smoothing Levenberg-Marquardt method for the complementarity problem over symmetric cone

In this paper, we propose a smoothing Levenberg-Marquardt method for the symmetric cone complementarity problem. Based on a smoothing function, we turn this problem into a system of nonlinear equations and then solve the equations by the method proposed. Under the condition of Lipschitz continuity of the Jacobian matrix and local error bound, the new method is proved to be globally convergent and locally superlinearly/quadratically convergent. Numerical experiments are also employed to show that the method is stable and efficient.

     

A class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions

In this paper, we introduce a one-parametric class of smoothing functions in the context of symmetric cones which contains two symmetric perturbed smoothing functions as special cases, and show that it is coercive under suitable assumptions. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve the complementarity problems over symmetric cones, and it is proved that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for randomly generated second-order cone programs and several practical second-order cone programs from the DIMACS library are reported.     

On the Lipschitzian property in linear complementarity problems over symmetric cones

Let V be a Euclidean Jordan algebra with symmetric cone K. We show that if a linear transformation L on V has the Lipschitzian property and the linear complementarity problem LCP(L,q) over K has a solution for every invertible q∈V, then 〈L(c),c〉>0 for all primitive idempotents c in V. We show that the converse holds for Lyapunov-like transformations, Stein transformations and quadratic representations. We also show that the Lipschitzian Q-property of the relaxation transformation R_A on V implies that A is a P-matrix.     

A new smoothing and regularization Newton method for the symmetric cone complementarity problem

Based on a regularized Chen–Harker–Kanzow–Smale (CHKS) smoothing function, we propose a new smoothing and regularization Newton method for solving the symmetric cone complementarity problem. By using the theory of Euclidean Jordan algebras, we establish the global and local quadratic convergence of the method on certain assumptions. The proposed method uses a nonmonotone line search technique which includes the usual monotone line search as a special case. In addition, our method treats both the smoothing parameter \(\mu \) and the regularization parameter \(\varepsilon \) as independent variables. Preliminary numerical results are reported which indicate that the proposed method is effective.     

A one-parametric class of merit functions for the symmetric cone complementarity problem

In this paper, we extend the one-parametric class of merit functions proposed by Kanzow and Kleinmichel [C. Kanzow, H. Kleinmichel, A new class of semismooth Newton-type methods for nonlinear complementarity problems, Comput. Optim. Appl. 11 (1998) 227-251] for the nonnegative orthant complementarity problem to the general symmetric cone complementarity problem (SCCP). We show that the class of merit functions is continuously differentiable everywhere and has a globally Lipschitz continuous gradient mapping. From this, we particularly obtain the smoothness of the Fischer-Burmeister merit function associated with symmetric cones and the Lipschitz continuity of its gradient. In addition, we also consider a regularized formulation for the class of merit functions which is actually an extension of one of the NCP function classes studied by [C. Kanzow, Y. Yamashita, M. Fukushima, New NCP functions and their properties, J. Optim. Theory Appl. 97 (1997) 115-135] to the SCCP. By exploiting the Cartesian P-properties for a nonlinear transformation, we show that the class of regularized merit functions provides a global error bound for the solution of the SCCP, and moreover, has bounded level sets under a rather weak condition which can be satisfied by the monotone SCCP with a strictly feasible point or the SCCP with the joint Cartesian R₀₂-property. All of these results generalize some recent important works in [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005) 293-327; C.-K. Sim, J. Sun, D. Ralph, A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function, Math. Program. 107 (2006) 547-553; P. Tseng, Merit function for semidefinite complementarity problems, Math. Program. 83 (1998) 159-185] under a unified framework.     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

Spherical functions on symmetric cones

In this note, we obtain a recursive formula for the spherical functions associated with the symmetric cone of a formally real Jordan algebra. We use this formula as an inspiration for a similar recursive formula involving the Jack polynomials.

     

Improved smoothing Newton methods for symmetric cone complementarity problems

There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems.     

Lyapunov-type least-squares problems over symmetric cones

The Lyapunov-type least-squares problem over symmetric cone is to find the least-squares solution of the Lyapunov equation with a constraint of symmetric cone in the Euclidean Jordan algebra, and it contains the Lyapunov-type least-squares problem over cone of semidefinite matrices as a special case. In this paper, we first give a detailed analysis for the image of Lyapunov operator in the Euclidean Jordan algebra. Relying on these properties together with some characterizations of symmetric cone, we then establish some necessary and?or sufficient conditions for solution existence of the Lyapunov-type least-squares problem. Finally, we study uniqueness of the least-squares solution.