Research Project: NP-Zor Eniyileme Problemleri İçin Kopozitif Yöntemin Dayalı çözüm Yaklaşımları
Loading...
Contributors
Funders
ID
TB.00120
Authors
Yıldırım, Emre Alper
Faculty Member
Publications
Rounding on the standard simplex: regular grids for global optimization
(Springer, 2014) Yıldırım, Emre Alper; Bomze, Immanuel M.; Gollowitzer, Stefan; Department of Industrial Engineering; Yes; College of Engineering
Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all l(p)-norms for p >= 1 . We show that the minimal l(p)-distance to the regular grid on the standard simplex can exceed one, even for very fine mesh sizes in high dimensions. Furthermore, for p = 1, the maximum minimal distance approaches the l(1)-diameter of the standard simplex. We also put our results into perspective with respect to the literature on approximating global optimization problems over the standard simplex by means of the regular grid.
Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis
(Taylor & Francis Ltd, 2017) Yıldırım, Emre Alper; Department of Industrial Engineering; Yes; College of Engineering
Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.
Analysis of copositive optimization based linear programming bounds on standard quadratic optimization
(Springer, 2015) Sağol, Gizem; Yıldırım, Emre Alper; Department of Industrial Engineering; Graduate School of Sciences and Engineering; Yes; College of Engineering; GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated in various ways from the inside and from the outside by two sequences of nested tractable convex cones of increasing accuracy. In this paper, we focus on the inner polyhedral approximations due to YA +/- ldA +/- rA +/- m (Optim Methods Softw 27(1):155-173, 2012) and the outer polyhedral approximations due to de Klerk and Pasechnik (SIAM J Optim 12(4):875-892, 2002). We investigate the sequences of upper and lower bounds on the optimal value of a standard quadratic optimization problem arising from these two hierarchies of inner and outer polyhedral approximations. We give complete algebraic descriptions of the sets of instances on which upper and lower bounds are exact at any given finite level of the hierarchy. We identify the structural properties of the sets of instances on which upper and lower bounds converge to the optimal value only in the limit. We present several geometric and topological properties of these sets. Our results shed light on the strengths and limitations of these inner and outer polyhedral approximations in the context of standard quadratic optimization.
