Skip to main content
SpringerLink
Log in

Complexity of convex optimization using geometry-based measures and a reference point

  • Published:
Mathematical Programming Submit manuscript

Abstract.

Our concern lies in solving the following convex optimization problem:where P is a closed convex subset of the n-dimensional vector space X. We bound the complexity of computing an almost-optimal solution of G P in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given reference point x r that might be close to the feasible region and / or the almost-optimal level set. This contrasts with other complexity bounds for convex optimization that rely on data-based condition numbers or algebraic measures, and that do not take into account any a priori reference point information.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Freund, R.M.: On the primal-dual geometry of level sets in linear and conic optimization. SIAM J. Optimization, to appear

  2. Freund, R.M., Vera, J.R.: Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optimization 10(1), 155–176 (1999)

    Article  MATH  Google Scholar 

  3. Freund, R.M., Vera, J.R.: Some characterizations and properties of the ‘‘distance to ill-posedness’’ and the condition measure of a conic linear system. Math. Programming 86, 225–260 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Grötschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988

  5. Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994

  6. Renegar, J.: Some perturbation theory for linear programming. Math. Programming 65(1), 73–91 (1994)

    MATH  Google Scholar 

  7. Renegar, J.: Linear programming, complexity theory, and elementary functional analysis. Math. Programming 70(3), 279–351 (1995)

    Article  Google Scholar 

  8. Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. Society for Industrial and Applied Mathematics, Philadelphia, 2001

  9. Ye, Y.: Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Operations Res. 19, 38–52 (1994)

    MathSciNet  MATH  Google Scholar 

  10. Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optimization 12(3), 782–810 (2002)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MIT Sloan School of Management, 50 Memorial Drive, Cambridge, MA, 02142-1347, USA

    Robert M. Freund

Authors
  1. Robert M. Freund
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert M. Freund.

Additional information

Mathematics Subject Classification (2000): 90C, 90C05, 90C60

This research has been partially supported through the Singapore-MIT Alliance. Portions of this research were undertaken when the author was a Visiting Scientist at Delft University of Technology.

Received: 1, October 2001

Rights and permissions

Reprints and permissions

About this article

Cite this article

Freund, R. Complexity of convex optimization using geometry-based measures and a reference point. Math. Program., Ser. A 99, 197–221 (2004). https://doi.org/10.1007/s10107-003-0435-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-003-0435-1

Keywords

Search

Navigation