Search

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian matrix of the loss function, we establish an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, we establish its KL property of exponent 1/2 on the global optimal solution set under the noisy and full sample setting, and achieve this property at its certain class of critical points under the noisy and partial sample setting. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

This paper is concerned with second-order optimality conditions for the mathematical program with semidefinite cone complementarity constraints. To achieve this goal, we first provide an exact characterization on the second-order tangent set to the semidefinite cone complementarity set in terms of the second-order directional derivative of the projection operator onto the semidefinite cone complementarity set, and then use the second-order tangent set to the semidefinite cone complementarity set to derive second-order necessary and sufficient conditions for the mathematical program with semidefinite cone complementarity constraints under suitable subregularity constraint qualifications. The obtained second-order necessary optimality condition is also illustrated via the mathematical program with semidefinite cone complementarity constraints reformulation of semidefinite rank regularized problem.

This paper focuses on a class of zero-norm composite optimization problems. For this class of nonconvex nonsmooth problems, we establish the Kurdyka–Łojasiewicz property of exponent being a half for its objective function under a suitable assumption and provide some examples to illustrate that such an assumption is not very restricted which, in particular, involve the zero-norm regularized or constrained piecewise linear–quadratic function, the zero-norm regularized or constrained logistic regression function, the zero-norm regularized or constrained quadratic function over a sphere.

We derive some conditions for a feasible point to be the isolated optimal solution for three classes of nuclear norm optimization problems by using the isolated calmness of two set-valued mappings:...

For the rank regularized minimization problem, we introduce several classes of stationary points by the problem itself and its equivalent reformulations including the mathematical program with an e...

This paper is concerned with a class of optimization problems with the nonnegative orthogonal constraint, in which the objective function is $L$-smooth on an open set containing the Stiefel manifold ${\rm St}(n,r)$. We derive a locally Lipschitzian error bound for the feasible points without zero rows when $n>r>1$, and when $n>r=1$ or $n=r$ achieve a global Lipschitzian error bound. Then, we show that the penalty problem induced by the elementwise $\ell_1$-norm distance to the nonnegative cone is a global exact penalty, and so is the one induced by its Moreau envelope under a lower second-order calmness of the objective function. A practical penalty algorithm is developed by solving approximately a series of smooth penalty problems with a retraction-based nonmonotone line-search proximal gradient method, and any cluster point of the generated sequence is shown to be a stationary point of the original problem. Numerical comparisons with the ALM \citep{Wen13} and the exact penalty method \citep{JiangM22} indicate that our penalty method has an advantage in terms of the quality of solutions despite taking a little more time., 34 pages, and 6 figures

This paper is concerned with the strong calmness of the KKT solution mapping for a class of canonically perturbed conic programming, which plays a central role in achieving fast convergence under situations when the Lagrange multiplier associated to a solution of these conic optimization problems is not unique. We show that the strong calmness of the KKT solution mapping is equivalent to a local error bound for solutions of perturbed KKT system, and is also equivalent to the pseudo-isolated calmness of the stationary point mapping along with the calmness of the multiplier set map at the corresponding reference point. Sufficient conditions are also provided for the strong calmness by establishing the pseudo-isolated calmness of the stationary point mapping in terms of the noncriticality of the associated multiplier, and the calmness of the multiplier set mapping in terms of a relative interior condition for the multiplier set. These results cover and extend the existing ones in \cite{Hager99,Izmailov12} for nonlinear programming and in \cite{Cui16,Zhang17} for semidefinite programming., 21 pages

This paper focuses on the characterization for the regular and limiting normal cones to the graph of the subdifferential mapping of the nuclear norm, which is essential to derive optimality conditions for the equivalent MPEC (mathematical program with equilibrium constraints) reformulation of rank minimization problems.

This paper concerns itself with the rank regularized minimization problem with a spectral norm ball constraint. We reformulate this NP-hard problem as an equivalent MPGCC (mathematical program with a generalized complementarity constraint) and show that the penalty problem, yielded by moving the generalized complementarity constraint to the objective, is exact in the sense that it has the same global optimal solution set as the MPGCC does when the penalty parameter is over a threshold. Then, by solving the exact penalty problem in an alternating way, we propose a multistage convex relaxation approach, and provide its theoretical guarantee for the rank regularized least squares problem with a spectral norm ball constraint. Specifically, we derive the error and approximate rank bounds for the optimal solution of each stage and quantify the reduction of the error and approximate rank bounds of the first stage convex relaxation (which is exactly the nuclear norm relaxation) in the subsequent stages. In partic...

