Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
0answers
33 views

Is this the correct proximal operator?

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
1answer
20 views

Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
0
votes
0answers
12 views

Impact of convexity under different changes of variables for different parts of optimization

Let $$ \min_x f(x)$$ such that $$ C(x) \le 0$$ where $C$, and $f$ each are convex under respective changes of variables. How does that impact the optimization? If standard algorithms are sensitive ...
1
vote
0answers
52 views

Feasible Region of QCQP and Semidefinite Programs

I am trying to visualize the feasible region of a Quadratically Constrained Quadratic Program (QCQP) which is expected to be non convex (actually is a set of ellipses in $\mathbb{R}^2$) and the ...
2
votes
1answer
38 views

Solve the closed form solution for argmax of $ x^Ty - x^T\ln(x)$

Let $y \in \mathbb{R}^n, \ln(x) = \begin{bmatrix} \ln(x_1) \\ \vdots \\ \ln(x_n) \end{bmatrix} \in \mathbb{R}^n$ Show that $$x^* = \text{argmax}_{x \in \mathcal{D}} \quad x^Ty - x^T\ln(x)$$ ...
0
votes
2answers
26 views

Optimization of the function of two variables

I have two functions $f(x,y)$ and $g(x,y)$. I want to minimize the sum of these functions w.r.t $x,y \in (0,1)$. I know that for fixed values of $x$, $f(.,y)$ is a decreasing function while $g(.,y)$ ...
-1
votes
1answer
14 views

Sum of convex and decreasing function

I have a sum of decreasing function and a convex function over some domain. Can I say that the sum is also a convex function (i.e. there exists a unique minimum)?
0
votes
0answers
15 views

