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.
218
questions
0
votes
0answers
39 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 ...
0
votes
0answers
41 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 ...
-1
votes
0answers
46 views
How to solve semidefinite program using CVX?
I am reading the research paper
Abel Molina, Thomas Vidick, John Watrous, Optimal counterfeiting attacks and generalizations for Wiesner's quantum money, 2012.
and I want to prove the SDP result in ...
0
votes
0answers
30 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 ...
6
votes
0answers
82 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 ...
2
votes
1answer
53 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))$, ...
0
votes
0answers
56 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 $\...
0
votes
0answers
59 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 ...
4
votes
1answer
90 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. \...
3
votes
0answers
54 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....
2
votes
0answers
110 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 ...
2
votes
1answer
120 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}
\...
1
vote
1answer
115 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}...
1
vote
2answers
129 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{...
2
votes
1answer
92 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} &...
5
votes
0answers
94 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} $$
...
2
votes
1answer
91 views
Project to nearest point on convex polyhedron
I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\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 \...
0
votes
1answer
228 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 ...
1
vote
1answer
122 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?
7
votes
0answers
266 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
vote
1answer
93 views
4
votes
2answers
430 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 ...
4
votes
1answer
185 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 ...
1
vote
1answer
90 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 ...
2
votes
0answers
111 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 ...
2
votes
0answers
54 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
1answer
90 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]\\
&\...
1
vote
1answer
86 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
1answer
201 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 ...
5
votes
0answers
105 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 ...
6
votes
1answer
83 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) + ...
3
votes
1answer
475 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.
$$
\...
3
votes
0answers
109 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_{\...
4
votes
1answer
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, ...
3
votes
2answers
467 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} \...
4
votes
1answer
53 views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
1
vote
1answer
146 views
Optimize multivariable function with interdependent variables
I have a cost function with 2 parameters. The variables are dependent on each other. So, if I just take a partial derivative with respect to one variable the slope is in terms of the other variable ...
2
votes
0answers
46 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
0
votes
0answers
37 views
Minimizing the ratio of two specific non negative quadratic convex functions
$F$ is $m\times m$ diagonal, with real non negative elements
$D$ is $n \times m$ complex
$P$ is $n \times 1$ complex
$A$ is $m \times 1$ complex.
Minimize $\Gamma(A)$, with respect to $A$.
$$\...
6
votes
1answer
115 views
numerical solution of an under-determined linear equation in high dimensions
I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
0
votes
1answer
76 views
Formulate and solve a simple conic programs in cvxpy language [closed]
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty.
Question
(A)...
0
votes
1answer
31 views
Gradient ascent method with a constant step size?
I'm trying to use the gradient ascent method on a convex function like the multivariate-Normal density function with respect to its parameters (the original is a bit more complicated), something ...
2
votes
1answer
119 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
3
votes
0answers
95 views
Why the MIRACLE of Lanczos/CG-like?
Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy...
In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
-1
votes
1answer
25 views
Semi-Definite relaxation of non-linear constraint?
I am implementing an optimization problem using semi-definite approach. One of my constraints is of following form
$ trace(A∗X)−(k∗trace(A∗X))+(k∗\sqrt {(trace(B∗X)} )==0$
where k is a constant, A ...
2
votes
0answers
40 views
Where can I find sample data for large linear programming optimization problems?
I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
1answer
531 views
Why does Newton's method with Linear Equality Constraints use KKT condition?
Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.
The problem only has equality constraint. Why ...
1
vote
0answers
47 views
Order of a principal term
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a bound for the total number of iterations for some process. See page 109:
$$\left[\frac{1}{\ln(2(1-\kappa))} \ln\frac{t_0-t^...
2
votes
1answer
141 views
Convergence rate and complexity for convex minimization problem
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
3
votes
0answers
113 views
First order methods for a large scale semidefinite program
I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...
