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)

0
votes
0answers
24 views

simplex algorithm - minimization

So I get the basic concept of simplex algorithm but I am working on a project where I have to implement any linear programming algorithm (I chose simplex method) to minimize a function, but I don't ...
0
votes
0answers
21 views

Is there a convergence proof for ADMM applied to biconvex/bilinear problems?

I wonder if there is a local convergence proof for ADMM applied to biconvex problems? More specifically, my problem is as follows: $\text{minimize}_{x,y} f(x) + g(y) + \| y \circ Ax \|_2^2 $ , ...
1
vote
0answers
28 views

Why Was Backprop Invented?

I'm currently researching artificial neural networks and I keep wondering why do we use "backpropagation" to train a neural network. An ANN is basically just a very large and complex function ...
2
votes
2answers
41 views

Minimizing Norm

I have below problem: Find $\bf C$ to minimize $\|\mathbf A-\mathbf B\mathbf C\|_F$. Given ${\bf B} \in \mathbb R^{m \times n}$, ${\bf B}$ has lin. ind. col. A satisfies: ${\bf DA} = {\bf E}$ , ...
0
votes
1answer
45 views

How to simplify the summation of log

I have a summation that involve log. I don't know how to solve this summation. I want to find an expression (even a good approximation is enough) for this summation. $\sum_{k=0}^{n}{log(a_k)}$ ...
3
votes
0answers
49 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
0
votes
1answer
34 views

meaning of Farkas' Lemma

Quoting from Jorge Nocedal's Numerical Optimization second edition, page 326 bottom to page 327, Farkas' Lemma Let the cone K be defined as in (12.45). Given any vector $g \in \mathbb{R}^n$, we ...
0
votes
0answers
14 views

Direction in Dual Simplex method

In the dual simplex problem, when primal become inconsistent then dual have direction. How can we find this direction using dual simplex algo ?
0
votes
0answers
8 views

Empirical likelihood method to Find the order of a parameter given a set of constraints

Firstly we assume that $X_1,...X_n$ are order statistics($X_i\leq X_{i+1}$) from an i.i.d sample of random variables and let $r$ be integer and $r\geq1$. Start with the Equation (1) as following ...
0
votes
0answers
22 views

Maximize $x^tQx$ s.t $||x|| \leq 1$

I would like to verify that I have solve correctly the following problem: $maximize\; x^tQx\; s.t. ||x|| \leq 1$ Using Lagrangian multipliers I derived the following: $2Qx = λx$ So $x$ are the ...
1
vote
0answers
12 views

Lagrange Multiplier for clustering with size constrains

I'm trying to solve a clustering problem with size constrains. Minimize $J=\sum_{i=1}^c\sum_{j=1}^n {{u_i}_j}^2{d_i}_j$ Subject to $\forall 1\le j\le n : \sum_{i=1}^c {{u_i}_j}=1$ and ...
0
votes
1answer
22 views

convergence of steepest gradient descent

The description of gradient descent in Wikipedia says: $$x_{n+1} = x_n - \gamma_n\nabla F(x_n)$$ for $n = 0,1,2,...$ Suppose that $x_n$ converges to $x$. Then, is it always true that $\nabla F(x) = ...
0
votes
0answers
13 views

(Empirical likelihood method) Find the order of a parameter given a set of constraints

Firstly we assume that $X_1,...X_n$ are order statistics($X_i\leq X_{i+1}$) from an i.i.d sample of random variables and let $r$ be integer and $r\geq1$. Start with the equation (1) \begin{equation} ...
1
vote
1answer
32 views

Optimal strategy in the following game:

In this game, 12 hidden D6s are rolled and summed. The player is given the total of the rolled dice. The player will then guess a number from 1 to 6. If there is a unrevealed dice with that number, ...
3
votes
1answer
31 views

How to find the largest disk in a square when there are points we must avoid?

