Absolute value equations with uncertain data
- PDF / 369,999 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 209 Views
Absolute value equations with uncertain data M. A. Raayatpanah1
· H. Moosaei2 · P. M. Pardalos3
Received: 27 February 2016 / Accepted: 2 January 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Absolute value equations (AVE) provide a useful tool for optimization as they subsume many mathematical programming problems. However, in some applications, it is difficult to determine the exact values of the problem data and there may be some certain errors. Finding a solution for AVE based on erroneous data using existing approaches might yield a meaningless solution. In this paper, robust optimization, which represents errors in the problem data, is used. We prove that a robust solution can be obtained by solving a robust counterpart problem, which is equivalent to a second order cone program. The results also show that robust solutions can significantly improve the performance of solutions, especially when the size of errors in the problem is large. Keywords Absolute value equations · Second-order conic programming · Robust optimization
1 Introduction We consider the absolute value equations (AVE ) of the type: Ax + B|x| = b,
B
(1)
M. A. Raayatpanah [email protected] H. Moosaei [email protected]; [email protected] P. M. Pardalos [email protected]
1
Department of Mathematics, Kharazmi University, Tehran, Iran
2
Department of Mathematics, University of Bojnord, Bojnord, Iran
3
Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA
123
M. A. Raayatpanah et al.
where A ∈ R m×n , B ∈ R m×n , and b ∈ R m are given and |x| denotes the componentwise absolute value of vector x ∈ R n . If m = n and det(B) = 0, then (1) can be reduced to Ax − |x| = b.
(2)
In [21], it has been shown that determining the existence of a solution for AVE of types (1) and (2) is NP-hard. It has also been proved in [14] that linear complementarity problems (LCP) [2,7,8,20] can be formulated as an AVE. Hence, the AVE formulation subsumes major fundamental problems of mathematical programming such as linear programs, quadratic programs, and bimatrix games. The AVE of type (1) and (2) have been studied in a series of papers. (See e.g. [9,10,12,13,15–18,21,23–26]). However, in some applications, it might be difficult to determine the exact problem data A, B or b. It is possible that a slight perturbation in the problem data can significantly change the solutions. Hence, existing methods may provide unrealistic solutions in practice, especially when the problem data is uncertain. In this case, it is desirable to find a solution, which is not exclusively optimal for a certain value of the problem data, but efficient for all possible uncertainty outcomes. We use robust optimization to present uncertainty in this work. In the early 1970s, Soyster [27] was one of the first researchers to study explicit approaches to robust optimization. In recent years, several papers have been published on the applications and theory of robust optimization [3
Data Loading...
