Questions tagged [constrained-optimization]
The constrained-optimization tag has no usage guidance.
70
questions
0
votes
0
answers
27
views
Learning over non-independent joint distributions
For integer $n\geq 1$, I have a "goodness" function $f_n(F)$ that takes as input a given joint CDF $F$ of $n$ variables, and spits out a number in $[0,1]$ on how "good" $F$ is. The ...
- 253
4
votes
0
answers
141
views
Trying to understand the theory behind my similar / better results than XGBoost using a calibrated linear model (GAM)
I just opened a discussion on reddit asking about why/how the calibrated linear models I've been training have been getting similar / better results than XGBoost in my experiments. I was told to cross ...
- 41
0
votes
0
answers
11
views
Tree-reweighted belief propagation: optimizing edge appearances $\mu$
I am currently implementing Tree-Reweighted Belief Propagation (TRBP) to optimize edge appearances. The authors in the main manuscript of this work keep the edge appearances, represented by 𝜇, fixed [...
- 105
1
vote
0
answers
50
views
How to solve alphas (or the dual equation) after getting Lagrangian dual of SVM
I'm trying to learn SVM by myself, and I'm stuck after getting the dual of SVM. I understand getting the dual after the primal. But, I am stuck here. Please help.
We assume that the hard margin case ...
- 11
0
votes
1
answer
83
views
Full-rank approximation to a square matrix
Let $\bf A$ be an $n \times n$ matrix with rank $r$ where $r<n$. How can I get a full-rank approximation for $\bf A$? In other words, I want to find the rank-$n$ $\bf X$ that minimizes the ...
- 830
1
vote
0
answers
34
views
How does quadratic programming solve the Support Vector Machine problem?
I have just been reading that Quadratic Programming can be used to solve the Support Vector Machine optimization.
My solver can minimize this typ of problem
$$\text{J}_{min} = \frac{1}{2}x^TQx + c^Tx$$...
- 349
0
votes
0
answers
29
views
Scale dependent solutions for scale-invariant cost function in nonlinear regression
Suppose, I have a nonlinear regression problem, where I have the lables of my training data $\bf{y}$ and two measurement matrixes $A$ and $B$. The cost function is $\Vert \frac{A*\textbf{w}}{B*\textbf{...
2
votes
0
answers
19
views
Constrained optimization between two bayesian variables
I have 2 separate Bayesain networks and I was hoping to maximize Value within the constraint of the Cost. What are is a good way ...
- 21
0
votes
0
answers
19
views
Convex optimization problem with nuclear norm constraint
We have the following convex optimization problem:$$
\text{minimize} \quad f({\bf X}) \quad \text{with constraint} \quad \|{\bf X}\|_{\rm tr} \leq t
$$
Where $\|{\bf X}\|_{\rm tr}$ is the Schatten 1-...
1
vote
0
answers
43
views
Can we convert the optimization of a loss function with regularization to the Lagrangian, constrained optimization *before* solving the optimization?
It is shown here that the optimization of a loss function with regularization,
$$\text{argmin}_b L(X,b) + c ||b||_p \phantom{aaaaaaaaaaaaaaaaaaaaaaaa} (*)$$
is equivalent to the constrained ...
- 351
1
vote
0
answers
32
views
Constrained imputation in Python
I actually have two original datasets (each one for a departure that are related to each one in a specific way , but it's not important to know how exactly) , but these 2 datasets contain some ...
- 11
1
vote
0
answers
32
views
Case study question on profit optimization
A famous restaurant selling burgers has closely studied the demand for burgers for past months including the times the customer requested a burger and it was already sold out. Further analysis
of data ...
- 21
2
votes
0
answers
41
views
If L2-Regularization includes no bias, why do many images show a circle as the constraint region?
I got a little bit (massively, to be honest), confused by the following apparent misconceptions I have learned recently.
Looking for information about L2-Regularization, the following image is one of ...
- 505
1
vote
1
answer
34
views
Incorporate known class likelihood (proportions, ratios, etc..) in the classification output
I'm working on the multi-class prediction problem, with 6 output classes. These represent different types of land cover. The classification model is pixel-based and I have extracted different ...
3
votes
0
answers
25
views
How to combine ML + Expert knowledge? (constrained machine learning)
I am working the sector of computer science for agriculture research. I deal here with algorithm for crop yield prediction. However, data in agriculture is very limited.
To overcome the issues of ...
- 31
3
votes
0
answers
115
views
Does there always exist a support vector such that $0 < a_n < C$ in SVM?
I have a question about SVM training in overlapping class distributions, where we are trying to minimize
$$
\dfrac{1}{2} \Vert \mathbf w \Vert_2^2 + C \sum_{n = 1}^N \xi_n \, ,
$$
subject to $y_n(\...
- 131
0
votes
0
answers
27
views
Least angle regression algorithm in terms of gradient in lasso
I'm trying to understand an algorithm for a minimization problem but it is unclear. Here is the function we consider:
$\lVert Y - X\beta\rVert_{2}^{2} + \lambda\lVert\beta\rVert_{1}$ where $Y\in\...
- 111
0
votes
0
answers
16
views
How to go about an optimization problem where posterior denstiy is involved
I am currently reading a paper by Yao et al.(2018) where they discussed about stacking bayesian prediction distribution for K models. I got the idea but I am not sure how you will implement it in ...
- 21
0
votes
0
answers
29
views
Obtaining PCA via Minimum Reconstruction Error
Absolutely nowhere I can find provides a rigorous proof of this fact. I attempt to do so as follows. Suppose we have centered data $X = [x_1 ... x_n]$ where $x_i$ are $d$ dimensional column vectors. ...
- 163
1
vote
1
answer
44
views
Algorithm for Creating 2x2 Tables to Demonstrate Simpson's Paradox
Suppose I have a 2x2 table: $T = \lbrace a,b,c,d \rbrace$, where $a=T(1,1), b=T(2,1), c=T(1,2), d=T(2,2)$, where all entries of $T$ are positive integers. Let us assume that $\frac{ad}{bc} > 1$.
...
- 303
0
votes
1
answer
40
views
Bayesian optimization with constraints
I want to perform Bayesian optimization for a certain physical task but with additional requirements. We have access to a set of variables and want to maximize (multiple) signal outputs from an ...
- 23
12
votes
2
answers
1k
views
Why l2 norm squared but l1 norm not squared?
In the Lasso, and ElasticNet, we use, as penalty, the l1 norm without squaring. But in the ElasticNet and Ridge, we use the l2 norm squared. Why is that, is there a particular reason (computational, ...
0
votes
0
answers
28
views
Dual to primal solution for regularized ERM
Consider the regularized ERM optimization: $$\min_{w} \frac{1}{n} \sum_{i=1}^n \phi_i(w^T x_i) + \lambda g(w) := f(w)$$
and dual problem
$$\max_{\alpha} -\frac{1}{n} \sum_{i=1}^n \phi_i(-\alpha_i) - \...
- 11
2
votes
1
answer
63
views
Interpretation of the entropic relaxation of the optimal transport problem
For two probabilities vector $r,c\in \mathbb{R}^k$, the optimal transport is to find the joint distribution of $r,c$ such that it
$$\min_{T\in P} \langle T,C \rangle\\P\in\mathbb{R}^{k\times x},\text{...
- 236
0
votes
0
answers
24
views
Implementations for non-negative regression in generalized linear models [duplicate]
What are some package for generalized linear models that give non-negative regression coefficients without regularization? I checked the thread (Nonnegative generalized linear model), but many ...
- 21
1
vote
0
answers
50
views
Relaxed non-negative least squares
I am reconstructing a probability vector from data using non-negative least squares:
$$
\sum_\alpha \left(\pi_\alpha - \sum_i W_{\alpha i}p_i\right)^2\rightarrow \min,\\
p_i\geq 0,\sum_i p_i=1
$$
...
- 3,512
4
votes
1
answer
58
views
Einstein notation $-$ or another $-$ to denote constraints in high dimensional ILP problems
When discussing marginal sums of arrays in 3 dimensions or more, is it customary in the statistical and/or data science communities to use the Einstein summation convention? Is some other form ...
- 2,194
4
votes
1
answer
229
views
Handling multicollinearity with Restricted Least Squares
The dummy variable trap - including a dummy variable
for every category and including a constant term in the regression together guarantees
perfect multicollinearity - is most commonly resolved by ...
- 73
1
vote
0
answers
168
views
CVXPY PSD constraint not working
I am using CVXPY to solve for a PSD matrix, example as follows:
...
2
votes
0
answers
122
views
Train a model subject to max error
I would like to train a neural network by minimizing a loss over samples (as usual), but doing so in a way that the maximum error is bounded.
What options do I have? Some that come to mind are:
...
0
votes
0
answers
45
views
How to ensure that the solution to an optimization problem is a probability distribution? [duplicate]
How to ensure that the solution to an optimisation problem is a probability distribution?
For example, assume we minimise over a distribution $p$. We must ensure that $\int p(x) \,dx=1 $.
But why don'...
- 127
3
votes
1
answer
133
views
Is standard gradient descent possible when we have constrained parameters?
Is it true that standard gradient descent algorithm (be it batch or mini batch or stochastic) cannot be used when we have certain constraint on parameters? If yes, why is it so? Is it because gradient ...
- 411
0
votes
1
answer
48
views
deriving the optimal distribution
Let the input variable $X \in \mathcal{X}$ and the target variable $Y \in \mathcal{Y}$. For a fixed hypothesis $h \in \mathcal{H}$ I want to solve
\begin{equation}
\min_{p(X,Y)} \int_{\mathcal{X}}\...
- 127
2
votes
0
answers
111
views
LASSO and duality theorem
I am confused with Lagrange duality theorem. Let us consider the problem
$$
\hat{\beta} = \underset{\beta \in \mathbb{R}^{n}}{\arg \min} \left[\sum_{i=1}^{n}(y_{i} - \beta_{i})^{2} + \lambda \sum_{i=...
- 73
1
vote
0
answers
36
views
alternative solution to fussed lasso
The question is related to strange result from fused lasso estimator
Let us consider fussed lasso estimator:
$$
\hat{\beta}^{FL} = \underset{\beta \in \mathbb{R}^{n}}{\arg \min} [(y_{i} - \beta_{i})^{...
- 73
4
votes
1
answer
97
views
strange result from fused lasso estimator
Let us consider the following estimator:
$$
\hat{\beta}^{F} = \underset{\beta \in \mathbb{R}^{n}}{\arg \min} (y_{i} - \beta_{i})^{2} + \lambda_{1} \sum_{i=1}^{n-1}|\beta_{i} - \beta_{i+1}|,
$$
which ...
- 73
3
votes
1
answer
138
views
How does removal of symmetry (e.g. via constraints) in a Bayesian optimization search space affect search efficiency?
There are many examples of search space symmetry in real-world optimization problems in the physical sciences. To motivate this, here are some that come to mind:
When optimizing a formulation such as ...
- 69
2
votes
0
answers
67
views
Covariance matrix of beta coefficients for constrained multiple regression
I have a linear least-squares problem with constraints that two of the coefficients must be non-negative. For a typical (unconstrained) least squares estimation, I know that the variance-covariance ...
- 21
1
vote
0
answers
1k
views
`Error: L-BFGS-B needs finite values of 'fn'` of Complex Objective Function
I'm trying to run R's maximum likelihood estimation function (stats4::mle), over a likelihood function in Free Shipping Is Not ...
- 21
0
votes
0
answers
117
views
Why SCM weights *should* sum to 1?
When we use synthetic controls, we consider $j=2, \dots, J+1$ units across $t \in \{T_{-} \ldots T_0 \ldots T_{+}\} \in \mathbb{Z}$ pre/post event-time periods. Abadie et. al. make the point that to ...
- 161
3
votes
1
answer
80
views
KKT Conditions for thresholds?
My main question is that when I use Lagrange Multipliers/KKT conditions to perform optimization with threshold constraints, I seem to get contradictory FOC.
Here is a characteristic example:
take an ...
- 75
1
vote
0
answers
668
views
How do you use pytorch to solve strictly constrained optimization problems? [closed]
I am trying to solve the following problem using pytorch: given a six sided die whose average roll is known to be 4.5, what is the maximum entropy distribution for the faces?
(Note: I know a bunch of ...
- 221
0
votes
0
answers
118
views
Speeding up an optimization involving matrix products in CVXR
I have an optimization problem where I need to minimize
$$-\log \det(U^T \text{diag}(p) U + V^T\text{diag}(1 - p)V)$$
where $p$ is a vector of probabilities, i.e. $0 \leq p_i \leq 1$, and $U$ and $V$ ...
user272429
1
vote
0
answers
84
views
Discrete Bayes Net learning under parameter constraints
What is some relevant research available on estimating the parameters of a Bayes Net (with known structure) when there are known constraints on conditional and marginal probabilities?
For example, ...
- 1,148
1
vote
1
answer
167
views
How do linear constraints affect the convexity of my OLS-like optimisation problem?
I would like to augment a linear regression (so a convex OLS problem) with some additional constraints on the coefficients to match the subject I'm working on.
Having $x\in \mathbb{R}^n$, the solution ...
- 11
0
votes
0
answers
198
views
Applying constraints within a neural network?
I need to solve a multi-objective problem. I would understand if there is any kind of possibility to cope this issue through a neural network. Hypothetically, I need to put some constraints within ...
2
votes
1
answer
21
views
Optimal Feature Engeneering creation: best optimization method?
basically I would like to solve this problem:
(1) say I have N features that I want to transform with a generic f(x, theta) ...
- 219
2
votes
0
answers
71
views
Can I use xboost as objective function in an optimization problem?
I am working on a marketing optimization problem, where the goal is maximize profit by optimally allocating spend to different products. Constraint is getting at least 1 Million revenue.
As a first ...
- 787
1
vote
0
answers
77
views
Solving coefficient sum constrained elastic net with quadratic objective term
I am looking for an algorithm to solve an equality constrained elastic net.
There are two adaptations I need to make to the standard elastic net. First the objective function includes a quadratic ...
- 11
2
votes
0
answers
69
views
Gradient descent finds local minima for a problem that can be formulated as a convex problem
I am trying to find
$$ \min_W \|Y-XW \|_F^2$$ $$s.t. \exists ij, W_{ij}\geq0 $$
where X is input data and Y is the output data we try to fit to. This is a convex optimization problem that can be ...
- 281