JAPAN Complementarity Problems over Symmetric Cones: A Survey of Recent Developments in Several Aspects
---
paper_title: CONSTRAINT NONDEGENERACY, STRONG REGULARITY AND NONSINGULARITY IN SEMIDEFINITE PROGRAMMING

paper_content:

It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.
---
paper_title: A Mathematical View of Interior-point Methods for Convex Optimization

paper_content:

This compact book, through the simplifying perspective it presents, will take a reader who knows little of interior-point methods to within sight of the research frontier, developing key ideas that were over a decade in the making by numerous interior-point method researchers. It aims at developing a thorough understanding of the most general theory for interior-point methods, a class of algorithms for convex optimization problems. The study of these algorithms has dominated the continuous optimization literature for nearly 15 years. In that time, the theory has matured tremendously, but much of the literature is difficult to understand, even for specialists. By focusing only on essential elements of the theory and emphasizing the underlying geometry, A Mathematical View of Interior-Point Methods in Convex Optimization makes the theory accessible to a wide audience, allowing them to quickly develop a fundamental understanding of the material.
---
paper_title: Self-Scaled Barrier Functions on Symmetric Cones and Their Classification

paper_content:

Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and algebraic classification theory. In a first part we recall the characterisation of the family of self-scaled cones as the set of symmetric cones and develop a primal-dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then show that any self-scaled barrier function decomposes in an essentially unique way into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean Jordan algebras.
---
paper_title: CONSTRAINT NONDEGENERACY, STRONG REGULARITY AND NONSINGULARITY IN SEMIDEFINITE PROGRAMMING

paper_content:

It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.
---
paper_title: Two classes of merit functions for the second-order cone complementarity problem

paper_content:

