skip to main content

On the stationarity for nonlinear optimization problems with polyhedral constraints
Abstract

For polyhedral constrained optimization problems and a feasible point$$\textbf{x}$$$x$, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\nabla _\varOmega f(\textbf{x})$$${\nabla }_{\Omega }f\left(x\right)$, has an orthogonal decomposition of the form$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$$\beta \left(x\right)+\phi \left(x\right)$. At a stationary point,$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$${\nabla }_{\Omega }f\left(x\right)=0$so$$\Vert \nabla _\varOmega f(\textbf{x})\Vert$$$‖{\nabla }_{\Omega }f\left(x\right)‖$reflects the distance to a stationary point. Away from a stationary point,$$\Vert \varvec{\beta }(\textbf{x})\Vert$$$‖\beta \left(x\right)‖$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert$$$‖\phi \left(x\right)‖$measure different aspects of optimality since$$\varvec{\beta }(\textbf{x})$$$\beta \left(x\right)$only vanishes when the KKT multipliers at$$\textbf{x}$$$x$have the correct sign, while$$\varvec{\varphi }(\textbf{x})$$$\phi \left(x\right)$only vanishes when$$\textbf{x}$$$x$is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\Vert \varvec{\beta }(\textbf{x})\Vert$$$‖\beta \left(x\right)‖$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert$$$‖\phi \left(x\right)‖$.

more » « less
Award ID(s):
NSF-PAR ID:
10415087
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Mathematical Programming
Volume:
205
Issue:
1-2
ISSN:
0025-5610
Format(s):
Medium: X Size: p. 107-134
Size(s):
p. 107-134
Sponsoring Org:
National Science Foundation
##### More Like this
1. Abstract

Using extensive numerical simulation of the Navier–Stokes equations, we study the transition from the Darcy’s law for slow flow of fluids through a disordered porous medium to the nonlinear flow regime in which the effect of inertia cannot be neglected. The porous medium is represented by two-dimensional slices of a three-dimensional image of a sandstone. We study the problem over wide ranges of porosity and the Reynolds number, as well as two types of boundary conditions, and compute essential features of fluid flow, namely, the strength of the vorticity, the effective permeability of the pore space, the frictional drag, and the relationship between the macroscopic pressure gradient$${\varvec{\nabla }}P$$$\nabla P$and the fluid velocityv. The results indicate that when the Reynolds number Re is low enough that the Darcy’s law holds, the magnitude$$\omega _z$$${\omega }_{z}$of the vorticity is nearly zero. As Re increases, however, so also does$$\omega _z$$${\omega }_{z}$, and its rise from nearly zero begins at the same Re at which the Darcy’s law breaks down. We also show that a nonlinear relation between the macroscopic pressure gradient and the fluid velocityv, given by,$$-{\varvec{\nabla }}P=(\mu /K_e)\textbf{v}+\beta _n\rho |\textbf{v}|^2\textbf{v}$$$-\nabla P=\left(\mu /{K}_{e}\right)v+{\beta }_{n}\rho {|v|}^{2}v$, provides accurate representation of the numerical data, where$$\mu$$$\mu$and$$\rho$$$\rho$are the fluid’s viscosity and density,$$K_e$$${K}_{e}$is the effective Darcy permeability in the linear regime, and$$\beta _n$$${\beta }_{n}$is a generalized nonlinear resistance. Theoretical justification for the relation is presented, and its predictions are also compared with those of the Forchheimer’s equation.

more » « less
2. Abstract

It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla$$${L}_{\beta ,\gamma }=-\text{div}{D}^{d+1+\gamma -n}\nabla$associated to a domain$$\Omega \subset {\mathbb {R}}^n$$$\Omega \subset {R}^{n}$with a uniformly rectifiable boundary$$\Gamma$$$\Gamma$of dimension$$d < n-1$$$d, the now usual distance to the boundary$$D = D_\beta$$$D={D}_{\beta }$given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$${D}_{\beta }{\left(X\right)}^{-\beta }={\int }_{\Gamma }{|X-y|}^{-d-\beta }d\sigma \left(y\right)$for$$X \in \Omega$$$X\in \Omega$, where$$\beta >0$$$\beta >0$and$$\gamma \in (-1,1)$$$\gamma \in \left(-1,1\right)$. In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$${L}_{\beta ,\gamma }$, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$${D}^{1-\gamma }$, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$$|D\nabla \left(ln\left(\frac{G}{{D}^{1-\gamma }}\right)\right){|}^{2}$satisfies a Carleson measure estimate on$$\Omega$$$\Omega$. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).

