Second-order negative-curvature methods for box-constrained and general constrained optimization

A Nonlinear Programming algorithm that converges to second-order stationary points is introduced in this paper. The main tool is a second-order negative-curvature method for box-constrained minimization of a certain class of functions that do not possess continuous second derivatives. This method is used to define an Augmented Lagrangian algorithm of PHR (Powell-Hestenes-Rockafellar) type. Convergence proofs under weak constraint qualifications are given. Numerical examples showing that the new method converges to second-order stationary points in situations in which first-order methods fail are exhibited.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

Improving ultimate convergence of an augmented Lagrangian method

Optimization methods that employ the classical Powell-Hestenes-Rockafellar augmented Lagrangian are useful tools for solving nonlinear programming problems. Their reputation decreased in the last 10 years due to the comparative success of interior-point Newtonian algorithms, which are asymptotically faster. In this research, a combination of both approaches is evaluated. The idea is to produce a competitive method, being more robust and efficient than its `pure` counterparts for critical problems. Moreover, an additional hybrid algorithm is defined, in which the interior-point method is replaced by the Newtonian resolution of a Karush-Kuhn-Tucker (KKT) system identified by the augmented Lagrangian algorithm. The software used in this work is freely available through the Tango Project web page:http://www.ime.usp.br/similar to egbirgin/tango/.

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.

Homeomorphisms of the annulus with a transitive lift

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the infinite strip (A) over tilde which is transitive. We show that, if the rotation numbers of both boundary components of A are strictly positive, then there exists a closed nonempty unbounded set B(-) subset of (A) over tilde such that B(-) is bounded to the right, the projection of B to A is dense, B - (1, 0) subset of B and (f) over tilde (B) subset of B. Moreover, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of B(-), lim sup (n ->infinity) p1((f) over tilde (n)((z) over tilde)) - p(1) ((z) over tilde)/n < - d. In particular, using a result of Franks, we show that the rotation set of any homeomorphism of the annulus that preserves orientation, boundary components, which has a transitive lift without fixed points in the boundary is an interval with 0 in its interior.

Weak local Nash equilibrium

In this paper, we consider a concept of local Nash equilibrium for non-cooperative games - the so-called weak local Nash equilibrium. We prove its existence for a significantly more general class of sets of strategies than compact convex sets. The theorems on existence of the weak local equilibrium presented here are applications of Brouwer and Lefschetz fixed point theorems. © 2013 Juliusz Schauder Centre for Nonlinear Studies Nicolaus Copernicus University.

Restauração de imagens utilizando projeções em conjuntos convexos e algoritmos evolucionistas

Pós-graduação em Ciência da Computação - IBILCE

Multiasset Derivatives and Joint Distributions of Asset Prices

Several of multiasset derivatives like basket options or options on the weighted maximum of assets exhibit the property that their prices determine uniquely the underlying asset distribution. Related to that the question how to retrieve this distributions from the corresponding derivatives quotes will be discussed. On the contrary, the prices of exchange options do not uniquely determine the underlying distributions of asset prices and the extent of this non-uniqueness can be characterised. The discussion is related to a geometric interpretation of multiasset derivatives as support functions of convex sets. Following this, various symmetry properties for basket, maximum and exchange options are discussed alongside with their geometric interpretations and some decomposition results for more general payoff functions.

Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.

From the Farkas Lemma to the Hahn–Banach Theorem

This paper provides new versions of the Farkas lemma characterizing those inequalities of the form f(x) ≥ 0 which are consequences of a composite convex inequality (S ◦ g)(x) ≤ 0 on a closed convex subset of a given locally convex topological vector space X, where f is a proper lower semicontinuous convex function defined on X, S is an extended sublinear function, and g is a vector-valued S-convex function. In parallel, associated versions of a stable Farkas lemma, considering arbitrary linear perturbations of f, are also given. These new versions of the Farkas lemma, and their corresponding stable forms, are established under the weakest constraint qualification conditions (the so-called closedness conditions), and they are actually equivalent to each other, as well as equivalent to an extended version of the so-called Hahn–Banach–Lagrange theorem, and its stable version, correspondingly. It is shown that any of them implies analytic and algebraic versions of the Hahn–Banach theorem and the Mazur–Orlicz theorem for extended sublinear functions.

The Use of the Relative Interior in Integration with Nonconvex Data

Introducing an appropriate inclusion between approximate minima associated with two nonconvex functions, we derive explicit relations between the closed convex hulls of these functions. The formula we obtain goes beyond the so-called epi-pointed property of functions which is usually concerned with such a topic.

Extraction of texture features from arbitrary-shaped regions for image retrieval

Lots of work has been done in texture feature extraction for rectangular images, but not as much attention has been paid to the arbitrary-shaped regions available in region-based image retrieval (RBIR) systems. In This work, we present a texture feature extraction algorithm, based on projection onto convex sets (POCS) theory. POCS iteratively concentrates more and more energy into the selected coefficients from which texture features of an arbitrary-shaped region can be extracted. Experimental results demonstrate the effectiveness of the proposed algorithm for image retrieval purposes.

Sufficient Conditions of Optimality for Control Pproblem Governed by Variational Inequalities

* This work was completed while the author was visiting the University of Limoges. Support from the laboratoire “Analyse non-linéaire et Optimisation” is gratefully acknowledged.

High-resolution image reconstruction from multiple low-resolution images.

In this paper, we demonstrate a digital signal processing (DSP) algorithm for improving spatial resolution of images captured by CMOS cameras. The basic approach is to reconstruct a high resolution (HR) image from a shift-related low resolution (LR) image sequence. The aliasing relationship of Fourier transforms between discrete and continuous images in the frequency domain is used for mapping LR images to a HR image. The method of projection onto convex sets (POCS) is applied to trace the best estimate of pixel matching from the LR images to the reconstructed HR image. Computer simulations and preliminary experimental results have shown that the algorithm works effectively on the application of post-image-captured processing for CMOS cameras. It can also be applied to HR digital image reconstruction, where shift information of the LR image sequence is known.

Smallest disentangling state spaces for general entangled bipartite quantum states

Entangled quantum states can be given a separable decomposition if we relax the restriction that the local operators be quantum states. Motivated by the construction of classical simulations and local hidden variable models, we construct `smallest' local sets of operators that achieve this. In other words, given an arbitrary bipartite quantum state we construct convex sets of local operators that allow for a separable decomposition, but that cannot be made smaller while continuing to do so. We then consider two further variants of the problem where the local state spaces are required to contain the local quantum states, and obtain solutions for a variety of cases including a region of pure states around the maximally entangled state. The methods involve calculating certain forms of cross norm. Two of the variants of the problem have a strong relationship to theorems on ensemble decompositions of positive operators, and our results thereby give those theorems an added interpretation. The results generalise those obtained in our previous work on this topic [New J. Phys. 17, 093047 (2015)].