Search

The focal point of this paper is the probabilistically constrained linear program (PCLP) and how it can be applied to control system, design under risk constraints. The PCLP is the counterpart of the classical linear program, where it is assumed that there is random uncertainty in the constraints and, therefore, the deterministic constraints are replaced by probabilistic ones. It is shown that for a wide class of probability density functions, called log-concave symmetric densities, the PCLP is a convex program. An equivalent formulation of the PCLP is also presented which provides insight into numerical implementation. This concept is applied to control system design. It is shown how the results in this paper can be applied to the design of controllers for discrete-time systems to obtain a closed loop system with a well-defined risk of violating the so-called property of svperstability. Furthermore, we address the problem of risk-adjusted pole placement. [ABSTRACT FROM AUTHOR]

This paper deals with a problem of guaranteed (robust) financial decision-making under model uncertainty. An efficient method is proposed for determining optimal robust portfolios of risky financial instruments in the presence of ambiguity (uncertainty) on the probabilistic model of the returns. Specifically, it is assumed that a nominal discrete return distribution is given, while the true distribution is only known to lie within a distance d from the nominal one, where the distance is measured according to the Kullback-Leibler divergence. The goal in this setting is to compute portfolios that are worst-case optimal in the mean-risk sense, that is, to determine portfolios that minimize the maximum with respect to all the allowable distributions of a weighted risk-mean objective. The analysis in the paper considers both the standard variance measure of risk and the absolute deviation measure. [ABSTRACT FROM AUTHOR]

In this paper we use the penalty approach to study three constrained minimization problems. A penalty function is said to have the exact penalty property [J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms, 2 vols., Springer-Verlag, Berlin, 1993] if there exists a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish a very simple sufficient condition for the exact penalty property. [ABSTRACT FROM AUTHOR]

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]

In this paper we discuss the issue of solving stochastic optimization problems by means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This is a well-studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo simulation is used); here we study the case where that assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme carry over to the optimization case, in the sense that convergence of approximating optimal solutions and optimal values to their true counterparts has the same rates as in pointwise estimation. We apply our results to two well-established sampling schemes, namely, Latin hypercube sampling and randomized quasi-Monte Carlo (QMC). The novelty of our work arises from the fact that, while there has been some work on the use of variance reduction techniques and QMC methods in stochastic optimization, none of the existing work--to the best of our knowledge--has provided a theoretical study on the effect of these techniques on rates of convergence for the optimization problem. We present numerical results for some two-stage stochastic programs from the literature to illustrate the discussed ideas. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Lagrangian-dual problem of a class of convex optimization problems. We first discuss the semismoothness of the Lagrangian-dual function φ. This property is then used to investigate the second-order properties of the Moreau--Yosida regularization ? of the function φ, e.g., the semismoothness of the gradient g of the regularized function ?. We show that φ and g are piecewise C² and semismooth, respectively, for certain instances of the optimization problem. We establish a relationship between the original problem and the Fenchel conjugate of the regularization of the corresponding Lagrangian dual problem. We also find some instances of the optimization problem whose Lagrangian-dual function φ is not piecewise smooth. However, its regularized function still possesses nice second-order properties. Finally, we provide an alternative way to study the semismoothness of the gradient under the structure of the epigraph of the dual function. [ABSTRACT FROM AUTHOR]

