0

I want to solve an optimization problem using a gradient descent algorithm

maximize $$ max \log( \frac{Ax + b}{ Cx + b} ) $$ $$s. t. \quad 0 \le x \le 1 $$

where x is a vector and the inequalities are component-wise (i.e. all the elements of x are constrained to the interval [0,1])

I have learned that there are some ways to deal with such a problem (lagrangian, barrier functions, ...).

What is the best strategy that can be used ?

user164999
  • 1
  • I don´t know, if it is the best way of calculation, but in this case, I would use the KKT-conditions to solve the problem: http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions – callculus42 Jul 18 '14 at 01:46
  • This is way too general a question. The answer depends entirely on what your function $f$ is like. For instance if $f$ is a smooth, concave function, you can use methods based on first order conditions. If you have more specific information on $f$ I can suggest algorithms that might work "best". – wonko Jul 18 '14 at 14:40
  • Thanks wonko for the reply, I modified the question with a specific function. Just be aware that I want to use gradient descent (or ascent here) in particular. I already know another solution based on first order approximation which converted the non-concave function to a concave one (DC programming). Thanks. – user164999 Jul 20 '14 at 01:14
  • What type of object is $A$, a row vector? – littleO Jul 20 '14 at 01:31
  • Yes, A and C are row vectors. – user164999 Jul 20 '14 at 11:27
  • It might be worth reading about linear fractional functions in Boyd and Vandenberghe (which is free online). Also section 4.2.5 on quasiconvex optimization (including the bisection strategy on p. 145) might be relevant. – littleO Jul 21 '14 at 16:42

1 Answers1

0

The logarithm is monotonic, so this is equivalent to

$$\begin{align*} \text{maximize }\;&{Ax+b \over Cx+b}\\ \text{subject to }\;&x \in [0,1]^n \end{align*}$$

This in turn can be solved using a combination of binary search and linear programming. Suppose we want to know whether the value $\alpha$ of the objective function is attainable. Then we can write the linear inequalities

\begin{align*} Ax+b &\le \alpha Cx + \alpha b\\ 0 &\le x_i \le 1 \end{align*}

and use a LP solver to test whether this system of linear inequalities is feasible. (Note that $A,b,C,\alpha$ are constants here, and the variables are $x$.) Next, use binary search on $\alpha$ to find the largest value of $\alpha$ such that this linear system of inequalities has a feasible solution. This tells you the maximum possible value of $(Ax+b)/(Cx+b)$; then $\log \alpha$ is the maximum possible value of your original optimization problem.

D.W.
  • 4,540