Wasserstein barycenter is the centroid of a collection of discrete probability distributions which minimizes the average of the $$\ell _2$$ -Wasserstein distance. This paper focuses on the computation of Wasserstein barycenters under the case where the support points are free, which is known to be a severe bottleneck in the D2-clustering due to the large scale and nonconvexity. We develop an inexact proximal alternating minimization (iPAM) method for computing an approximate Wasserstein barycenter, and provide its global convergence analysis. This method can achieve a good accuracy with a reduced computational cost when the unknown support points of the barycenter have low cardinality. Numerical comparisons with the 3-block B-ADMM in Ye et al. (IEEE Trans Signal Process 65:2317–2332, 2017) and an alternating minimization method involving the LP subproblems on synthetic and real data show that the proposed iPAM can yield comparable even a little better objective values in less CPU time, and hence, the computed barycenter will render a better role in the D2-clustering.

This paper is concerned with high-dimensional error-in-variables regression that aims at identifying a small number of important interpretable factors for corrupted data from many applications where measurement errors or missing data can not be ignored. Motivated by CoCoLasso due to Datta and Zou \cite{Datta16} and the advantage of the zero-norm regularized LS estimator over Lasso for clean data, we propose a calibrated zero-norm regularized LS (CaZnRLS) estimator by constructing a calibrated least squares loss with a positive definite projection of an unbiased surrogate for the covariance matrix of covariates, and use the multi-stage convex relaxation approach to compute the CaZnRLS estimator. Under a restricted eigenvalue condition on the true matrix of covariates, we derive the $\ell_2$-error bound of every iterate and establish the decreasing of the error bound sequence, and the sign consistency of the iterates after finite steps. The statistical guarantees are also provided for the CaZnRLS estimator under two types of measurement errors. Numerical comparisons with CoCoLasso and NCL (the nonconvex Lasso proposed by Poh and Wainwright \cite{Loh11}) demonstrate that CaZnRLS not only has the comparable or even better relative RSME but also has the least number of incorrect predictors identified.

This paper proposes a mechanism to produce equivalent Lipschitz surrogates for zero-norm and rank optimization problems by means of the global exact penalty for their equivalent mathematical programs with an equilibrium constraint (MPECs). Specifically, we reformulate these combinatorial problems as equivalent MPECs by the variational characterization of the zero-norm and rank function, show that their penalized problems, yielded by moving the equilibrium constraint into the objective, are the global exact penalization, and obtain the equivalent Lipschitz surrogates by eliminating the dual variable in the global exact penalty. These surrogates, including the popular SCAD function in statistics, are also difference of two convex functions (D.C.) if the function and constraint set involved in zero-norm and rank optimization problems are convex. We illustrate an application by designing a multi-stage convex relaxation approach to the rank plus zero-norm regularized minimization problem.

This paper is concerned with the least squares loss constrained low-rank plus sparsity optimization problems that seek a low-rank matrix and a sparse matrix by minimizing a positive combination of the rank function and the zero norm over a least squares constraint set describing the observation or prior information on the target matrix pair. For this class of NP-hard optimization problems, we propose a two-stage convex relaxation approach by the majorization for suitable locally Lipschitz continuous surrogates, which have a remarkable advantage in reducing the error yielded by the popular nuclear norm plus $$\ell _1$$l1-norm convex relaxation method. Also, under a suitable restricted eigenvalue condition, we establish a Frobenius norm error bound for the optimal solution of each stage and show that the error bound of the first stage convex relaxation (i.e. the nuclear norm plus $$\ell _1$$l1-norm convex relaxation), can be reduced much by the second stage convex relaxation, thereby providing the theoretical guarantee for the two-stage convex relaxation approach. We also verify the efficiency of the proposed approach by applying it to some random test problems and some problems with real data arising from specularity removal from face images, and foreground/background separation from surveillance videos.

This paper concerns with the graphical derivative of the normals to the conic constraint $g(x)\in\!K$, where $g\!:\mathbb{X}\to\mathbb{Y}$ is a twice continuously differentiable mapping and $K\subseteq\mathbb{Y}$ is a nonempty closed convex set assumed to be $C^2$-cone reducible. Such a generalized derivative plays a crucial role in characterizing isolated calmness of the solution maps to generalized equations whose multivalued parts are modeled via the normals to the nonconvex set $\Gamma=g^{-1}(K)$. The main contribution of this paper is to provide an exact characterization for the graphical derivative of the normals to this class of nonconvex conic constraints under an assumption without requiring the nondegeneracy of the reference point as the papers \cite{Gfrerer17,Mordu15,Mordu151} do., Comment: 28pages