In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most O(n2log(x°}T s° /e) iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to O(nlog(x°}T s° /e). To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported. [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 presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

In this paper we study optimization problems with, equality and inequality constraints on a Banach space where the objective function and the binding constraints are either differentiable at the optimal solution or Lipschitz near the optimal solution. Necessary and sufficient optimality conditions and constraint qualifications in terms of the Michel-Penot subdifferential are given, and the results are applied to bilevel optimization problems. [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]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47-67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems allows for a special kind of duality framework. This paper explores the duality framework proposed by Freund, and proposes a particular form of the problem that exposes some useful properties of the gauge optimization framework (such as the variational properties of its value function), and yet maintains most of the generality of the abstract form of gauge optimization. [ABSTRACT FROM AUTHOR]

The multiobjective optimization model studied in this paper deals with simultaneous minimization of finitely many linear functions subject to an arbitrary number of uncertain linear constraints. We first provide a radius of robust feasibility guaranteeing the feasibility of the robust counterpart under affine data parametrization. We then establish dual characterizations of robust solutions of our model that are immunized against data uncertainty by way of characterizing corresponding solutions of robust counterpart of the model. Consequently, we present robust duality theorems relating the value of the robust model with the corresponding value of its dual problem. [ABSTRACT FROM AUTHOR]

In [SIAM J. Optim., 17 (2006), pp. 188-217] Audet and Dennis proposed the class of mesh adaptive direct search (MADS) algorithms for minimization of a nonsmooth function under general nonsmooth constraints. The notation used in the paper evolved since the preliminary versions, and, unfortunately, even though the statement of Proposition 4.2 is correct, it is not compatible with the final notation. The purpose of this note is to show that the proposition is valid. [ABSTRACT FROM AUTHOR]

This paper proposes two new constraint qualification conditions (CQs) which are useful for a unified study of CQs from both a convex analysis and a nonsmooth analysis point of view. Our CQs cover the existing CQs of Mangasarian–Fromovitz and Farkas–Minkowski types. Some sufficient conditions for the validity of the new CQs are given. Under these CQs, we derive formulae for computing and/or estimating the (basic and singular) subdifferentials of marginal/optimal value function in semi-infinite programming from some results of modern variational analysis and generalized differentiation. Examples are given to illustrate the obtained formulae. [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]

The recently introduced proximal average of two convex functions is a convex function with many useful properties. In this paper, we introduce and systematically study the proximal average for finitely many convex functions. The basic properties of the proximal average with respect to the standard convex-analytical notions (domain, Fenchel conjugate, subdifferential, proximal mapping, epi-continuity, and others) are provided and illustrated by several examples. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) min{x*Cx | x *Akx≥ 1, k = 0, 1,. . ., m, x ∈ Fn} and (2) max {x*Cx | x*Akχ ≤ 1, k = 0, 1,. . ., m, x ∈ 픞n}, where F is either the real field ℝ or the complex field ℂ, and Ak, C are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the Ak's are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by O(m²) when 픞 = ℝ, and by O(m) when 픞 = ℂ. Moreover, when two or more of the Ak's are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the Ak's are indefinite while other Ak's are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by O(1/ logm) for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. When two or more of the Ak's in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight. [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]

We present a new generating set search (GSS) approach for minimizing functions subject to linear constraints. GSS is a class of direct search optimization methods that includes generalized pattern search. One of our main contributions in this paper is a new condition to define the set of conforming search directions that admits several computational advantages. For continuously differentiable functions we also derive a bound relating a measure of stationarity, which is equivalent to the norm of the gradient of the objective in the unconstrained case, and a parameter used by GSS algorithms to control the lengths of the steps. With the additional assumption that the derivative is Lipschitz, we obtain a big-O bound. As a consequence of this relationship, we obtain subsequence convergence to a KKT point, even though GSS algorithms lack explicit gradient information. Numerical results indicate that the bound provides a reasonable estimate of stationarity. [ABSTRACT FROM AUTHOR]

This paper deals with approximate (ε-efficient) solutions of vector optimization problems. We introduce a new ε-efficiency concept which extends and unifies different approximate solution notions introduced in the literature. We obtain necessary and sufficient conditions via nonlinear scalarization, which allow us to study this new class of approximate solutions in a general framework, since any convexity hypothesis is required. Several examples are proposed to show the concepts introduced and the results attained. [ABSTRACT FROM AUTHOR]

