| 1. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Mathematical Programs with Cardinality Constraints : Reformulation by Complementarity-type Constraints and a Regularization Method
- 2014
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discreteoptimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between thelocal minima is also discussed in detail. Since our reformulation is a mini-mization problem in continuous variables, it allows to apply ideas from thatfield to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinalityconstraints. This regularization method is shown to be globally convergentto a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.
|
|
| 2. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
- 2016
-
Ingår i: SIAM Journal on Optimization. - : Society for Industrial & Applied Mathematics (SIAM). - 1052-6234 .- 1095-7189. ; 26:1, s. 397-425
-
Tidskriftsartikel (refereegranskat)abstract
- Optimization problems with cardinality constraints are very difficult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in detail. Since our reformulation is a minimization problem in continuous variables, it allows to apply ideas from that field to cardinality-constrained problems. Here, in particular, we therefore also derive suitable stationarity conditions and suggest an appropriate regularization method for the solution of optimization problems with cardinality constraints. This regularization method is shown to be globally convergent to a Mordukhovich-stationary point. Extensive numerical results are given to illustrate the behavior of this method.
|
|
| 3. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
On a Reformulation of Mathematical Programs with Cardinality Constraints
- 2015
-
Ingår i: Advances in Global Optimization. - Switzerland : Springer International Publishing. - 9783319083766 - 9783319083773 ; , s. 3-14
-
Bokkapitel (refereegranskat)abstract
- Mathematical programs with cardinality constraints are optimization problems with an additional constraint which requires the solution to be sparse in the sense that the number of nonzero elements, i.e. the cardinality, is bounded by a given constant. Such programs can be reformulated as a mixed-integer ones in which the sparsity is modeled with the use of complementarity-type constraints. It is shown that the standard relaxation of the integrality leads to a nonlinear optimization program of the striking property that its solutions (global minimizers) are the same as the solutions of the original program with cardinality constraints. Since the number of local minimizers of the relaxed program is typically larger than the number of local minimizers of the cardinality-constrained problem, the relationship between the local minimizers is also discussed in detail. Furthermore, we show under which assumptions the standard KKT conditions are necessary optimality conditions for the relaxed program. The main result obtained for such conditions is significantly different from the existing optimality conditions that are known for the somewhat related class of mathematical programs with complementarity constraints.
|
|
