On a Modified Subgradient Algorithm for Dual Problems via Sharp Augmented Lagrangian*

We study convergence properties of a modified subgradient algorithm, applied to the dual problem defined by the sharp augmented Lagrangian. The primal problem we consider is nonconvex and nondifferentiable, with equality constraints. We obtain primal and dual convergence results, as well as a condition for existence of a dual solution. Using a practical selection of the step-size parameters, we demonstrate the algorithm and its advantages on test problems, including an integer programming and an optimal control problem. *Partially Supported by 2003 UniSA ITEE Small Research Grant Ero2. Supported by CAPES, Brazil, Grant No. 0664-02/2, during her visit to the School of Mathematics and Statistics, UniSA.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Generalized sensitivity analysis of nonlinear programs using a sequence of quadratic programs

ABSTRACT

Local sensitivity information is obtained for KKT points of parametric NLPs that may exhibit active set changes under parametric perturbations; under appropriate regularity conditions, computationally relevant generalized derivatives of primal and dual variable solutions of parametric NLPs are calculated. Ralph and Dempe obtained directional derivatives of solutions of parametric NLPs exhibiting active set changes from the unique solution of an auxiliary quadratic program. This article uses lexicographic directional derivatives, a newly developed tool in nonsmooth analysis, to generalize the classical NLP sensitivity analysis theory of Ralph and Dempe. By viewing said auxiliary quadratic program as a parametric NLP, the results of Ralph and Dempe are applied to furnish a sequence of coupled QPs, whose unique solutions yield generalized derivative information for the NLP. A practically implementable algorithm is provided. The theory developed here is motivated by widespread applications of nonlinear programming sensitivity analysis, such as in dynamic control and optimization problems.     

Augmented Lagrangian Duality and Nondifferentiable Optimization Methods in Nonconvex Programming

In this paper we present augmented Lagrangians for nonconvex minimization problems with equality constraints. We construct a dual problem with respect to the presented here Lagrangian, give the saddle point optimality conditions and obtain strong duality results. We use these results and modify the subgradient and cutting plane methods for solving the dual problem constructed. Algorithms proposed in this paper have some advantages. We do not use any convexity and differentiability conditions, and show that the dual problem is always concave regardless of properties the primal problem satisfies. The subgradient of the dual function along which its value increases is calculated without solving any additional problem. In contrast with the penalty or multiplier methods, for improving the value of the dual function, one need not to take the penalty like parameter to infinity in the new methods. In both methods the value of the dual function strongly increases at each iteration. In the contrast, by using the primal-dual gap, the proposed algorithms possess a natural stopping criteria. The convergence theorem for the subgradient method is also presented.     

Multicategory ψ-Learning and Support Vector Machine: Computational Tools

Many margin-based binary classification techniques such as support vector machine (SVM) and ψ-learning deliver high performance. An earlier article proposed a new multicategory ψ-learning methodology that shows great promise in generalization ability. However,ψ-learning is computationally difficult because it requires handling a nonconvex minimization problem. In this article, we propose two computational tools for multicategory ψ-learning. The first one is based on d.c. algorithms and solved by sequential quadratic programming, while the second one uses the outer approximation method, which yields the global minimizer via sequential concave minimization. Numerical examples show the proposed algorithms perform well.     

Criteria for Unconstrained Global Optimization

We develop criteria for the existence and uniqueness of the global minima of a continuous bounded function on a noncompact set. Special attention is given to the problem of parameter estimation via minimization of the sum of squares in nonlinear regression and maximum likelihood. Definitions of local convexity and unimodality are given using the level set. A fundamental theorem of nonconvex optimization is formulated: If a function approaches the minimal limiting value at the boundary of the optimization domain from below and its Hessian matrix is positive definite at the point where the gradient vanishes, then the function has a unique minimum. It is shown that the local convexity level of the sum of squares is equal to the minimal squared radius of the regression curvature. A new multimodal function is introduced, the decomposition function, which can be represented as the composition of a convex function and a nonlinear function from the argument space to a space of larger dimension. Several general global criteria based on majorization and minorization functions are formulated.     

Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound

We consider a recent branch-and-bound algorithm of the authors for nonconvex quadratic programming. The algorithm is characterized by its use of semidefinite relaxations within a finite branching scheme. In this paper, we specialize the algorithm to the box-constrained case and study its implementation, which is shown to be a state-of-the-art method for globally solving box-constrained nonconvex quadratic programs. S. Burer was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

Relaxation in nonconvex optimal control problems described by fractional differential equations

We consider the minimization problem of an integral functional with integrand that is not convex in the control on solutions of a control system described by fractional differential equation with mixed nonconvex constraints on the control. A relaxation problem is treated along with the original problem. It is proved that, under general assumptions, the relaxation problem has an optimal solution, and that for each optimal solution there is a minimizing sequence of the original problem that converges to the optimal solution with respect to the trajectory, the control, and the functional in appropriate topologies simultaneously.     

On duality bound methods for nonconvex global optimization

A counter-example is given to several recently published results on duality bound methods for nonconvex global optimization.     

Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems

As computing resources continue to improve, global solutions for larger size quadrically constrained optimization problems become more achievable. In this paper, we focus on larger size problems and get accurate bounds for optimal values of such problems with the successive use of SDP relaxations on a parallel computing system called Ninf (Network-based Information Library for high performance computing).