Abstract: Abstract In this paper, we develop an active set identification technique for the \(\ell _0\) regularization optimization. Such a technique has a strong ability to identify the zero components in a neighbourhood of a strict L-stationary point. Based on the identification technique, we propose an active set Barzilar–Borwein algorithm and prove that any limit point of the sequence generated by the algorithm is a strong stationary point. Some preliminary numerical results are provided, showing that the method is promising. PubDate: 2020-04-01

Abstract: Abstract In this paper, a class of smoothing penalty functions is proposed for optimization problems with equality, inequality and bound constraints. It is proved exact, under the condition of weakly generalized Mangasarian–Fromovitz constraint qualification, in the sense that each local optimizer of the penalty function corresponds to a local optimizer of the original problem. Furthermore, necessary and sufficient conditions are discussed for the inverse proposition of exact penalization. Based on the theoretical results in this paper, a class of smoothing penalty algorithms with feasibility verification is presented. Theories on the penalty exactness, feasibility verification and global convergence of the proposed algorithm are presented. Numerical results show that this algorithm is effective for nonsmooth nonconvex constrained optimization problems. PubDate: 2020-04-01

Abstract: Abstract In order to cluster the textual data with high dimension in modern data analysis, the spherical k-means clustering is presented. It aims to partition the given points with unit length into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In this paper, we mainly study seeding algorithms for spherical k-means clustering, for its special case (with separable sets), as well as for its generalized problem (\(\alpha \)-spherical k-means clustering). About the spherical k-means clustering with separable sets, an approximate algorithm with a constant factor is presented. Moreover, it can be generalized to the \(\alpha \)-spherical separable k-means clustering. By slickly constructing a useful function, we also show that the famous seeding algorithms such as k-means++ and k-means for k-means problem can be applied directly to solve the \(\alpha \)-spherical k-means clustering. Except for theoretical analysis, the numerical experiment is also included. PubDate: 2020-04-01

Abstract: Abstract In this paper we study a broad class of nonconvex and nonsmooth minimization problems, whose objective function is the sum of a smooth function of the entire variables and two nonsmooth functions of each variable. We adopt the framework of the proximal alternating linearized minimization (PALM), together with the inertial strategy to accelerate the convergence. Since the inertial step is performed once the x-subproblem/y-subproblem is updated, the algorithm is a Gauss–Seidel type inertial proximal alternating linearized minimization (GiPALM) algorithm. Under the assumption that the underlying functions satisfy the Kurdyka–Łojasiewicz (KL) property and some suitable conditions on the parameters, we prove that each bounded sequence generated by GiPALM globally converges to a critical point. We apply the algorithm to signal recovery, image denoising and nonnegative matrix factorization models, and compare it with PALM and the inertial proximal alternating linearized minimization. PubDate: 2020-04-01

Abstract: Abstract In this paper, we propose an accelerated iterative hard thresholding algorithm for solving the \(l_0\) regularized box constrained regression problem. We substantiate that there exists a threshold, if the extrapolation coefficients are chosen below this threshold, the proposed algorithm is equivalent to the accelerated proximal gradient algorithm for solving a corresponding constrained convex problem after finite iterations. Under some proper conditions, we get that the sequence generated by the proposed algorithm is convergent to a local minimizer of the \(l_0\) regularized problem, which satisfies a desired lower bound. Moreover, when the data fitting function satisfies the error bound condition, we prove that both the iterate sequence and the corresponding sequence of objective function values are R-linearly convergent. Finally, we use several numerical experiments to verify our theoretical results. PubDate: 2020-04-01

Abstract: Abstract The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm. PubDate: 2020-04-01

Abstract: Abstract Unitary symmetric eigenvalues (US-eigenvalues) of symmetric complex tensors and unitary eigenvalues (U-eigenvalues) for non-symmetric complex tensors are very important because of their background of quantum entanglement. US-eigenvalue is a generalization of Z-eigenvalue from the real case to the complex case, which is closely related to the best complex rank-one approximations to higher-order tensors. The problem of finding US-eigenpairs can be converted to an unconstrained nonlinear optimization problem with complex variables, their complex conjugate variables and real variables. However, optimization methods often need a first- or second-order derivative of the objective function, and cannot be applied to real valued functions of complex variables because they are not necessarily analytic in their argument. In this paper, we first establish the first-order complex Taylor series and Wirtinger calculus of complex gradient of real-valued functions with complex variables, their complex conjugate variables and real variables. Based on this theory, we propose a norm descent cautious BFGS method for computing US-eigenpairs of a symmetric complex tensor. Under appropriate conditions, global convergence and superlinear convergence of the proposed method are established. As an application, we give a method to compute U-eigenpairs for a non-symmetric complex tensor by finding the US-eigenpairs of its symmetric embedding. The numerical examples are presented to support the theoretical findings. PubDate: 2020-04-01

