Optimality conditions and global convergence for nonlinear semidefinite programming

Mathematical Programming - Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear...     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

Optimality conditions for sparse nonlinear programming

The sparse nonlinear programming(SNP) is to minimize a general continuously differentiable function subject to sparsity, nonlinear equality and inequality constraints. We first define two restricted constraint qualifications and show how these constraint qualifications can be applied to obtain the decomposition properties of the Fréchet, Mordukhovich and Clarke normal cones to the sparsity constrained feasible set. Based on the decomposition properties of the normal cones, we then present and analyze three classes of Karush-KuhnTucker(KKT) conditions for the SNP. At last, we establish the second-order necessary optimality condition and sufficient optimality condition for the SNP.     

Optimality conditions for nonlinear infinite programming problems

An infinite programming problem consists in minimizing a functional defined on a real Banach space under an infinite number of constraints. The main purpose of this article is to provide sufficient conditions of optimality under generalized convexity assumptions. Such conditions are necessarily satisfied when the problem possesses the property that every stationary point is a global minimizer.     

Optimality conditions for piecewiseC 2 nonlinear programming

Several types of finite-dimensional nonlinear programming models are considered in this article. Second-order optimality conditions are derived for these models, under the assumption that the functions involved are piecewiseC ². In rough terms, a real-valued function defined on an open subsetW orR ⁿ is said to be piecewiseC ^k onW if it is continuous onW and if it can be constructed by piecing together onW a finite number of functions of classC ^k .     

Optimality conditions in smooth nonlinear programming

This survey is concerned with necessary and sufficient optimality conditions for smooth nonlinear programming problems with inequality and equality constraints. These conditions deal with strict local minimizers of order one and two and with isolated minimizers. In most results, no constraint qualification is required. The optimality conditions are formulated in such a way that the gaps between the necessary and sufficient conditions are small and even vanish completely under mild constraint qualifications.This paper is dedicated to the memory of W. Wetterling.The authors would like to thank Wolfgang Wetterling and Frank Twilt for fruitful discussions and an anonymous referee for many valuable comments.     

Optimality conditions for nondifferentiable minimax fractional programming with complex variables

We show that a minimax fractional programming problem is equivalent to a minimax nonfractional parametric problem for a given parameter in complex space. We establish the necessary and sufficient optimality conditions of nondifferentiable minimax fractional programming problem with complex variables under generalized convexities.     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

极小扰动约束非线性规划的最优性条件

考虑当目标函数在约束条件下的最优值作扰动时，使各约束作极小扰动的非线性规划问题．文中引进了极小扰动约束规划的极小扰动有效解概念．利用把问题归为一个相应的多目标规划问题，给出了极小扰动约束有效解的最优性条件．     

On a Newton-like method for constrained nonlinear minimization via slack variables

We show that Tapia's quasi-Newton diagonalized approach to constrained minimization can be formulated in such a way that no linear systems have to be solved of dimension larger than the natural ones or which present singularities. Numerical experiments indicate fast local convergence, but also substantial difficulties of global convergence.This work was supported by the National Science Council of Italy in the framework of the SOFTMAT project. Part of the work was done during visits at the Computer Science Department, Stanford University, and at the Numerical Optimization Centre, Hatfield Polytechnic; the author thanks Prof. G. Golub and Prof. L. Dixon for providing a stimulating atmosphere. Thanks are also due to Dr. M. Bertocchi, University of Bergamo, for collaboration in performing the numerical experiments.     

A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

 In this paper, we present a nonlinear programming algorithm for solving semidefinite programs (SDPs) in standard form. The algorithm's distinguishing feature is a change of variables that replaces the symmetric, positive semidefinite variable X of the SDP with a rectangular variable R according to the factorization X=RR ^T . The rank of the factorization, i.e., the number of columns of R, is chosen minimally so as to enhance computational speed while maintaining equivalence with the SDP. Fundamental results concerning the convergence of the algorithm are derived, and encouraging computational results on some large-scale test problems are also presented. Received: March 22, 2001 / Accepted: August 30, 2002 Published online: December 9, 2002 Key Words. semidefinite programming – low-rank factorization – nonlinear programming – augmented Lagrangian – limited memory BFGS This research was supported in part by the National Science Foundation under grants CCR-9902010, INT-9910084, CCR-0203426 and CCR-0203113     