The objectives of this paper are twofold. We devise a general framework for identifying locally optimal algorithmic parameters. Algorithmic parameters are treated as decision variables in a problem for which no derivative knowledge or existence is assumed. A derivative-free method for optimization seeks to minimize some measure of performance of the algorithm being fine-tuned. This measure is treated as a black-box and may be chosen by the user. Examples are given in the text. The second objective is to illustrate this framework by specializing it to the identification of locally optimal trust-region parameters in unconstrained optimization. The derivative-free method chosen to guide the process is the mesh adaptive direct search, a generalization of pattern search methods. We illustrate the flexibility of the latter and in particular make provision for surrogate objectives. Locally, optimal parameters with respect to overall computational time on a set of test problems are identified. Each function call may take several hours and may not always return a predictable result. A tailored surrogate function is used to guide the search towards a local solution. The parameters thus identified differ from traditionally used values, and allow one to solve a problem that remained otherwise unsolved in a reasonable time using traditional values. [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]

The problem of minimizing a conic function subject to an ellipsoidal constraint is discussed in this paper. The feasible set of this problem is divided into three different cases. Necessary and sufficient optimality conditions are obtained for different cases where there is a characterization of optimality for the basic case. These conditions provide a sound basis for the further development of efficient methods for trust-region subproblems of a conic model. [ABSTRACT FROM AUTHOR]

In this paper we consider a general optimization problem (OP) and study the convergence and approximation of optimal values and optimal solutions to changes in the cost function and the set of feasible solutions. By a "general" OP we mean that the cost function and the constraints are defined on a Hausdorff topological space. First we obtain convergence results for a general OP, and then we present an application of these results on the approximation of the optimal value and the optimal solutions for the so-called general capacity problem in metric spaces. [ABSTRACT FROM AUTHOR]

In this paper we prove global convergence for asynchronous parallel pattern search. In standard pattern search, decisions regarding the update of the iterate and the step-length control parameter are synchronized implicitly across all search directions. We lose this feature in asynchronous parallel pattern search since the search along each direction proceeds semiautonomously. By bounding the value of the step-length control parameter after any step that produces decrease along a single search direction, we can prove that all the processes share a common accumulation point and, if the function is continuously differentiable, that such a point is a stationary point of the standard nonlinear unconstrained optimization problem. [ABSTRACT FROM AUTHOR]

In this paper we introduce different relaxations of the concept of active constraint at a given point with respect to a certain linear inequality system with an arbitrary number of constraints. We show that these concepts provide useful local information in linear optimization, for instance conditions for a given feasible solution to be a unique, extreme point, optimal solution or a strongly unique optimal solution. [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]

This paper gives conditions ensuring the epiconvergence or P-convergence of sequences of convexly composite functions via the study of Painlevé-Kuratowski convergence of inverse images of sets. The convergence of multipliers of optimization problems associated with convexly composite functions is also established. [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]

Duality and penalty methods are popular in optimization. The study on duality and penalty methods for nonconvex multiobjective optimization problems is very limited, in this paper, we introduce vector valued nonlinear Lagrangian and penalty functions and formulate nonlinear Lagrangian dual problems and nonlinear penalty problems for multiobjective constrained optimization problems. We establish strong duality and exact penalization results. The strong duality is an inclusion between the set of infimum points of the original multiobjective constrained optimization problem and that of the nonlinear Lagrangian dual problem. Exact penalization is established via. a generalized calmness-type condition. [ABSTRACT FROM AUTHOR]

Cubic-regularization and trust-region methods with worst-case first-order complexity O(ε-3/2) and worst-case second-order complexity O(ε-3/2) have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic-regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. Asymptotic convergence and order of convergence results are also presented. Finally, some numerical experiments comparing the new algorithm with a well-established quadratic regularization method are shown. [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]

We present an algorithm for large-scale equality constrained optimization. The method is based on a characterization of inexact sequential quadratic programming (SQP) steps that can ensure global convergence. Inexact SQP methods are needed for large-scale applications for which the iteration matrix cannot be explicitly formed or factored and the arising linear systems must be solved using iterative linear algebra techniques. We address how to determine when a given inexact step makes sufficient progress toward a solution of the nonlinear program, as measured by an exact penalty function. The method is globalized by a line search. An analysis of the global convergence properties of the algorithm and numerical results are presented. [ABSTRACT FROM AUTHOR]

