Minimax feature selection problem for constructing a classifier using support vector machines

A minimax feature selection problem for constructing a classifier using support vector machines is considered. Properties of the solutions of this problem are analyzed. An improvement of the saddle point search algorithm based on extending the bound for the step parameter is proposed. A new nondifferential optimization algorithm is developed that, together with the saddle point search algorithm, forms a hybrid feature selection algorithm. The efficiency of the algorithm for computing Dykstra’s projections as applied for the feature selection problem is experimentally estimated.     

On the optimality of some classes of invex problems

In this paper we define two notions: Kuhn–Tucker saddle point invex problem with inequality constraints and Mond–Weir weak duality invex one. We prove that a problem is Kuhn–Tucker saddle point invex if and only if every point, which satisfies Kuhn–Tucker optimality conditions forms together with the respective Lagrange multiplier a saddle point of the Lagrange function. We prove that a problem is Mond–Weir weak duality invex if and only if weak duality holds between the problem and its Mond–Weir dual one. Additionally, we obtain necessary and sufficient conditions, which ensure that strong duality holds between the problem with inequality constraints and its Wolfe dual. Connections with previously defined invexity notions are discussed.     

On structure-oriented hybrid two-stage iteration methods for the large and sparse blocked system of linear equations

In this paper, we first present a class of structure-oriented hybrid two-stage iteration methods for solving the large and sparse blocked system of linear equations, as well as the saddle point problem as a special case. And the new methods converge to the solution under suitable restrictions, for instance, when the coefficient matrix is positive stable matrix generally. Numerical experiments for a model generalized saddle point problem are given, and the results show that our new methods are feasible and efficient, and converge faster than the Classical Uzawa Method.     

Convergence results for a self-dual regularization of convex problems

We study a one-parameter regularization technique for convex optimization problems whose main feature is self-duality with respect to the Legendre–Fenchel conjugation. The self-dual technique, introduced by Goebel, can be defined for both convex and saddle functions. When applied to the latter, we show that if a saddle function has at least one saddle point, then the sequence of saddle points of the regularized saddle functions converges to the saddle point of minimal norm of the original one. For convex problems with inequality and state constraints, we apply the regularization directly on the objective and constraint functions, and show that, under suitable conditions, the associated Lagrangians of the regularized problem hypo/epi-converge to the original Lagrangian, and that the associated value functions also epi-converge to the original one. Finally, we find explicit conditions ensuring that the regularized sequence satisfies Slater's condition.     

Existence of a Saddle Point in Nonconvex Constrained Optimization

The existence of a saddle point in nonconvex constrained optimization problems is considered in this paper. We show that, under some mild conditions, the existence of a saddle point can be ensured in an equivalent p-th power formulation for a general class of nonconvex constrained optimization problems. This result expands considerably the class of optimization problems where a saddle point exists and thus enlarges the family of nonconvex problems that can be solved by dual-search methods.     

Hölder Continuity of the Saddle Point Set for Real-Valued Functions

This paper is concerned with Hölder continuity of the solution to a saddle point problem. Some new su?cient conditions for the uniqueness and Hölder continuity of the solution for a perturbed saddle point problem are established. Applications of the result on Hölder continuity of the solution for perturbed constrained optimization problems are presented under mild conditions. Examples are given to illustrate the obtained results.     

Saddle points for vector valued functions: existence, necessary and sufficient theorems

Necessary and sufficient conditions for a point to be a weak saddle point of a vector valued function (i.e. to be a solution of the vector saddle point problem) are given. Also, an existence result for a vector saddle point to have a solution is given.     

Saddle points of general augmented Lagrangians for constrained nonconvex optimization

Local and global saddle point conditions for a general augmented Lagrangian function proposed by Mangasarian are investigated in the paper for inequality and equality constrained nonconvex optimization problems. Under second order sufficiency conditions, it is proved that the augmented Lagrangian admits a local saddle point, but without requiring the strict complementarity condition. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the original problem.     

Separation Approach for Augmented Lagrangians in Constrained Nonconvex Optimization

This paper aims at showing that the class of augmented Lagrangian functions, introduced by Rockafellar and Wets, can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem; hence, it is part of a more general theory. By means of the image space analysis, local and global saddle-point conditions for the augmented Lagrangian function are investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Under second-order sufficiency conditions in the image space, it is proved that the augmented Lagrangian admits a local saddle point. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set.     

A note on the existence of saddle points of p-th power Lagrangian for constrained nonconvex optimization

Li and Sun [D. Li and X.L. Sun, Existence of a saddle point in nonconvex constrained optimization, J. Global Optim. 21 (2001), pp. 39--50; D. Li and X.L. Sun, Convexification and existence of saddle point in a p-th-power reformulation for nonconvex constrained optimization, Nonlinear Anal. 47 (2001), pp. 5611--5622], present the existence of a global saddle point of the p-th power Lagrangian functions for constrained nonconvex optimization, under second-order sufficiency conditions and additional conditions that the feasible set is compact and the global solution of the primal problem is unique. In this article, it is shown that the same results can be obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the primal problem.     

