Robustness to uncertain optimization using scalarization techniques and relations to multiobjective optimization

In this paper, we propose two kinds of robustness concepts by virtue of the scalarization techniques (Benson’s method and elastic constraint method) in multiobjective optimization, which can be characterized as special cases of a general non-linear scalarizing approach. Moreover, we introduce both constrained and unconstrained multiobjective optimization problems and discuss their relations to scalar robust optimization problems. Particularly, optimal solutions of scalar robust optimization problems are weakly efficient solutions for the unconstrained multiobjective optimization problem, and these solutions are efficient under uniqueness assumptions. Two examples are employed to illustrate those results. Finally, the connections between robustness concepts and risk measures in investment decision problems are also revealed.     

Exterior penalty in optimal control problem with state-control constraints

We consider an abstract optimal control problem with additional equality and inequality state and control constraints, we use the exterior penalty function to transform the constrained optimal control problem into a sequence of unconstrained optimal control problems, under conditions in control lie in L ₁, the sequence of the solution to the unconstrained problem contains a subsequence converging of the solution of constrained problem, this convergence is strong when the problemis non convex, and is weak if the problemis convex in control. This generalizes the results of P.Nepomiastcthy [4] where he considered the control in the Hilbert space L ²(I,? ^m ).     

Selected topics in robust convex optimization

Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but- bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional chance constrained settings of problems with stochastic data, and (4) a novel generic application of the RO methodology in Robust Linear Control.      

An approach to constrained global optimization based on exact penalty functions

In the field of global optimization many efforts have been devoted to solve unconstrained global optimization problems. The aim of this paper is to show that unconstrained global optimization methods can be used also for solving constrained optimization problems, by resorting to an exact penalty approach. In particular, we make use of a non-differentiable exact penalty function ${P_q(x;\varepsilon)}$ . We show that, under weak assumptions, there exists a threshold value ${\bar \varepsilon >0 }$ of the penalty parameter ${\varepsilon}$ such that, for any ${\varepsilon \in (0, \bar \varepsilon]}$ , any global minimizer of P _q is a global solution of the related constrained problem and conversely. On these bases, we describe an algorithm that, by combining an unconstrained global minimization technique for minimizing P _q for given values of the penalty parameter ${\varepsilon}$ and an automatic updating of ${\varepsilon}$ that occurs only a finite number of times, produces a sequence {x ^k } such that any limit point of the sequence is a global solution of the related constrained problem. In the algorithm any efficient unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. Some numerical experimentation confirms the effectiveness of the approach.     

One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations

The ? ₁-synthesis model and the ? ₁-analysis model recover structured signals from their undersampled measurements. The solution of the former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in the presence of measurement noise, to be robust. The condition is one–for–all in the sense that it applies to both the ? ₁-synthesis and ? ₁-analysis models, to both constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity–norm optimization problem is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions is included.     

A constrained optimization reformulation and a feasible descent direction method for L_{1/2} regularization

In this paper, we first propose a constrained optimization reformulation to the \(L_{1/2}\) regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the \(L_{1/2}\) regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained \(L_{1/2}\) regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.     

On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

We propose a multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for stochastic optimization both with and without inequality constraints. The algorithm combines the smoothed functional (SF) scheme for estimating the gradient with the quasi-Newton method to solve the optimization problem. Newton algorithms typically update the Hessian at each instant and subsequently (a) project them to the space of positive definite and symmetric matrices, and (b) invert the projected Hessian. The latter operation is computationally expensive. In order to save computational effort, we propose in this paper a quasi-Newton SF (QN-SF) algorithm based on the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update rule. In Bhatnagar (ACM TModel Comput S. 18(1): 27–62, 2007), a Jacobi variant of Newton SF (JN-SF) was proposed and implemented to save computational effort. We compare our QN-SF algorithm with gradient SF (G-SF) and JN-SF algorithms on two different problems – first on a simple stochastic function minimization problem and the other on a problem of optimal routing in a queueing network. We observe from the experiments that the QN-SF algorithm performs significantly better than both G-SF and JN-SF algorithms on both the problem settings. Next we extend the QN-SF algorithm to the case of constrained optimization. In this case too, the QN-SF algorithm performs much better than the JN-SF algorithm. Finally we present the proof of convergence for the QN-SF algorithm in both unconstrained and constrained settings.     

A second-order smooth penalty function algorithm for constrained optimization problems

This paper introduces a second-order differentiability smoothing technique to the classical l ₁ exact penalty function for constrained optimization problems(COP). Error estimations among the optimal objective values of the nonsmooth penalty problem, the smoothed penalty problem and the original optimization problem are obtained. Based on the smoothed problem, an algorithm for solving COP is proposed and some preliminary numerical results indicate that the algorithm is quite promising.     

