# Tagged Questions

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

0answers
36 views

### Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem  (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1answer
63 views

### How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
1answer
40 views

### Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \}$ and $H : \mathbf{c}^{T}\mathbf{x} = \beta$ with \$ \min_S ( ...
1answer
139 views

### Global Min-Max Optimization

When is \begin{equation} \min_X \max_Y f(X,Y) \end{equation} globally solvable? (i.e. we can find global solution for the optimization problem?) I am not looking for reformulations. Is it only when ...
3answers
74 views

### Proof of Convexity

Is the function $Trace(AX^TBX)$ a convex function in $X$ or not ? Here, $X$ is a rectangular matrix and $A,B$ are square, symmetric, p.s.d matrices. The entries in $X,A,B$ are real valued.
1answer
160 views

### Joint Convexity

Is the problem \begin{equation} \min_X \max_Y -\operatorname{tr}(X^TY)-\operatorname{tr}(Y^TYX) \end{equation} Jointly convex in $X$ and $Y$? Can we solve it globally? Why or Why not? $X$ and $Y$ ...
1answer
67 views

### Convex Sets Versus Convex Functions

Can we specify all convex sets, in terms of convex constraints (convex inequality functions) on a variable?
1answer
120 views

### What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
0answers
30 views

### General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
1answer
153 views

### Strict convex function?

I try to prove that $g(x)= K |x|^2/2 + z(x)$ is strictly convex, given that $z(x) \geq - m(1 + |x|^p)$ with $m \geq 0$, $0 \leq p \leq 2$, forall $x \in \mathbb{R}^n$, provided $K$ is sufficiently ...
3answers
58 views

### lower bound of a special type of convex functions

Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.) How to show \$f(x)\geq\frac{1}{2L}\|\nabla ...
1answer
36 views

### Concave optimal value?