This paper concerns with a noisy structured low-rank matrix recovery problem which can be modeled as a structured rank minimization problem. We reformulate this problem as a mathematical program with a generalized complementarity constraint (MPGCC), and show that its penalty version, yielded by moving the generalized complementarity constraint to the objective, has the same global optimal solution set as the MPGCC does whenever the penalty parameter is over a threshold. Then, by solving the exact penalty problem in an alternating way, we obtain a multi-stage convex relaxation approach. We provide theoretical guarantees for our approach under a mild restricted eigenvalue condition, by quantifying the reduction of the error and approximate rank bounds of the first stage convex relaxation (which is exactly the nuclear norm relaxation) in the subsequent stages and establishing the geometric convergence of the error sequence in a statistical sense. Numerical experiments are conducted for some structured low-rank matrix recovery examples to confirm our theoretical findings., Comment: 29 pages, 2 figures

We reformulate the zero-norm minimization problem as an equivalent mathematical program with equilibrium constraints and establish that its penalty problem, induced by adding the complementarity constraint to the objective, is exact. Then, by the special structure of the exact penalty problem, we propose a decomposition method that can seek a global optimal solution of the zero-norm minimization problem under the null space condition in [M. A. Khajehnejad et al. IEEE Trans. Signal. Process., 59(2011), pp. 1985-2001] by solving a finite number of weighted $l_1$-norm minimization problems. To handle the weighted $l_1$-norm subproblems, we develop a partial proximal point algorithm where the subproblems may be solved approximately with the limited memory BFGS (L-BFGS) or the semismooth Newton-CG. Finally, we apply the exact penalty decomposition method with the weighted $l_1$-norm subproblems solved by combining the L-BFGS with the semismooth Newton-CG to several types of sparse optimization problems, and compare its performance with that of the penalty decomposition method [Z. Lu and Y. Zhang, SIAM J. Optim., 23(2013), pp. 2448- 2478], the iterative support detection method [Y. L. Wang and W. T. Yin, SIAM J. Sci. Comput., 3(2010), pp. 462-491] and the state-of-the-art code FPC_AS [Z. W. Wen et al. SIAM J. Sci. Comput., 32(2010), pp. 1832-1857]. Numerical comparisons indicate that the proposed method is very efficient in terms of the recoverability and the required computing time.

It has been an open question whether the family of merit functions ψ p ( p > 1 ) \psi _p\ (p>1) , the generalized Fischer-Burmeister (FB) merit function, associated to the second-order cone is smooth or not. In this paper we answer it partly, and show that ψ p \psi _p is smooth for p ∈ ( 1 , 4 ) p\in (1,4) , and we provide the condition for its coerciveness. Numerical results are reported to illustrate the influence of p p on the performance of the merit function method based on ψ p \psi _p .

This paper is concerned with the rank constrained optimization problem whose feasible set is the intersection of the rank constraint set $\mathcal{R}=\!\big\{X\in\mathbb{X}\ |\ {\rm rank}(X)\le \kappa\big\}$ and a closed convex set $\Omega$. We establish the local (global) Lipschitzian type error bounds for estimating the distance from any $X\in \Omega$ ($X\in\mathbb{X}$) to the feasible set and the solution set, respectively, under the calmness of a multifunction associated to the feasible set at the origin, which is specially satisfied by three classes of common rank constrained optimization problems. As an application of the local Lipschitzian type error bounds, we show that the penalty problem yielded by moving the rank constraint into the objective is exact in the sense that its global optimal solution set coincides with that of the original problem when the penalty parameter is over a certain threshold. This particularly offers an affirmative answer to the open question whether the penalty problem (32) in (Gao and Sun, 2010) is exact or not. As another application, we derive the error bounds of the iterates generated by a multi-stage convex relaxation approach to those three classes of rank constrained problems and show that the bounds are nonincreasing as the number of stages increases.

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641---1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.

For a locally optimal solution to the nonlinear semidefinite programming problem, under Robinson's constraint qualification, we show that the nonsingularity of Clarke's Jacobian of the Fischer-Burmeister (FB) nonsmooth system is equivalent to the strong regularity of the Karush-Kuhn-Tucker point. Consequently, from Sun's paper [Math. Oper. Res., 31 (2006), pp. 761-776] the semismooth Newton method applied to the FB system may attain the locally quadratic convergence under the strong second order sufficient condition and constraint nondegeneracy.

We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer–Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function ψFB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293–327), which confirm the theoretical results and the effectiveness of the algorithm.

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.

