DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

On a class of ill-posed minimization problems in image processing

In this paper, we show that minimization problems involving sublinear regularizing terms are ill-posed, in general, although numerical experiments in image processing give very good results. The energies studied here are inspired by image restoration and image decomposition. Rewriting the nonconvex sublinear regularizing terms as weighted total variations, we give a new approach to perform minimization via the well-known Chambolle's algorithm. The approach developed here provides an alternative to the well-known half-quadratic minimization one.     

Accelerated Path-Following Iterative Shrinkage Thresholding Algorithm With Application to Semiparametric Graph Estimation

We propose an accelerated path-following iterative shrinkage thresholding algorithm (APISTA) for solving high-dimensional sparse nonconvex learning problems. The main difference between APISTA and the path-following iterative shrinkage thresholding algorithm (PISTA) is that APISTA exploits an additional coordinate descent subroutine to boost the computational performance. Such a modification, though simple, has profound impact: APISTA not only enjoys the same theoretical guarantee as that of PISTA, that is, APISTA attains a linear rate of convergence to a unique sparse local optimum with good statistical properties, but also significantly outperforms PISTA in empirical benchmarks. As an application, we apply APISTA to solve a family of nonconvex optimization problems motivated by estimating sparse semiparametric graphical models. APISTA allows us to obtain new statistical recovery results that do not exist in the existing literature. Thorough numerical results are provided to back up our theory.     

Existence of a Saddle Point in Nonconvex Constrained Optimization

The existence of a saddle point in nonconvex constrained optimization problems is considered in this paper. We show that, under some mild conditions, the existence of a saddle point can be ensured in an equivalent p-th power formulation for a general class of nonconvex constrained optimization problems. This result expands considerably the class of optimization problems where a saddle point exists and thus enlarges the family of nonconvex problems that can be solved by dual-search methods.     

Minimum Maximal Flow Problem: An Optimization over the Efficient Set

The network flow theory and algorithms have been developed on the assumption that each arc flow is controllable and we freely raise and reduce it. We however consider in this paper the situation where we are not able or allowed to reduce the given arc flow. Then we may end up with a maximal flow depending on the initial flow as well as the way of augmentation. Therefore the minimum of the flow values that are attained by maximal flows will play an important role to see how inefficiently the network can be utilized. We formulate this problem as an optimization over the efficient set of a multicriteria program, propose an algorithm, prove its finite convergence, and report on some computational experiments.     

An Iterative Coordinate Descent Algorithm for High-Dimensional Nonconvex Penalized Quantile Regression

We propose and study a new iterative coordinate descent algorithm (QICD) for solving nonconvex penalized quantile regression in high dimension. By permitting different subsets of covariates to be relevant for modeling the response variable at different quantiles, nonconvex penalized quantile regression provides a flexible approach for modeling high-dimensional data with heterogeneity. Although its theory has been investigated recently, its computation remains highly challenging when p is large due to the nonsmoothness of the quantile loss function and the nonconvexity of the penalty function. Existing coordinate descent algorithms for penalized least-squares regression cannot be directly applied. We establish the convergence property of the proposed algorithm under some regularity conditions for a general class of nonconvex penalty functions including popular choices such as SCAD (smoothly clipped absolute deviation) and MCP (minimax concave penalty). Our Monte Carlo study confirms that QICD substantially improves the computational speed in the p ? n setting. We illustrate the application by analyzing a microarray dataset.     

A method for approximating pairwise comparison matrices by consistent matrices

In several methods of multiattribute decision making, pairwise comparison matrices are applied to derive implicit weights for a given set of decision alternatives. A class of the approaches is based on the approximation of the pairwise comparison matrix by a consistent matrix. In the paper this approximation problem is considered in the least-squares sense. In general, the problem is nonconvex and difficult to solve, since it may have several local optima. In the paper the classic logarithmic transformation is applied and the problem is transcribed into the form of a separable programming problem based on a univariate function with special properties. We give sufficient conditions of the convexity of the objective function over the feasible set. If such a sufficient condition holds, the global optimum of the original problem can be obtained by local search, as well. For the general case, we propose a branch-and-bound method. Computational experiments are also presented.     

Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints

A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.     

A system of evolution hemivariational inequalities modeling thermoviscoelastic frictional contact

In this paper we prove the existence and uniqueness of the weak solution for a dynamic thermoviscoelastic problem which describes frictional contact between a body and a foundation. We employ the Kelvin–Voigt viscoelastic law, include the thermal effects and consider the general nonmonotone and multivalued subdifferential boundary conditions. The model consists of the system of the hemivariational inequality of hyperbolic type for the displacement and the parabolic hemivariational inequality for the temperature. The existence of solutions is proved by using a surjectivity result for operators of pseudomonotone type. The uniqueness is obtained for a large class of operators of subdifferential type satisfying a relaxed monotonicity condition.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.