Let $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{m \times n}$. Consider a compact set $C \subset \mathbb{R}^n$. For all $x \in C$ define  f(x) := \min_{y \in \mathbb{R}^m} \{ x^\top A y ...
1answer
43 views

### Simple question about the solution of non-linear equations

Given, say $4$ non linear equations with $4$ positive parameters, $$f_1(x,y,z,t)=a,\quad f_2(x,y,z,t)=b,\quad f_3(x,y,z,t)=c,\quad f_4(x,y,z,t)=d$$ for given $a,b,c,d$, If I am able to show that ...
0answers
68 views

### Max Quadratic Expression

Let $A \in \mathbb{R}^{n \times n}$, $A = A^\top$, $B \in \mathbb{R}^{m \times n}$, and $\mathcal{C} \subset \mathbb{R}^n$ be a compact, convex set. For $A$ not negative semidefinite, how to globally ...
1answer
65 views

### A point which I couldnt understand in a paper.

Currently I am reading a paper and the author has an optimization problem $$\max_w\frac{w^2\alpha}{w^2\beta+v}$$ Then he substitutes $w^2$ with $x$ and defines an objective function using a ...
0answers
125 views

### Convex Functions on 2 variables over an interval

It is required to show that $f(x) = x_1x_2$ is a convex function on $[a,ma]^T$ where $a\ge 0$ and $m\ge1$.To show convexity we need to show that for $\lambda \in [0,1]$: \$f(\lambda x + (1-\lambda ...
1answer
38 views

### Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
0answers
45 views

### Prove that $\text{int}(\text{dom}(f))$ is a convex set.

Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
2answers
405 views

### Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: 1) How ...
0answers
61 views

### Explain $x^*$ of subgradient in KKT -conditions: primal optima or dual optima?

I asked this question here but I noticed that this notation $x^*$ may actually mean two things: primal optimality and dual optimality. Please, explain this notation particularly here: I understand ...
1answer
56 views

### Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
1answer
77 views

### Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find \min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
0answers
28 views

### using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with \$|S| ...
1answer
38 views

### property of cones and their duals

I am reading Convex Optimization by Boyd and Vandenberghe (free at http://www.stanford.edu/~boyd/cvxbook/) and I am trying to justifying their assertion (p. 53) that if $K$ is a proper cone, $K^*$ is ...
0answers
99 views

### sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
3answers
215 views

### Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
1answer
90 views

### What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
1answer
59 views

### Matrix computations problem: rank, pseudo inverse,…

Suppose we are given two arbitrary $m \times n$ matrices, $A$, $B$, where we know $B$ has full column rank. Let $m>>n$. Can we always find a square $m \times m$ matrix $X$, such that $A=XB$? I ...
0answers
70 views

### Is positively weighted sum of eigenvalues of a matrix X, convex function of X?

Is positively weighted sum of eigenvalues of a matrix X, convex function of the matrix X?
0answers
235 views

### Calculation/Estimate of Lipschitz Constant for Strictly Convex Function

I have a strictly convex function $f(\bf{x}) = \dfrac{1}{2}\bf{x'Ax + b'x}$ where $\bf{f} : \mathbb{R^n} \rightarrow \mathbb{R}$ and I was wondering how I can find/estimate the Lipschitz ...
1answer
141 views

### Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
1answer
87 views

### Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
1answer
85 views

### Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)

Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian. ...
1answer
207 views

### Lagrangian Multipliers

I have a fundamental question about Lagrange multipliers. Here it is: I have a function to maximize with respect to a parameter say $\theta$, subject to two constraints. Lets assume that the first ...
1answer
20 views

### unstable optimizer, stable objective

I am trying to minimize a convex objective numerically using gradient descent. I select the starting point randomly. I repeat the experiment multiple times. The optimal objective value I get each time ...
0answers
95 views

### Upper bound for L1-L2 optimization problem

I am interested in the following convex optimization problem: \begin{align*} \max & ||x||_1 \\ \text{s.t.} & ||x-a||_1 \le K \\ & ||b\circ x||_2 \le 1\\ & x \in R^n \end{align*} where ...
0answers
142 views

### Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given \$a, b \in ...
2answers
39 views

### Convexity of a function and constraint

Consider the quadratic function $f(x_1,x_2,x_3,x_4)=x_1+2x_2+4x_4+x_1^2+5x_2^2+3x_3^2x_4^2-4x_1x_2-2x_2x_3+2x_3x_4$. Is f a convex function? Consider a constraint defined using the above function f: ...
2answers
136 views

### definition of strongly convex

There are several equivalent definitions for strongly convex. For example, some literature said: A function $f$ is strongly convex with modulus $c$ if either of the following holds f(\alpha ...
0answers
71 views

### Branch-and-Price algorithms for IP/MIP

I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
1answer
74 views

### what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]

we 100000000 sets/locations. each set has, A = % chance of finding a cure (there are many different types of cures) for cancer B = time it takes to extract a cure to caner C = the optimal % chance (IN ...
0answers
89 views

### minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
1answer
69 views

### Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1$$ $$\text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s}$, \$Z \in ...
1answer
135 views

### Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1answer
85 views

### Gradient of Moreau-Yosida Regularization

Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as $F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$ \$Prox_f(x)=\arg\min_y ...
0answers
28 views

### construction of a packing for polytope

Let $C=[-1,1]^n$ and $H$ be a plane with equation $\sum_{i=1}^nr_i=s, 1\le s\le n.$ (Here $r_i$ are such that $Proba(r_i=1)=Proba(r_i=-1)=1/2$). The intersection $C \cap H$ is a polytope, $P(n, s)$. ...
3answers
302 views

### Why is the affine hull of the unit circle R^2?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $R^n$ as \text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + \ldots ...
0answers
93 views

### Formulation and solution of non-linear optimzation problem with inequality constraints

I'd like to know if the following problem is well formulated and has solutions. I'm very new to the subject of nonlinear optimization with inequality constraints ('teaching myself the Kuhn-Tucker ...
1answer
79 views

### Intuition behind gradient VS curvature

In Newton's method, one computes the gradient of a cost function, (the 'slope') as well as its hessian matrix, (ie, second derivative of the cost function, or 'curvature'). I understand the intuition, ...
3answers
184 views

### Summary of Optimization Methods.

Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background). Anyway, I seem to ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 121, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8862180113792419, "perplexity_flag": "middle"}