Abstract: Abstract Multi-source Weber problem (MSWP) is a classical nonconvex and NP-hard model in facility location. A well-known method for solving MSWP is the location–allocation algorithm which consists of a location phase to locate new facilities and an allocation phase to allocate customers at each iteration. This paper considers the more general and practical case of MSWP called the constrained multi-source Weber problem (CMSWP), i.e., locating multiple facilities with the consideration of the gauge for measuring distances and locational constraints on new facilities. According to the favorable structure of the involved location subproblems after reformulation, an alternating direction method of multipliers (ADMM) type method is contributed to solving these subproblems under different distance measures in a uniform framework. Then a new ADMM-based location–allocation algorithm is presented for CMSWP and its local convergence is theoretically proved. Some preliminary numerical results are reported to verify the effectiveness of proposed methods. PubDate: 2020-04-01

Abstract: Abstract This paper considers a generalization of the “max-cut-polytope” \(\hbox {conv}\{\ xx^T\mid x\in {\mathbb {R}}^n, \ \ x_k = 1 \ \hbox {for} \ 1\le k\le n\}\) in the space of real symmetric \(n\times n\)-matrices with all-one diagonal to a complex “unit modulus lifting” \(\hbox {conv}\{xx^*\mid x\in {\mathbb {C}}^n, \ \ x_k = 1 \ \hbox {for} \ 1\le k\le n\}\) in the space of complex Hermitian \(n\times n\)-matrices with all-one diagonal. The unit modulus lifting arises in applications such as digital communications and shares similar symmetry properties as the max-cut-polytope. Set-completely positive representations of both sets are derived and the relation of the complex unit modulus lifting to its semidefinite relaxation is investigated in dimensions 3 and 4. It is shown that the unit modulus lifting coincides with its semidefinite relaxation in dimension 3 but not in dimension 4. In dimension 4 a family of deep valid cuts for the unit modulus lifting is derived that could be used to strengthen the semidefinite relaxation. It turns out that the deep cuts are also implied by a second lifting that could be used alternatively. Numerical experiments are presented comparing the first lifting, the second lifting, and the unit modulus lifting for \(n=4\). PubDate: 2020-04-01

Abstract: Abstract Spherically constrained optimization, which minimizes an objective function on a unit sphere, has wide applications in numerical multilinear algebra, signal processing, solid mechanics, etc. In this paper, we consider a certain case that the derivatives of the objective function are unavailable. This case arises frequently in computational science, chemistry, physics, and other enormous areas. To explore the spherical structure of the above problem, we apply the Cayley transform to preserve iterates on the sphere and propose a derivative-free algorithm, which employs a simple model-based trust-region framework. Under mild conditions, global convergence of the proposed algorithm is established. Preliminary numerical experiments illustrate the promising performances of our algorithm. PubDate: 2020-04-01

Abstract: Abstract Protein molecular conformation is an important and challenging problem in biophysics. It is to recover the structure of proteins based on limited information such as noised distances, lower and upper bounds on some distances between atoms. In this paper, based on the recent progress in numerical algorithms for Euclidean distance matrix (EDM) optimization problems, we propose a EDM model for protein molecular conformation. We reformulate the problem as a rank-constrained least squares problem with linear equality constraints, box constraints, as well as a cone constraint. Due to the nonconvexity of the problem, we develop a majorized penalty approach to solve the problem. We apply the accelerated block coordinate descent algorithm proposed in Sun et al. (SIAM J Optim 26(2):1072–1100, 2016) to solve the resulting subproblem. Extensive numerical results demonstrate the efficiency of the proposed model. PubDate: 2020-04-01

Abstract: Abstract In this paper, we propose a hybrid Bregman alternating direction method of multipliers for solving the linearly constrained difference-of-convex problems whose objective can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous concave function. At each iteration, we choose either subgradient step or proximal step to evaluate the concave part. Moreover, the extrapolation technique was utilized to compute the nonsmooth convex part. We prove that the sequence generated by the proposed method converges to a critical point of the considered problem under the assumption that the potential function is a Kurdyka–Łojasiewicz function. One notable advantage of the proposed method is that the convergence can be guaranteed without the Lischitz continuity of the gradient function of concave part. Preliminary numerical experiments show the efficiency of the proposed method. PubDate: 2020-04-01

Abstract: Abstract Charged-particle therapy is a rapidly growing precision radiotherapy technique that treats tumors with ion beams. Because ion-beam delivery systems have multiple degrees of freedom (including the beam trajectories, energies and fluences), it can be extremely difficult to find a treatment plan that accurately matches the dose prescribed to the tumor while sparing nearby healthy structures. This inverse problem is called inverse treatment planning (ITP). Many ITP approaches have been proposed for the simpler case of X-ray therapy, but the work dedicated to charged-particle therapy is usually limited to optimizing the beam fluences given the trajectories and energies. To fill this gap, we consider the problem of simultaneously optimizing the beam trajectories, energies, and fluences, which we call full ITP. The solutions are the global minima of an objective function defined on a very large search space and having deep local basins of attraction; because of this difficulty, full ITP has not been studied (except in preliminary work of ours). We provide a proof of concept for full ITP by showing that it can be solved efficiently using simulated annealing (SA). The core of our work is the incremental design of a state exploration mechanism that substantially speeds up SA without altering its global convergence properties. We also propose an original approach to tuning the cooling schedule, a task critical to the performance of SA. Experiments with different irradiation configurations and increasingly sophisticated SA algorithms demonstrate the benefits and potential of the proposed methodology, opening new horizons to charged-particle therapy. PubDate: 2020-03-19

