Search

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

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

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 .

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.

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.

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

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.

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.