The exact penalty principle

The exact penalty approach aims at replacing a constrained optimization problem by an equivalent unconstrained optimization problem. Most results in the literature of exact penalization are mainly concerned with finding conditions under which a solution of the constrained optimization problem is a solution of an unconstrained penalized optimization problem, and the reverse property is rarely studied. In this paper, we study the reverse property. We give the conditions under which the original constrained (single and/or multiobjective) optimization problem and the unconstrained exact penalized problem are exactly equivalent. The main conditions to ensure the exact penalty principle for optimization problems include the global and local error bound conditions. By using variational analysis, these conditions may be characterized by using generalized differentiation.     

A coordinate gradient descent method for nonsmooth separable minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with ?₁-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report numerical experience with solving the ?₁-regularization of unconstrained optimization problems from Moré et al. in ACM Trans. Math. Softw. 7, 17–41, 1981 and from the CUTEr set (Gould and Orban in ACM Trans. Math. Softw. 29, 373–394, 2003). Comparison with L-BFGS-B and MINOS, applied to a reformulation of the ?₁-regularized problem as a bound-constrained optimization problem, is also reported.     

Optimality Conditions in Terms of Alternance: Two Approaches

In Optimization Theory, necessary and sufficient optimality conditions play an essential role. They allow, first of all, checking whether a point under study satisfies the conditions, and, secondly, if it does not, finding a “better” point. For the class of directionally differentiable functions, a necessary condition for an unconstrained minimum requires the directional derivative to be non-negative in all directions. This condition becomes efficient for special classes of directionally differentiable functions. For example, in the case of convex and max-type functions, the necessary condition for a minimum takes the form of inclusion. The problem of verifying this condition is reduced to that of finding the point of some convex and compact set C which is nearest to the origin. If the origin does not belong to C, we easily find the steepest descent direction, and are able to construct a numerical method. In the classical Chebyshev polynomial approximation problem, necessary optimality conditions are expressed in the form of alternation of signs of some values. In the present paper, a generalization of the alternance approach to a general optimization problem is given. Two equivalent forms of the alternance condition (the so-called inside form and the outside one) are discussed in detail. In some cases, it may be more convenient to use the conditions in the form of inclusion, in some other—the condition in the alternance form as in the Chebyshev approximation problem. Numerical methods based on the condition in the form of inclusion usually are “gradient-type” methods, while methods employing the alternance form are often “Newton-type”. It is hoped that in some cases it will be possible to enrich the existing armory of optimization algorithms by a new family of efficient tools. In the paper, we discuss only unconstrained optimization problems in the finite-dimensional setting. In many cases, a constrained optimization problem can be reduced (via Exact Penalization Techniques) to an unconstrained one.     

Mixed complementarity problems for robust optimization equilibrium in bimatrix game

In this paper, we investigate the bimatrix game using the robust optimization approach, in which each player may neither exactly estimate his opponent’s strategies nor evaluate his own cost matrix accurately while he may estimate a bounded uncertain set. We obtain computationally tractable robust formulations which turn to be linear programming problems and then solving a robust optimization equilibrium can be converted to solving a mixed complementarity problem under the l ₁ ∩ l _∞-norm. Some numerical results are presented to illustrate the behavior of the robust optimization equilibrium.     

Stability of properly efficient points and isolated minimizers of constrained vector optimization problems

In this paper the constrained vector optimization problem mic _C f(x), g(x) ? ? K, is considered, where\(f:\mathbb{R}^n \to \mathbb{R}^m \) and\(g:\mathbb{R}^n \to \mathbb{R}^p \) are locally Lipschitz functions and\(C \subset \mathbb{R}^m \) and\(K \subset \mathbb{R}^p \) are closed convex cones. Several solution concepts are recalled, among them the concept of a properly efficient point (p-minimizer) and an isolated minimizer (i-minimizer). On the base of certain first-order optimalitty conditions it is shown that there is a close relation between the solutions of the constrained problem and some unconstrained problem. This consideration allows to “double” the solution concepts of the given constrained problem, calling sense II optimality concepts for the constrained problem the respective solutions of the related unconstrained problem, retaining the name of sense I concepts for the originally defined optimality solutions. The paper investigates the stability properties of thep-minimizers andi-minimizers. It is shown, that thep-minimizers are stable under perturbations of the cones, while thei-minimizers are stable under perturbations both of the cones and the functions in the data set. Further, it is shown, that sense I concepts are stable under perturbations of the objective data, while sense II concepts are stable under perturbations both of the objective and the constraints. Finally, the so called structural stability is discused.     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite programming.     

New efficient numerical procedures for solving stochastic variational problems with a priori maximum pointwise error estimates