Recently Tseng (Math Program 83:159–185, 1998) extended a class of merit functions, proposed by Luo and Tseng (A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, pp. 204–225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.
---
paper_title: Interior-Point Polynomial Algorithms in Convex Programming

paper_content:

Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynomial time methods, interior point methods, interior point methods for linear and quadratic programming, polynomial time methods for nonlinear convex programming, efficient computation methods for control problems and variational inequalities, and acceleration of path-following methods are covered. In this book, the authors describe the first unified theory of polynomial-time interior-point methods. Their approach provides a simple and elegant framework in which all known polynomial-time interior-point methods can be explained and analyzed; this approach yields polynomial-time interior-point methods for a wide variety of problems beyond the traditional linear and quadratic programs. The book contains new and important results in the general theory of convex programming, e.g., their "conic" problem formulation in which duality theory is completely symmetric. For each algorithm described, the authors carefully derive precise bounds on the computational effort required to solve a given family of problems to a given precision. In several cases they obtain better problem complexity estimates than were previously known. Several of the new algorithms described in this book, e.g., the projective method, have been implemented, tested on "real world" problems, and found to be extremely efficient in practice. Contents : Chapter 1: Self-Concordant Functions and Newton Method; Chapter 2: Path-Following Interior-Point Methods; Chapter 3: Potential Reduction Interior-Point Methods; Chapter 4: How to Construct Self- Concordant Barriers; Chapter 5: Applications in Convex Optimization; Chapter 6: Variational Inequalities with Monotone Operators; Chapter 7: Acceleration for Linear and Linearly Constrained Quadratic Problems
---
paper_title: Extension of primal-dual interior point algorithms to symmetric cones

paper_content:

In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.
---
paper_title: REDUCTION OF MONOTONE LINEAR COMPLEMENTARITY PROBLEMS OVER CONES TO LINEAR PROGRAMS OVER CONES

paper_content:

Dedicated to Hoang Tuy on the occasion of his seventieth birthday Abstract. This short note presents a constructive way of reducing monotone LCPs (linear complementarity problems) over cones to LPs (li- near programs) over cones. In particular, the monotone semideflnite lin- ear complementarity problem (SDLCP) in symmetric matrices, which was recently proposed by Kojima, Shindoh and Hara, is reducible to an SDP (semideflnite program). This gives a negative answer to their question whether the monotone SDLCP in symmetric matrices is an essential gen- eralization of the SDP.
---
paper_title: CONSTRAINT NONDEGENERACY, STRONG REGULARITY AND NONSINGULARITY IN SEMIDEFINITE PROGRAMMING

paper_content:

It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.
---
paper_title: Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones

paper_content:

We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones. While the analysis in [L. Faybusovich, Positivity, 1 (1997), pp. 331-357] depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang [Math. Oper. Res., 23 (1998), pp. 39-60], where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices. As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects. Consequently, we show the existence of a path having the following properties: (a) The path is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility.
---
paper_title: On Two Interior-Point Mappings for Nonlinear Semidefinite Complementarity Problems

paper_content:

Extending our previous work Monteiro and Pang 1996, this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. These trajectories completely "fill up" the set of interior feasible points of the problem in the same way as the weighted central paths do the interior of the feasible region of a linear program. Unlike the approach based on the theory of maximal monotone maps taken by Shida and Shindoh 1996 and Shida, Shindoh, and Kojima 1995, our approach is based on the theory of local homeomorphic maps in nonlinear analysis.
---
paper_title: Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones

paper_content:

We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones. While the analysis in [L. Faybusovich, Positivity, 1 (1997), pp. 331-357] depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang [Math. Oper. Res., 23 (1998), pp. 39-60], where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices. As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects. Consequently, we show the existence of a path having the following properties: (a) The path is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility.
---
paper_title: Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones

paper_content:

We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones. While the analysis in [L. Faybusovich, Positivity, 1 (1997), pp. 331-357] depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang [Math. Oper. Res., 23 (1998), pp. 39-60], where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices. As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects. Consequently, we show the existence of a path having the following properties: (a) The path is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility.
---
paper_title: Complementarity Functions and Numerical Experiments on Some Smoothing Newton Methods for Second-order-cone Complementarity Problems

paper_content:

Two results on the second-order-cone complementarity problem are presented. We show that the squared smoothing function is strongly semismooth. Under monotonicity and strict feasibility we provide a new proof, based on a penalized natural complementarity function, for the solution set of the second-order-cone complementarity problem being bounded. Numerical results of squared smoothing Newton algorithms are reported.
---
paper_title: Q-superlinear convergence of the iterates in primal-dual interior-point methods

paper_content:

Sufficient conditions are given for the Q-superlinear convergence of the iterates produced by primal-dual interior-point methods for linear complementarity problems. It is shown that those conditions are satisfied by several well known interior-point methods. In particular it is shown that the iteration sequences produced by the simplified predictor–corrector method of Gonzaga and Tapia, the simplified largest step method of Gonzaga and Bonnans, the LPF+ algorithm of Wright, the higher order methods of Wright and Zhang, Potra and Sheng, and Stoer, Wechs and Mizuno are Q-superlinearly convergent.
---
paper_title: An Infeasible Interior Point Method for Linear Complementarity Problems over Symmetric Cones

paper_content:

This paper presents a path following method for solving linear complementarity problems over symmetric cones. The starting point has to be strictly feasible with respect to the inequality constraints, but may be infeasible with respect to the equality constraints. Therefore, the algorithm falls into the broad class of infeasible interior point methods. The algorithm is a corrector‐predictor type method and it generalizes several corrector‐predictor methods presented in the literature. It has polynomial complexity under general assumption and superlinear convergence under some mild additional assumptions.
---
paper_title: Cartesian P-property and Its Applications to the Semidefinite Linear Complementarity Problem

paper_content:

We introduce a Cartesian P-property for linear transformations between the space of symmetric matrices and present its applications to the semidefinite linear complementarity problem (SDLCP). With this Cartesian P-property, we show that the SDLCP has GUS-property (i.e., globally unique solvability), and the solution map of the SDLCP is locally Lipschitzian with respect to input data. Our Cartesian P-property strengthens the corresponding P-properties of Gowda and Song [15] and allows us to extend several numerical approaches for monotone SDLCPs to solve more general SDLCPs, namely SDLCPs with the Cartesian P-property. In particular, we address important theoretical issues encountered in those numerical approaches, such as issues related to the stationary points in the merit function approach, and the existence of Newton directions and boundedness of iterates in the non-interior continuation method of Chen and Tseng [6].
---
paper_title: Analysis of nonsmooth vector-valued functions associated with second-order cones

paper_content:

Let Open image in new window be the Lorentz/second-order cone in Open image in new window . For any function f from Open image in new window to Open image in new window , one can define a corresponding function fsoc(x) on Open image in new window by applying f to the spectral values of the spectral decomposition of x∈ Open image in new window with respect to Open image in new window . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Frechet differentiability, continuous differentiability, as well as (ρ-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.
---
paper_title: Corrector-predictor methods for sufficient linear complementarity problems

paper_content:

We present a new corrector-predictor method for solving sufficient linear complementarity problems for which a sufficiently centered feasible starting point is available. In contrast with its predictor-corrector counterpart proposed by Miao, the method does not depend on the handicap ? of the problem. The method has $O((1+\kappa)\sqrt{n}L)$ -iteration complexity, the same as Miao's method, but our error estimates are sightly better. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also present a family of infeasible higher order corrector-predictor methods that are superlinearly convergent even in the absence of strict complementarity. The algorithms of this class are globally convergent for general positive starting points. They have $O((1+\kappa)\sqrt{n}L)$ -iteration complexity for feasible, or "almost feasible", starting points and O((1+?)2 nL)-iteration complexity for "sufficiently large" infeasible starting points.
---
paper_title: Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

paper_content:

We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Monteiro and Zhang [Math. Program., 81 (1998), pp. 281-299] introduced this family of directions when analyzing semidefinite programs. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd [Tech. rep. 1388, School of OR & IE, Cornell University, Ithaca, NY, 2003], which established convergence of infeasible-interior-point methods for self-scaled conic programs using the NT direction. Our work is built on earlier analyses by Faybusovich [J. Comput. Appl. Math., 86 (1997), pp. 149-175] and Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Of independent interest, we provide a constructive proof of Lyapunov lemma in the Jordan algebraic se...
---
paper_title: Extension of primal-dual interior point algorithms to symmetric cones

paper_content:

In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.
---
paper_title: A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming

paper_content:

A primal-dual infeasible-interior-point path-following algorithm is proposed for solving semidefinite programming (SDP) problems. If the problem has a solution, then the algorithm is globally convergent. If the starting point is feasible or close to being feasible, the algorithm finds an optimal solution in at most $O(\sqrt{n}L)$ iterations, where n is the size of the problem and L is the logarithm of the ratio of the initial error and the tolerance. If the starting point is large enough, then the algorithm terminates in at most O(nL) steps either by finding a solution or by determining that the primal-dual problem has no solution of norm less than a given number. Moreover, we propose a sufficient condition for the superlinear convergence of the algorithm. In addition, we give two special cases of SDP for which the algorithm is quadratically convergent.
---
paper_title: Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones

paper_content:

We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones. While the analysis in [L. Faybusovich, Positivity, 1 (1997), pp. 331-357] depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang [Math. Oper. Res., 23 (1998), pp. 39-60], where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices. As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects. Consequently, we show the existence of a path having the following properties: (a) The path is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility.
---
paper_title: On a Homogeneous Algorithm for the Monotone Complementarity Problem

paper_content:

We present a generalization of a homogeneous self-dual linear programming (LP) algorithm to solving the monotone complementarity problem (MCP). The algorithm does not need to use any "big-M" parameter or two-phase method, and it generates either a solution converging towards feasibility and comple- mentarity simultaneously or a certificate proving infeasibility. Moreover, if the MCP is polynomially solvable with an interior feasible starting point, then it can be polynomially solved without using or knowing such information at all. To our knowledge, this is the first interior-point and infeasible-starting algorithm for solving the MCP that possesses these desired features. Preliminary computational results are presented.
---
paper_title: Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

paper_content:

We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Monteiro and Zhang [Math. Program., 81 (1998), pp. 281-299] introduced this family of directions when analyzing semidefinite programs. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd [Tech. rep. 1388, School of OR & IE, Cornell University, Ithaca, NY, 2003], which established convergence of infeasible-interior-point methods for self-scaled conic programs using the NT direction. Our work is built on earlier analyses by Faybusovich [J. Comput. Appl. Math., 86 (1997), pp. 149-175] and Schmieta and Alizadeh [Math. Program., 96 (2003), pp. 409-438]. Of independent interest, we provide a constructive proof of Lyapunov lemma in the Jordan algebraic se...
---
paper_title: Extension of primal-dual interior point algorithms to symmetric cones

paper_content:

In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.
---
paper_title: A Polynomial Time Interior-Point Path-Following Algorithm for LCP Based on Chen-Harker-Kanzow Smoothing Techniques

paper_content:

); otherwise, the complexity bound is O(nL). The relations between our search direction and the one used in the standard interior-point algorithm are also discussed.
---
paper_title: An Infeasible Interior Point Method for Linear Complementarity Problems over Symmetric Cones

paper_content:

This paper presents a path following method for solving linear complementarity problems over symmetric cones. The starting point has to be strictly feasible with respect to the inequality constraints, but may be infeasible with respect to the equality constraints. Therefore, the algorithm falls into the broad class of infeasible interior point methods. The algorithm is a corrector‐predictor type method and it generalizes several corrector‐predictor methods presented in the literature. It has polynomial complexity under general assumption and superlinear convergence under some mild additional assumptions.
---
paper_title: A Note on the Local Convergence of a Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Based on the Alizadeh--Haeberly--Overton Search Direction

paper_content:

This note points out an error in the local quadratic convergence proof of the predictor-corrector interior-point algorithm for solving the semidefinite linear complementarity problem based on the Alizadeh--Haeberly--Overton search direction presented in [M. Kojima, M. Shida, and S. Shindoh, SIAM J. Optim., 9 (1999), pp. 444--465]. Their algorithm is slightly modified and the local quadratic convergence of the resulting method is established.
---
paper_title: Asymptotic Behavior of HKM Paths in Interior Point Methods for Monotone Semidefinite Linear Complementarity Problems: General Theory

paper_content:

An interior point method (IPM) defines a search direction at an interior point of the feasible region. These search directions form a direction field which in turn defines a system of ordinary dierential equations (ODEs). Thus, it is natural to define the underlying paths of the IPM as the solutions of the systems of ODEs. In [8], these o-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to the given monotone semidefinite linear complementarity problem (SDLCP). The o-central path of a simple example is also studied in [8] whose asymptotic behavior near the solution of the example is analyzed. In this paper, which is an extension of [8], we study the asymptotic behavior of o-central path for general SDLCP (using the dual HKM direction), instead of for a given example. We give a necessary and sucient condition for when an o-central path is analytic as a function of p µ at the solution of the SDLCP. Then we show that if the given SDLCP has a unique solution, the first derivative of its o-central path, as a function of p µ, is bounded. We work under the assumption that the given SDLCP satisfies strict complementarity condition.
---
paper_title: Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems

paper_content:

We consider semidefinite monotone linear complementarity problems (SDLCP) in the space *** equation here *** n of real symmetric n×n-matrices equipped with the cone *** equation here *** n+ of all symmetric positive semidefinite matrices. One may define weighted (using any M∈ *** equation here *** n++ as weight) infeasible interior point paths by replacing the standard condition XY=rI, r>0, (that defines the usual central path) by (XY+YX)/2=rM. Under some mild assumptions (the most stringent is the existence of some strictly complementary solution of (SDLCP)), these paths have a limit as r↓0, and they depend analytically on all path parameters (such as r and M), even at the limit point r=0.
---
paper_title: Superlinear Convergence of Infeasible Predictor-Corrector Path-Following Interior Point Algorithm for SDLCP using the HKM Direction

paper_content:

Interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In [31], these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to a given monotone semidefinite linear complementarity problem (SDLCP). The study of these paths provides a way to understand how iterates generated by an interior point algorithm behave. In this paper, we give a weak sufficient condition using these off-central paths that guarantees superlinear convergence of a predictor-corrector path-following interior point algorithm for SDLCP using the HKM direction. This sufficient condition is implied by a currently known sufficient condition for superlinear convergence. Using this sufficient condition, we show that for any linear semi-definite feasibility problem, superlinear convergence using the interior point algorithm, with the HKM direction, can be achieved, for a suitable starting point. We work under the assumption of strict complementarity.
---
paper_title: A Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Using the Alizadeh-Haeberly-Overton Search Direction

paper_content:

This paper proposes a globally convergent predictor-corrector infeasible-interior-point algorithm for the monotone semidefinite linear complementarity problem using the Alizadeh--Haeberly--Overton search direction, and shows its quadratic local convergence under the strict complementarity condition.
---
paper_title: A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming

paper_content:

A primal-dual infeasible-interior-point path-following algorithm is proposed for solving semidefinite programming (SDP) problems. If the problem has a solution, then the algorithm is globally convergent. If the starting point is feasible or close to being feasible, the algorithm finds an optimal solution in at most $O(\sqrt{n}L)$ iterations, where n is the size of the problem and L is the logarithm of the ratio of the initial error and the tolerance. If the starting point is large enough, then the algorithm terminates in at most O(nL) steps either by finding a solution or by determining that the primal-dual problem has no solution of norm less than a given number. Moreover, we propose a sufficient condition for the superlinear convergence of the algorithm. In addition, we give two special cases of SDP for which the algorithm is quadratically convergent.
---
paper_title: Coercivity and Strong Semismoothness of the Penalized Fischer-Burmeister Function for the Symmetric Cone Complementarity Problem

paper_content:

For the nonlinear complementarity problem (NCP), Chen et al. (Math. Program., 88:211–216, 2000) proposed a penalized Fischer-Burmeister (FB) function that has most desirable properties among complementarity functions (C-functions). Motivated by their work, the authors showed (Kum and Lim in Penalized Complementarity Functions on Symmetric Cones, submitted, 2009) that this function naturally extends to a C-function for the symmetric cone complementarity problem (SCCP). In this note, we show that the main coercivity property of this function for NCP also extends to the SCCP. The proof uses a new trace inequality on Euclidean Jordan algebras. We also show that the penalized FB function is strongly semismooth in the case of a semidefinite cone and a second-order cone.
---
paper_title: Smoothing algorithms for complementarity problems over symmetric cones

paper_content:

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.
---
paper_title: Fischer-Burmeister Complementarity Function on Euclidean Jordan Algebras ∗

paper_content:

∗The work was partly supported by a Discovery Grant from NSERC, and the National Natural Science Foundation of China (10671010, 70640420143). 1 Lingchen Kong, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada; Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, P. R. China (e-mail: konglchen@126.com) 2 Levent Tuncel, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada (e-mail: ltuncel@math.uwaterloo.ca) 3 Naihua Xiu, Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, P. R. China (e-mail: nhxiu@center.njtu.edu.cn)
---
paper_title: Growth Behavior of Two Classes of Merit Functions for Symmetric Cone Complementarity Problems

paper_content:

In the solution methods of the symmetric cone complementarity problem (SCCP), the squared norm of a complementarity function serves naturally as a merit function for the problem itself or the equivalent system of equations reformulation. In this paper, we study the growth behavior of two classes of such merit functions, which are induced by the smooth EP complementarity functions and the smooth implicit Lagrangian complementarity function, respectively. We show that, for the linear symmetric cone complementarity problem (SCLCP), both the EP merit functions and the implicit Lagrangian merit function are coercive if the underlying linear transformation has the P-property; for the general SCCP, the EP merit functions are coercive only if the underlying mapping has the uniform Jordan P-property, whereas the coerciveness of the implicit Lagrangian merit function requires an additional condition for the mapping, for example, the Lipschitz continuity or the assumption as in (45).
---
paper_title: New smooth C-functions for symmetric cone complementarity problems

paper_content:

In this paper, with the help of the Jordan-algebraic technique we introduce two new complementarity functions (C-functions) for symmetric cone complementary problems, and show that they are continuously differentiable and strongly semismooth everywhere.
---
paper_title: VECTOR-VALUED IMPLICIT LAGRANGIAN FOR SYMMETRIC CONE COMPLEMENTARITY PROBLEMS

paper_content:

The implicit Lagrangian was first proposed by Mangasarian and Solodov as a smooth merit function for the nonnegative orthant complementarity problem. It has attracted much attention in the past ten years because of its utility in reformulating complementarity problems as unconstrained minimization problems. In this paper, exploiting the Jordan-algebraic structure, we extend it to the vector-valued implicit Lagrangian for symmetric cone complementary problem (SCCP), and show that it is a continuously differentiable complementarity function for SCCP and whose Jacobian is strongly semismooth. As an application, we develop the real-valued implicit Lagrangian and the corresponding smooth merit function for SCCP, and give a necessary and sufficient condition for the stationary point of the merit function to be a solution of SCCP. Finally, we show that this merit function can provide a global error bound for SCCP with the uniform Cartesian P-property.
---
paper_title: On the coerciveness of some merit functions for complementarity problems over symmetric cones

paper_content:

Abstract 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.
---
paper_title: Extension of smoothing functions to symmetric cone complementarity problems

paper_content:

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.
---
paper_title: A Regularized Smoothing Newton Method for Symmetric Cone Complementarity Problems

paper_content:

This paper extends the regularized smoothing Newton method in vector complementarity problems to symmetric cone complementarity problems (SCCP), which includes the nonlinear complementarity problem, the second-order cone complementarity problem, and the semidefinite complementarity problem as special cases. In particular, we study strong semismoothness and Jacobian nonsingularity of the total natural residual function for SCCP. We also derive the uniform approximation property and the Jacobian consistency of the Chen-Mangasarian smoothing function of the natural residual. Based on these properties, global and quadratical convergence of the proposed algorithm is established.
---
paper_title: Corrector-predictor methods for sufficient linear complementarity problems

paper_content:

We present a new corrector-predictor method for solving sufficient linear complementarity problems for which a sufficiently centered feasible starting point is available. In contrast with its predictor-corrector counterpart proposed by Miao, the method does not depend on the handicap ? of the problem. The method has $O((1+\kappa)\sqrt{n}L)$ -iteration complexity, the same as Miao's method, but our error estimates are sightly better. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also present a family of infeasible higher order corrector-predictor methods that are superlinearly convergent even in the absence of strict complementarity. The algorithms of this class are globally convergent for general positive starting points. They have $O((1+\kappa)\sqrt{n}L)$ -iteration complexity for feasible, or "almost feasible", starting points and O((1+?)2 nL)-iteration complexity for "sufficiently large" infeasible starting points.
---
paper_title: Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions

paper_content:

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.
---
paper_title: Smoothing method for mathematical programs with symmetric cone complementarity constraints

paper_content:

In this article, we consider the mathematical program with symmetric cone complementarity constraints (MPSCCC) in a general form. It contains the mathematical program with second-order-cone complementarity constraints and the mathematical program with complementarity constraints. We present a smoothing method that approximates the primal MPSCCC by means of the Chen–Mangasarian class of smoothing functions. We show that a sequence of stationary points of the approximate programs converges to a C(larke)-stationary point of the primal MPSCCC under suitable conditions.
---
paper_title: A new class of smoothing complementarity functions over symmetric cones

paper_content:

Abstract A popular approach to solving the complementarity problem is to reformulate it as an equivalent system of smooth equations via a smoothing complementarity function. In this paper, first we propose a new class of smoothing complementarity functions, which contains the natural residual smoothing function and the Fischer–Burmeister smoothing function for symmetric cone complementarity problems. Then we give some unified formulae of the Frechet derivatives associated with Jordan product. Finally, the derivative of the new proposed class of smoothing complementarity functions is deduced over symmetric cones.
---
paper_title: A one-parametric class of merit functions for the symmetric cone complementarity problem

paper_content:

Abstract 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 02 -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.
---
paper_title: Penalized complementarity functions on symmetric cones

paper_content:

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.
---
paper_title: Semismooth and Semiconvex Functions in Constrained Optimization

paper_content:

We introduce semismooth and semiconvex functions and discuss their properties with respect to nonsmooth nonconvex constrained optimization problems. These functions are locally Lipschitz, and hence have generalized gradients. The author has given an optimization algorithm that uses generalized gradients of the problem functions and converges to stationary points if the functions are semismooth. If the functions are semiconvex and a constraint qualification is satisfied, then we show that a stationary point is an optimal point.We show that the pointwise maximum or minimum over a compact family of continuously differentiable functions is a semismooth function and that the pointwise maximum over a compact family of semiconvex functions is a semiconvex function. Furthermore, we show that a semismooth composition of semismooth functions is semismooth and give a type of chain rule for generalized gradients.
---
paper_title: Optimization and Nonsmooth Analysis

paper_content:

1. Introduction and Preview 2. Generalized Gradients 3. Differential Inclusions 4. The Calculus of Variations 5. Optimal Control 6. Mathematical Programming 7. Topics in Analysis.
---
paper_title: A modification and an extension of Lemarechal’s algorithm for nonsmooth minimization

paper_content:

An algorithm is given for finding stationary points for constrained minimization problems having locally Lipschitz problem functions that are not necessarily convex or differentiable but are semismooth.
---
paper_title: Error bounds for analytic systems and their applications

paper_content:

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush--Kuhn--Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0---1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.
---
paper_title: NE/SQP: A robust algorithm for the nonlinear complementarity problem

paper_content:

In this paper, we present a new iterative method for solving the nonlinear complementarity problem. This method, which we call NE/SQP (for Nonsmooth Equations/Successive Quadratic Programming), is a damped Gauss--Newton algorithm applied to solve a certain nonsmooth-equation formulation of the complementarity problem; it is intended to overcome a major deficiency of several previous methods of this type. Unlike these earlier algorithms whose convergence critically depends on a solvability assumption on the subproblems, the NE/SQP method involves solving a sequence of nonnegatively constrained convex quadratic programs of the least-squares type; the latter programs are always solvable and their solution can be obtained by a host of efficient quadratic programming subroutines. Hence, the new method is a robust procedure which, not only is very easy to describe and simple to implement, but also has the potential advantage of being capable of solving problems of very large size. Besides the desirable feature of robustness and ease of implementation, the NE/SQP method retains two fundamental attractions of a typical member in the Gauss--Newton family of algorithms; namely, it is globally and locally quadratically convergent. Besides presenting the detailed description of the NE/SQP method and the associated convergence theory, we also report the numerical results of an extensive computational study which is aimed at demonstrating the practical efficiency of the method for solving a wide variety of realistic nonlinear complementarity problems.
---
paper_title: Self-Scaled Barrier Functions on Symmetric Cones and Their Classification

paper_content:

Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and algebraic classification theory. In a first part we recall the characterisation of the family of self-scaled cones as the set of symmetric cones and develop a primal-dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then show that any self-scaled barrier function decomposes in an essentially unique way into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean Jordan algebras.
---
paper_title: Monotonicity of Löwner Operators and Its Applications to Symmetric Cone Complementarity Problems ∗

paper_content:

We prove necessary and sufficient conditions for locally Lipschitz Lowner operators to be monotone, strictly monotone and strongly monotone. Utilizing our characterization of the strict monotonicity of Lowner operators, we generalize Mangasarian class of Nonlinear Complementarity Problem (NCP)-functions to the setting of symmetric cone complementarity problem. This affirmatively answers a question of Tseng [Math Program 83:159–185, 1998].
---
paper_title: Semismooth Matrix Valued Functions

paper_content:

Matrix-valued functions play an important role in the development of algorithms for semidefinite programming problems. This paper studies generalized differential properties of such functions related to nonsmooth-smoothing Newton methods. The first part of this paper discusses basic properties such as the generalized derivative, Rademacher's theorem, B-derivative, directional derivative, and semismoothness. The second part shows that the matrix absolute-value function, the matrix semidefinite-projection function, and the matrix projective residual function are strongly semismooth.
---
paper_title: Analysis of Nonsmooth Symmetric-Matrix-Valued Functions with Applications to Semidefinite Complementarity Problems

paper_content:

For any function f from $\mathbb R$ to $\mathbb R$, one can define a corresponding function on the space of n × n (block-diagonal) real symmetric matrices by applying f to the eigenvalues of the spectral decomposition. We show that this matrix-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Frechet differentiability, continuous differentiability, as well as ($\rho$-order) semismoothness. Our analysis uses results from nonsmooth analysis as well as perturbation theory for the spectral decomposition of symmetric matrices. We also apply our results to the semidefinite complementarity problem, addressing some basic issues in the analysis of smoothing/semismooth Newton methods for solving this problem.
---
paper_title: On a global projection-type error bound for the linear complementarity problem

paper_content:

Abstract We consider a projection-type error bound for the linear complementarity problem involving a matrix M and vector q . First, we show that the Mangasarian-Ren sufficient condition on M for this error bound to hold globally, for all q such that the problem is solvable, is also necessary. Second, we derive necessary and sufficient conditions on M and q for this error bound to hold globally, thus extending a result of Luo and Tseng which in addition assumes M is psd-plus. Third, we derive necessary and sufficient conditions on M for this error bound to hold globally, independent of q . These conditions are closely related to M being Lipschitzian. We also discuss application of our result to the affine variational inequality problem.
---
paper_title: A special newton-type optimization method

paper_content:

The Kuhn–Tucker conditions of an optimization problem with inequality constraints are transformed equivalently into a special nonlinear system of equations T 0(z) = 0. It is shown that Newton's method for solving this system combines two valuable properties: The local Q-quadratic convergence without assuming the strict complementary slackness condition and the regularity of the Jacobian of T 0 at a point z under reasonable conditions, so that Newton’s method can be used also far from a Kuhn–Tucker point
---
paper_title: A non-interior-point continuation method for linear complementarity problems

paper_content:

This paper presents a continuation method for linear complementarily problems based on a new smooth equation formulation. In particular, the case of a linear complementarity problem defined by a positive semidefinite or $P_0 $ matrix is studied in detail. Extensive numerical testing of the continuation method is performed for both problems in the literature and randomly generated problems.
---
paper_title: Some Noninterior Continuation Methods for LinearComplementarity Problems

paper_content:

We introduce some new path-following methods for the solution of the linear complementarity problem. We call these methods noninterior continuation methods since, in contrast to interior-point methods, not all iterates have to stay in the positive orthant. This is possible since we reformulate certain perturbed complementarity problems as a nonlinear system of equations. However, similar to interior-point methods, we also try to follow the central path. We present some conditions which guarantee the existence of this central path, prove a global convergence result for some implementable noninterior continuation methods, and report some numerical results obtained with these methods. We also prove global error bound results for the perturbed linear complementarity problems.
---
paper_title: Smoothing methods for convex inequalities and linear complementarity problems

paper_content:

A smooth approximationp (x, α) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e−αx), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy forα sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finiteα. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.
---
paper_title: Non-Interior continuation methods for solving semidefinite complementarity problems

