Subgradient Method for Nonconvex Nonsmooth Optimization

In this paper, we introduce a new method for solving nonconvex nonsmooth optimization problems. It uses quasisecants, which are subgradients computed in some neighborhood of a point. The proposed method contains simple procedures for finding descent directions and for solving line search subproblems. The convergence of the method is studied and preliminary results of numerical experiments are presented. The comparison of the proposed method with the subgradient and the proximal bundle methods is demonstrated using results of numerical experiments.     

A Feasible Point Method with Bundle Modification for Nonsmooth Convex Constrained Optimization

In this paper, a bundle modification strategy is proposed for nonsmooth convex constrained minimization problems. As a result, a new feasible point bundle method is presented by applying this strategy. Whenever the stability center is updated, some points in the bundle will be substituted by new ones which have lower objective values and/or constraint values, aiming at getting a better bundle. The method generates feasible serious iterates on which the objective function is monotonically decreasing. Global convergence of the algorithm is established, and some preliminary numerical results show that our method performs better than the standard feasible point bundle method.     

A Trust-region Method for Nonsmooth Nonconvex Optimization

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.     

Comparing Nonsmooth Nonconvex Bundle Methods in Solving Hemivariational Inequalities

Hemivariational inequalities can be considered as a generalization of variational inequalities. Their origin is in nonsmooth mechanics of solid, especially in nonmonotone contact problems. The solution of a hemivariational inequality proves to be a substationary point of some functional, and thus can be found by the nonsmooth and nonconvex optimization methods. We consider two type of bundle methods in order to solve hemivariational inequalities numerically: proximal bundle and bundle-Newton methods. Proximal bundle method is based on first order polyhedral approximation of the locally Lipschitz continuous objective function. To obtain better convergence rate bundle-Newton method contains also some second order information of the objective function in the form of approximate Hessian. Since the optimization problem arising in the hemivariational inequalities has a dominated quadratic part the second order method should be a good choice. The main question in the functioning of the methods is how remarkable is the advantage of the possible better convergence rate of bundle-Newton method when compared to the increased calculation demand.     

Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods

Journal of Global Optimization - We propose a general formulation of nonconvex and nonsmooth sparse optimization problems with convex set constraint, which can take into account most existing types...     

Proximal Point Methods and Nonconvex Optimization

The goal of this paper is to discover some possibilities for applying the proximal point method to nonconvex problems. It can be proved that – for a wide class of problems – proximal regularization performed with appropriate regularization parameters ensures convexity of the auxiliary problems and each accumulation point of the method satisfies the necessary optimality conditions.     

Extrapolated Smoothing Descent Algorithm for Constrained Nonconvex and Nonsmooth Composite Problems*

In this paper, the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems,where the nonconvex term is possibly nonsmooth. Their algorithm adopts the proximal gradient algorithm with extrapolation and a safe-guarding policy to minimize the smoothed objective function for better practical and theoretical performance. Moreover, the algorithm uses a easily checking rule to update the smoothing parameter to ensure that any accumulation point of the generated sequence is an (affine-scaled) Clarke stationary point of the original nonsmooth and nonconvex problem. Their experimental results indicate the effectiveness of the proposed algorithm.     

Optimality Conditions for Nonconvex Constrained Optimization Problems

Abstract

We present optimality conditions for a class of nonsmooth and nonconvex constrained optimization problems. To achieve this aim, various well-known constraint qualifications are extended based on the concept of tangential subdifferential and the relations between them are investigated. Moreover, local and global necessary and sufficient optimality conditions are derived in the absence of convexity of the feasible set. In addition to the theoretical results, several examples are provided to illustrate the advantage of our outcomes.     

A Note on the Existence of Nonsmooth Nonconvex Optimization Problems

Sufficient conditions for the existence of a solution to an abstract optimization problem in Banach spaces are given, which do not rely on convexity, regularity properties or a straightforward coerciveness assumption. Applications to sparsity-constrained optimization and to problems from mechanics are provided.     

一种约束非光滑优化问题的信赖域算法

提出了一种易实施的求解带线性约束的非光滑优化问题的信赖域算法，并在一定的条件下证明了该算法所产生的迭代序列的任何聚点都是原问题的稳定点．有限的数值例子表明，该方法是行之有效的．     

On Second-order Sufficient Conditions in Constrained Nonsmooth Optimization

In this paper, we establish a second-order sufficient condition for constrained optimization problems of a class of so called t-stable functions in terms of the first-order and the second-order Dini type directional derivatives. The result extends the corresponding result of [D. Bednarik and K. Pastor, Math. Program. Ser. A, 113（2008）, 283-298] to constrained optimization problems.     

脉冲噪声下图像去模糊非光滑非凸最小化问题的近端线性化最小化算法

去除脉冲噪声是图像复原中的重要任务之一.我们提出一类非光滑非凸模型来恢复模糊和脉冲噪声污染的图像,该模型具有灵活的先验信息引入机制,如盒子约束或低秩等.为了求解所提非凸问题,我们采用近端线性化最小化算法.对于算法中的子问题,我们运用交替方向乘子法.在目标函数满足Kurdyka-Lojasiewicz性质的假设下,我们证明所提算法的全局收敛性.数值实验表明,在主观和客观质量评价方面,我们的方法优于$\ell_{1}$TV和非凸TV模型.     

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.     

Unified Robust Necessary Optimality Conditions for Nonconvex Nonsmooth Uncertain Multiobjective Optimization

Journal of Optimization Theory and Applications - This paper is devoted to presenting new error bounds of regularized gap functions for polynomial variational inequalities with exponents explicitly...     

The Lagrangian Globalization Method for Nonsmooth Constrained Equations

The difficulty suffered in optimization-based algorithms for the solution of nonlinear equations lies in that the traditional methods for solving the optimization problem have been mainly concerned with finding a stationary point or a local minimizer of the underlying optimization problem, which is not necessarily a solution of the equations. One method to overcome this difficulty is the Lagrangian globalization (LG for simplicity) method. This paper extends the LG method to nonsmooth equations with bound constraints. The absolute system of equations is introduced. A so-called Projected Generalized-Gradient Direction (PGGD) is constructed and proved to be a descent direction of the reformulated nonsmooth optimization problem. This projected approach keeps the feasibility of the iterates. The convergence of the new algorithm is established by specializing the PGGD. Numerical tests are given. This author's work was done when she was visiting The Hong Kong Polytechnic University. His work is also supported by the Research Grant Council of Hong Kong.     

A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems

In this paper we propose a new branch and bound algorithm using a rectangular partition and ellipsoidal technique for minimizing a nonconvex quadratic function with box constraints. The bounding procedures are investigated by d.c. (difference of convex functions) optimization algorithms, called DCA. This is based upon the fact that the application of the DCA to the problems of minimizing a quadratic form over an ellipsoid and/or over a box is efficient. Some details of computational aspects of the algorithm are reported. Finally, numerical experiments on a lot of test problems showing the efficiency of our algorithm are presented.     

On Approximations with Finite Precision in Bundle Methods for Nonsmooth Optimization

Journal of Optimization Theory and Applications - We consider the proximal form of a bundle algorithm for minimizing a nonsmooth convex function, assuming that the function and subgradient values...     

解约束非凸规划问题的同伦方法的收敛性定理

本文在利用组合内点同伦方法求解约束非凸规划问题时,得到了一些新的收敛性定理.证明了同伦映射为正则映射的条件下,选取合适的同伦方程,用此同伦方法得到的K-K-T点一定是问题局部最优解.