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.
232
questions
0
votes
0
answers
29
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
49
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 ...
- 443
0
votes
0
answers
74
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
63
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
27
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
122
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
64
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
58
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
12
votes
2
answers
1k
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 ...
- 123
2
votes
1
answer
88
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
61
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
82
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
62
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
231
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
81
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
76
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
41
views
Can this volume intgral be expressed as a convex function?
This question is related to the following:
https://math.stackexchange.com/q/4151405/685910 - the context is summarized below for clarity.
In the setting of convex optimization, I am looking for a ...
- 11
0
votes
0
answers
54
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
76
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
0
answers
94
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 ...
- 8,087
3
votes
1
answer
107
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
104
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
0
votes
0
answers
84
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 ...
- 1
4
votes
1
answer
290
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. \...
- 143
3
votes
0
answers
75
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
121
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
421
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
228
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
137
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
128
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
98
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
162
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 ...
- 350
0
votes
1
answer
631
views
Norm constraint in CVXPY
I'm trying to implement the algorithm outlined in https://arxiv.org/abs/1211.5608 on a small scale. I have a linear operator $\mathcal{A}$ which is defined as $$\text{trace}(A^*_l(hm^*))$$ where $$A_l ...
- 3
1
vote
1
answer
233
views
Solving a linear program with an active set method
Is it possible to solve a linear program with an active set method? If so what would be the similarities and differences to the simplex method?
- 13
7
votes
0
answers
278
views
Finding points inside cells of power (generalized Voronoi) diagram
Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by:
$$\...
- 1,331
1
vote
1
answer
138
views
5
votes
2
answers
725
views
log(det(X)) in Semidefinite Programming
I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
- 131
4
votes
1
answer
212
views
Underdetermined Minimum Volume Enclosing Ellipsoid
Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
- 131
1
vote
1
answer
99
views
In which cases does the nonlinear conjugate gradient method take more than $n$ steps?
I have programmed a couple of Matlab implementations of nonlinear Conjugate Gradient methods (Fletcher Reeves and Polak Ribeire). However, I am concerned with how many steps it's taking to optimise ...
- 51
2
votes
0
answers
136
views
Proving convexity of Frobenius norm and correlation function formulations of an optimization problem
I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting.
Firstly, I would like to make the variables I used in the problem and ...
- 21
2
votes
0
answers
63
views
Interior point of convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
141
views
Could the convex problem be tackled by CVX?
I want to solve the convex optimization as follows:
\begin{align}
\underset{X_1,X_2}{\min} &\ -\frac{1}{N}\sum_{i=1}^N\log\det\left(I+H_i^HX_2H_i\right)-\log\left[1+h^H(X_1+X_2)h\right]\\
&\...
- 131
1
vote
1
answer
91
views
Disciplined convex programming expression of $x\sqrt{1-x}$
Anyone have an idea for a DCP (disciplined convex programming) representation of the concave function $x\sqrt{1-x}$, which is has domain $[0,1]$?
The Taylor series about $x=0$ is
$$x - \frac{x^2}{2}...
2
votes
1
answer
337
views
Gradient descent in constrained optimization of barrier function
This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained ...
- 31
5
votes
0
answers
111
views
Minimum of quadratic assignment (QAP) with convex objective
Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem:
$$
\min_{\textrm{permutation matrices }P}
\mathrm{tr}(BP^\top AP+C^\top ...
- 1,331
6
votes
1
answer
119
views
Sparsity-Promoting Convex Optimization Over Simplex
Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + ...
- 402
3
votes
1
answer
742
views
Convex optimization with constraints involving matrix inverse
I have the following convex optimization problem. I would like to ask is there any efficient way to solve it in Python? Can I use CVXOPT package? If so, any detailed instruction? Thanks a lot.
$$
\...
- 31
3
votes
0
answers
116
views
A maximization problem, with motivation in machine learning
Consider the minimization problem described this paper. Let $f_{\lambda}$ be the minimizer. As a part of extending my work, I am able to show the following facts
$$\lim_\limits{\lambda \to 0}\|f_{\...
- 141
4
votes
1
answer
85
views
Geometric Programming - symbolic version
I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
- 965
3
votes
2
answers
877
views
Convexity of Sum of $k$-smallest Eigenvalue
If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $.
Define the function as $f(A)=\sum_{i=1}^{k} \...
- 89