paper_content:

There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
---
paper_title: A Class of Smoothing Functions for Nonlinear and Mixed Complementarity Problems

paper_content:

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].
---
paper_title: Merit functions for semi-definite complementarity problems

paper_content:

Merit functions such as the gap function, the regularized gap function, the implicit Lagrangian, and the norm squared of the Fischer-Burmeister function have played an important role in the solution of complementarity problems defined over the cone of nonnegative real vectors. We study the extension of these merit functions to complementarity problems defined over the cone of block-diagonal symmetric positive semi-definite real matrices. The extension suggests new solution methods for the latter problems.
---
paper_title: Algorithms for Solving Equations

paper_content:

The main goal of this work is an attempt to understand the efficiency of algorithms for solving systems of equations. For example, consider a map / from complex Cartesian space C n to C n given by polynomials. How fast can one find good approximations to one or all of the zeros of / ? However, for clarity of exposition and development we will usually swing from one extreme to another about this example, proving theorems on one hand for a single complex polynomial and on the other hand for an analytic map / : F —> F from one Banach space to another (both real or both complex). This subject should undoubtedly be considered as numerical analysis. However, my point of view has been especially influenced by complexity theory of computer science. Thus the emphasis is on the algorithms themselves and a global study of their speed. Hence less emphasis is given to the results obtained by algorithms and the asymptotic criteria of efficiency that are often found in numerical analysis literature. This global study, or complexity theory, gives a more systematic, more abstract, more theoretical flavor to our approach, and thus we are less concerned about producing immediately faster methods for problem solving. A basic understanding of the tried and effective is sought. The global study of the algorithm forces the introduction of topology and geometry into the subject. If any algorithm has proved itself for the problem of nonlinear systems, it is Newton's method and its many modifications. The Greeks essentially used it for finding square roots; and for that purpose it is still a top method today. On the other hand, for nonlinear functional equations framed in a Banach space setting, Newton's method finds a central place. In the account here, the one theme is Newton's method. We will prove theorems about it for one variable (dealing with the fundamental theorem of algebra) and for maps of Banach spaces; we will approximate Dantzig's [8] simplex method for the linear programming problem by Newton's method.
---
paper_title: A new approach to continuation methods for complementarity problems with uniform P-functions

