Search

We make a unified analysis of interior proximal methods of solving convex second-order cone programming problems. These methods use a proximal distance with respect to second-order cones which can be produced with an appropriate closed proper univariate function in three ways. Under some mild conditions, the sequence generated is bounded with each limit point being a solution, and global rates of convergence estimates are obtained in terms of objective values. A class of regularized proximal distances is also constructed which can guarantee the global convergence of the sequence to an optimal solution. These results are illustrated with some examples. In addition, we also study the central paths associated with these distance-like functions, and for the linear SOCP we discuss their relations with the sequence generated by the interior proximal methods. From this, we obtain improved convergence results for the sequence for the interior proximal methods using a proximal distance continuous at the boundary of second-order cones.

For the symmetric cone complementarity problem, we show that each stationary point of the unconstrained minimization reformulation based on the Fischer-Burmeister merit function is a solution to the problem, provided that the gradient operators of the mappings involved in the problem satisfy column monotonicity or have the Cartesian P"0-property. These results answer the open question proposed in the article that appeared in Journal of Mathematical Analysis and Applications 355 (2009) 195-215.

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.

Recently there have two different effective methods proposed by Kanzow et al. in (Kanzow, 2001 [8]) and (Kanzow and Petra, 2004 [9]), respectively, which commonly use the Fischer–Burmeister (FB) function to recast the mixed complementarity problem (MCP) as a constrained minimization problem and a nonlinear system of equations, respectively. They all remark that their algorithms may be improved if the FB function is replaced by other NCP functions. Accordingly, in this paper, we employ the generalized Fischer–Burmeister (GFB) where the 2-norm in the FB function is relaxed to a general p-norm (p>1) for the two methods and investigate how much the improvement is by changing the parameter p as well as which method is influenced more when we do so, by the performance profiles of iterations and function evaluations for the two methods with different p on MCPLIB collection.

We present a smooth approximation for the generalized Fischer–Burmeister function where the 2-norm in the FB function is relaxed to a general p -norm ( p > 1 ), and establish some favorable properties for it — for example, the Jacobian consistency. With the smoothing function, we transform the mixed complementarity problem (MCP) into solving a sequence of smooth system of equations, and then trace a smooth path generated by the smoothing algorithm proposed by Chen (2000) [28] to the solution set. In particular, we investigate the influence of p on the numerical performance of the algorithm by solving all MCPLIP test problems, and conclude that the smoothing algorithm with p ∈ ( 1 , 2 ] has better numerical performance than the one with p > 2 .

In this paper, we consider a neural network model for solving the nonlinear complementarity problem (NCP). The neural network is derived from an equivalent unconstrained minimization reformulation of the NCP, which is based on the generalized Fischer-Burmeister function @f"p(a,b)[email protected]?(a,b)@?"p-(a+b). We establish the existence and the convergence of the trajectory of the neural network, and study its Lyapunov stability, asymptotic stability as well as exponential stability. It was found that a larger p leads to a better convergence rate of the trajectory. Numerical simulations verify the obtained theoretical results.

In this paper, we consider the problem of minimizing a sum of Tchebycheff norms @F(x)=@?"i"="1^m@?b"i-A"i^Tx@?"~, where A"i@?R^n^x^d and b"i@?R^d. We derive a smooth approximation of @F(x) by the entropy regularization technique, and convert the problem into a parametric family of strictly convex minimization. It turns out that the minimizers of these problems generate a trajectory that will go to the primal-dual solution set of the original problem as the parameter tends to zero. By this, we propose a smoothing algorithm to compute an @e-optimal primal-dual solution pair. The algorithm is globally convergent and has a quadratic rate of convergence. Numerical results are reported for a path-following version of the algorithm and made comparisons with those yielded by the primal-dual path-following interior point algorithm, which indicate that the proposed algorithm can yield the solutions with favorable accuracy and is comparable with the interior point method in terms of CPU time for those problems with m@?max{n,d}.