Optimality conditions and Lagrangian duality in continuous-time nonlinear programming

Using a perturbation approach, the Kuhn-Tucker saddlepoint and stationary-point optimality conditions and a Lagrangian duality theory are established for a general class of continuous-time nonlinear programming problems. It is shown that most of the duality formulations in the existing literature of continuous programming are special cases of this Lagrangian formulation.     

A homotopy method for nonlinear semidefinite programming

In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl _e ib are done. Numerical results show that the proposed algorithm is feasible and applicable.     

Optimality conditions for non-lipschitz generalized convex programming via clarke-rockafellar gradients

For nonlinear programs with non-Lipschitz. generalized con\ex data functions. we develop various explicit first-order sufficient and /or necessary optimality conditions. These involve a natural generalization of the well known Karush-Kuhn-Tucker conditions, but with the familiar gradient condition modified so as to involve asymptotic (i.e. singular), as well as ordinary, Clarke-Rockafellar generalized gradients. In this way we cover situations in which the sets of ordinary generalized gradients are empty or unbounded, which can occur even at points where the functions are finite everywhere nearby. Along wit the use of asymptotic gradients, the novelty here lies in the identification of weak hypotheses on the data functions suitable for deriving such optimality results. In particular. the notions of protoconvexity is found to play a central role. along with the more familiar notions of quasiconvexity and’ pseudoconvexity     

Optimality conditions for quadratic programming

This paper establishes a set of necessary and sufficient conditions in order that a vectorx be a local minimum point to the general (not necessarily convex) quadratic programming problem:minimizep ^T x + 1/2x ^T Qx, subject to the constraintsHx h.     

Duality theories in nonlinear semidefinite programming

We consider the duality theories in nonlinear semidefinite programming. Some duality theorems are established to show the important relations among the optimal solutions and optimal values of the primal, the dual and the saddle point problems of nonlinear semidefinite programming.     

Ellipsoidal classification via semidefinite programming

We propose a classification approach exploiting relationships between ellipsoidal separation and Support-vector Machine (SVM) with quadratic kernel. By adding a (Semidefinite Programming) SDP constraint to SVM model we ensure that the chosen hyperplane in feature space represents a non-degenerate ellipsoid in input space. This allows us to exploit SDP techniques within Support-vector Regression (SVR) approaches, yielding better results in case ellipsoid-shaped separators are appropriate for classification tasks. We compare our approach with spherical separation and SVM on some classification problems.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

Exact augmented Lagrangian functions for nonlinear semidefinite programming

In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems into unconstrained nonlinear programming ones. Here, we first establish a unified framework for constructing these exact functions, generalizing Di Pillo and Lucidi’s work from 1996, that was aimed at solving nonlinear programming problems. Then, through our framework, we propose a practical augmented Lagrangian function for NSDP, proving that it is continuously differentiable and exact under the so-called nondegeneracy condition. We also present some preliminary numerical experiments.     

Optimality conditions for fractional minmax programming

Let V ?H be real separable Hilbert spaces. The abstract wave equation u′' + A(t)u = g(u), where u(t) ?V, A(t) maps V to its dual $\text{V}{}^1$, and g is a nonlinear map from the ball S(R₀) = {u?V: ∥u∥ < R₀} into H, is considered. It is assumed that g is locally Lipschitz in S(R₀) and possibly singular at the boundary. Local existence and continuation theorems are established for the Cauchy problem u(0) = u₀?S(R₀), u′(0) = u₁?H. Global existence is shown for g(u) = εφ(u), where φ has a potential and ε is small. Global nonexistence is shown for g(u) = εφ(u), where φ satisfies an abstract convexity property and ε is large.