Questions tagged [convex-optimization]
Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.
14
questions
0
votes
1
answer
45
views
step-fixed algorithm first iterates
let us have the fixed-step gradient algorithm, with $p = 2$ and we assume that for $X = (x, y)$,
$∇ f(X) = \begin{pmatrix}
x -1\\
y -2
\end{pmatrix}$
Let me assume we intialize with $X_0 = (0,0)$ what ...
- 15
0
votes
1
answer
66
views
step-fixed algorithm to minimize f, which step to ensure convergence?
If we want to apply the fixed-step gradient algorithm to the minimization of $f(x) = \frac{1}{2}(Ax, x)$ where $A$ is a symmetric 2x2 matrix with eigenvalues $\lambda_1 > \lambda_2 > 0$, for ...
- 15
2
votes
0
answers
48
views
trust region method for linearly-constrained convex optimization
I'm interested in the problem of minimizing a convex function $f(x)$ for $x$ living in some Banach space $X$, subject to the linear constraint $Kx = g$ where $K : X \to Y^*$ for some other space $Y$.
...
- 10.4k
2
votes
2
answers
103
views
Can this problem be solved using convex optimization?
I have the following problem:
$$\begin{align}
\max & \quad \frac{\mu^\top x - c^\top|x - x_0|}{x^{\top}\Sigma x} \tag{1} \\
\text{subject to }
& \quad x \leq \mathbb{1} \tag{2}\\
& \quad ...
- 23
2
votes
0
answers
77
views
How to solve this nonconvex problem in python
I have the following problem to solve
minimize $$\sum_{i=1}^I\sum_{k=1}^Kx_{i,k}.$$
The constraints are as follows:
$$\sum_{i=1}^I\sum_{j=1}^J\ln(c+x_{i,k}A_{i,j,k})\geqslant B_k,\forall k,$$ and
$$\...
- 121
1
vote
1
answer
94
views
How does the slack variable work in the problem formulation?
Recently I am reading a paper. In it, after they achieve eq(15), which is
$$ \operatorname{Tr}(\boldsymbol{Q})-\sqrt{2 \ln (1 / \rho)} \sqrt{\|\boldsymbol{Q}\|_F^2+2\|\boldsymbol{r}\|^2}+\ln (\rho) \...
- 133
2
votes
0
answers
61
views
Equivalency of lasso problems
In the literature, I've seen the lasso problem phrased as the minimization of: $$\frac12x^tAx-x^tb+\lambda||x||_1$$
or of:
$$\frac12||Ax-b||_2^2+\lambda'||x||_1=\frac12x^tA^tAx-x^tA^tb+b^tb+\lambda'||...
- 21
0
votes
1
answer
74
views
Why using large bound to supplement inifinity in interior point method can be bad
Here in the documentation of mosek (https://docs.mosek.com/latest/pythonfusion/debugging-numerical.html)
we see:
Never use a very large number as replacement for infinity
. Instead define the ...
- 127
2
votes
1
answer
123
views
How to formulate a convex expression to minimize the difference between Frobenius norm of a positive semidefinite matrix and a positive value
So what I am trying to do is to minimize the distance between the Frobenius norm of a PSD matrix and a real positive value, which can be formulated as
$$\min \left|\|\textbf{P}\|_F - J\right|^2$$
...
- 133
0
votes
1
answer
79
views
How to formulate the convex hull which is a regular polygon on the complex plane
Suppose that I have a convex regular polygon with $k$ vertices on the complex plane, and the first vertex lies on the positive real axis. Is there a neat way to formulate the convex hull with the ...
- 133
0
votes
0
answers
90
views
How to determine whether the symmetric stiffness matrix is positive definite or not? Is it related to the problem?
For two-dimensional or three-dimensional elliptic equations, when will the stiffness matrix be asymmetric and positive definite? This affected the solution efficiency so much that I had to choose an ...
- 21
3
votes
0
answers
61
views
What 2nd-order optimization algorithms have convergence guarantees for strictly- but not strongly-convex problems?
A function $f$ is strictly convex if
$$f((1 - \lambda)x + \lambda y) \le (1 - \lambda)f(x) + \lambda f(y)$$
with equality if and only if $x$ and $y$ are equal.
This implies that the second derivative ...
- 10.4k
1
vote
1
answer
48
views
Name this optimum-within-convex-hull algorithm: State is a convex combination of hull vertices; Nonnegativity ensured by reparameterization
I'm looking for the "official" name(s) for a procedure for optimizing a convex loss function over a convex subset. This seems to be a default/naïve algorithm that folks come up with before ...
- 153
1
vote
0
answers
58
views
Beyond the LP relaxation of binary least squares
I have a binary quadratic program with a convex objective function, of the form,
\begin{align}
\text{minimize}\;\;& x^tAx+b^tx\\
\text{subject to}\;\;& x_i\in\{0,1\}
\end{align}
where $A$ is ...
- 503