The bisection method applies to onedimensional convex problems of the form

where x_l < x_u are both finite, and f : R → R is convex. The algorithm is initialized with the upper and lower bounds on x: x = x_l , x̅ = x_u, and the initial x is set as the midpoint

Then, the algorithm updates the bounds as follows: a sub-gradient g of f at x is evaluated; if g < 0, we set x = x; otherwise, we  set x̅ = x. Then the midpoint x is recomputed, and the process is iterated until convergence.

1. Show that the bisection method locates a solution x* within accuracy ϵ in at most log₂(x_u – x_l)/ϵ – 1 steps.

2. Propose a variant of the bisection method for solving the unconstrained problem minx f (x), for convex f .
3. Write a code to solve the problem with the specific class of functions f : R → R, with values

where A, B, C are given n x m matrices, with every element of A non-negative.

Transcribed Image Text:

min f(x) x ≤ x ≤ xu < < : x