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.
250
questions
2
votes
1
answer
114
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$$
...
- 21
0
votes
1
answer
73
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 ...
- 21
0
votes
0
answers
66
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 ...
- 1
3
votes
0
answers
59
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.1k
1
vote
1
answer
40
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
50
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 ...
- 471
1
vote
0
answers
63
views
min(f(x)) is convex or concave based on type of f(x)
i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
- 11
2
votes
0
answers
98
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at MathOverflow
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
where $D$ is a $...
- 21
3
votes
1
answer
89
views
A question related with $p$-Laplacian and conjugate gradient method
I have the following energy functional of $p$-Laplacian equation:
$$
E(u) = \frac{1}{p} \int_{\Omega} |\nabla u|^p dx
$$
for $2.8 \leq p \leq 5$.
My goal is to minimize the energy functional by using ...
- 143
1
vote
1
answer
143
views
Space complexity of a semidefinite program
What is the space complexity of a semidefinite program (SDP)?
What is the answer to the same question for convex optimization problems in general?
2
votes
0
answers
93
views
Parameter choice rules for L1 regularization?
I am solving an L1 regularized least squares of the form like:
$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
- 121
0
votes
1
answer
53
views
Optimization of the log-absolute: reformulating to DCP-compliant on Julia
I am trying to reformulate this optimization problem in order to get a DCP-complaint expression on Julia (I am using the ...
- 205
2
votes
1
answer
81
views
Convex optimization: what is atom library?
By reading the CVX users' guide, I frequently came across with the term "atom library", which I suppose to be a set of functions that one must use to construct mathematical expressions on ...
- 205
6
votes
1
answer
205
views
Minimum distance from point to surface
I’m looking for code that is well-suited to solving a fairly simple minimization problem:
I have a reference point $\mathbf p$ in 3D space, and I want to minimize $\|\mathbf x - \mathbf p\|^2$ subject ...
- 119
3
votes
2
answers
728
views
Why slack variables for inequality constraints?
When solving constraint optimization problems with (primal dual) interior points methods, I often read (e.g. on slide 17) that one should not use the inequality constraints $g(x)\leq 0$ directly, but ...
- 241
0
votes
1
answer
78
views
Distributed Optimization of Least Powers
I have $F_i \in \mathbb{R}^{m}$, $y_i \in \mathbb{R}$, $\beta_i \in (1,\infty)$ for $i = 1,\ldots, n$.
I would like to solve the following convex optimization problem
$$\min_{x} \sum_{i = 0}^n |F_i\...
- 23
3
votes
1
answer
131
views
Rewriting quadratically-constrained optimization problem as a semidefinite program
Suppose $A,H$ are positive definite matrices and $\alpha,t$ are scalars. Is there a way to massage the following problem into a form suitable for a specialized solver?
$$\begin{array}{ll} \underset{\...
- 2,273
1
vote
0
answers
22
views
Unconstrained convex optimization: correlation between dimensionality and Lipschitz constant
The author of the SIAM News article "Optimization Theory and Perspectives on the Field of Machine Learning" mentions:
... For unconstrained convex optimization, GD (gradient descent) ...
- 8,602
1
vote
2
answers
387
views
What algorithm does CVXPY actually use to solve semidefinite programs with the constraints of the form $\sum\limits_i E_iXE_i^T \succ B$?
Crossposted on Mathematics SE
CVXPY is a famous software as a solver for optimization problems. Nowadays, I use it to run a program presented in a paper, the Example 7.1, and the program runs as ...
- 113
0
votes
0
answers
42
views
Reformulate a problem with concave objective function into a QP
I would like to convert this problem into a QP (Quadratic program).
$$\text{Maximize } \sum_{k=1}^{K}\sum_{n=1}^{N}log2(1+p_{kn}b_{kn})\\
\text{subject to } \sum_{k=1}^{K}\sum_{n=1}^{N}p_{kn}\leq P_{0}...
- 1
0
votes
1
answer
129
views
Efficiently solving SDP relaxation of an integer quadratic program
I have an integer quadratic program of the form,
\begin{align}
\underset{x}{\max}&\;\;\|Ax-b\|_2^2\\
\text{subject to}&\;\;x\in{\bf Z}\geq0
\end{align}
I'm currently using the (admittedly ...
- 471
0
votes
0
answers
714
views
optimization problem with L2-norm constraint
I am currently trying to solve a regression problem, which leads me to an optimization problem. Say that we have measured data ($\hat{S}(\omega)\in \mathbb{C}^{N\times N}$), and each entry of this ...
- 1
1
vote
0
answers
145
views
Help with CVXPY and Disciplined Convex Programming
I'm trying to recreate Figure 1 in this paper. This requires maximizing equation (19), which I have convinced myself is concave, but I am having trouble implementing it in CVXPY. Here is the code I ...
1
vote
0
answers
223
views
Problem in parameterizing a CVXPY program
I am trying to parameterize a CVXPY program as I need to repeatedly solve the problem, but I noticed that when my parameters are complex numbers, CVXPY models the problem in each iteration. For ...
- 111
3
votes
1
answer
725
views
Questions regarding the result of the CVXPY
I want to optimize the function
$$\min_{X \in \mathbb{S}^{n}_{+}} \mbox{tr} \left( C^T X \right) + \mbox{tr} \left( X^{-1} \right),$$
of which I optimize the equivalent problem
$$\min \mbox{tr}\left(C^...
- 133
0
votes
1
answer
381
views
Why is a elementwise max not DCP?
I am trying to formulate a convex optimization problem using CVXPY. Everything works, except a constraint that does not seem to follow DCP rules.
Let $D \in \Bbb R^n$ be a decision variable and let $Q$...
- 43
0
votes
0
answers
181
views
Absolute value constraint in quadratic programming optimization
$$
argmin(x,y)=x^2+y^2+2y
$$
$$
s.t.\ \ y=|x-10|
$$
How can I convert the absolute value constraint to the constraint matrix (GX<=h, AX=b) in cvxopt?
- 109
13
votes
2
answers
3k
views
How do I find the minimum-area ellipse that encloses a set of points?
I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
- 133
2
votes
1
answer
96
views
Formulating this optimization problem
Suppose I want to minimize below objective function
$\sum | g(x_i) \cdot I_{g(x_i)<0} |^2$
i.e, the latter penalty terms like $ |g(x_i)|^2 $ are only computed when $g(x_i)<0$. $|g(x_i)|^2$ are ...
- 121
0
votes
0
answers
65
views
Comparing minimas of two different functions
The goal is to find vectors $x_u$ and $y_i$, both of the same length $f=64$, and to do this the following loss function is minimized:
$$\sum_{u, i} (1 + \alpha \cdot r_{ui})(p_{ui} - x_{u}^{T}y_i)^2$$
...
- 41
0
votes
1
answer
175
views
successive convex approximation and Convergence
In successive convex approximation method, can the solution be considered to be an acceptable solution if the algorithm reaches the maximum number of iterations without noticeable convergence? or it ...
- 11
0
votes
1
answer
68
views
Expressing a Constraint in an optimization problem
If I have a vector of M "continuous" decision variables (say it is called x) , and if I want a constraint to express that only one of them is allowed to have a nonzero value (i.e. no more ...
- 11
6
votes
1
answer
239
views
Optimization problem
In the expression:
$${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}}\, ,$$
$$\text{subject to tr}(\Omega)=1, \Omega \ge 0\, ,$$
where ${\Omega}$ is nonnegative and symmetric ...
- 81
2
votes
0
answers
123
views
Efficient solver of a Integer programming
I am solving an Integer programming using MATLAB, yet the efficiency is low.
Here is the problem:
Suppose $v$ is a $N \times 1$ vector. For $v_i \in v$, $v_i \in \{0,1\}$.
$D$ is a 0-1 matrix, which ...
- 21
1
vote
0
answers
107
views
Maximizing $l_1$-normalized entropy using CVXPY
Suppose that $x = (x_1, ..., x_n)$ is a vector of variables and I would like to maximize the Shannon entropy of $\frac{|x|}{||x||_1}$ (i.e. the vector of absolute values of $x_i$, normalized to have $...
- 119
0
votes
0
answers
64
views
Equivalence between zero sum games and linear program
It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the ...
- 131
0
votes
0
answers
178
views
Relative interior requirement in Slater's condition
I'm reading Convex Optimization by Boyd and Vandenberghe. This is how they describe Slater's condition:
What I don't understand is why it is necessary to enforce that $x$ be in the relative interior ...
- 63
6
votes
1
answer
194
views
continuous analogues of Newton's method
Suppose we want to minimize some convex functional $J(u)$ where $u$ lives in some Banach space $V$.
The classical Newton method
$$\mathrm d^2J(u_n)(u_{n + 1} - u_n) = -\mathrm dJ(u_n)$$
can be viewed ...
- 10.1k
3
votes
1
answer
210
views
Log-Determinant constraints in SDP
This is a belated follow up to my question here, because I didn't want to tack questions onto questions.
According to the Mosek documentation here, one possibility for expressing $t \leq log(det(X))$, ...
- 131
0
votes
0
answers
143
views
CVXOPT intermediate step valuation stepping out of function domain of defintion
I am using CVXOPT, particularly to solve a nonlinear convex optimization problem. Either the objective function or the constraints involve some functions that are only defined in a strict subset of $\...
- 121
1
vote
1
answer
287
views
L2 norm optimization problem
I have an optimization problem where i need to find an image x, that is very close to x' such that:
monitor(x') is valid but monitor(x) is invalid. (output is valid
when the neural network output is ...
- 11
5
votes
1
answer
696
views
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program?
Assume my problem is something like
$$\min\limits_x. \quad f(x)$$
$$s.t. \...
- 153
3
votes
0
answers
143
views
What is this QR-factorization-based preconditioning called?
I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization....
- 203
2
votes
0
answers
204
views
Understanding Illumination Optimisation Problem
I am a newbie to convex optimisation and I am learning with the aid of CVXPY. I am requesting for clarity on the illumination problem as described in Boyd & Vandenberghe lecture 1 slides here. I ...
- 43
2
votes
1
answer
1k
views
Why is CVXPY throwing a DCP error with cp.sqrt but no error with cp.norm
I am trying to use CVXPY to optimise signal-to-noise-plus interference ratio (SINR) for a visible light communication (VLC) system. I have one of my SINR constraints stated as
\begin{equation}
\...
- 43
1
vote
1
answer
481
views
How to best code a problem with scipy, cvxpy or Convex.jl with given generated data
I have a curve fitting problem of the form:
$$
\textbf{y} = f(\textbf{x}, a,b,c,d) + \varepsilon
$$
$$
f(x, a,b,c,d) = \frac{b}{e^{x\cdot a}+c}+d
$$
with the constraint
\begin{equation}
\begin{aligned}...
- 141
1
vote
2
answers
144
views
Solving a specific sparse linear system without dense materialization
I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form
$$
\left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
- 113
2
votes
1
answer
199
views
Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint
I am wondering if there is a well-known transformation allowing one to solve convex optimization problems of the form
$$\begin{array}{ll} \underset{x}{\text{maximize}} & r^T x\\ \text{subject to} &...
- 121
5
votes
0
answers
104
views
Generally quadratic convex problem with one non-convex term
How would you approach a standard convex quadratic problem with convex constraints but one non-convex term ? Say $|x|^{0.4}$.
$$\min_x \frac{1}{2} x^{T}Qx + g^Tx + c^T \mathrm{sign}(x) |x|^{0.4} $$
...
- 151
3
votes
1
answer
195
views
Project to nearest point on convex polytope
I have a point $y \in \mathbb{R}^d$ and a convex polytope $\mathcal{P}$ given as the intersection of half-spaces:
$$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \le ...
- 400