1
$\begingroup$

Could someone kindly suggest a method of solving the following constrained (equality and inequality) system of equations in the least squares fashion?

$$\min_x\frac 12\|Ax-b\|_2^2$$

such that

$$\begin{matrix}x_i + x_j = 1 \quad \text{for a certain }i,j\\0 < x_k < \tau_k \quad \text{where } k\ne i,j\end{matrix}$$

$\tau_k$ is the upper bound for $x_k$.

I would like to develop a solver for this in MATLAB. Would a gradient-descent based method a proper approach?

$\endgroup$
  • 1
    $\begingroup$ Easy to do in CVX. The CVX distribution supplies the necessary solvers. cvxr.com/cvx $\endgroup$ – Mark L. Stone May 6 at 22:56
  • $\begingroup$ I think CVX is great. However, I am trying to write a standalone solver. Would appreciate any tips for finding a proper method. $\endgroup$ – AFP May 6 at 22:58
  • $\begingroup$ Is this a school assignment? Else, why do you need to implement your own solver? $\endgroup$ – Mark L. Stone May 6 at 23:00
  • $\begingroup$ It's not a school assignment. $\endgroup$ – AFP May 6 at 23:11
  • 1
    $\begingroup$ Cvx is proprietary. Why not consider FLOS cvxpy? You may see its tag info for a basic example and some introductory tutorials to get started. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 7 at 1:56
1
$\begingroup$

As other mentioned, you can easily use CVX or YALMIP together with a free solver (such as SDPT3 or Sedumi) to solve the problem. If you want to write your own solver, you should use a primal-dual approach to solve the problem. There are many papers for solving convex problems subject to linear equality constraints. See this fantastic book for more detail

$\endgroup$
  • 1
    $\begingroup$ A primal-dual approach is one option, but there are options too, such as the projected gradient method and accelerated projected gradient methods. $\endgroup$ – littleO May 7 at 8:55
  • 1
    $\begingroup$ I agree but the projection step is usually difficult and one has to solve a new optimization problem (which is similar to the original problem) at each iteration. That's why I suggested primal-dual approach since it is a projection free approach. $\endgroup$ – Soroosh Shafiee May 7 at 9:00
  • 1
    $\begingroup$ But, in this case the projection step is just a linear algebra problem, at least if I'm interpreting "$k \neq i, j$" correctly. $\endgroup$ – littleO May 7 at 9:03
1
$\begingroup$

You can solve this problem using the projected gradient method (or an accelerated projected gradient method). Let $S$ be the set of all $x$ that satisfy the given constraints. The gradient of the objective function $f$ is $$ \nabla f(x) = A^T(Ax - b) $$ and the projected gradient iteration is $$ x^+ = P_S(x - t \nabla f(x)). $$ The function $P_S$ projects onto $S$. This projection step requires solving a linear algebra subproblem. (Note that the second set of constraints can be handled independently of the first set of constraints. If the linear constraints are described more explicitly, we can give more detail.) The projected gradient iteration will converge if the step size $t > 0$ is sufficiently small.

$\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.