Constrained Nonlinear Optimization

Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Frank Navarro Rojas
    • Categories Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    Generalized Nash Equilibrium Problems (GNEPs) are a generalization of the classic Nash Equilibrium Problems (NEPs), where each player’s strategy set depends on the choices of the other players. In this work we study constraint qualifications and optimality conditions tailored for GNEPs and we discuss their relations and implications for global convergence of algorithms. Surprisingly, differently … Read more

    On the local stability of semidefinite relaxations

  • Sameer Agarwal
  • Diego Cifuentes
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions … Read more

    Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

  • Gabor Pataki
  • Quoc Tran-Dinh
  • Yuzixuan (Melody) Zhu
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine … Read more

    Numerically tractable optimistic bilevel problems

  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , ,

    We consider fully convex lower level standard optimistic bilevel problems. We show that this class of mathematical programs is sufficiently broad to encompass significant real-world applications. We establish that the critical points of a relaxation of the original problem correspond to the equilibria of a suitably defined generalized Nash equilibrium problem. The latter game is … Read more

    Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis

  • Shiqian Ma
  • Junyu Zhang
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper we study nonconvex and nonsmooth multi-block optimization over Riemannian manifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. We develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings. First, we introduce … Read more

    Globally Solving the Trust Region Subproblem Using Simple First-Order Methods

  • Amir Beck
  • Yakov Vaisbourd
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We consider the trust region subproblem which is given by a minimization of a quadratic, not necessarily convex, function over the Euclidean ball. Based on the well-known second-order necessary and sufficient optimality conditions for this problem, we present two sufficient optimality conditions defined solely in terms of the primal variables. Each of these conditions corresponds … Read more

    Convergence Analysis of Processes with Valiant Projection Operators in Hilbert Space

  • Yair Censor
  • Rafiq Mansour
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    Convex feasibility problems require to find a point in the intersection of a finite family of convex sets. We propose to solve such problems by performing set-enlargements and applying a new kind of projection operators called valiant projectors. A valiant projector onto a convex set implements a special relaxation strategy, proposed by Goffin in 1971, … Read more

    A sequential optimality condition related to the quasinormality constraint qualification and its algorithmic consequences

  • Roberto Andreani
  • N. S. Fazzio
  • María Laura Schuverdt
  • Leonardo D. Secchin
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In the present paper, we prove that the augmented Lagrangian method converges to KKT points under the quasinormality constraint qualification, which is associated with the external penalty theory. For this purpose, a new sequential optimality condition for smooth constrained optimization, called PAKKT, is defined. The new condition takes into account the sign of the dual … Read more

    Portfolio Optimization with Entropic Value-at-Risk

  • Ahmadi-Javid Amir
  • Fallah-Tafti Malihe
    • Categories Constrained Nonlinear Optimization, Finance and Economics, Stochastic Programming

    The entropic value-at-risk (EVaR) is a new coherent risk measure, which is an upper bound for both the value-at-risk (VaR) and conditional value-at-risk (CVaR). As important properties, the EVaR is strongly monotone over its domain and strictly monotone over a broad sub-domain including all continuous distributions, while well-known monotone risk measures, such as VaR and … Read more

    Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

  • Pavel Dvurechensky
  • Alexander Gasnikov
  • Alexander Tiurin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … Read more