The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform

V Jeyakumar - One of the best experts on this subject based on the ideXlab platform.

  • trust region problems with Linear Inequality constraints exact sdp relaxation global optimality and robust optimization
    Mathematical Programming, 2014
    Co-Authors: V Jeyakumar
    Abstract:

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonLinear optimization problems. It enjoys many attractive properties such as an exact semi-definite Linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra Linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with Linear Inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite Linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite Linear programming problem and so, their solutions can be validated in polynomial time.

  • trust region problems with Linear Inequality constraints exact sdp relaxation global optimality and robust optimization
    arXiv: Optimization and Control, 2013
    Co-Authors: V Jeyakumar
    Abstract:

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonLinear optimization problems. It enjoys many attractive properties such as an exact semi-definite Linear programming relaxation (SDP relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra Linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with Linear Inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite Linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust (LSP) or (SOCP) under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a SDP and so, their solutions can be validated in polynomial time.

Ashok Vardhan Makkuva - One of the best experts on this subject based on the ideXlab platform.

  • equivalence of additive combinatorial Linear inequalities for shannon entropy and differential entropy
    IEEE Transactions on Information Theory, 2018
    Co-Authors: Ashok Vardhan Makkuva
    Abstract:

    This paper addresses the correspondence between Linear inequalities for Shannon entropy and differential entropy for sums of independent group-valued random variables. We show that any balanced (with the sum of coefficients being zero) Linear Inequality for Shannon entropy holds if and only if its differential entropy counterpart also holds; moreover, any Linear Inequality for differential entropy must be balanced. In particular, our result shows that recently proved differential entropy inequalities by Kontoyiannis and Madiman can be deduced from their discrete counterparts due to Tao in a unified manner. Generalizations to certain abelian groups are also obtained. Our proof of extending inequalities for Shannon entropy to differential entropy relies on a result of Renyi which relates the Shannon entropy of a finely discretized random variable to its differential entropy and also helps in establishing that the entropy of the sum of quantized random variables is asymptotically equal to that of the quantized sum; the converse uses the asymptotics of the differential entropy of convolutions with weak additive noise.

  • equivalence of additive combinatorial Linear inequalities for shannon entropy and differential entropy
    arXiv: Information Theory, 2016
    Co-Authors: Ashok Vardhan Makkuva
    Abstract:

    This paper addresses the correspondence between Linear inequalities of Shannon entropy and differential entropy for sums of independent group-valued random variables. We show that any balanced (with the sum of coefficients being zero) Linear Inequality of Shannon entropy holds if and only if its differential entropy counterpart also holds; moreover, any Linear Inequality for differential entropy must be balanced. In particular, our result shows that recently proved differential entropy inequalities by Kontoyiannis and Madiman \cite{KM14} can be deduced from their discrete counterparts due to Tao \cite{Tao10} in a unified manner. Generalizations to certain abelian groups are also obtained. Our proof of extending inequalities of Shannon entropy to differential entropy relies on a result of Renyi \cite{Renyi59} which relates the Shannon entropy of a finely discretized random variable to its differential entropy and also helps in establishing the entropy of the sum of quantized random variables is asymptotically equal to that of the quantized sum; the converse uses the asymptotics of the differential entropy of convolutions with weak additive noise.

Sujit K Ghosh - One of the best experts on this subject based on the ideXlab platform.

  • efficient sampling methods for truncated multivariate normal and student t distributions subject to Linear Inequality constraints
    Journal of statistical theory and practice, 2015
    Co-Authors: Sujit K Ghosh
    Abstract:

    Sampling from a truncated multivariate distribution subject to multiple Linear Inequality constraints is a recurring problem in many areas in statistics and econometrics, such as the order-restricted regressions, censored data models, and shape-restricted nonparametric regressions. However, the sampling problem remains nontrivial due to the analytically intractable normalizing constant of the truncated multivariate distribution. We first develop an efficient rejection sampling method for the truncated univariate normal distribution, and analytically establish its superiority in terms of acceptance rates compared to some of the popular existing methods. We then extend our methodology to obtain samples from a truncated multivariate normal distribution subject to convex polytope restriction regions. Finally, we generalize the sampling method to truncated scale mixtures of multivariate normal distributions. Empirical results are presented to illustrate the superior performance of our proposed Gibbs sampler in...

Maziar Salahi - One of the best experts on this subject based on the ideXlab platform.

  • a fast eigenvalue approach for solving the trust region subproblem with an additional Linear Inequality
    Computational & Applied Mathematics, 2018
    Co-Authors: Maziar Salahi, Akram Taati
    Abstract:

    In this paper, we study the extended trust region subproblem (eTRS) in which the trust region intersects the Euclidean ball with a single Linear Inequality constraint. By reformulating the Lagrangian dual of eTRS as a two-parameter Linear eigenvalue problem, we state a necessary and sufficient condition for its strong duality in terms of an optimal solution of a Linearly constrained bivariate concave maximization problem. This results in an efficient algorithm for solving eTRS of large size whenever the strong duality is detected. Finally, some numerical experiments are given to show the effectiveness of the proposed method.

  • trust region subproblem with an additional Linear Inequality constraint
    Optimization Letters, 2016
    Co-Authors: Maziar Salahi, Saeed Fallahi
    Abstract:

    This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with a single Linear Inequality constraint. We present an efficient algorithm to solve the problem using a diagonalization scheme that requires solving a simple convex minimization problem. Attainment of the global optimality conditions is discussed. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.

  • a fast eigenvalue approach for solving the trust region subproblem with an additional Linear Inequality
    arXiv: Optimization and Control, 2015
    Co-Authors: Maziar Salahi, Akram Taati
    Abstract:

    In this paper, we study the extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with a single Linear Inequality constraint. By reformulating the Lagrangian dual of eTRS as a two-parameter Linear eigenvalue problem, we state a necessary and sufficient condition for its strong duality in terms of an optimal solution of a Linearly constrained bivariate concave maximization problem. This results in an efficient algorithm for solving eTRS of large size whenever the strong duality is detected. Finally, some numerical experiments are given to show the effectiveness of the proposed method.

A. Taati - One of the best experts on this subject based on the ideXlab platform.

  • An efficient algorithm for large-scale extended trust-region subproblems with non-intersecting Linear constraints
    Optimization Letters, 2021
    Co-Authors: S. Ansary Karbasy, A. Hamdi, M. Salahi, A. Taati
    Abstract:

    In this paper, we study the extended trust-region subproblem in which the trust-region intersects the ball with m Linear Inequality constraints (m-eTRS). We assume that the Linear constraints do not intersect inside the ball. We show that the optimal solution of m-eTRS can be found by solving one TRS, computing the local non-global minimizer of TRS if it exists and solving at most two TRSs with an additional Linear equality constraint (1-eqTRS). Both TRS and (1-eqTRS) are polynomially and efficiently solvable, thus the new algorithm significantly improves over the SOCP/SDP relaxation of Burer and Yang [Math Program 149(1-2):253–264, 2015]. on two classes of test problems, the efficiency of the proposed approach is compared with the SOCP/SDP relaxation and branch and bound algorithm of Beck and Pan [J Global Optim 69(2):309–342, 2017].

  • Local nonglobal minima for solving large-scale extended trust-region subproblems
    Computational Optimization and Applications, 2017
    Co-Authors: M. Salahi, A. Taati, Henry Wolkowicz
    Abstract:

    We study large-scale extended trust-region subproblems ( eTRS ) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust-region subproblem ( TRS ) but with an additional Linear Inequality constraint. It is well known that strong duality holds for the TRS   and that there are efficient algorithms for solving large-scale TRS   problems. It is also known that there can exist at most one local non-global minimizer ( LNGM ) for TRS . We combine this with known characterizations for strong duality for eTRS   and, in particular, connect this with the so-called hard case for TRS . We begin with a recent characterization of the minimum for the TRS   via a generalized eigenvalue problem and extend this result to the LNGM . We then use this to derive an efficient algorithm that finds the global minimum for eTRS   by solving at most three generalized eigenvalue problems.