In the paper [J.-S. Chen, S. Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40 (2008) 389-404], the authors proposed a derivative-free descent algorithm for nonlinear complementarity problems (NCPs) by the generalized Fischer-Burmeister merit function: @j"p(a,b)=12[@?(a,b)@?"p-(a+b)]^2, and observed that the choice of the parameter p has a great influence on the numerical performance of the algorithm. In this paper, we analyze the phenomenon theoretically for a derivative-free descent algorithm which is based on a penalized form of @j"p and uses a different direction from that of Chen and Pan. More specifically, we show that the algorithm proposed is globally convergent and has a locally R-linear convergence rate, and furthermore, its convergence rate will become worse when the parameter p decreases. Numerical results are also reported for the test problems from MCPLIB, which further verify the theoretical results obtained.

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.

We consider the Tikhonov regularization method for the second-order cone complementarity problem (SOCCP) with the Cartesian P 0 -property. We show that many results of the regularization method for the P 0 -nonlinear complementarity problem still hold for this important class of nonmonotone SOCCP. For example, under the more general setting, every regularized problem has the unique solution, and the solution trajectory generated is bounded if the original SOCCP has a nonempty and bounded solution set. We also propose an inexact regularization algorithm by solving the sequence of regularized problems approximately with the merit function approach based on Fischer–Burmeister merit function, and establish the convergence result of the algorithm. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed method.

We consider a regularization method for nonlinear complementarity problems with F being a P"0-function which replaces the original problem with a sequence of the regularized complementarity problems. In this paper, this sequence of regularized complementarity problems are solved approximately by applying the generalized Newton method for an equivalent augmented system of equations, constructed by the generalized Fischer-Burmeister (FB) NCP-functions @f"p with p>1. We test the performance of the regularization semismooth Newton method based on the family of NCP-functions through solving all test problems from MCPLIB. Numerical experiments indicate that the method associated with a smaller p, for example [email protected]?[1.1,2], usually has better numerical performance, and the generalized FB functions @f"p with [email protected]?[1.1,2) can be used as the substitutions for the FB function @f"2.

Consider the single-facility Euclidean κ -centrum location problem in R n . This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the Fischer–Burmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to solve problems of dimension n up to 10,000 efficiently.

In this paper, we analyze the effect of making algebraically equivalent transformations for the standard centering equation X s = μ e , and specifically consider two cases: power transformation and logarithmic transformation. Especially, for the last case, an infeasible long-step primal–dual path following interior point algorithm is developed, and its global convergence analysis and polynomial-time complexity bound are also given.

Consider the problem of computing the smallest enclosing ball of a set of m balls in R n . This problem arises in many applications such as location analysis, military operations, and pattern recognition, etc. In this paper, we reformulate this problem as an unconstrained convex optimization problem involving the maximum function max{0, t}, and then develop a simple algorithm particularly suitable for problems in high dimensions. This algorithm could efficiently handle problems of dimension n up to 10,000 under a moderately large m, as well as problems of dimension m up to 10,000 under a moderately large n. Numerical results are given to show the efficiency of algorithm.

In this paper we consider the single-facility Euclidean r-centrum location problem in R^n, which generalizes and unifies the classical 1-center and 1-median problem. Specifically, we reformulate this problem as a nonsmooth optimization problem only involving the maximum function, and then develop a smoothing algorithm that is shown to be globally convergent. The method transforms the original nonsmooth problem with certain combinatorial property into the solution of a deterministic smooth unconstrained optimization problem. Numerical results are presented for some problems generated randomly, indicating that the algorithm proposed here is extremely efficient for large problems.

Based on the min-max principle, the standard centering equation in the interior point method is replaced by the optimality condition of a new proximity measure function. Thus, a self-adjusting mechanism is constructed in the new perturbed system. The Newton direction can be adjusted self-adaptively according to the information of last iterates. A self-adjusting interior point method is given based on the new perturbed system. Numerical comparison is made between this algorithm and a primal-dual interior point algorithm using “standard” perturbed system. Results demonstrate the efficiency and some advantages of the proposed algorithm.

This paper proposes a new regularization approach, referred to as the Lagrangian regularization approach, which aims to circumvent the nondifferentiability of a positively homogeneous function δ ( · | R - m ) in a conceptual unconstrained reformulation for constrained optimization problems. With the appropriate choices of regularizing function, we obtain a family of smooth functions that include, as special cases, the existing penalty and barrier functions. As such, our approach can be used as an instrumental tool to resolve the nondifferentiability of δ ( · | R - m ) as well as a unified way to construct penalty functions. For convex programming cases, we present its global convergence analysis.