more » « less
3. Abstract

For a given material,controllable deformationsare those deformations that can be maintained in the absence of body forces and by applying only boundary tractions. For a given class of materials,universal deformationsare those deformations that are controllable for any material within the class. In this paper, we characterize the universal deformations in compressible isotropic implicit elasticity defined by solids whose constitutive equations, in terms of the Cauchy stress$$\varvec{\sigma }$$$\sigma$and the left Cauchy-Green strain$$\textbf{b}$$$b$, have the implicit form$$\varvec{\textsf{f}}(\varvec{\sigma },\textbf{b})=\textbf{0}$$$f\left(\sigma ,b\right)=0$. We prove that universal deformations are homogeneous. However, an important observation is that, unlike Cauchy (and Green) elasticity, not every homogeneous deformation is constitutively admissible for a given implicit-elastic solid. In other words, the set of universal deformations is material-dependent, yet it remains a subset of homogeneous deformations.

more » « less
4. Abstract

We introduce a distributional Jacobian determinant$detD{V}_{\beta }\left(Dv\right)$\det DV_{\beta}(Dv)in dimension two for the nonlinear complex gradient${V}_{\beta }\left(Dv\right)={|Dv|}^{\beta }\left({v}_{{x}_{1}},-{v}_{{x}_{2}}\right)$V_{\beta}(Dv)=\lvert Dv\rvert^{\beta}(v_{x_{1}},-v_{x_{2}})for any$\beta >-1$\beta>-1, whenever$v\in {W}_{\mathrm{loc}}^{1,2}$v\in W^{1\smash{,}2}_{\mathrm{loc}}and$\beta {|Dv|}^{1+\beta }\in {W}_{\mathrm{loc}}^{1,2}$\beta\lvert Dv\rvert^{1+\beta}\in W^{1\smash{,}2}_{\mathrm{loc}}.This is new when$\beta \ne 0$\beta\neq 0.Given any planar ∞-harmonic function 𝑢, we show that such distributional Jacobian determinant$detD{V}_{\beta }\left(Du\right)$\det DV_{\beta}(Du)is a nonnegative Radon measure with some quantitative local lower and upper bounds.We also give the following two applications.

Applying this result with$\beta =0$\beta=0, we develop an approach to build up a Liouville theorem, which improves that of Savin.Precisely, if 𝑢 is an ∞-harmonic function in the whole${\mathbb{R}}^{2}$\mathbb{R}^{2}with$\underset{R\to \mathrm{\infty }}{lim inf}\underset{c\in \mathbb{R}}{inf}\frac{1}{R}{⨍}_{B\left(0,R\right)}|u\left(x\right)-c|\mathit{d}x<\mathrm{\infty },$\liminf_{R\to\infty}\inf_{c\in\mathbb{R}}\frac{1}{R}\barint_{B(0,R)}\lvert u(x)-c\rvert\,dx<\infty,then$u=b+a\cdot x$u=b+a\cdot xfor some$b\in \mathbb{R}$b\in\mathbb{R}and$a\in {\mathbb{R}}^{2}$a\in\mathbb{R}^{2}.

Denoting by${u}_{p}$u_{p}the 𝑝-harmonic function having the same nonconstant boundary condition as 𝑢, we show that$detD{V}_{\beta }\left(D{u}_{p}\right)\to detD{V}_{\beta }\left(Du\right)$\det DV_{\beta}(Du_{p})\to\det DV_{\beta}(Du)as$p\to \mathrm{\infty }$p\to\inftyin the weak-⋆ sense in the space of Radon measure.Recall that${V}_{\beta }\left(D{u}_{p}\right)$V_{\beta}(Du_{p})is always quasiregular mappings, but${V}_{\beta }\left(Du\right)$V_{\beta}(Du)is not in general.

more » « less
5. Abstract

A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$$\left({a}_{1},{a}_{2},\dots ,{a}_{n}\right)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$${b}_{1}\le {b}_{2}\le \cdots \le {b}_{n}$satisfies$$b_i \le i$$${b}_{i}\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$${R}^{n}$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$$x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$$x=\left(a,b,\cdots ,b\right)$, which we refer to as$${\textbf{x}}$$$x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$$x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$$x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

more » « less