Weighted Thresholding Homotopy Method for Sparsity Constrained Optimization

Weighted or reweighted strategies have not been considered for sparsity constrained optimization. In this paper, we reformulate the sparsity constraint as an equivalent weighted l1-norm constraint in the sparsity constrained optimization problem. To solve the reformulated problem, we investigate the problem in the Lagrange dual framework, and prove that the strong duality property holds. Then … Read more

Iterative weighted thresholding method for sparse solution of underdetermined linear equations

Recently, iterative reweighted methods have attracted much interest in compressed sensing, since they perform better than unweighted ones in most cases. Currently, weights are chosen heuristically in existing iterative reweighted methods, and nding an optimal weight is an open problem since we do not know the exact support set beforehand. In this paper, we present … Read more

A new customized proximal point algorithm for linearly constrained convex optimization

In this paper, we propose a new customized proximal point algorithm for linearly constrained convex optimization problem, and further use it to solve the separable convex optimization problem with linear constraints. Which is different to the existing customized proximal point algorithms, the proposed algorithm does not involve any relaxation step but still ensure the convergence. … Read more

Minimum cost Layout Decomposition and Legalization for Triple Patterning Lithography

With the need of 16/11nm cells, triple patterning lithography (TPL) has been concerned in lithography industry. Based on a new conflict projection technique to identify conflicts, we formulate in this paper the TPL layout decomposition problem as a minimum cost coloring problem. The problem is solved in two steps. First, it is relaxed to a … Read more

Homotopy methods based on l0 norm for the compressed sensing problem

In this paper, two homotopy methods, which combine the advantage of the homotopy technique with the effectiveness of the iterative hard thresholding method, are presented for solving the compressed sensing problem. Under some mild assumptions, we prove that the limits of the sequences generated by the proposed homotopy methods are feasible solutions of the problem, … Read more

Local Search Approximation Algorithms for the Complement of the Min-hBcCut Problems

Min-$k$-cut is the problem of partitioning vertices of a given graph or hypergraph into $k$ subsets such that the total weight of edges or hyperedges crossing different subsets is minimized. For the capacitated min-$k$-cut problem, each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on … Read more

On the Globally Concavized Filled Function Method

In this paper we present a new definition on the globally concavized filled function for the continuous global minimization problem, which was modified from that by Ge [3]. A new class of globally concavized filled functions are constructed. These functions contain two easily determinable parameters, which are not dependent on the radius of the basin … Read more

On the globally convexized filled function method for box constrained continuous global optimization

In this paper we show that the unconstrained continuous global minimization problem can not be solved by any algorithm. So without loss of generality we consider the box constrained continuous global minimization problem. We present a new globally convexized filled function method for the problem. The definition of globally convexized filled function is adapted from … Read more

A sequential convexification method (SCM) for continuous global optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the original objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function is in the region where the function value of the original … Read more