Duality in nonlinear programming

In this paper are defined new first- and second-order duals of the nonlinear programming problem with inequality constraints. We introduce a notion of a WD-invex problem. We prove weak, strong, converse, strict converse duality, and other theorems under the hypothesis that the problem is WD-invex. We obtain that a problem with inequality constraints is WD-invex if and only if weak duality holds between the primal and dual problems. We introduce a notion of a second-order WD-invex problem with inequality constraints. The class of WD-invex problems is strictly included in the class of second-order ones. We derive that the first-order duality results are satisfied in the second-order case.     

Multilinear programming: Duality theories

It has been pointed out that the text and proof of a proposition in Ref. 1 are worded ambiguously. The version below is intended to be clearer.     

Multilinear programming: Duality theories

A type of nonlinear programming problem, called multilinear, whose objective function and constraints involve the variables through sums of products is treated. It is a rather straightforward generalization of the linear programming problem. This, and the fact that such problems have recently been encountered in several fields of application, suggested their study, with particular emphasis on the analogies between them and linear problems. This paper develops one such analogy, namely a duality concept which includes its linear counterpart as a special case and also retains essentially all of the desirable characteristics of linear duality theory. It is, however, found that a primal then has several duals. The duals are arrived at by way of a game which is closely associated with a multilinear programming problem, but which differs in some respects from those generally treated in game theory. Its generalizations may in fact be of interest in their own right.Professor J. Stoer and an anonymous reviewer made helpful comments on an earlier version of this paper. Those comments are greatly appreciated.     

Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

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.     

On filter-successive linearization methods for nonlinear semidefinite programming

In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially effcient.     

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...     

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     

A sequential quadratic penalty method for nonlinear semidefinite programming

In this article, a nonlinear semidefinite program is reformulated into a mathematical program with a matrix equality constraint and a sequential quadratic penalty method is proposed to solve the latter problem. We discuss the differentiability and convexity of the penalty function. Necessary and sufficient conditions for the convergence of optimal values of penalty problems to that of the original semidefinite program are obtained. The convergence of optimal solutions of penalty problems to that of the original semidefinite program is also investigated. We show that any limit point of a sequence of stationary points of penalty problems satisfies the KKT optimality condition of the semidefinite program. Smoothed penalty problems that have the same order of smothness as the original semidefinite program are adopted. Corresponding results such as the convexity of the smoothed penalty function, the convergence of optimal values, optimal solutions and the stationary points of the smoothed penalty problems are obtained.     

Duality in nonlinear multiobjective programming using augmented Lagrangian functions

A vector-valued generalized Lagrangian is constructed for a nonlinear multiobjective programming problem. Using the Lagrangian, a multiobjective dual is considered. Without assuming differentiability, weak and strong duality theorems are established using Pareto efficiency.The research of the second author was partially supported a GTE/SLU grant while visiting St. Lawrence University in the summer of 1991.     

Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming

This paper aims at showing that the class of augmented Lagrangian functions for nonlinear semidefinite programming problems can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem. By means of the image space analysis, a global saddle point condition for the augmented Lagrangian function is investigated. It is shown that the existence of a saddle point is equivalent to a regular nonlinear separation of two suitable subsets of the image space. Without requiring the strict complementarity, it is proved that, under second order sufficiency conditions, the augmented Lagrangian function admits a local saddle point. The existence of global saddle points is then obtained under additional assumptions that do not require the compactness of the feasible set. Motivated by the result on global saddle points, we propose two modified primal-dual methods based on the augmented Lagrangian using different strategies and prove their convergence to a global solution and the optimal value of the original problem without requiring the boundedness condition of the multiplier sequence.     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming

We investigate in this paper global convergence properties of the augmented Lagrangian method for nonlinear semidefinite programming (NLSDP). Four modified augmented Lagrangian methods for solving NLSDP based on different algorithmic strategies are proposed. Possibly infeasible limit points of the proposed methods are characterized. It is proved that feasible limit points that satisfy the Mangasarian-Fromovitz constraint qualification are KKT points of NLSDP without requiring the boundedness condition of the multipliers. Preliminary numerical results are reported to compare the performance of the modified augmented Lagrangian methods.     

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     

On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming

In this paper, we present new convergence properties of the augmented Lagrangian method for nonlinear semidefinite programs (NSDP). Convergence to the approximately global solutions and optimal values of NSDP is first established for a basic augmented Lagrangian scheme under mild conditions, without requiring the boundedness condition of the multipliers. We then propose four modified augmented Lagrangian methods for NSDP based on different algorithmic strategies. We show that the same convergence of the proposed methods can be ensured under weaker conditions.     

Convex approximations in stochastic programming by semidefinite programming

The following question arises in stochastic programming: how can one approximate a noisy convex function with a convex quadratic function that is optimal in some sense. Using several approaches for constructing convex approximations we present some optimization models yielding convex quadratic regressions that are optimal approximations in L ₁, L _?? and L ₂ norm. Extensive numerical experiments to investigate the behavior of the proposed methods are also performed.     

Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.