Sequences of generalized Lagrangian duals and their sums of squares (SOS) of polynomials relaxations for a polynomial optimization problem (POP) are introduced. The sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the sequence converge to the optimal value of the POP using a method from the penalty function approach. The sequence of SOS relaxations is transformed into a sequence of semidefinite programing (SDP) relaxations of the POP, which correspond to duals of modification and generalization of SDP relaxations given by Lasserre for the POP. [ABSTRACT FROM AUTHOR]

We present algorithms for solving a number of new models of facility location which generalize the classical Fermat-Torricelli problem. Our first approach involves using Nesterov's smoothing technique and the minimization majorization principle to build smooth approximations that are convenient for applying smooth optimization schemes. Another approach uses subgradient-type algorithms to cope directly with the nondifferentiability of the cost functions. Convergence results of the algorithms are proved and numerical tests are presented to show the effectiveness of the proposed algorithms. [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]

Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases, and other information retrieval and clustering applications. The problem is most naturally posed as continuous optimization. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (i) that it is equivalent to a problem in polyhedral combinatorics; (ii) that it is NP-hard; and (iii) that a polynomial-time local search heuristic exists. [ABSTRACT FROM AUTHOR]

We consider active set identification for linearly constrained optimization problems in the absence of explicit information about the derivative of the objective function. We begin by presenting some general results on active set identification that are not tied to any particular algorithm. These general results are sufficiently strong that, given a sequence of iterates converging to a Karush–Kuhn–Tucker point, it is possible to identify binding constraints for which there are nonzero multipliers. We then focus on generating set search methods, a class of derivative-free direct search methods. We discuss why these general results, which are posed in terms of the direction of steepest descent, apply to generating set search, even though these methods do not have explicit recourse to derivatives. Nevertheless, there is a clearly identifiable subsequence of iterations at which we can reliably estimate the set of constraints that are binding at a solution. We discuss how active set estimation can be used to accelerate generating set search methods and illustrate the appreciable improvement that can result using several examples from the CUTEr test suite. We also introduce two algorithmic refinements for generating set search methods. The first expands the subsequence of iterations at which we can make inferences about stationarity. The second is a more flexible step acceptance criterion. [ABSTRACT FROM AUTHOR]

We study approximations of optimization problems with probabilistic constraints in which the original distribution of the underlying random vector is replaced with an empirical distribution obtained from a random sample. We show that such a sample approximation problem with a risk level larger than the required risk level will yield a lower bound to the true optimal value with probability approaching one exponentially fast. This leads to an a priori estimate of the sample size required to have high confidence that the sample approximation will yield a lower bound. We then provide conditions under which solving a sample approximation problem with a risk level smaller than the required risk level will yield feasible solutions to the original problem with high probability. Once again, we obtain a priori estimates on the sample size required to obtain high confidence that the sample approximation problem will yield a feasible solution to the original problem. Finally, we present numerical illustrations of how these results can be used to obtain feasible solutions and optimality bounds for optimization problems with probabilistic constraints. [ABSTRACT FROM AUTHOR]

This work deals with bound constrained multiobjective optimization (MOP) of nonsmooth functions for problems where the structure of the objective functions either cannot be exploited, or are absent. Typical situations arise when the functions are computed as the result of a computer simulation. We first present definitions and optimality conditions as well as two families of single-objective formulations of MOP. Next, we propose a new algorithm called BiMads for the biobjective optimization (BOP) problem (i.e., MOP with two objective functions). The property that Pareto points may be ordered in BOP and not in MOP is exploited by our algorithm. BiMads generates an approximation of the Pareto front by solving a series of single-objective formulations of BOP. These single-objective problems are solved using the recent Mads (mesh adaptive direct search) algorithm for nonsmooth optimization. The Pareto front approximation is shown to satisfy some first order necessary optimality conditions based on the Clarke calculus. Finally, BiMads is tested on problems from the literature designed to illustrate specific difficulties encountered in biobjective optimization, such as a nonconvex or disjoint Pareto front, local Pareto fronts, or a nonuniform Pareto front. [ABSTRACT FROM AUTHOR]

We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach. [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]

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]