paper_content:

We design a new continuation method for the solution of nonlinear complementarity problems with uniform P-functions. Similar to interior-point methods, we try to follow the central path inexactly. In contrast to interior-point methods, however, our iterates are allowed to stay outside of the positive orthant. The method is shown to be globally and superlinearly (quadratically) convergent.
---
paper_title: Errata: On semidefinite linear complementarity problems

paper_content:

Abstract.We correct an error in the statement of Theorem 8 in [1].
---
paper_title: A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems

paper_content:

We study a smoothing Newton method for solving a nonsmooth matrix equation that includes semidefinite programming and the semidefinite complementarity problem as special cases. This method, if specialized for solving semidefinite programs, needs to solve only one linear system per iteration and achieves quadratic convergence under strict complementarity and nondegeneracy. We also establish quadratic convergence of this method applied to the semidefinite complementarity problem under the assumption that the Jacobian of the problem is positive definite on the affine hull of the critical cone at the solution. These results are based on the strong semismoothness and complete characterization of the B-subdifferential of a corresponding squared smoothing matrix function, which are of general theoretical interest.
---
paper_title: CONSTRAINT NONDEGENERACY, STRONG REGULARITY AND NONSINGULARITY IN SEMIDEFINITE PROGRAMMING

paper_content:

It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.
---
paper_title: Analysis of Nonsmooth Symmetric-Matrix-Valued Functions with Applications to Semidefinite Complementarity Problems