We have $n$ points $X =\{x_1, x_2, \dots, x_n\}$ inside (let's say) the unit square $Q$. We must find a disk $D\subset Q$ such that none of the points of $X$ are inside the disk. (The points can be on ...
0
votes
4answers
93 views

Let $x$ and $y$ be real numbers such that $x^2 + y^2 = 1$. Find the maximum value of $2x - 5y$.

Let $x$ and $y$ be real numbers such that $x^2 + y^2 = 1$. Find the maximum value of $2x - 5y$. I do know how to solve this problem using trigonometry, however I need to solve it by using vectors. ...
-2
votes
0answers
23 views

Linear programming right hand side is abstract

I am solving a problem in network flows which uses linear programming to find the minimal point of a. the problem stated is to minimize a with contain to: $x_1 + x_2 \le a$ $x_3 + x_4 \le a$ ...
0
votes
0answers
33 views

Using semidefinite programming to solve the following problem

I am struggling with the following problem, and wonder is SDP can help: $$\mathrm{maximize\ } \alpha_{10}+\alpha_5+(\alpha_2+\alpha_8)/2 \mathrm{\ subjected\ to\ } \mathrm{T_1}\succeq0, ...
0
votes
0answers
36 views

Lagrange multiplier method

Question 1: Could somebody please refer me to an introduction to Lagrange multipliers which is easy to read but still in full generality? Question 2: I am interested in particular in the following ...
0
votes
0answers
30 views

Minimizing Unintegrable Exponential Function

I am trying to develop an algorithm which minimizes an unintegrable function. I don't have a strong mathematics background and am unaware of such strategies. My integral is of the following form: ...
0
votes
0answers
18 views

How does one minimize determinant on this linear system?

I have a problem where want to determine loading factors such that can reduce a covariance matrix as close to 0 volume as possible, where the original covariance matrix is specified as: $\ \ \ \ \ \ ...
0
votes
1answer
21 views

Maximize linear combination

Given a set of positive values $v_1, v_2, ..., v_n$ and a set positive of factors $\alpha_1, \alpha_2, ..., \alpha_n$, both ordered increasingly, show the maximum linear combination you can get is ...
1
vote
1answer
24 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
2
votes
3answers
112 views

Generalization of minimisation problem

First I would like indtroduce my problem ! There is an easy way to solve this one : Find the value of $$ \inf_{(a,b)\in \mathbb{R}^2} \int_0^1 (t^2-at-b)^2 dt $$ and precise for which values $a$ ...
0
votes
0answers
15 views

Formulation of a SDP problem in a standard form with constraints on blocks

I have a semidefinite problem, \begin{align} \min_{\beta,\eta,R} &t\notag\\ \textrm{s.t.} & \beta ,\eta \geq 0\notag\\ &\Bigl[\begin{matrix} K\odot R&&1+\eta-\beta\\ ...
0
votes
0answers
13 views

Optimising money in bonds

Hi im doing an optimisation problem but dont understand what the terms mean. Suppose someone wants to invest $\$110,000$. They have $4$ choices as to what they invest their money into: $\bullet$ ...
1
vote
0answers
8 views

Does a larger change in $R^2$ indicate a given parameter is “more important” in model fitting?

I have a set of experimental data, and a given model which is supposed to fit that data. Let's say this model has $n$ parameters. I need to write a parameter estimation algorithm to determine the ...
0
votes
0answers
19 views

Book on duallity and sensitivity in nonlinear optimization

I am looking for a recommended book on duallity and sensitivity in nonlinear optimization, as duallity and sensitivity is a well studied topic in LP , I am struggeling to find books in this subject ...
0
votes
0answers
20 views

Continuity of optimisation problem

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
1
vote
1answer
30 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
2
votes
1answer
35 views

How can I optimize a multi-variable expression with a constant target.

I would like to know what methods are applied for optimizing multi-variable expressions with a defined target. I have a specific example I need help with, but I would like to be pointed into the ...
0
votes
0answers
17 views

Maximize a concave function under nonconvex constraints

I have to maximize the rate, which is a concave function, under certain constraints, where one of them is not convex; My optimization problem is: $\max_{\mathbf{P}_{2,n}} \frac{B}{L} \sum_{k=1}^L ...
1
vote
0answers
56 views

Finding $ \max_{x \in [2,4]} \left| 2 x \cos(2 x) - (x - 2)^{2} \right| $.

This is a problem taken from Burden’s and Faires’ Numerical Analysis. Define $ f: \Bbb{R} \to \Bbb{R} $ by $$ \forall x \in \Bbb{R}: \quad f(x) \stackrel{\text{df}}{=} 2 x \cos(2 x) - (x - 2)^{2}. $$ ...
0
votes
1answer
15 views

How do I know that method of steepest descent works?

Here is the definition of the method of steepest descent given in the book "The mathematics of nonlinear programming" by Peressini. Suppose $f(x)$ is a function with continuous partial derivatives on ...
0
votes
0answers
17 views

Maximize the intersection over union of oriented rectangles

I have an oriented rectangle in the form region=(x1,y1, ..., x4, y4) I want to know which is the axis-aligned rectangle with the same center that maximize the intersection over union of the areas of ...
2
votes
0answers
15 views

l1 Quadratic Programming

Within a SQP- algorithm it can happen that the constraints of the quadratic sub- problems are infeasible. In order to overcome this infeasibilities, a l1 penalty method can be used according to ...
0
votes
0answers
22 views

Formulate a solvable optimization problem

I am trying to solve an optimization problem which could be temporarily formulated as follows, Objective: $\min \quad c_0(1-x_1)x_2x_3(1-x_4) + c_1x_1x_2(1-x_3)x_4 + c_2x_1(1-x_2)x_3(1-x_4)$ ...
0
votes
1answer
68 views

Which optimization class does the following problem falls into (LP, MIP, CP..) and which solver to use

I have the following optimization problem. I want to solve it using a computer solver. But I am not sure which problem class it falls into or which solver to use. Problem: There is a set of objects ...
0
votes
0answers
6 views

Minimizing wasted assignment of attributes to a person by optimising profiles and assigning them to each person

My maths is poor in this area but I'll try to be specific. I can solve this with brute force over the possible solution space but I'm wondering if I am ignorant of an algorithm, theory or approach ...
0
votes
1answer
19 views

Solution of the LP relaxation - always round to the nearest integer?

If an optimal solution to the LP relaxation of an IP is not integer, can we always get a feasible IP solution by rounding it to the nearest integer? Or can we generalize this process by saying, if we ...
0
votes
0answers
17 views

Maximally distant orthogonal matrices

I would like to construct a set of $k$ orthogonal matrices in $\mathbb{R}^{n \times n}$ with maximal summed pairwise distance (in terms of L2 operator norm). Any ideas? I am thinking of just doing ...
1
vote
0answers
42 views

connection among big-M, Lagrangian, Pentalty Method, and Augmented Lagrangian

In the context of solving linear programs, the big-M method refers to adding additional variables to the problem such that there is, as far as I understand it, a trivial basic feasible solution. In ...
0
votes
0answers
18 views

Pseudoinverse with positive solutions

I'm not a mathematician but the engineering problem I'm considering is more of a mathematical question, that's why I post it here: Consider the matrices $M$ ($n \times 1$), $T$ ($n \times m$) and $F ...
1
vote
0answers
40 views

Implementation of Lagrange Multiplier to solve constrained optimization problem.

I'm trying to solve an optimization problem. I have a list of around 4000 geo coordinates data, and I want to cluster them into 30 groups based on the distance, so that the closer properties belongs ...
2
votes
0answers
41 views

Finding maxima of a 3-variable function.

Let $x,y,z$ be positive real number satisfy $x+y+z=3$ Find the maximum value of $P=\frac{2}{3+xy+yz+zx}+(\frac{xyz}{(x+1)(y+1)(z+1)})^\frac{1}{3}$
11
votes
2answers
301 views

Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES)

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
1
vote
3answers
50 views

Finding the absolute maximum of the following 3d function

$ f(x,y) = \frac{(\lambda_1x+\lambda_2y+\lambda_3)^2}{x^2+y^2+1} $ I know that the function looks like some deformed dorito chip depending on the lambda values. That is about as far as I've gotten. ...
0
votes
0answers
14 views

What is an inner-outer iteration?

Inner-outer iterations are used in papers, for finding a stationary point of a system or in optimization. It is not clear, what is called an inner-outer loop though? Is it a nested loop where the ...
0
votes
0answers
19 views

Hierarchical Linear Programming

I am stuck with the following problem from research. For each time, $t$, I get a new data point $x_t$ and the current optimum value is a function of $\{x_t:t=1,2,\dots,T\}$ obtained by solving a LP. ...
0
votes
0answers
21 views

Find out the optimization type

I am formulating a problem and intend to solve it by optimization. Here is the current result: *Objective:*$\quad\min\quad c + f_1(x)x_1 + f_2(x)x_2$ Constraint: $\quad ax_1 + bx_2 <= d$ where ...