Robust optimization with applications to game theory

In this article, we investigate robust optimization equilibria with two players, in which each player can neither evaluate his opponent's strategy nor his own cost matrix accurately while may estimate a bounded set of the strategy or cost matrix. We obtain a result that solving this equilibria can be formulated as solving a second-order cone complementarity problem under an ellipsoid uncertainty set or a mixed complementarity problem under a box uncertainty set. We present some numerical results to illustrate the behaviour of robust optimization equilibria.     

A DC programming approach for feature selection in support vector machines learning

Feature selection consists of choosing a subset of available features that capture the relevant properties of the data. In supervised pattern classification, a good choice of features is fundamental for building compact and accurate classifiers. In this paper, we develop an efficient feature selection method using the zero-norm l ₀ in the context of support vector machines (SVMs). Discontinuity at the origin for l ₀ makes the solution of the corresponding optimization problem difficult to solve. To overcome this drawback, we use a robust DC (difference of convex functions) programming approach which is a general framework for non-convex continuous optimisation. We consider an appropriate continuous approximation to l ₀ such that the resulting problem can be formulated as a DC program. Our DC algorithm (DCA) has a finite convergence and requires solving one linear program at each iteration. Computational experiments on standard datasets including challenging feature-selection problems of the NIPS 2003 feature selection challenge and gene selection for cancer classification show that the proposed method is promising: while it suppresses up to more than 99% of the features, it can provide a good classification. Moreover, the comparative results illustrate the superiority of the proposed approach over standard methods such as classical SVMs and feature selection concave.     

Sparse recovery in probability via <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-minimization with Weibull random matrices for 0 &lt; <Emphasis Type="Italic">q</Emphasis> ≤ 1

Although Gaussian random matrices play an important role of measurement matrices in compressed sensing, one hopes that there exist other random matrices which can also be used to serve as the measurement matrices. Hence, Weibull random matrices induce extensive interest. In this paper, we first propose the l_2,q robust null space property that can weaken the D-RIP, and show that Weibull random matrices satisfy the l_2,q robust null space property with high probability. Besides, we prove that Weibull random matrices also possess the l _q quotient property with high probability. Finally, with the combination of the above mentioned properties, we give two important approximation characteristics of the solutions to the l _q -minimization with Weibull random matrices, one is on the stability estimate when the measurement noise e ∈ ? ⁿ needs a priori ||e||₂ ≤ ?, the other is on the robustness estimate without needing to estimate the bound of ||e||₂. The results indicate that the performance of Weibull random matrices is similar to that of Gaussian random matrices in sparse recovery.     

A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

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.     

Finite alogorithms for robust linear regression

In this paper Hubert's M-estimator for robust linear regression is analyzed. Newton type methods for solution of the problem are defined and analyzed, and finite convergence is proved. Numerical experiments with a large number of test problems demonstrate efficiency and indicate that this kind of approach may be useful also in solving thel ₁ problem.     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

The Exactness Property of the Vector Exact l1 Penalty Function Method in Nondifferentiable Invex Multiobjective Programming

In this article, the vector exact l₁ penalty function method used for solving nonconvex nondifferentiable multiobjective programming problems is analyzed. In this method, the vector penalized optimization problem with the vector exact l₁ penalty function is defined. Conditions are given guaranteeing the equivalence of the sets of (weak) Pareto optimal solutions of the considered nondifferentiable multiobjective programming problem and of the associated vector penalized optimization problem with the vector exact l₁ penalty function. This equivalence is established for nondifferentiable invex vector optimization problems. Some examples of vector optimization problems are presented to illustrate the results established in the article.     

Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

Partial inverse of a monotone operator

ForT a maximal monotone operator on a Hilbert spaceH andA a closed subspace ofH, the “partial inverse”T _A ofT with respect toA is introduced.T _A is maximal monotone. The proximal point algorithm, as it applies toT _A , results in a simple procedure, the “method of partial inverses”, for solving problems in which the object is to findx ∈ A andy ∈ A ^⊥ such thaty ∈ T(x). This method specializes to give new algorithms for solving numerous optimization and equilibrium problems.     

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.     

Smoothed penalty algorithms for optimization of nonlinear models

We introduce an algorithm for solving nonlinear optimization problems with general equality and box constraints. The proposed algorithm is based on smoothing of the exact l ₁-penalty function and solving the resulting problem by any box-constraint optimization method. We introduce a general algorithm and present theoretical results for updating the penalty and smoothing parameter. We apply the algorithm to optimization problems for nonlinear traffic network models and report on numerical results for a variety of network problems and different solvers for the subproblems.     

Optimizing Lyapunov functions for systems with structured uncertainties

The robust stability problem of a nominally linear system with nonlinear, time-varying structured perturbationsp _j ,j=1,...,q, is considered. The system is of the form $$\dot x = A_N x + \sum\limits_{j = 1}^q {p_j A_j x} .$$ When the Lyapunov direct method is utilized to solve the problem, the most frequently chosen Lyapunov function is some quadratic form. The paper presents a procedure of optimization of Lyapunov functions. Under some simple conditions, the weak convergence of the procedure is ensured, making the procedure effective in solving the robust stability problem. The procedure is simple, requiring only numerical routines such as inverting positive-definite symmetric matrices and determining the eigenvalues and eigenvectors of symmetric matrices. It is expected that the optimal Lyapunov function may be used in a robust linear feedback controller design. The examples demonstrate the effectiveness of the method. As shown when considering a system of dimension 24, the method is effective for large-scale systems.     