paper_content:

For any function f from $\mathbb R$ to $\mathbb R$, one can define a corresponding function on the space of n × n (block-diagonal) real symmetric matrices by applying f to the eigenvalues of the spectral decomposition. We show that this matrix-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Frechet differentiability, continuous differentiability, as well as ($\rho$-order) semismoothness. Our analysis uses results from nonsmooth analysis as well as perturbation theory for the spectral decomposition of symmetric matrices. We also apply our results to the semidefinite complementarity problem, addressing some basic issues in the analysis of smoothing/semismooth Newton methods for solving this problem.
---
paper_title: Global Lipschitzian error bounds for semidefinite complementarity problems with emphasis on NCPs

paper_content:

Error bound theory play an important role in many mathematical programming problems. In this paper, we propose a new assumption condition under which we establish a global Lipshitzian error bound for the semidefinite complementarity problem (SDCP). As corollaries, two results involving the assumptions of strong monotonicity and BD-regularity are given. When the SDCP reduces to the nonlinear complementarity problem (NCP), our results strictly generalize the well-known error bound results which were established under the assumptions of strong monotonicity and uniform P-property. We also establish a new error bound for the NCP under BD-regularity and some R"0-type condition.
---
paper_title: The bounded smooth reformulation and a trust region algorithm for semidefinite complementarity problems