Abstract: Abstract This paper presents a general sparse portfolio selection model with expectation, chance and cardinality constraints. For the sparse portfolio selection model, we derive respectively the sample based reformulation and distributionally robust reformulation with mixture distribution based ambiguity set. These reformulations are mixed-integer programming problem and programming problem with difference of convex functions (DC), respectively. As an application of the general model and its reformulations, we consider the sparse enhanced indexation problem with multiple constraints. Empirical tests are conducted on the real data sets from major international stock markets. The results demonstrate that the proposed model, the reformulations and the solution method can efficiently solve the enhanced indexation problem and our approach can generally achieve sparse tracking portfolios with good out-of-sample excess returns and high robustness. PubDate: 2020-03-17

Abstract: Abstract We study the capacitated assortment and price optimization problem, where a retailer sells categories of substitutable products subject to a capacity constraint. The goal of the retailer is to determine the subset of products as well as their selling prices so as to maximize the expected revenue. We model the customer purchase behavior using the nested logit model and formulate this problem as a non-linear binary integer program. For this NP-complete problem, we show that there exists a pseudo polynomial time approximation scheme that finds its \(\epsilon \)-approximate solution. We first convert the original problem into an equivalent fixed point problem. We then show that finding an \(\epsilon \)-approximate solution to the fixed point problem can be achieved by binary search, where a non-linear auxiliary problem is repeatedly approximated by a dynamic programing based algorithm involving an approximation to a series of multiple-choice parametric knapsack problems. For the special case when the capacity constraints are cardinal and nest-specific, we develop an algorithm that finds the optimal solution in strongly polynomial time. Moreover, our algorithm can be directly applied to find an \(\epsilon \)-approximate solution to the capacitated assortment optimization problem under the nested logit model, which is the first approximate algorithm that is polynomial with respect to the number of nests in the literature. PubDate: 2020-03-14

Abstract: Abstract While a range of models have been proposed for the multiperiod blend scheduling problem (MBSP), solving even medium-size MBSP instances remains challenging due to the presence of bilinear terms and binary variables. To address this challenge, we develop solution methods for MBSP focusing on the cost minimization objective. We develop a novel preprocessing algorithm to calculate lower bounds on stream flows. We define product dedicated flow variables to address product specific features involved in MBSP. Bounds on stream flows and new product dedicated flow variables are then used to generate tightening constraints which significantly improve the solution time of the mixed integer nonlinear programming models as well as models based on linear approximations. PubDate: 2020-03-14

Abstract: Abstract The split feasibility problem is to find an element in the intersection of a closed set C and the linear preimage of another closed set D, assuming the projections onto C and D are easy to compute. This class of problems arises naturally in many contemporary applications such as compressed sensing. While the sets C and D are typically assumed to be convex in the literature, in this paper, we allow both sets to be possibly nonconvex. We observe that, in this setting, the split feasibility problem can be formulated as an optimization problem with a difference-of-convex objective so that standard majorization-minimization type algorithms can be applied. Here we focus on the nonmonotone proximal gradient algorithm with majorization studied in Liu et al. (Math Program, 2019. https://doi.org/10.1007/s10107-018-1327-8, Appendix A). We show that, when this algorithm is applied to a split feasibility problem, the sequence generated clusters at a stationary point of the problem under mild assumptions. We also study local convergence property of the sequence under suitable assumptions on the closed sets involved. Finally, we perform numerical experiments to illustrate the efficiency of our approach on solving split feasibility problems that arise in completely positive matrix factorization, (uniformly) sparse matrix factorization, and outlier detection. PubDate: 2020-03-11

Abstract: Abstract This article is dedicated to the weight set decomposition of a multiobjective (mixed-)integer linear problem with three objectives. We propose an algorithm that returns a decomposition of the parameter set of the weighted sum scalarization by solving biobjective subproblems via Dichotomic Search which corresponds to a line exploration in the weight set. Additionally, we present theoretical results regarding the boundary of the weight set components that direct the line exploration. The resulting algorithm runs in output polynomial time, i.e. its running time is polynomial in the encoding length of both the input and output. Also, the proposed approach can be used for each weight set component individually and is able to give intermediate results, which can be seen as an “approximation” of the weight set component. We compare the running time of our method with the one of an existing algorithm and conduct a computational study that shows the competitiveness of our algorithm. Further, we give a state-of-the-art survey of algorithms in the literature. PubDate: 2020-03-11

Abstract: Abstract In this paper, we investigate several properties of the solution maps of variational inequalities with polynomial data. First, we prove some facts on the \(R_0\)-property, the local boundedness, and the upper semicontinuity of the solution maps. Second, we establish results on the solution existence and the local upper-Hölder stability under the copositivity condition. Third, when the constraint set is semi-algebraic, we discuss the genericity of the \(R_0\)-property and the finite-valuedness of the solution maps. PubDate: 2020-03-06