Computational Science

Questions tagged [convex-optimization]

Ask Question

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.

225 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
11
votes
2answers
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 ...
2
votes
1answer
86 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 ...
0
votes
0answers
60 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$$ ...
0
votes
1answer
78 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 ...
0
votes
1answer
60 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 ...
4
votes
0answers
176 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 ...
2
votes
0answers
71 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 ...
1
vote
0answers
56 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 $...
0
votes
0answers
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 ...
0
votes
0answers
49 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 ...
0
votes
0answers
46 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
87 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
76 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
86 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
65 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
188 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
64 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
114 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
239 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
161 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
134 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
114 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
95 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
119 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
407 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
172 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
271 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
103 views

Why am I getting this DCPError when my matrix is PSD?

...
4
votes
2answers
560 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
202 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
92 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
121 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
59 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
128 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
87 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
264 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
106 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
102 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
588 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
113 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
609 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
54 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
166 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
48 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
39 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
120 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
35 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
128 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: ...

1
2 3 4 5

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.