Duality and saddle-point type optimality for interval-valued programming

In this paper, Mond-Weir’s type dual in programming problem with an interval-valued objective function and interval-valued inequality constrict conditions is formulated. Duality theorems are established under suitable conditions. A real-valued Lagrangian function for the interval-valued programming is defined. Further, the saddle point of Lagrangian function is also defined and saddle point optimality conditions are presented.     

Semi-convergence analysis of the Uzawa-SOR methods for singular saddle point problems

Recently, Zhang and Shang proposed a class of Uzawa-SOR methods for solving the nonsingular saddle point problems; see Zhang and Shang (2010). In this paper, we give the semi-convergence analysis of this method when it is applied to solve the singular saddle point problems under some conditions. Finally, numerical experiments are presented to illustrate the feasibility and effectiveness of this method.     

近似锥一次类凸集值向量优化问题强有效解的广义鞍点刻画

本文研究了近似锥一次类凸集值向量优化强有效解的广义鞍点表示问题.利用择一定理,得到了近似锥-次类凸集值优化问题强有效解为广义鞍点的充分条件和必要条件.所得结果丰富了集值优化理论,并且拓广了广义鞍点的应用.     

A new alternating positive semidefinite splitting preconditioner for saddle point problems from time-harmonic eddy current models

Based on the special positive semidefinite splittings of the saddle point matrix, we propose a new alternating positive semidefinite splitting (APSS) iteration method for the saddle point problem arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current problem. We prove that the new APSS iteration method is unconditionally convergent for both cases of the simple topology and the general topology. The new APSS matrix can be used as a preconditioner to accelerate the convergence rate of Krylov subspace methods. Numerical results show that the new APSS preconditioner is superior to the existing preconditioners.     

Saddle point and exact penalty representation for generalized proximal Lagrangians

In this paper, we introduce a generalized proximal Lagrangian function for the constrained nonlinear programming problem and discuss existence of its saddle points. In particular, the local saddle point is obtained by using the second-order sufficient conditions, and the global saddle point is given without requiring compactness of constraint set and uniqueness of the optimal solution. Finally, we establish equivalent relationship between global saddle points and exact penalty representations.     

Another approach to multiobjective programming problems withF-convex functions

In this paper, optimality conditions for multiobjective programming problems havingF-convex objective and constraint functions are considered. An equivalent multiobjective programming problem is constructed by a modification of the objective function. Furthermore, anF—Lagrange function is introduced for a constructed multiobjective programming problem, and a new type of saddle point is introduced. Some results for the new type of a saddle point are given.     

多目标半定规划的互补弱鞍点和G-鞍点最优性条件

对于含矩阵函数半定约束和多个目标函数的多目标半定规划问题，给出Lagrange函数在弱有效意义下的互补弱鞍点和Geofrrion恰当有效意义下的G-鞍点的定义及其等价定义．然后，在较弱的凸性条件下，利用含矩阵和向量约束的择一性定理，建立多目标半定规划的互补弱鞍点和G-鞍点充分必要条件．     

Discrete Approximation Scheme in Distributionally Robust Optimization

Discrete approximation, which has been the prevailing scheme in stochastic programming in the past decade, has been extended to distributionally robust optimization (DRO) recently. In this paper, we conduct rigorous quantitative stability analysis of discrete approximation schemes for DRO, which measures the approximation error in terms of discretization sample size. For the ambiguity set defined through equality and inequality moment conditions, we quantify the discrepancy between the discretized ambiguity sets and the original set with respect to the Wasserstein metric. To establish the quantitative convergence, we develop a Hoffman error bound theory with Hoffman constant calculation criteria in a infinite dimensional space, which can be regarded as a byproduct of independent interest. For the ambiguity set defined by Wasserstein ball and moment conditions combined with Wasserstein ball, we present similar quantitative stability analysis by taking full advantage of the convex property inherently admitted by Wasserstein metric. Efficient numerical methods for specifically solving discrete approximation DRO problems with thousands of samples are also designed. In particular, we reformulate different types of discrete approximation problems into a class of saddle point problems with completely separable structures. The stochastic primal-dual hybrid gradient (PDHG) algorithm where in each iteration we update a random subset of the sampled variables is then amenable as a solution method for the reformulated saddle point problems. Some preliminary numerical tests are reported.     

Inf–sup conditions for twofold saddle point problems

Necessary and sufficient conditions for existence and uniqueness of solutions are developed for twofold saddle point problems which arise in mixed formulations of problems in continuum mechanics. This work extends the classical saddle point theory to accommodate nonlinear constitutive relations and the twofold saddle structure. Application to problems in incompressible fluid mechanics employing symmetric tensor finite elements for the stress approximation is presented.     

广义不变凸多目标半无限规划的鞍点条件

利用广义代数运算,定义了一类不变凸函数和不完全向量值Lagrange函数的鞍点,研究了涉及此类函数的多目标半无限规划问题,得到了广义鞍点的必要性和充分性条件.在更弱的凸性条件下,得到了几个重要结果.