Search

This paper proposes a method for finding the global infimum of a multivariate polynomial f via sum of squares (SOS) relaxation over its truncated tangency variety. This variety is truncated of the set of all points x ∈ Rn where the level sets of f are tangent to the sphere in Rn centered in the origin and with radius x. It is demonstrated that: • The infimum of f on Rn and on its truncated tangency variety coincide. • A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge monotonically, increasing to the infimum of f. This opens up the possibility of solving previously intractable polynomial optimization problems. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

In this paper we study some second order conditions that may be added to the first order nessessary optimality condition 0 ∈ ∂p&fnop;(¯X) (with ∂pƒ denoting the proximal subdifferential) in order to obtain a sufficient condition for a strict local minimum for extended--real-valued, nonsmooth functions. Three different types of second order conditions are investigated, all based on a different second order subdifferential. Namely, the subhessian, the graphical derivative, and the (contingent) coderivative to the proximal subdifferential. [ABSTRACT FROM AUTHOR]

The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at hand that can be applied to general classes of functions. In this paper we show how to reduce the question of determining a convex envelope to lower-dimensional optimization problems when the underlying function is indefinite and (n-1)-convex. Our structural result about this reduction technique enables us to give descriptions for the convex envelope of a variety of two-dimensional functions. [ABSTRACT FROM AUTHOR]

In this paper, we present new convergence properties of the primal-dual method based on four types of augmented Lagrangian functions in the context of constrained global optimization. Convergence to a global optimal solution is first established for a basic primal-dual scheme under standard conditions. We then prove this convergence property for a modified augmented Lagrangian method using a safeguarding strategy without appealing to the boundedness assumption of the multiplier sequence. We further show that, under the same weaker conditions, the convergence to a global optimal solution can still be achieved by either modifying the multiplier updating rule or normalizing the multipliers in augmented Lagrangian methods. [ABSTRACT FROM AUTHOR]

This paper is concerned with the Lipschitzian behavior of the optimal set of convex semi-infinite optimization problems under continuous perturbations of the right-hand side of the constraints and linear perturbations of the objective function. In this framework we provide a sufficient condition for the metric regularity of the inverse of the optimal set mapping. This condition consists of the Slater constraint qualification, together with a certain additional requirement in the Karush-Kuhn-Tucker conditions. For linear problems this sufficient condition turns out to be also necessary for the metric regularity, and it is equivalent to some well-known stability concepts. [ABSTRACT FROM AUTHOR]

In this paper, we consider Levitin--Polyak-type well-posedness for a general constrained optimization problem. We introduce generalized Levitin--Polyak well-posedness and strongly generalized Levitin--Polyak well-posedness. Necessary and sufficient conditions for these types of well-posedness are given. Relations among these types of well-posedness are investigated. Finally, we consider convergence of a class of penalty methods and a class of augmented Lagrangian methods under the assumption of strongly generalized Levitin--Polyak well-posedness. [ABSTRACT FROM AUTHOR]

In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m x m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point, of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems. [ABSTRACT FROM AUTHOR]

We outline a new approach for radiosurgery treatment planning, based on solving a series of optimization problems. We consider a specific treatment planning problem for a specialized device known as the gamma knife which provides an advanced stereotactic approach to the treatment, of tumors, vascular malformations, and pain disorders within the head. Tile sequence of optimization problems involves nonlinear and mixed integer programs whose solution is required in a given planning time (typically less than 30 minutes). This paper outlines several modeling decisions that result in more efficient and robust, solutions. Furthermore, it, outlines a new approach for determining starting points for the nonlinear programs, based on a skeletonization of the target volume. Treatment plans generated for real patient data show the efficiency of the approach. [ABSTRACT FROM AUTHOR]

We introduce a new barrier-type function which is not, a barrier function in the usual sense: it has finite value at the boundary of the feasible region. Despite this, the iteration bound of a large-update interior-point method based on this function is shown to be O(square root of n (log n) log n/epsilon), which is as good as tile currently best known bound for large update methods. The recently introduced properly of exponential convexity for the kernel function underlying the barrier function, as well as the strong convexity of the kernel function, are crucial in the analysis. [ABSTRACT FROM AUTHOR]

We present efficiency criteria for multicriteria problems with 힎(T)-valued maps via directional derivatives and subdifferentials. It turns out that the essential structure of similar results known for ℝn-valued optimization problems remains valid. As an improvement, our formulas allow us to distinguish between efficient and weakly efficient elements. [ABSTRACT FROM AUTHOR]

A condition ensuring metric sub regularity (respectively, calmness) of general multifunction between Banach spaces is derived. This condition is expressed solely in terms of the given data at the reference point and does not involve any information concerning the solution set of the corresponding inclusion given by the multifunction. In finite dimensions this condition can be expressed in terms of a derivative which appears to be a combination of the co derivative and the contingent derivative. It is further shown that this sufficient condition is in some sense the weakest possible first order condition sufficient for sub regularity. We extend this condition under the additional assumption that one part of the multifunction is known to be sub regular in advice. We also derive second order conditions for metric sub regularity, both sufficient and necessary, for multifunction associated with constraint systems as they occur in optimization. We show that the main difference between the necessary and sufficient, conditions is the replacement of an inequality by a strict inequality, just as in the case of "no gap" second order optimality conditions in optimization. [ABSTRACT FROM AUTHOR]