In this article, we show that a one-parametric class of SOC merit functions has a Lipschitz continuous gradient; and moreover, the Lipschitz constant is related to the parameter in this class of SOC merit functions. This fact will lay a building block when the merit function approach as well as the Newton-type method are employed for solving the second-order cone complementarity problem with this class of merit functions.

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 this paper, we study the properties of the penalized Fischer-Burmeister (FB) second-order cone (SOC) complementarity function. We show that the function possesses similar desirable properties of the FB SOC complementarity function for local convergence; for example, with the function the second-order cone complementarity problem (SOCCP) can be reformulated as a (strongly) semismooth system of equations, and the corresponding nonsmooth Newton method has local quadratic convergence without strict complementarity of solutions. In addition, the penalized FB merit function has bounded level sets under a rather weak condition which can be satisfied by strictly feasible monotone SOCCPs or SOCCPs with the Cartesian R 01-property, although it is not continuously differentiable. Numerical results are included to illustrate the theoretical considerations.

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.

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).

We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:1---19, 1993) holds.

We provide some characterizations for SOC-monotone and SOC-convex functions by using differential analysis. From these characterizations, we particularly obtain that a continuously differentiable function defined in an open interval is SOC-monotone (SOC-convex) of order n ? 3 if and only if it is 2-matrix monotone (matrix convex), and furthermore, such a function is also SOC-monotone (SOC-convex) of order n ? 2 if it is 2-matrix monotone (matrix convex). In addition, we also prove that Conjecture 4.2 proposed in Chen (Optimization 55:363---385, 2006) does not hold in general. Some examples are included to illustrate that these characterizations open convenient ways to verify the SOC-monotonicity and the SOC-convexity of a continuously differentiable function defined on an open interval, which are often involved in the solution methods of the convex second-order cone optimization.

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.

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.

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.

Consider the problem of minimizing the sum of p-norms, where p is a fixed real number in the interval [1,2]. This nondifferentiable problem arises in many applications, including the VLSI (very-large-scale-integration) layout problem, the facilities location problem and the Steiner minimum tree problem under a given topology. In this paper, we establish the optimality conditions, duality and uniqueness results for the problem. We then present a smoothing Newton method by the semismooth equations which are derived from the optimality conditions. The method is globally and superlinearly convergent, and moreover, it is quadratically convergent when p∈[1,3/2]∪{2}. Particularly, the quadratic convergence is proved for the case wherep∈(1,3/2]∪{2} without requiring strict complementarity. Preliminary numerical results are reported, which indicate that the method proposed is extremely promising.

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ℝ++. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538–543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem.

In this paper, we present a detailed investigation for the properties of a one-parametric class of SOC complementarity functions, which include the globally Lipschitz continuity, strong semismoothness, and the characterization of their B-subdifferential. Moreover, for the merit functions induced by them for the second-order cone complementarity problem (SOCCP), we provide a condition for each stationary point to be a solution of the SOCCP and establish the boundedness of their level sets, by exploiting Cartesian P-properties. We also propose a semismooth Newton type method based on the reformulation of the nonsmooth system of equations involving the class of SOC complementarity functions. The global and superlinear convergence results are obtained, and among others, the superlinear convergence is established under strict complementarity. Preliminary numerical results are reported for DIMACS second-order cone programs, which confirm the favorable theoretical properties of the method.

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately.

In last decades, there has been much effort on the solution and the analysis of the nonlinear complementarity problem (NCP) by reformulating NCP as an unconstrained minimization involving an NCP function. In this paper, we propose a family of new NCP functions, which include the Fischer-Burmeister function as a special case, based on a p-norm with p being any fixed real number in the interval (1,+?), and show several favorable properties of the proposed functions. In addition, we also propose a descent algorithm that is indeed derivative-free for solving the unconstrained minimization based on the merit functions from the proposed NCP functions. Numerical results for the test problems from MCPLIB indicate that the descent algorithm has better performance when the parameter p decreases in (1,+?). This implies that the merit functions associated with p?(1,2), for example p=1.5, are more effective in numerical computations than the Fischer-Burmeister merit function, which exactly corresponds to p=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.

We consider two classes of proximal-like algorithms for minimizing a proper lower semicontinuous quasi-convex function f(x) subject to non-negative constraints $$x \geq 0$$ . The algorithms are based on an entropy-like second-order homogeneous distance function. Under the assumption that the global minimizer set is nonempty and bounded, we prove the full convergence of the sequence generated by the algorithms, and furthermore, obtain two important convergence results through imposing certain conditions on the proximal parameters. One is that the sequence generated will converge to a stationary point if the proximal parameters are bounded and the problem is continuously differentiable, and the other is that the sequence generated will converge to a solution of the problem if the proximal parameters approach to zero. Numerical experiments are done for a class of quasi-convex optimization problems where the function f(x) is a composition of a quadratic convex function from $${\mathbb{R}}^ n$$ to $$\mathbb{R}$$ and a continuously differentiable increasing function from $${\mathbb{R}}$$ to $${\mathbb{R}}$$ , and computational results indicate that these algorithms are very promising in finding a global optimal solution to these quasi-convex problems.