A complementarity partition theorem for multifold conic systems
- Authors: Peña, Javier , Roshchina, Vera
- Date: 2012
- Type: Text , Journal article
- Relation: Mathematical Programming Vol.142 , no.1-2 (2012), p.579-589
- Full Text: false
- Reviewed:
- Description: Consider a homogeneous multifold convex conic system {Mathematical expression}and its alternative system {Mathematical expression}, where K 1,..., K r are regular closed convex cones. We show that there is a canonical partition of the index set {1,..., r} determined by certain complementarity sets associated to the most interior solutions to the two systems. Our results are inspired by and extend the Goldman-Tucker Theorem for linear programming. © 2012 Springer and Mathematical Optimization Society.
Fractal bodies invisible in 2 and 3 directions
- Authors: Plakhov, Alexander , Roshchina, Vera
- Date: 2013
- Type: Text , Journal article
- Relation: Discrete and Continuous Dynamical Systems - Series A Vol. 33, no. 4 (2013), p. 1615-1631
- Full Text:
- Reviewed:
- Description: We study the problem of invisibility for bodies with a mirror surface in the framework of geometrical optics. We show that for any two given directions it is possible to construct a two-dimensional fractal body invisible in these directions. Moreover, there exists a three-dimensional fractal body invisible in three orthogonal directions. The work continues the previous study in [1, 12], where two-dimensional bodies invisible in one direction and threedimensional bodies invisible in one and two orthogonal directions were constructed.
- Description: 2003010679
Bodies with mirror surface invisible from two points
- Authors: Plakhov, Andrew , Roshchina, Vera
- Date: 2014
- Type: Text , Journal article
- Relation: Nonlinearity Vol. 27, no. 6 (June 2014), p. 1193-1203
- Full Text: false
- Reviewed:
- Description: We consider a setting where a bounded set with a piecewise smooth boundary in Euclidean space is identified with a body with a mirror surface, and the billiard in the complement of the set is identified with the dynamics of light rays outside the body in the framework of geometric optics. We show that in this setting it is possible to construct a body invisible from two points. © 2014 IOP Publishing Ltd & London Mathematical Society.
Directed subdifferentiable functions and the directed subdifferential without Delta-convex structure
- Authors: Baier, Robert , Farkhi, Elza , Roshchina, Vera
- Date: 2014
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 160, no. 2 (2014), p. 391-414
- Full Text: false
- Reviewed:
- Description: We show that the directed subdifferential introduced for differences of convex (delta-convex, DC) functions by Baier and Farkhi can be constructed from the directional derivative without using any information on the delta-convex structure of the function. The new definition extends to a more general class of functions, which includes Lipschitz functions definable on o-minimal structure and quasidifferentiable functions. © 2013 Springer Science+Business Media New York.
Facially exposed cones are not always nice
- Authors: Roshchina, Vera
- Date: 2014
- Type: Text , Journal article
- Relation: SIAM Journal on Optimization Vol. 24, no. 1 (2014), p. 257-268
- Full Text:
- Reviewed:
- Description: We address the conjecture proposed by Gábor Pataki that every facially exposed cone is nice. We show that the conjecture is true in the three-dimensional case; however, there exists a four-dimensional counterexample of a cone that is facially exposed but is not nice.
Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Authors: Briquel, Irenee , Cucker, Felipe , Peña, Javier , Roshchina, Vera
- Date: 2014
- Type: Text , Journal article
- Relation: Mathematics of Computation Vol. 83, no. 287 (2014), p. 1279-1317
- Full Text: false
- Reviewed:
- Description: A solution for Smale's 17th problem, for the case of systems with bounded degree was recently given. This solution, an algorithm computing approximate zeros of complex polynomial systems in average polynomial time, assumed infinite precision. In this paper we describe a finite-precision version of this algorithm. Our main result shows that this version works within the same time bounds and requires a precision which, on the average, amounts to a polynomial amount of bits in the mantissa of the intervening floating-point numbers. © 2013 American Mathematical Society.
Solving second-order conic systems with variable precision
- Authors: Cucker, Felipe , Peña, Javier , Roshchina, Vera
- Date: 2014
- Type: Text , Journal article
- Relation: Mathematical Programming Vol. 150, no. 2 (2014), p. 217-250
- Full Text: false
- Reviewed:
- Description: We describe and analyze an interior-point method to decide feasibility problems of second-order conic systems. A main feature of our algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited. © 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
Some preconditioners for systems of linear inequalities
- Authors: Peña, Javier , Roshchina, Vera , Soheili, Negar
- Date: 2014
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 8, no. 7 (2014), p. 2145-2152
- Full Text: false
- Reviewed:
- Description: We show that a combination of two simple preprocessing steps would generally improve the conditioning of a homogeneous system of linear inequalities. Our approach is based on a comparison among three different but related notions of conditioning for linear inequalities. © 2014, Springer-Verlag Berlin Heidelberg.
On local coincidence of a convex set and its tangent cone
- Authors: Meng, Kaiwen , Roshchina, Vera , Yang, Xiaoqi
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 164, no. 1 (2015), p. 123-137
- Full Text: false
- Reviewed:
- Description: In this paper, we introduce the exact tangent approximation property for a convex set and provide its characterizations, including the nonzero extent of a convex set. We obtain necessary and sufficient conditions for the closedness of the positive hull of a convex set via a limit set defined by truncated upper level sets of the gauge function. We also apply the exact tangent approximation property to study the existence of a global error bound for a proper, lower semicontinuous and positively homogeneous function.
Compact convex sets with prescribed facial dimensions
- Authors: Roshchina, Vera , Sang, Tian , Yost, David
- Date: 2018
- Type: Text , Book chapter
- Relation: 2016 Matrix Annals p. 167-175
- Full Text:
- Reviewed:
- Description: While faces of a polytope form a well structured lattice, in which faces of each possible dimension are present, this is not true for general compact convex sets. We address the question of what dimensional patterns are possible for the faces of general closed convex sets. We show that for any finite sequence of positive integers there exist compact convex sets which only have extreme points and faces with dimensions from this prescribed sequence. We also discuss another approach to dimensionality, considering the dimension of the union of all faces of the same dimension. We show that the questions arising from this approach are highly nontrivial and give examples of convex sets for which the sets of extreme points have fractal dimension.
A counterexample to De Pierro's conjecture on the convergence of under-relaxed cyclic projections
- Authors: Cominetti, Roberto , Roshchina, Vera , Williamson, Andrew
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 1 (2019), p. 3-12
- Full Text:
- Reviewed:
- Description: The convex feasibility problem consists in finding a point in the intersection of a finite family of closed convex sets. When the intersection is empty, a best compromise is to search for a point that minimizes the sum of the squared distances to the sets. In 2001, de Pierro conjectured that the limit cycles generated by the ε-under-relaxed cyclic projection method converge when ε ↓ 0 towards a least squares solution. While the conjecture has been confirmed under fairly general conditions, we show that it is false in general by constructing a system of three compact convex sets in R3 for which the ε-under-relaxed cycles do not converge. © 2018 Informa UK Limited, trading as Taylor & Francis Group.
Outer limits of subdifferentials for min–max type functions
- Authors: Eberhard, Andrew , Roshchina, Vera , Sang, Tian
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Vol. 68, no. 7 (2019), p. 1391-1409
- Full Text:
- Reviewed:
- Description: We generalize the outer subdifferential construction suggested by Cánovas, Henrion, López and Parra for max type functions to pointwise minima of regular Lipschitz functions. We also answer an open question about the relation between the outer subdifferential of the support of a regular function and the end set of its subdifferential posed by Li, Meng and Yang.
The Demyanov–Ryabova conjecture is false
- Authors: Roshchina, Vera
- Date: 2019
- Type: Text , Journal article
- Relation: Optimization Letters Vol. 13, no. 1 (2019), p. 227-234. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: It was conjectured by Demyanov and Ryabova (Discrete Contin Dyn Syst 31(4):1273–1292, 2011) that the minimal cycle in the sequence obtained via repeated application of the Demyanov converter to a finite family of polytopes is at most two. We construct a counterexample for which the minimal cycle has length 4.
Variational analysis Down Under open problem session
- Authors: Bui, Hoa , Lindstrom, Scott , Roshchina, Vera
- Date: 2019
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 182, no. 1 (2019), p. 430-437
- Full Text:
- Reviewed:
- Description: We state the problems discussed in the open problem session at Variational Analysis Down Under conference held in honour of Prof. Asen Dontchev on 19-21 February 2018 at Federation University Australia.
Refining the partition for multifold conic optimization problems
- Authors: Ramirez, Hector , Roshchina, Vera
- Date: 2020
- Type: Text , Journal article
- Relation: Optimization Vol. 69, no. 11 (2020), p. 2489-2507
- Full Text:
- Reviewed:
- Description: In this paper, we give a unified treatment of two different definitions of complementarity partition of multifold conic programs introduced independently in Bonnans and Ramirez [Perturbation analysis of second-order cone programming problems, Math Program. 2005;104(2-30):205-227] for conic optimization problems, and in Pena and Roshchina [A complementarity partition theorem for multifold conic systems, Math Program. 2013;142(1-2):579-589] for homogeneous feasibility problems. We show that both can be treated within the same unified geometric framework and extend the latter notion to optimization problems. We also show that the two partitions do not coincide, and their intersection gives a seven-set index partition. Finally, we demonstrate that the partitions are preserved under the application of nonsingular linear transformations, and in particular, that a standard conversion of a second-order cone program into a semidefinite programming problem preserves the partitions.
- Description: This research was partially supported by ANID (Chile) under REDES project number 180032 and by the Australian Research Council grant DE150100240. The second author was supported by FONDECYT (Fondo de Fomento al Desarrollo Cientifico y Tecnologico) regular projects 1160204 and 1201982, and Basal Program CMM-AFB 170001 (Comision Nacional de Investigacion Cientifica y Tecnologica), all from ANID (Chile).