We compare six state-of-the-art local optimization solvers, with a focus on there efficiency when invoked within an interval-based global optimization algorithm. For comparison purposes we design three special performance indicators: a solution check indicator (measuring whether the local minimizes found are good candidates for near-optimal verified feasible points), a function value indicator (measuring the contribution to the progress of the global search), and a running time indicator (estimating the computational cost of the local search within the global search). The solvers are compared on the COCONUT Environment test set consisting of 1307 problems. Our main goal is to predict the behavior of the solvers in terms of the three performances indicators on a new problem. For this we introduce a k-nearest neighbor method applied over a feature space consisting of several categorical and numerical features of the optimization problems. The quality and robustness of the prediction is demonstrated by various quality measurements with detailed comparative tests. In particular, we found that on the test set we are able to pick a "best" solver in 66 89% of the cases and avoid picking all "useless" solvers in 95-99% of the cases (when a useful alternative exists). The resulting automated solver selection method is implemented as an inference engine of the COCONUT Environment. [ABSTRACT FROM AUTHOR]

A new method for quasi-Newton minimization outperforms BFGS by combining least-change updates of the Hessian with step sizes estimated from a Wishart model of uncertainty. The Hessian update is in the Broyden family but uses a negative parameter, outside the convex range, that is usually regarded as the safe zone for Broyden updates. Although full Newton steps based on this update tend to be too long, excellent performance is obtained with shorter steps estimated from the Wishart model. In numerical comparisons to BFGS the new statistical quasi-Newton (SQN) algorithm typically converges with about 25% fewer iterations, functions, and gradient evaluations on the top 1/3 hardest unconstrained problems in the CUTE library. Typical improvement on the 1/3 easiest problems is about 5%. The framework used to derive SQN provides a simple way to understand differences among various Broyden updates such as BFGS and DFP and shows that these methods do not preserve accuracy of the Hessian, in a certain sense, while the new method does. In fact, BFGS, DFP, and all other updates with nonnegative Broyden parameters tend to inflate Hessian estimates, and this accounts for their observed propensity to correct eigenvalues that are too small more readily than eigenvalues that are too large. Numerical results on three new test functions validate these conclusions. [ABSTRACT FROM AUTHOR]

The aim of this article is to find explicit necessary conditions for local optimal pairs of problems governed by divergence-type elliptic PDEs, in terms depending on the nonlinearities involved in the cost functional and state equation. Several examples of optimization problems governed by ODEs and PDEs are presented. [ABSTRACT FROM AUTHOR]

We prove sharpness of efficient solutions xk to vector optimization problems resulting from Ekeland vector variational principles. We achieve this by sharpening some of the existing vector variational principles and showing that xk remains efficient not only for perturbations in the direction k but also for other directions of perturbations. [ABSTRACT FROM AUTHOR]

We study local weak sharp minima and sharp minima for smooth semi-infinite optimization problems SIP. We provide severed dual and primal characterizations for a point to be a sharp minimum or a weak sharp minimum of SIP. As applications, we present several sufficient and necessary conditions of calmness for infinitely many smooth inequalities. In particular, we improve some calmness results in [R. Henrion and J. Outrata, Math. Program., 104 (2005), pp. 437-464]. [ABSTRACT FROM AUTHOR]

We consider a smooth finite dimensional parametric optimization problem P(y) with objective function f(x, y). Here, x and y denote the state variable and the parameter, respectively. In the case that x̅ is a strongly stable Karush-Kuhn-Tucker point for P(y̅), a neighborhood of x̅ contains a unique Karush-Kuhn-Tucker point x(y) for P(y), provided that y is sufficiently close to y̅. This gives rise to the critical value function y ↦ φ(y) := f(x(y), y). Under the additional assumption that the Mangasarian-Fromovitz constraint qualification is satisfied at x̅, we show that φ has finite modulus of concavity. That means φ becomes convex in a neighborhood of y̅ by adding to it the function y ↦ (α/2) ⋅ ||y - y̅||² for some α > 0. Moreover, we present an explicit upper bound for the α to be used. The latter bound turns out to be sharp for problem data in general position. [ABSTRACT FROM AUTHOR]

