1
$\begingroup$

With some given $s$ value, let \begin{equation} \begin{aligned} h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\ &=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)^2-s)\\ &=f(\beta)-g(\beta, s) \end{aligned} \end{equation} The problem is: \begin{equation} \min h(\beta) \end{equation} I used Disciplined Convex-Concave Programming and DCCP package based on CVXPY. The code follows:

import cvxpy as cp
import numpy as np
import dccp
from dccp.problem import is_dccp

# Generate data.
m = 20
n = 15
np.random.seed(1)
X = np.random.randn(m, n)
Y = np.random.randn(m)

# Define and solve the DCCP problem.
def loss_fn(X, Y, beta):
    return cp.norm2(cp.matmul(X, beta) - Y)**2

def obj_g(X, Y, beta, sval):
    return cp.pos(loss_fn(X, Y, beta) - sval)

beta = cp.Variable(n)
s = 10000000000000
constr = obj_g(X, Y, beta, s) 
t = cp.Variable(1)
t.value = [1]
cost = loss_fn(X, Y, beta) - t
problem = cp.Problem(cp.Minimize(cost), [constr >= t])
print("problem is DCP:", problem.is_dcp())   # false
print("problem is DCCP:", is_dccp(problem))  # true

problem.solve(verbose=True, solver=cp.ECOS, method='dccp')
# Print result.
print("\nThe optimal value is", problem.value)
print("The optimal beta is")
print(beta.value)
print("The norm of the residual is ", cp.norm(X*beta - Y, p=2).value)

Because of the large value $s$, I would hope to get a solution similar to the least squares estimation. But there is no solution as the output shows:

problem is DCP: False
problem is DCCP: True

ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -0.000e+00  +2e+01  9e-02  1e-04  1e+00  9e+00    ---    ---    1  1  - |  -  - 
 1  -7.422e-04  +2.695e-09  +2e-01  1e-03  1e-06  1e-02  9e-02  0.9890  1e-04   2  1  1 |  0  0
 2  -1.638e-05  +5.963e-11  +2e-03  1e-05  2e-08  1e-04  1e-03  0.9890  1e-04   2  1  1 |  0  0
 3  -2.711e-07  +9.888e-13  +2e-05  1e-07  2e-10  2e-06  1e-05  0.9890  1e-04   4  1  1 |  0  0
 4  -3.991e-09  +1.379e-14  +2e-07  1e-09  2e-12  2e-08  1e-07  0.9890  1e-04   1  0  0 |  0  0
 5  -5.507e-11  +1.872e-16  +3e-09  2e-11  2e-14  2e-10  1e-09  0.9890  1e-04   1  0  0 |  0  0

OPTIMAL (within feastol=1.6e-11, reltol=4.8e+01, abstol=2.6e-09).
Runtime: 0.001112 seconds.


ECOS 2.0.7 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -5.811e-01  +1e+01  6e-01  6e-01  1e+00  2e+00    ---    ---    1  1  - |  -  - 
 1  -7.758e+00  -2.575e+00  +1e+00  2e-01  7e-01  6e+00  3e-01  0.9890  1e-01   1  1  1 |  0  0
 2  -3.104e+02  -9.419e+01  +4e-02  2e-01  8e-01  2e+02  8e-03  0.9725  8e-04   2  1  1 |  0  0
 3  -2.409e+03  -9.556e+02  +5e-03  2e-01  8e-01  1e+03  1e-03  0.8968  5e-02   3  2  2 |  0  0
 4  -1.103e+04  -5.209e+03  +2e-03  2e-01  7e-01  6e+03  4e-04  0.9347  3e-01   2  2  2 |  0  0
 5  -1.268e+04  -1.592e+03  +8e-04  1e-01  1e+00  1e+04  2e-04  0.7916  4e-01   3  2  2 |  0  0
 6  -1.236e+05  -2.099e+04  +9e-05  1e-01  1e+00  1e+05  2e-05  0.8979  9e-03   1  1  1 |  0  0
 7  -4.261e+05  -1.850e+05  +4e-05  2e-01  7e-01  2e+05  1e-05  0.7182  3e-01   2  1  1 |  0  0
 8  -2.492e+07  -1.078e+07  +7e-07  1e-01  7e-01  1e+07  2e-07  0.9838  1e-04   3  2  2 |  0  0
 9  -2.226e+08  -9.836e+07  +5e-08  9e-02  5e-01  1e+08  1e-08  0.9339  2e-03   2  3  2 |  0  0

UNBOUNDED (within feastol=1.0e-09).
Runtime: 0.001949 seconds.

The optimal value is None
The optimal beta is
None
The norm of the residual is  None
$\endgroup$
  • $\begingroup$ Did you try turning on solve output? $\endgroup$ – Mark L. Stone Oct 2 at 23:58
  • $\begingroup$ I just added the solve output. $\endgroup$ – John Smith Oct 3 at 0:47
  • $\begingroup$ Just a comment which might be silly but how would you expect that you find a least square fitting of $X_{i}$ random matrices to $Y_{i}$ random vectors? I mean if there is no solution based on your calculation it looks pretty intuitive to me... There should not be a solution obviously... Otherwise $X_{i}$ and $Y_{i}$ which must be uncorrelated random matrices and vectors respectively, are correlated suddenly which is obviously wrong... Am I missing something here?! $\endgroup$ – Alone Programmer Oct 3 at 22:49
  • $\begingroup$ I am afraid to say, yes, you missed something here: correlation can be strong or weak. Correlation of 0 is also a correlation. Obviously there is a solution for least squares: cvxpy.org/examples/basic/least_squares.html $\endgroup$ – John Smith Oct 4 at 14:39

Your Answer

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

Browse other questions tagged or ask your own question.