7
$\begingroup$

Suppose we are given a convex function $f(\cdot)$ on $[0,1]$. One wants to solve the following optimization problem:

\begin{equation} \begin{aligned} & \text{minimize} && \sum_{i=1}^n \alpha_i f(x_i), \\ & \text{subject to} && \sum_{j=1}^n \beta_j g_l(x_j) \leq 0, \text{ for } l \in \{1,2,...,m\}, \end{aligned} \end{equation}

where $x_i \in [0,1]$ for $i \in \{1,2,...,n\}$; $\alpha_i$s and $\beta_j$s are also in $[0,1]$. Also, $g_l(\cdot)$ is linear on [0,1], for $l \in \{1,2,...,m\}$.

I am thinking how to use gradient descent method to solve this problem. i.e., assume we repeat updating the variables via, say, $x_i ^{(t+1)} = x_i ^{(t)} - a f^{'}(x_i ^{(t)})$ for the $t$-th iteration, where $a$ is some step size. Since the constraints might be violated after the update, how can we make the constraints satisfied while moving the variables towards the optimum ?

In particular, in each iteration, one has to keep an eye on how the functions in the constraints are going, i.e., one might want to compute also the derivatives of the functions in the constraints. But do we have a general method to control this procedure ?

$\endgroup$
5
$\begingroup$

Look into the projected gradient method. It's the natural generalization of gradient descent to problems with linear constraints. E.g., http://www2.esm.vt.edu/~zgurdal/COURSES/4084/4084-Docs/LECTURES/GradProj.pdf or a Google search.

$\endgroup$
1
$\begingroup$

In general, these types of problems are naturally harder to solve algorithmically than unconstrained or equality constrained optimization problems, and are often solved by interior point methods. If your constraint and objective functions are 'nice' enough, there are some analytic tools you can use to take advantage of methods used for easier types of problems, to choose descent directions and such.

Chapter 11 of "Convex Optimization" would be a good start (http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf).

$\endgroup$
0
$\begingroup$

Projected decent as described by Ulbrich worked really well for me:

https://www.springer.com/cda/content/document/cda_downloaddocument/9781402088384-c2.pdf?SGWID=0-0-45-642711-p173830414

I coded everything from scratch previously. However, I am now trying to see if there are easier implementations in TensorFlow, for example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.