Ph.D Thesis
Ph.D Student Hallak Nadav Block-Type Optimality Condition and Algorithms in Nonconvex Optimization Department of Industrial Engineering and Management Assistant Professor Shoham Sabach Professor Amir Beck

Abstract

This thesis studies three different models that can be described generally by a nonsmooth and nonconvex composite model over a closed set which is not necessarily convex. The first model studied is a class of problems consisting of minimizing a continuously differentiable function penalized with a combinatorial term that counts the number of nonzero elements in the decision variable, over a set satisfying some symmetry properties. These problems are hard to solve, yet prominent in many fields and applications.

We first study the proximal mapping operator in the setting of the model and provide an efficient method to compute it. The method is then improved for symmetric sets satisfying a property called "second order monotonicity" that is common in many important and frequently used sets, a result that we also established. Under the assumption that the underlying set satisfies the "second order monotonicity" property, we define optimality conditions for the model, and prove the existence of a hierarchy between them. Algorithms that are guaranteed to converge to points satisfying the aforementioned optimality conditions, are developed and tested by numerical experiments.

The second model consists of minimizing a lower bounded continuously differentiable function over a block separable set incorporating a group sparsity expression (a combinatorial term that counts the number of groups that are used) as a constraint or as a penalty (or both). This class of problems is generally hard to solve, yet highly applicable in numerous practical settings. The proximal mapping in the model's setting is proved to be calculable, and an efficient method to compute it is derived. Necessary optimality conditions for the problem are devised, and a hierarchy between stationary-based and coordinate-wised based conditions is established. Methods that obtain points satisfying the optimality conditions are presented, analyzed and tested in applications from the fields of investment and graph theory.

The third model studies the minimization of a composite model of two functions in which one has a Lipschitz continuous gradient and the other is concave but not necessarily differentiable, over a convex polytope. The studied problem is in general hard to solve as it is nonsmooth and nonconvex, forcing one to settle with a solution that satisfies some type of optimality condition. Stationarity, which is defined as the lack of feasible descent directions, is a fundamental condition in smooth and nonsmooth nonconvex problems. Yet, there are very few methods that actually converge to stationary points, none of which fully addresses the problem at hand. We show that stationarity, although defined by an infinite number of directions, can be equivalently defined using a finite set of directions. A method that obtains such a set of directions is developed, and a method that converges to stationary points by minimizing a univariate auxiliary function at each iteration is provided.