Let f be a continuous function on $\Rl^n$, and suppose f is continuously differentiable on an open dense subset. Such functions arise in many applications, and very often minimizers are points at which f is not differentiable. Of particular interest is the case where f is not convex, and perhaps not even locally Lipschitz, but is a function whose gradient is easily computed where it is defined. We present a practical, robust algorithm to locally minimize such functions, based on gradient sampling. No subgradient information is required by the algorithm. When f is locally Lipschitz and has bounded level sets, and the sampling radius $\eps$ is fixed, we show that, with probability 1, the algorithm generates a sequence with a cluster point that is Clarke $\eps$-stationary. Furthermore, we show that if f has a unique Clarke stationary point $\bar x$, then the set of all cluster points generated by the algorithm converges to $\bar x$ as $\eps$ is reduced to zero. Numerical results are presented demonstrating the robustness of the algorithm and its applicability in a wide variety of contexts, including cases where f is not locally Lipschitz at minimizers. We report approximate local minimizers for functions in the applications literature which have not, to our knowledge, been obtained previously. When the termination criteria of the algorithm are satisfied, a precise statement about nearness to Clarke $\eps$-stationarity is available. A MATLAB implementation of the algorithm is posted at http://www.cs.nyu.edu/overton/papers/gradsamp/alg. [ABSTRACT FROM AUTHOR]

A basic closed semialgebraic subset S of $\R^n$ is defined by simultaneous polynomial inequalities $g_1\ge 0,\dotsc,g_m\ge 0$. We give a short introduction to Lasserre's method for minimizing a polynomial f on a compact set S of this kind. It consists of successively solving tighter and tighter convex relaxations of this problem which can be formulated as semidefinite programs. We give a new short proof for the convergence of the optimal values of these relaxations to the infimum $f^\ast$ of f on S which is constructive and elementary. In the case where f possesses a unique minimizer $x^\ast$, we prove that every sequence of "nearly" optimal solutions of the successive relaxations gives rise to a sequence of points in $\R^n$ converging to $x^\ast$. [ABSTRACT FROM AUTHOR]

We propose a semidefinite optimization approach to the problem of deriving tight moment inequalities for $P(X\in S)$, for a set S defined by polynomial inequalities and a random vector X defined on $\Omega\subseteq {\cal R}^n$ that has a given collection of up to kth-order moments. In the univariate case, we provide optimal bounds on $P(X\in S)$, when the first k moments of X are given, as the solution of a semidefinite optimization problem in k + 1 dimensions. In the multivariate case, if the sets S and $\Omega$ are given by polynomial inequalities, we obtain an improving sequence of bounds by solving semidefinite optimization problems of polynomial size in n, for fixed k. We characterize the complexity of the problem of deriving tight moment inequalities. We show that it is NP-hard to find tight bounds for $k\geq 4$ and $\Omega={\cal R}^n$ and for $k\geq 2$ and $\Omega={\cal R}^n_+,$ when the data in the problem is rational. For k = 1 and $\Omega={\cal R}^n_+$ we show that we can find tight upper bounds by solving n convex optimization problems when the set S is convex, and we provide a polynomial time algorithm when S and $\Omega$ are unions of convex sets, over which linear functions can be optimized efficiently. For the case k = 2 and $\Omega={\cal R}^n$, we present an efficient algorithm for finding tight bounds when S is a union of convex sets, over which convex quadratic functions can be optimized efficiently. [ABSTRACT FROM AUTHOR]

We develop an extended version of the extremal principle in variational analysis that can be treated as a variational counterpart to the classical separation results in the case of nonconvex sets and which plays an important role in the generalized differentiation theory and its applications to optimization-related problems. The main difference between the conventional extremal principle and the extended version developed below is that, instead of the translation of sets involved in the extremal systems, we allow deformations. The new version seems to be more flexible in various applications and covers, in particular, multiobjective optimization problems with general preference relations. In this way we obtain new necessary optimality conditions for constrained problems of multiobjective optimization with nonsmooth data and also for multiplayer multiobjective games. [ABSTRACT FROM AUTHOR]

A primal-dual active set method for quadratic problems with bound constraints is presented. Based on a guess on the active set, a primal dual pair (x, s) is computed that satisfies the first order optimality condition and the complementarity condition. If (x, s) is not, feasible, a new active sat is determined, and the process is iterated. Sufficient conditions for the iterations to stop in a finite number of steps with an optimal solution are provided. Computational experience indicates that this approach often requires only a few (less than 10) iterations to find the optimal solution. [ABSTRACT FROM AUTHOR]

For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They arc proved exact, in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that controls both the weight, of the penalty terms and the regularization of the nonsmooth terms. [ABSTRACT FROM AUTHOR]

We give second-order expansions for quite general nonsmooth functions from the VU-space decomposition point of view. The results depend or, primal dual gradient structure, which we relate to general concepts of second-order epi-derivatives and partly smooth functions. Expressions for the associated second order objects are given in terms of U-subspace Hessians. [ABSTRACT FROM AUTHOR]

Reoptimization techniques for an interior point, method applied to solving a sequence of linear programming problems are discussed. Conditions are giver, for problem perturbations that can be absorbed in merely one Newt, on step. The analysis is performed for both short-step and long step feasible path following methods. A practical procedure is then derived for an infeasible path-following method. It is applied in the context of crash start for several large-scale structured linear programs. Numerical results with OOPS, a new object oriented parallel solver, demonstrate the efficiency of the approach. For large structured linear programs, crash start leads to about 40% reduction in the number of iterations and translates into a 25% reduction of the solution time. The crash procedure parallelizes well, and speed ups between 3.1 3.8 on four processors are achieved. [ABSTRACT FROM AUTHOR]