In a previous paper we gave a new formulation and derived the Euler equations and other necessary conditions to solve strong, pathwise, stochastic variational problems with trajectories driven by Brownian motion. Thus, unlike current methods which minimize the control over deterministic functionals (the expected value), we find the control which gives the critical point solution of random functionals of a Brownian path and then, if we choose, find the expected value.This increase in information is balanced by the fact that our methods are anticipative while current methods are not. However, our methods are more directly connected to the theory and meaningful examples of deterministic variational theory and provide better means of solution for free and constrained problems. In addition, examples indicate that there are methods to obtain nonanticipative solutions from our equations although the anticipative optimal cost function has smaller expected value.In this paper we give new, efficient numerical methods to find the solution of these problems in the quadratic case. Of interest is that our numerical solution has a maximal, a priori, pointwise error of O(h3/2) where h is the node size. We believe our results are unique for any theory of stochastic control and that our methods of proof involve new and sophisticated ideas for strong solutions which extend previous deterministic results by the first author where the error was O(h²).We note that, although our solutions are given in terms of stochastic differential equations, we are not using the now standard numerical methods for stochastic differential equations. Instead we find an approximation to the critical point solution of the variational problem using relations derived from setting to zero the directional derivative of the cost functional in the direction of simple test functions.Our results are even more significant than they first appear because we can reformulate stochastic control problems or constrained calculus of variations problems in the unconstrained, stochastic calculus of variations formulation of this paper. This will allow us to find efficient and accurate numerical solutions for general constrained, stochastic optimization problems. This is not yet being done, even in the deterministic case, except by the first author.     

Epsilon-Ritz Method for Solving a Class of Fractional Constrained Optimization Problems

In this paper, epsilon and Ritz methods are applied for solving a general class of fractional constrained optimization problems. The goal is to minimize a functional subject to a number of constraints. The functional and constraints can have multiple dependent variables, multiorder fractional derivatives, and a group of initial and boundary conditions. The fractional derivative in the problem is in the Caputo sense. The constrained optimization problems include isoperimetric fractional variational problems (IFVPs) and fractional optimal control problems (FOCPs). In the presented approach, first by implementing epsilon method, we transform the given constrained optimization problem into an unconstrained problem, then by applying Ritz method and polynomial basis functions, we reduce the optimization problem to the problem of optimizing a real value function. The choice of polynomial basis functions provides the method with such a flexibility that initial and boundary conditions can be easily imposed. The convergence of the method is analytically studied and some illustrative examples including IFVPs and FOCPs are presented to demonstrate validity and applicability of the new technique.     

Modular solvers for image restoration problems using the discrepancy principle

Many problems in image restoration can be formulated as either an unconstrained non‐linear minimization problem, usually with a Tikhonov‐like regularization, where the regularization parameter has to be determined; or as a fully constrained problem, where an estimate of the noise level, either the variance or the signal‐to‐noise ratio, is available. The formulations are mathematically equivalent. However, in practice, it is much easier to develop algorithms for the unconstrained problem, and not always obvious how to adapt such methods to solve the corresponding constrained problem. In this paper, we present a new method which can make use of any existing convergent method for the unconstrained problem to solve the constrained one. The new method is based on a Newton iteration applied to an extended system of non‐linear equations, which couples the constraint and the regularized problem, but it does not require knowledge of the Jacobian of the irregularity functional. The existing solver is only used as a black box solver, which for a fixed regularization parameter returns an improved solution to the unconstrained minimization problem given an initial guess. The new modular solver enables us to easily solve the constrained image restoration problem; the solver automatically identifies the regularization parameter, during the iterative solution process. We present some numerical results. The results indicate that even in the worst case the constrained solver requires only about twice as much work as the unconstrained one, and in some instances the constrained solver can be even faster. Copyright © 2002 John Wiley & Sons, Ltd.     

H∞ control for uncertain Takagi–Sugeno fuzzy systems with time-varying delays and nonlinear perturbations

This paper investigates the robust H_∞ control for Takagi–Sugeno (T–S) fuzzy systems with time-varying delays and nonlinear perturbations. Delay-dependent criteria for uncertain fuzzy systems have been proposed. The LMI optimization approach is applied to solve the H_∞ control problem and find the minimization of H_∞ norm bound. Computer simulations show that significant improvement over the previous results can be obtained.     

A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems

The aim of this paper is to develop an efficient algorithm for solving a class of unconstrained nondifferentiable convex optimization problems in finite dimensional spaces. To this end we formulate first its Fenchel dual problem and regularize it in two steps into a differentiable strongly convex one with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method with the aim of accelerating the resulting convergence scheme. The theoretical results are finally applied to an l ₁ regularization problem arising in image processing.