A reduced Hessian SQP method for inequality constrained optimization

This paper develops a reduced Hessian method for solving inequality constrained optimization problems. At each iteration, the proposed method solves a quadratic subproblem which is always feasible by introducing a slack variable to generate a search direction and then computes the steplength by adopting a standard line search along the direction through employing the l _∞ penalty function. And a new update criterion is proposed to generate the quasi-Newton matrices, whose dimensions may be variable, approximating the reduced Hessian of the Lagrangian. The global convergence is established under mild conditions. Moreover, local R-linear and superlinear convergence are shown under certain conditions.     

Remarks on estimating upper limit of norm of delayed connection weight matrix in the study of global robust stability of delayed neural networks

The question of estimating the upper limit of the norm ∥B∥₂ of the delayed connection weight matrix B, which is a key step in some recently reported global robust stability criteria for delayed neural networks (DNNs), is considered. An estimate of the upper limit of ∥B∥₂ was previously given by Cao, Huang and Qu. More recently Singh has presented an alternative estimate. Presently it is shown that an estimate of the upper limit of ∥B∥₂ may be found in some cases, which would be an improvement over each of the above-mentioned two estimates. Some observations concerning the determination of the least conservative upper limit of ∥B∥₂ are presented.     

A reduced gradient method for quadratic programs with quadratic constraints and lp-constrained lp-approximation problems

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l_p-constrained l_p-approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.     

Robust H∞ control for a class of switched nonlinear cascade systems via multiple Lyapunov functions approach

This paper addresses the problem of robust H_∞ control for a class of switched nonlinear cascade systems with parameter uncertainty using the multiple Lyapunov functions (MLFs) approach. Each subsystem under consideration is composed of two cascade-connected parts. The uncertain parameters are assumed to be in a known compact set and are allowed to enter the system nonlinearly. Based on the explicit construction of Lyapunov functions, which avoids solving the Hamilton-Jacobi equations, sufficient conditions for the solvability of the robust H_∞ control problem are presented. As an application, the hybrid robust H_∞ control problem for a class of uncertain non-switched nonlinear cascade systems is solved when no single continuous controller is effective. Finally, a numerical example is provided to demonstrate the feasibility of the proposed method.     

Characterizing robust set containments and solutions of uncertain linear programs without qualifications

Qualification-free dual characterizations are given for robust polyhedral set containments where a robust counterpart of an uncertain polyhedral set is contained in another polyhedral set or a polyhedral set is contained in a robust counterpart of an uncertain polyhedral set. These results are used to characterize robust solutions of uncertain linear programs, where the uncertainty is defined in terms of intervals or l₁-balls. The hidden separable sub-linearity of the robust counterparts allows qualification-free dual characterizations.     

On the chromatic number for a set of metric spaces

We study the problem of finding the chromatic number of a metric space with a forbidden distance. Using the linear-algebraic technique in combinatorics and convex optimization methods, we obtain a set of new estimates and observe the change of the asymptotic lower bound for the chromatic number of Euclidean space under the continuous change of the metric from l ₁ to l ₂.     

Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods

This paper is devoted to subexponential estimates in Shirshov’s height theorem. A word W is n-divisible if it can be represented in the form W = W ₀ W ₁ ?W _n , where W ₁ ? W ₂ ??? W _n . If an affine algebra A satisfies a polynomial identity of degree n, then A is spanned by non-n-divisible words of generators a ₁ ??? a _l . A. I. Shirshov proved that the set of non-n-divisible words over an alphabet of cardinality l has bounded height h over the set Y consisting of all words of degree ≤ n ? 1. We show that h < Φ (n, l), where Φ(n, l) = 2⁸⁷ l?n ^{12 log3 n+48}. Let l, n, and d ≥ n be positive integers. Then all words over an alphabet of cardinality l whose length is greater than ψ(n, d, l) are either n-divisible or contain the dth power of a subword, where ψ(n, d, l) = 2¹⁸ l(nd)^{3 log3(nd)+13} d ². In 1993, E. I. Zelmanov asked the following question in the Dniester Notebook: Suppose that F _2,m is a 2-generated associative ring with the identity x ^m = 0. Is it true that the nilpotency degree of F _2,m has exponential growth? We give the definitive answer to E. I. Zelmanov by this result. We show that the nilpotency degree of the l-generated associative algebra with the identity x ^d = 0 is smaller than ψ(d, d, l). This implies subexponential estimates on the nilpotency index of nil-algebras of arbitrary characteristic. Shirshov’s original estimate was just recursive; in 1982 a double exponent was obtained, and an exponential estimate was obtained in 1992. Our proof uses Latyshev’s idea of an application of the Dilworth theorem. We think that Shirshov’s height theorem is deeply connected to problems of modern combinatorics. In particular, this theorem is related to the Ramsey theory. We obtain lower and upper estimates of the number of periods of length 2, 3, n ? 1 in some non-n-divisible word. These estimates differ only by a constant.