Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
0answers
15 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 ...
1
vote
0answers
20 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)$$ ...
1
vote
1answer
28 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
1answer
27 views

How to find the analytical solution of this optimization problem?

I have an optimization problem of the form $$\begin{align} \text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,& \sum_{i=1}^{k}x_{ij}\leq 1,\;\forall ...
0
votes
0answers
6 views

Proximal operator of the sum of two norms

I'm a little new to this and not sure how to evaluate the proximal operator in this context, assuming a closed form exists. Calculate $\text{prox}_{c,f+g}(v)$, where $f(x) = \frac{1}{2}\|Ax-b\|_2^2$...
3
votes
1answer
63 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...
2
votes
0answers
23 views

Maximizing $\frac{\int_r^1xf(x)dx}{2-F(r)}$

Consider a continuous distribution on $(0,1)$ with probability distribution function $f$ and cumulative distribution function $F$. Define $$g(r)=\frac{\int_r^1xf(x)dx}{2-F(r)}$$ and let $r_M\in(0,1)$ ...
0
votes
0answers
11 views

Find rotation matrix to match points in parallel projection

I am given two sets of 3D points (actually 2D, see below) with corresponding pairs. I am seeking two 3D rotation matrices, such that (only) the X and Y components of the rotated points match best (...
0
votes
1answer
31 views

Minima of symmetric polynomials subject to two symmetric constraints

The homogeneous symmetric polynomial of degree $k$ in $n$ variables is $$ f_k(x_1,x_2,\dots,x_n) = \sum_{i_1<i_2<\cdots<i_k}x_{i_1}x_{i_2}\cdots x_{i_k}. $$ Consider the following ...
-1
votes
0answers
13 views

Solve $\max \mathrm{sum}(AXB \geq \gamma), X \in \{0,1\}^{N \times N}$

I have a problem to find the best permutation matrix $X \in \{0,1\}^{N \times N}$, so as to maximize the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
6
votes
1answer
947 views

Why does SVD provide the least squares solution to $Ax=b$?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
1
vote
2answers
31 views

Maximizing the sum of the squares of numbers whose sum is constant

I wonder how one goes about to find the maximum of $\sum v_i^2$, the $v_i$'s being positive integers whose sum $\sum_i v_i$ is fixed.
1
vote
0answers
12 views

Finding optimal cyclic permutations

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
0
votes
0answers
12 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 ...
0
votes
1answer
12 views

In Constrained Optimization, Restrict Domain to Open Set $A\subset\mathbb{R^N}$?

In constrained optimization and context of economics (e.g. utility function with quantity of goods as arguments subject to wealth), why do textbooks always restrict domain of the objective function ...
1
vote
0answers
10 views

Invertibility of bordered Hessian

I have an optimization problem: $max f(x)$ s.t. $Ax=b$, where $x \in R^n$ and $b \in R^m$, $m \le n$. I know that $f$ is strictly quasi-concave, and that $A$ has rank $m$ (linearly independent, ...
0
votes
1answer
455 views

How to solve for maximum area of a rectangle under a curve?

Having trouble with this optimization question and was hoping I could get some help with it. The function of the curve is $8^{-\frac{x}{5}}$. I would greatly appreciate a full explanation. I already ...
0
votes
0answers
15 views

Solve $ \max U = [\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} ]^{{\sigma \over {\sigma - 1}}} $

The problem is $$ \eqalign{ & \max U = \left[\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} \right]^{{\sigma \over {\sigma - 1}}} \cr & \...
0
votes
0answers
9 views

Momentum Potential Term in Optimization Problem for Implicit Euler Solver

I'm trying to understand the explanation of the implicit Euler solver (Section 3.1) set forth in this paper: Projective Dynamics: Fusing Constraint Projections for Fast Simulation For the purposes of ...
2
votes
0answers
33 views

Finding a maximum with some constraints

I would like to maximize the term $ l_1b_1+l_2b_2+l_3b_3-2 $ such that the following conditions hold: $ 1>l_1>l_2>l_3>0 $, $ l_1,l_2,l_3 \in \mathbb{Q} $, $ b_1,b_2,b_3 \in \mathbb{N} $...
0
votes
1answer
32 views

Is sup of max, same as max of sup?

Let $\sigma_1, \sigma_2 \dots \sigma_n$ be functions of $\omega \in \mathbb{R}_+$. Is $\sup_{\omega}(\max_{i=1:n} (\sigma_i))$ same as $\max_{i=1:n}( \sup_{\omega}(\sigma_i))$? Could you also please ...
1
vote
4answers
44 views

$\cos2\theta +\cos\theta +k = 0 $ - set of all values of $k$ for which there is a solution

The set of all values of $k$ (real), such that the equation $\cos2\theta +\cos\theta +k = 0 $ admits a solution for $\theta$ is? MY ATTEMPT: I substituted $\cos2\theta$ with $2\cos^2\theta - 1 $. On ...
1
vote
1answer
42 views

Are minimizing a function and root finding the same?

What is the relationship between minimizing a function and finding a root of an equation? Are the the same? I know in both problem we have similar algorithms, such as gradient decent, or newton's ...
0
votes
0answers
16 views

How to find the maximal length of a system?

Let P be the set of $(a,b,c)^t \in \mathbb{R}$ which satisfies the following inequalities: $-2a+b+c \leq 4$ $a-2b + c \leq 1$ $2a + 2b-c \leq 5$ where $a \geq 1 $, $b \geq 2$, and $c \geq 3 $. ...
4
votes
2answers
46 views

Maximizing product of five-digits numbers

From a French 2016 puzzle and math contest, where no calculator is allowed Using each of the digits $0,1,2,3,4,5,6,7,8,9$ exactly once, find two five-digit integers such that their product is ...
0
votes
0answers
11 views

Direction of a gradient at maximizer on the boundary

Let $u \in C(\bar{B})$ where $B=B_1(0) \subset \mathbb{R}^n$ is the unit ball. Assume $u$ attains its maximum at $x_0 \in \partial{B}$ and $\nabla u(x_0) \neq 0$. What can we say about the direction ...
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
0answers
17 views

alignment of two sets of vectors

I have a maximisation problem to do with aligning two ordered sets of 3D unit vectors. I want to apply the same rotation to all the vectors in one set so that they are in closest alignment with those ...
0
votes
0answers
21 views

Calculate the division between total height by base's diameter.

One silo for grains storage was built in a form of a cylinder (floor and walls) with a hemispherical roof. The silo is design to have a certain volume $V$. Calculate the division between total height ...
3
votes
1answer
68 views

Maximization of a determinant

I'd like to compute $$ \DeclareMathOperator*{\argmax}{arg\,max} A^*=\argmax_{\substack{A\in\mathbb{R}^{d\times k}\\A^T A=I}} \det(A^T \Lambda A) $$ where $k\leq d$, $\Lambda=\operatorname{diag}(\...
0
votes
1answer
13 views

Why does Frobenius norm make BFGS scale-invariant?

On slide 11 here it is claimed that the weighted Frobenius norm leads to a scale-invariant optimization method. Similar claims about this norm can be found throughout the literature see 1,2,3. In ...
1
vote
1answer
25 views

Reducing KKT system

I was using CVXOPT library to solve one of my quadratic programming problem. I found that, CVXOPT library solves KKT system efficiently by reducing a 3x3 matrox into 2x2 blocks which has the following ...
1
vote
0answers
18 views

Can I call my algorithm as EM algorithm? Can I claim convergence guaranty?

I am trying to minimize the following problem: $$\hat{x} = \underset{\bar{x}}{\operatorname{argmin}} \left( \left\|y- A_{MV}^{EPG} \bar{x}\right\|^2 + \|\mu_{T} \bar{x}\|^2 + \|D_{s} \bar{x}\|^2 \...
2
votes
0answers
28 views

Maxima of $f(x)/e^x$ where $f(x)$ is an approximation of $e^x$ using Stirling's

Let $$f(x)=1+\sum_{n=1}^\infty\frac{x^n}{\sqrt{2\pi n}(n/e)^n}\tag1$$ and let $$g(x)=\frac{f(x)}{e^x}\tag2$$ If we plot $g(x)$ we get a graph that looks like this: Clearly there is a maximum at ...
3
votes
1answer
47 views

What is the name of this problem? linear Matrix equation optimization?!

I have almost no knowledge in linear algebra but I need to understand the process of solving a problem. In fact I'm looking for some keywords or hints to know what exactly should I be Googling! So any ...
0
votes
0answers
18 views

maximize a sum of unit fractions (without containing a subset of sum 1)

Let $ u \ge 2 $ be fixed. Then consider: $ S(u)=\max\left\lbrace \sum_{i=1}^{u+1} \frac{c_i}{t_i} \, \middle| \, 2 \le t_1 \le t_2-1 \le \ldots \le t_{u+1}-1, \, t_i \in \mathbb{N}, \, c_i \in \...
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 ...
3
votes
2answers
58 views

Minimize $\mbox{trace}(AX)$ over $X$ with a positive semidefinite $X$

I want to minimize $\mbox{trace}(AX)$ over $X$, under the constraint that $X$ is positive semidefinite. I guess the solution should be bounded only for a positive semidefinite $A$, and it's zero, or ...
2
votes
1answer
20 views

Canonical forms which have “minimal” Gershgórin discs, do they exist?

I'm wondering about if there is some way to define, uniquely or not a canonical form which has minimal radii for Gersgórin discs. To be more specific for a given matrix $\bf A$, find $\bf C$ and $\bf ...
0
votes
1answer
430 views
0
votes
1answer
30 views

How can this be minimized?

I have the following function of $x_1$ and $x_2$: $$e(x_1,x_2)= (x_1^2+x_2^2)(a+n)+2a(-x_1+x_1x_2-x_2)+a^2$$ where $a$ and $n$ are real numbers. I want to find the values of $x_1$ and $x_2$ that ...
3
votes
2answers
103 views

How to maximize Std Dev given a range of possible values, a number of values, and a specific mean?

(I'm asking here and not stats.stackexchange because I'd like a mathematical proof of this) In this question: Prove how to maximize Standard Deviation given a certain mean $\bar{x}$ and set of values;...
1
vote
0answers
27 views

minimize quadratic form

In question Minimize Energy using Gauss-Seidel method with successive over- relaxation., when $$ E = \sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 + \lambda\sum_{i,j}\|\mathbf N_i - \mathbf N_j\|^2 = \...
1
vote
0answers
29 views

In Nonsmooth Optimization, whats the point of $x \in G$ being a local minimum results in $0 \in \delta\ f(x)+N_G(x)$

I'm reading about nonsmooth optimization and specially the book 'Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control' by Marko M. Mäkelä, Pekka Neittaanmäki. At page ...
6
votes
0answers
147 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
0
votes
1answer
12 views

Formulating a problem involving sets with ILP

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost ...
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
14 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 ...
7
votes
0answers
152 views

Optimal decomposition of discrete function into sum of factorised terms

I am trying to solve the following optimisation problem. Let $x_i \in \{1, \ldots, N_i\}$ be discrete variables, and $f(x_1, \ldots , x_n)$ any real-valued function. I want to decompose $f$ into a ...