Solving $I^* = \arg\min_{I'} \left( \|\phi_\ell(I) - \phi_\ell(I')\|_2^2 + R(I') \right)$ with gradient descent

I am trying to create the results from this a paper that is trying to understand the types of features a convolutional neural network is learning to recognize. I don't think understanding ...
17
votes
5answers
504 views

How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?

Let $A$ be a real $m \times n$ matrix. How do you prove that $\{ Ax \mid x \geq 0, x \in \mathbb R^n \}$ is closed (as in, contains all its limit points)? The inequality $x \geq 0$ is ...
0
votes
1answer
48 views

Unique critical point and psd implies pd and hence strict relative maximum

Let $f(x)$ be of class $C^{(2)}$ on an open set A, $x_0\in A\subseteq R^n$ a critical point. In addition, the hessian matrix of f(x) at $x_0$, $H(x_0)=\{f_{ij}\}|_{x=x_0}$, is negative semi-definite. ...
1
vote
2answers
98 views

Decrease in the size of gradient in gradient descent

Gradient descent reduces the value of the objective function in each iteration. This is repeated until convergence happens. The question is if the norm of gradient has to decrease as well in every ...
1
vote
0answers
16 views

Benders decomposition Master Problem

I am currently working on implementation of Bender's Decomposition for MIP. I am looking at the simplest model \begin{equation} \begin{split} \min_{x,y} &\; c^Tx + f(y)\\ s.t. & \; Ax + Dy \ge ...
1
vote
0answers
20 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
0
votes
1answer
7 views

Strongly monotone and cocoercive

A map $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ is $m$-strongly monotone if $$ (x-y)^{\sf T}((f(x)-f(y)) \geq m \|x-y\|_2^2 $$ for $m > 0$ and is $\delta$-cocoercive if $$ (x-y)^{\sf T}((f(x)-f(y)) \...
0
votes
0answers
21 views

Number of solutions to a system of nonlinear equations for n number of variables

We can use Descartes' rule of signs to find the number of roots for a polynomial. We can use Bezout's Theorem to find the number of roots to a nonlinear system of equations with two variables. What ...
4
votes
1answer
50 views

How can I experiment with Lagrange multiplier in QCQP?

Suppose we want to solve following optimization problem (it is a PCA problem in this post) $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \mathbf w^\top \...
1
vote
0answers
15 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
2
votes
1answer
1k views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
0
votes
1answer
41 views

maximize 3-variable linear function [version 1.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}x_2 + \frac{...
0
votes
0answers
27 views

Sum/product of two functions of two variables are to be minimized

I have two functions $f(x,y)$ and $g(x,y)$ whose sum/product (whichever is possible) is to be minimized. The values of $x,y$ can vary in the interval $0<x,y<1$ (hence none of them can have a ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
1answer
24 views

Why $f:R^2\to R$, with $\mbox{dom} f=R^2_+$ and $f(x_1,x_2) =x_1x_2$ is quasiconcave?

Why $f:R^2\to R$, with $\mbox{dom} f=R^2_+$ and $f(x_1,x_2) =x_1x_2$ is quasiconcave? I have tried to use Jensen eniquality to check that superlevel set $\{x\in R^2_+ | x_1x_2 \ge \alpha\}$ is convex....
1
vote
1answer
22 views

Is the root of a sum of squared differences convex?

Let $x \in \mathbb{R}^n$. Let there be a collection of functions $d_i = (x_j - x_k)^2$ (note that the subscripts $j$ and $k$ are fixed for each $d_i$, and there can be repeated use of subscripts on ...
0
votes
1answer
35 views

Related to Caratheodary theorem

If $P$ is a set of vectors $\textbf{x}_i$'s where every $\textbf{x}_i$ is of dimension $d$ and $|P|=K$. In this case at many places I have seen that the vectors $\textbf{x}_2-\textbf{x}_1,\textbf{x}...
2
votes
1answer
553 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
11 views

McCormick Envelopes with more then 2 variable

Suppose that I have the function $z=\sin(x)\cdot y$, where $0\leq x<=0.5$ and $0\leq y\leq 1.0$. If I do the best convex relaxation of $\sin$ and than compute $z=\operatorname{Relax} \sin(x) \cdot ...
2
votes
3answers
2k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
0
votes
1answer
35 views

What are spurious local optima?

I keep seeing that word "spurious" (when used in the context of optimization), but I'm having trouble finding a good reference on what the definition of the term is.
0
votes
1answer
18 views

floor/ceiling/round functions in the constraints of an optimization?

I have a constrained optimization problem in which I have to impose a "floor" or "ceiling" constraint to the solution. In fact I decided to use these nonlinear rounding functions because I needed to ...
1
vote
0answers
14 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
1answer
23 views

On accelerated Proximal Gradient Methods

I am working on accelerated optimization scheme, which unified in the paper by Paul Tseng, "On Accelerated Proximal Gradient Methods for Convex-Concave Optimization". But unfortunately, it is ...
0
votes
1answer
12 views

Does projected gradint descent(pgd) results in the same minimizer as the one given by unconstrained gd and projected back on the constrained set?

For $f: \mathbb{R}^n \mapsto \mathbb{R}$ with $f(x) < \infty,\;\forall x \in \mathbb{R}^n$ and for convenience let's assume $f$ is continuously differentiable. Suppose we are trying to solve the ...
0
votes
1answer
19 views

Is convexity the most general dividing line between “easy” and “hard” optimization problems.

Just got started with Boyd's Convex Optimization. It's great stuff and I see how it directly subsumes the all-important linear programming class of models. However, it seems that if a problem is non-...
0
votes
1answer
46 views

Minimizing a strictly convex function with inequality constraint

So we've been learning about the Kuhn Tucker conditions in my non-linear optimization course and I've been having trouble with this problem: QUestion: description here Question: a strictly convex ...
2
votes
1answer
26 views

What are some applications of entropy maximization and minimum volume covering ellipsoid?

I'm reading Boyd's Convex Optimization textbook. In particular, I'm currently focusing on Chapter 5 (Duality). There is a frequent recurrence of two examples: Minimum volume covering ellipsoid \...
1
vote
1answer
46 views

A question about Lagrange multiplier in optimization

I read @amoeba 's answer in this post, PCA optimization problem is $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \|\mathbf w\|_2=1 $$ where $\mathbf C$ ...
0
votes
0answers
27 views

How do I prove that this function is concave on $f_{ij}(x)$?

I am trying to apply convex optimization to the following problem- ${f^*}(x) = \mathop {\arg \max }\limits_{{f_i}(x)} \sum\limits_i {\ln \left\{ {u_i^* - \sum\limits_j {\frac{1}{{\left( {1 - {\rho _{...
0
votes
1answer
52 views

Directional Derivative defines Descent Direction

Let $f:\mathbb{R}^m \mapsto \mathbb{R}$ be a proper convex function that is not necessarily differentiable and let $x\in\mathbb{R}^n$ be such that $\mathbf{0} \notin \partial f(x)$. I want to prove ...
1
vote
1answer
1k views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...
1
vote
0answers
51 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
0
votes
1answer
27 views

Robusness of median

If we let $X$ be a set of pints in $\mathrm{R}^2$, and let $g(X) = \arg \min_{y \in \mathrm{R}^2} \sum_{x_i \in X} \parallel x_i -y \parallel_2$ (geometric median of $X$). If $X$ and $X'$ are ...
0
votes
0answers
14 views

Uniqueness of projection implies convexity [duplicate]

Prove that for a compact set A in finite dimensional Euclidean space X, A is convex if and only if for any point x in X, the projection of x to A is unique. If we know A is convex, we can show the ...
0
votes
0answers
9 views

Minimizing component-wise convex functions

I want to minimize a function $f(\vec x,\vec y)$, whereby $\vec x$ and $\vec y$ are vectors. If I hold $\vec x$ constant, $f(\vec x,\vec y)$ is convex with respect to $\vec y$, and the reverse is true ...
2
votes
1answer
78 views

Linear program with two equality constraints

Compute the minimal value of $$x_1 + 2x_2 + 3x_3$$ when $x_1$, $x_2$, $x_3$ satisfy $$x_1 − 2x_2 + x_3 = 4$$ $$−x_1 + 3x_2 = 5$$ and $$x_1 \ge 0, \qquad x_2 \ge 0, \qquad ...
0
votes
3answers
70 views

Orthogonal Projection onto the $ {\ell}_{\infty} $ Ball

What is the Ortohogonal Projection onto the $ {\ell}_{\infty} $ Ball? Namely, given $ x \in {\mathbb{R}}^{n} $ what would be: $$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x ...
0
votes
1answer
34 views

Convex or non-convex function

I want to minimize the following function $$\frac{a}{bxy+cd}e^{\frac{a}{bxy+cd}}H+2-\Gamma(1,\frac{eaf}{b(1-x)},\frac{eagf}{bx(1-y)})$$ where $a,b,c,d,e,f,g,H$ are constants and greater than $0$. $\...
2
votes
0answers
23 views

How to deal with a convex constraint

I want to deal with a convex constraint \begin{align} F(P)=P^{H}AP_{0}+P_{0}^{H}AP-P_{0}^{H}AP_{0}\succeq 0 \end{align} where $(\cdot)^{H}$ represents Hermitian transpose, $A$ is a positive definite ...
3
votes
2answers
1k views

Time complexity of a convex quadratically constrained quadratic program (QCQP)

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references? Thank you very much.
3
votes
0answers
551 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through Lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...