NDLI: Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety

Please wait, while we are loading the content...

Building Bridges between Symbolic Computation and Satisfiability Checking

Nonnegative Matrix Factorization: Algorithms, Complexity and Applications

Error-Correcting Sparse Interpolation in the Chebyshev Basis

Algorithms for Finite Field Arithmetic

Exact Linear Algebra Algorithmic: Theory and Practice

Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication

Optimization Problems over Noncompact Semialgebraic Sets

An Introduction to Finite Element Methods

Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets

Formal Solutions of Linear Differential Systems with Essential Singularities in their Coefficients

Removing Apparent Singularities of Systems of Linear Differential Equations with Rational Function Coefficients

Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences

A Fast Algorithm for Computing the P-curvature

Algebraic Diagonals and Walks

Open Non-uniform Cylindrical Algebraic Decompositions

Structure of Polyzetas and Explicit Representation on Transcendence Bases of Shuffle and Stuffle Algebras

p-Adic Stability In Linear Algebra

On þ-adic Expansions of Algebraic Integers

A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms

Computer Algebra Applied to a Solitary Waves Study

Graph-Coloring Ideals: Nullstellensatz Certificates, Gröbner Bases for Chordal Graphs, and Hardness of Gröbner Bases

Amenability of Schreier Graphs and Strongly Generic Algorithms for the Conjugacy Problem

Computing the Rank Profile Matrix

Minkowski Decomposition and Geometric Predicates in Sparse Implicitization

Improving the Use of Equational Constraints in Cylindrical Algebraic Decomposition

Real Quantifier Elimination by Computation of Comprehensive Gröbner Systems

Computation of Dimension in Filtered Free Modules by Gröbner Reduction

Separable Automorphisms on Matrix Algebras over Finite Field Extensions: Applications to Ideal Codes.

Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms

Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety

Certifying Isolated Singular Points and their Multiplicity Structure

Real Root Finding for Rank Defects in Linear Hankel Matrices

Constructing All Composition Series of a Finite Group

Computing Hypergeometric Solutions of Second Order Linear Differential Equations using Quotients of Formal Solutions

An Algorithm to Check Whether a Basis of a Parametric Polynomial System is a Comprehensive Gröbner Basis and the Associated Completion Algorithm

Integral D-Finite Functions

On the Sign of a Trigonometric Expression

Implementation of the DKSS Algorithm for Multiplication of Large Numbers

Formulas for Continued Fractions: An Automated Guess and Prove Approach

De Nugis Groebnerialium 4: Zacharias, Spears, Möller

Computing Logarithmic Vector Fields Associated with Parametric Semi-Quasihomogeneous Hypersurface Isolated Singularities

Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields

Data-Discriminants of Likelihood Equations

Green's Functions for Stieltjes Boundary Problems

Matrices with Two Nonzero Entries per Row

Near Optimal Subdivision Algorithms for Real Root Isolation

A Relaxed Algorithm for Online Matrix Inversion

Subtropical Real Root Finding

Matrix-F5 Algorithms and Tropical Gröbner Bases Computation

Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety

Content Provider	ACM Digital Library
Author	Guo, Feng Wang, Chu Zhi, Lihong Safey El Din, Mohab
Abstract	We consider the problem of optimizing a parametric linear function over a non-compact real trace of an algebraic set. Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the optimal value function. Rostalski and Sturmfels showed that when the algebraic set is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the algebraic set. First, we generalize this approach to non-compact situations. We prove that the graph of the opposite of the optimal value function is still contained in the affine cone over a dual variety similar to the one considered in compact case. In consequence, we present an algorithm for solving the considered parametric optimization problem for generic parameters' values. For some special parameters' values, the representing polynomials of the dual variety can be identically zero, which give no information on the optimal value. We design a dedicated algorithm that identifies those regions of the parameters' space and computes for each of these regions a new polynomial defining the optimal value over the considered region.
Starting Page	205
Ending Page	212
Page Count	8
File Format	PDF
ISBN	9781450334358
DOI	10.1145/2755996.2756666
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Polynomial optimization Recession pointed cone Dual variety
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in