paper_content:

In this paper, we present a new merit function for the semidefinite complementarity problem (SDCP) by extending the bounded smooth reformulation for variational inequality problems. We prove that the merit function has a bounded level set and any stationary point of it is a global minimizer without the assumption of monotonicity. Moreover, we present a trust region algorithm for solving the minimization problem with semidefinite constraints. The trust region subproblem is solved by the truncated conjugate gradient method and the global convergence is established even without requiring the existence of an accumulation point of the generated sequence.
---
paper_title: Non-Interior continuation methods for solving semidefinite complementarity problems

paper_content:

There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
---
paper_title: Inexact non-interior continuation method for solving large-scale monotone SDCP

paper_content:

For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent.
---
paper_title: Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

paper_content:

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Frechet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.
---
paper_title: Merit functions for semi-definite complementarity problems

paper_content:

Merit functions such as the gap function, the regularized gap function, the implicit Lagrangian, and the norm squared of the Fischer-Burmeister function have played an important role in the solution of complementarity problems defined over the cone of nonnegative real vectors. We study the extension of these merit functions to complementarity problems defined over the cone of block-diagonal symmetric positive semi-definite real matrices. The extension suggests new solution methods for the latter problems.
---
paper_title: A New Merit Function and a Descent Method for Semidefinite Complementarity Problems

paper_content:

Recently, Tseng extended several merit functions for the nonlinear complementarity problem to the semidefinite complementarity problem (SDCP) and investigated various properties of those functions. In this paper, we propose a new merit function for the SDCP based on the squared Fischer-Burmeister function and show that it has some favorable properties. Particularly, we give conditions under which the function provides a global error bound for the SDCP and conditions under which it has bounded level sets. We also present a derivative-free method for solving the SDCP and prove its global convergence under suitable assumptions.
---
paper_title: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions

paper_content:

We show that the Fischer-Burmeister complementarity functions, associated to the semidefinite cone (SDC) and the second order cone (SOC), respectively, are strongly semismooth everywhere. Interestingly enough, the proof relys on a relationship between the singular value decomposition of a nonsymmetric matrix and the spectral decomposition of a symmetric matrix.
---
paper_title: Quadratic Convergence of a Nonsmooth Newton-Type Method for Semidefinite Programs Without Strict Complementarity

paper_content:

We consider a Newton-type method for the solution of semidefinite programs. This Newton-type method is based on a semismooth reformulation of the semidefinite program as a nonsmooth system of equations. We establish local quadratic convergence of this method under a linear independence assumption and a weak nondegeneracy condition that implies uniqueness of the optimal solution but does not imply strict complementarity.
---
paper_title: Complementarity Functions and Numerical Experiments on Some Smoothing Newton Methods for Second-order-cone Complementarity Problems

paper_content:

Two results on the second-order-cone complementarity problem are presented. We show that the squared smoothing function is strongly semismooth. Under monotonicity and strict feasibility we provide a new proof, based on a penalized natural complementarity function, for the solution set of the second-order-cone complementarity problem being bounded. Numerical results of squared smoothing Newton algorithms are reported.
---
paper_title: A Damped Gauss-Newton Method for the Second-Order Cone Complementarity Problem

paper_content:

We investigate some properties related to the generalized Newton method for the Fischer-Burmeister (FB) function over second-order cones, which allows us to reformulate the second-order cone complementarity problem (SOCCP) as a semismooth system of equations. Specifically, we characterize the B-subdifferential of the FB function at a general point and study the condition for every element of the B-subdifferential at a solution being nonsingular. In addition, for the induced FB merit function, we establish its coerciveness and provide a weaker condition than Chen and Tseng (Math. Program. 104:293–327, 2005) for each stationary point to be a solution, under suitable Cartesian P-properties of the involved mapping. By this, a damped Gauss-Newton method is proposed, and the global and superlinear convergence results are obtained. Numerical results are reported for the second-order cone programs from the DIMACS library, which verify the good theoretical properties of the method.
---
paper_title: A one-step smoothing Newton method for second-order cone programming

paper_content:

A new smoothing function for the second-order cone programming is given by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this new function, a one-step smoothing Newton method is presented for solving the second-order cone programming. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. This algorithm does not have restrictions regarding its starting point and is Q-quadratically convergent. Numerical results suggest the effectiveness of our algorithm.
---
paper_title: On the coderivative of the projection operator onto the second-order cone

paper_content:

The limiting (Mordukhovich) coderivative of the metric projection onto the second-order cone \(\mathbb{R}^{n}\) is computed. This result is used to obtain a sufficient condition for the Aubin property of the solution map of a parameterized second-order cone complementarity problem and to derive necessary optimality conditions for a mathematical program with a second-order cone complementarity problem among the constraints.
---
paper_title: Two classes of merit functions for the second-order cone complementarity problem

paper_content:

Recently Tseng (Math Program 83:159–185, 1998) extended a class of merit functions, proposed by Luo and Tseng (A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, pp. 204–225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.
---
paper_title: Three-Dimensional Quasi-Static Frictional Contact by using Second-Order Cone Linear Complementarity Problem

paper_content:

A new formulation is presented for the three-dimensional incremental quasi-static problems with unilateral frictional contact. Under the assumptions of small rotations and small strains, a second-order cone linear complementarity problem is formulated, which consists of complementarity conditions defined by bilinear functions and second-order cone constraints. The equilibrium configurations are obtained by using a combined smoothing and regularization method for the second-order cone complementarity problem. Copyright © 2005 John Wiley & Sons, Ltd.
---
paper_title: A one-parametric class of merit functions for the second-order cone complementarity problem

paper_content:

We investigate a one-parametric class of merit functions for the second-order cone complementarity problem (SOCCP) which is closely related to the popular Fischer---Burmeister (FB) merit function and natural residual merit function. In fact, it will reduce to the FB merit function if the involved parameter ? equals 2, whereas as ? tends to zero, its limit will become a multiple of the natural residual merit function. In this paper, we show that this class of merit functions enjoys several favorable properties as the FB merit function holds, for example, the smoothness. These properties play an important role in the reformulation method of an unconstrained minimization or a nonsmooth system of equations for the SOCCP. Numerical results are reported for some convex second-order cone programs (SOCPs) by solving the unconstrained minimization reformulation of the KKT optimality conditions, which indicate that the FB merit function is not the best. For the sparse linear SOCPs, the merit function corresponding to ?=2.5 or 3 works better than the FB merit function, whereas for the dense convex SOCPs, the merit function with ?=0.1, 0.5 or 1.0 seems to have better numerical performance.
---
paper_title: A Combined Smoothing and Regularization Method for Monotone Second-Order Cone Complementarity Problems

paper_content:

The second-order cone complementarity problem (SOCCP) is a wide class of problems containing the nonlinear complementarity problem (NCP) and the second-order cone programming problem (SOCP). Recently, Fukushima, Luo, and Tseng [SIAM J. Optim., 12 (2001), pp. 436--460] extended some merit functions and their smoothing functions for NCP to SOCCP. Moreover, they derived computable formulas for the Jacobians of the smoothing functions and gave conditions for the Jacobians to be invertible. In this paper, we propose a globally and quadratically convergent algorithm, which is based on smoothing and regularization methods, for solving monotone SOCCP. In particular, we study strong semismoothness and Jacobian consistency, which play an important role in establishing quadratic convergence of the algorithm. Furthermore, we examine the effectiveness of the algorithm by means of numerical experiments.
---
paper_title: Analysis of nonsmooth vector-valued functions associated with second-order cones

paper_content:

Let Open image in new window be the Lorentz/second-order cone in Open image in new window . For any function f from Open image in new window to Open image in new window , one can define a corresponding function fsoc(x) on Open image in new window by applying f to the spectral values of the spectral decomposition of x∈ Open image in new window with respect to Open image in new window . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Frechet differentiability, continuous differentiability, as well as (ρ-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.
---
paper_title: Conditions for Error Bounds and Bounded Level Sets of Some Merit Functions for the Second-Order Cone Complementarity Problem

paper_content:

Recently this author studied several merit functions systematically for the second-order cone complementarity problem. These merit functions were shown to enjoy some favorable properties, to provide error bounds under the condition of strong monotonicity, and to have bounded level sets under the conditions of monotonicity as well as strict feasibility. In this paper, we weaken the condition of strong monotonicity to the so-called uniform P *-property, which is a new concept recently developed for linear and nonlinear transformations on Euclidean Jordan algebra. Moreover, we replace the monotonicity and strict feasibility by the so-called R 01 or R 02-functions to keep the property of bounded level sets.
---
paper_title: The solution set structure of monotone linear complementarity problems over second-order cone

paper_content:

The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique.
---
paper_title: Robust Nash equilibria in N-person non-cooperative games: Uniqueness and reformulation

paper_content:

The present invention provides an apparatus for monitoring access by a processor in a computing system to certain defined portions of memory. According to the present invention, the user specifies an address or range of address (the "watchword") in memory to be monitored. Each processor contains hardware which monitors outgoing memory references. If the processor attempts to access the defined portion of memory, the present invention generates a signal which is sent back to the issuing processor to inform it that referenced the watchword in memory. The present invention has several applications. In particular however, the present invention can be used in conjunction with debugging software packages as an aid for debugging user software programs on multiprocessing computer systems. Specifically, the present invention can be used to pinpoint which processor in a multiprocessing computer system accessed the watchword portion of memory. For example, if a processor executed an instruction containing an error, causing improper calculation of a write destination address which resulted in data errors in memory, the present invention can pinpoint precisely which processor in the multiprocessing computer system executed the erroneous instruction, thus pinpointing the erroneous code to within a few instructions. An additional feature of the present invention is that it operates wholly independently and in parallel with the output circuitry of a processor. Thus, no additional levels of logic are introduced into the processor-to-memory path, and as a result the present invention does not adversely impact overall system performance.
---
paper_title: A new smoothing Newton-type method for second-order cone programming problems

paper_content:

A new smoothing function of the well-known Fischer-Burmeister function is given. Based on this new function, a smoothing Newton-type method is proposed for solving second-order cone programming. At each iteration, the proposed algorithm solves only one system of linear equations and performs only one line search. This algorithm can start from an arbitrary point and it is Q-quadratically convergent under a mild assumption. Numerical results demonstrate the effectiveness of the algorithm.
---
paper_title: A new merit function and its related properties for the second-order cone complementarity problem

paper_content:

Recently, J.-S. Chen and P. Tseng extended two merit functions for the non- linear complementarity problem (NCP) and the semideflnite complementarity problem (SDCP) to the second-order cone commplementarity problem (SOCCP) and showed sev- eral favorable properties. In this paper, we extend a merit function for the NCP studied by Yamada, Yamashita, and Fukushima to the SOCCP and show that the SOCCP is equivalent to an unconstrained smooth minimization via this new merit function. Fur- thermore, we study conditions under which the new merit function provides a global error bound which plays an important role in analyzing the convergence rate of iterative methods for solving the SOCCP; and conditions under which the new merit function has bounded level sets which ensures that the sequence generated by a descent method has at least one accumulation point.
---
paper_title: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

paper_content:

A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝn. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝn and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.
---
paper_title: A proximal gradient descent method for the extended second-order cone linear complementarity problem

paper_content:

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.
---
paper_title: A smoothing method for second order cone complementarity problem

paper_content:

In this paper, the second order cone complementarity problem is studied. Based on a perturbed symmetrically smoothing function, which has coerciveness under proper conditions, we present a smoothing Newton method for this problem. The boundedness of the level set can be obtained from the coerciveness, which plays an important role in the convergence analysis. Furthermore, the proposed algorithm for the reformulation has no restrictions on the starting point and solves only one system of equations. Preliminary numerical results indicate that the algorithm is effective.
---
paper_title: Log-Sigmoid nonlinear Lagrange method for nonlinear optimization problems over second-order cones

paper_content:

This paper analyzes the rate of local convergence of the Log-Sigmoid nonlinear Lagrange method for nonconvex nonlinear second-order cone programming. Under the componentwise strict complementarity condition, the constraint nondegeneracy condition and the second-order sufficient condition, we show that the sequence of iteration points generated by the proposed method locally converges to a local solution when the penalty parameter is less than a threshold and the error bound of solution is proportional to the penalty parameter. Finally, we report numerical results to show the efficiency of the method.
---
paper_title: A globally convergent method based on Fischer-Burmeister operators for solving second-order cone constrained variational inequality problems

paper_content:

The Karush-Kuhn-Tucker system of a second-order cone constrained variational inequality problem is transformed into a semismooth system of equations with the help of Fischer-Burmeister operators over second-order cones. The Clarke generalized differential of the semismooth mapping is presented. A modified Newton method with Armijo line search is proved to have global convergence with local superlinear rate of convergence under certain assumptions on the variational inequality problem. An illustrative example is given to show how the globally convergent method works.
---
paper_title: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions

paper_content:

We show that the Fischer-Burmeister complementarity functions, associated to the semidefinite cone (SDC) and the second order cone (SOC), respectively, are strongly semismooth everywhere. Interestingly enough, the proof relys on a relationship between the singular value decomposition of a nonsymmetric matrix and the spectral decomposition of a symmetric matrix.
---
paper_title: A descent method for a reformulation of the second-order cone complementarity problem

paper_content:

Analogous to the nonlinear complementarity problem and the semi-definite complementarity problem, a popular approach to solving the second-order cone complementarity problem (SOCCP) is to reformulate it as an unconstrained minimization of a certain merit function over R^n. In this paper, we present a descent method for solving the unconstrained minimization reformulation of the SOCCP which is based on the Fischer-Burmeister merit function (FBMF) associated with second-order cone [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293-327], and prove its global convergence. Particularly, we compare the numerical performance of the method for the symmetric affine SOCCP generated randomly with the FBMF approach [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293-327]. The comparison results indicate that, if a scaling strategy is imposed on the test problem, the descent method proposed is comparable with the merit function approach in the CPU time for solving test problems although the former may require more function evaluations.
---
paper_title: On a Homogeneous Algorithm for the Monotone Complementarity Problem

paper_content:

We present a generalization of a homogeneous self-dual linear programming (LP) algorithm to solving the monotone complementarity problem (MCP). The algorithm does not need to use any "big-M" parameter or two-phase method, and it generates either a solution converging towards feasibility and comple- mentarity simultaneously or a certificate proving infeasibility. Moreover, if the MCP is polynomially solvable with an interior feasible starting point, then it can be polynomially solved without using or knowing such information at all. To our knowledge, this is the first interior-point and infeasible-starting algorithm for solving the MCP that possesses these desired features. Preliminary computational results are presented.
---
paper_title: Sufficiency of linear transformations on Euclidean Jordan algebras

paper_content:

We extend the row-sufficiency and column-sufficiency of a linear transformation from \({\mathbb {R}^n}\) to the setting of Euclidean Jordan algebras. For linear complementarity problems over symmetric cones, we show that the column-sufficiency along with Cross Commutative property is equivalent to the convexity of the solution set, while the row-sufficiency is necessary for the existence of solutions under some conditions.
---
paper_title: Strict Semimonotonicity Property of Linear Transformations on Euclidean Jordan Algebras

paper_content:

Motivated by the equivalence of the strict semimonotonicity property of the matrix A and the uniqueness of the solution to the linear complementarity problem LCP(A,q) for q∈R+n, we study the strict semimonotonicity (SSM) property of linear transformations on Euclidean Jordan algebras. Specifically, we show that, under the copositive condition, the SSM property is equivalent to the uniqueness of the solution to LCP(L,q) for all q in the symmetric cone K. We give a characterization of the uniqueness of the solution to LCP(L,q) for a Z transformation on the Lorentz cone ℒ+n. We study also a matrix-induced transformation on the Lorentz space ℒn.
---

Title: JAPAN Complementarity Problems over Symmetric Cones: A Survey of Recent Developments in Several Aspects

Section 1: Introduction
Description 1: This section provides an overview of the complementarity problem over a symmetric cone, known as the Symmetric Cone Complementarity Problem (SCCP), and introduces the content and structure of the paper.

Section 2: Euclidean Jordan algebra
Description 2: This section gives a brief introduction to Euclidean Jordan algebras, including definitions and fundamental properties, as essential background information for understanding symmetric cones.

Section 3: Interior-point methods for the SCCP
Description 3: This section surveys recent developments in interior-point algorithms for solving the SCCP, including their complexity, theoretical results, and extensions from semidefinite optimization problems.

Section 4: Interior point map and its properties
Description 4: This section focuses on the properties of the interior point map associated with the SCCP and discusses results related to feasibility and homeomorphism.

Section 5: Algorithms and their convergence properties
Description 5: This section outlines various interior-point algorithms for the SCCP, including infeasible interior point algorithms, homogeneous algorithms, and combined algorithms, emphasizing their convergence properties.

Section 6: Local convergence properties
Description 6: This section discusses studies on the local convergence properties of interior point algorithms for the SCCP, highlighting conditions necessary for superlinear or quadratic convergence.

Section 7: Merit or smoothing function methods for the SCCP
Description 7: This section reviews the class of merit or smoothing function methods, which reformulate the SCCP into minimization problems or use smoothing functions to enable Newton-type methods.

Section 8: Merit or smoothing function methods for the SDCP
Description 8: This section provides a chronological overview of research on merit functions for the Semidefinite Complementarity Problem (SDCP), a special case of the SCCP.

Section 9: Merit or smoothing function methods for the SOCCP
Description 9: This section documents research on smoothing functions for the Second Order Cone Complementarity Problem (SOCCP).

Section 10: Properties of the SCCP
Description 10: This section explores various properties of the SCCP, such as P-properties, relaxation transformations, and sufficiency conditions, and discusses their significance in determining the solution sets of SCCPs.